# Performance optimization when switching from nested to flat representation (genetic algorithm)

The code below is the core of a Genetic Algorithm (NSGA-II to be precise, without crowding-distance calculation), but I've taken out all the GA-specific parts and made a generic example. I think I've carried over most of the principles/'constraints' from the original algorithm, but I might have missed something.

As you can see in loop(), I need to convert a nested list (2-dimensional) to a flat list pretty often and I'm curious of if there are any better ways to do it. I've added some asserts so that it's easier to follow the size and type (nested or flat) of the lists.

Since expected size of input is m=100 individuals (Number) for 500 generations (loops), speed is important. Memory usage is not that important (although knowing how to reduce it would be interesting), but execution time is.

Any comments performance-related or otherwise are appreciated.

from itertools import chain
from timeit import timeit
import logging

import numpy as np

class Number:
def __init__(self, value=None):
if value:
self.value = value
else:
self.value = np.random.randint(10)
self.rank = -1
self.strictly_better_than_list = None
self.strictly_worse_than_count = -1

self.distance = np.random.randint(10)

def strictly_better_than(self, other):
# Placeholder for similar inexpensive computation
if self.value < other.value:
return True
return False

def assign_sort_rank(numbers):
# Needs flat list
assert isinstance(numbers[0], Number)

rank_sorted = [[]]
for number_a in numbers:
assert type(number_a) == Number, type(number_a)
number_a.strictly_better_than_list = []
number_a.strictly_worse_than_count = 0
for number_b in numbers:
assert type(number_b) == Number, type(number_b)
if number_a.strictly_better_than(number_b):
number_a.strictly_better_than_list.append(number_b)
elif number_b.strictly_better_than(number_a):
number_a.strictly_worse_than_count += 1
if number_a.strictly_worse_than_count == 0:
number_a.rank = 0
rank_sorted[0].append(number_a)
i = 0
while rank_sorted[i]:
current_front = rank_sorted[i]
next_front = []
for number_a in current_front:
for number_b in number_a.strictly_better_than_list:
number_b.strictly_worse_than_count -= 1
assert number_b.strictly_worse_than_count >= 0, number_b.strictly_worse_than_count
if number_b.strictly_worse_than_count == 0:
number_b.rank = i + 1
next_front.append(number_b)
rank_sorted.append(next_front)
i += 1
# The last front will always be empty
return rank_sorted[:-1]

def random_selection(li):
# Need flat list ??
numbers = []
for _ in range(len(li)):
numbers.append(np.random.choice(li))
return numbers

def rank_distance_selection(numbers_1, numbers_2):
# Need flat lists
assert isinstance(numbers_1[0], Number)
if numbers_2:
assert isinstance(numbers_2[0], Number)

n = len(numbers_1)  # == len(numbers_2)
rank_sorted = assign_sort_rank(np.concatenate((numbers_1, numbers_2)))
new_numbers = []
for front in rank_sorted:
# This sort is a placeholder for a custom sort that can't be done by 'sorted',
# but it still sorts by the same value (distance)
front = sorted(front, key=lambda num: num.distance)
# Add fronts to empty number pool until no more complete fronts can be added.
if added_count + len(front) <= n:
new_numbers.append(front)
# Then, add individuals from the last front based on their distance.
else:
break
# Return nested, rank sorted list
return new_numbers

def generate_from_numbers(numbers):
# Takes a flat list, but can be made to work a nested list
new_numbers = []
for i in range(0, len(numbers) - 1, 2):
number_a = numbers[i]
number_b = numbers[i+1]
mangled_numbers = mangle(number_a, number_b)
new_numbers.extend(mangled_numbers)
return new_numbers

def mangle(number_a, number_b):
# placeholders for similar computations
number_1 = Number(number_a.value - number_b.value)
number_2 = Number(number_a.value + number_b.value)
return number_1, number_2

def view_numbers(numbers):
# Placeholder that need nested, rank sorted list
assert isinstance(numbers[0], list)
# Numbers should now be sorted ascending in rank, firstly, and within the
# same rank in ascending distance
for front in numbers:
for number in front:
print(number.value, number.rank, number.distance)

def loop(m=100, n=500):
a = [Number() for _ in range(m)]
b = []
c = []
for i in range(n):
print("Iteration:", i)
b = rank_distance_selection(a, list(chain.from_iterable(b)))
view_numbers(b)  # A placeholder that needs nested list
c = random_selection(list(chain.from_iterable(b)))
a = generate_from_numbers(c)
assert len(a) == len(list(chain.from_iterable(b))) == len(c) == m, \
(len(a), len(list(chain.from_iterable(b))), len(c))

loop()

• Don't use assert. python -O file.py and they are all useless. – Peilonrayz Apr 27 '16 at 23:43
• I added them in so that the constraints of the original algorithm would be clearer ("this function need that kind of list") as it may not be self-evident in the generic representation above and to make the flow easier to follow ("now the list is in this form") – tsorn Apr 27 '16 at 23:50
• That makes sense. Seemed like you were relying on them, on a re-read I understand your intent. – Peilonrayz Apr 27 '16 at 23:57

A minor change

def random_selection(li):
# Need flat list ??
numbers = []
for _ in range(len(li)):
numbers.append(np.random.choice(li))
return numbers


can be

number = [np.random.choice(li) for _ in li]


or even

number = np.random.choice(li, len(li))  # with optional .tolist()


You don't make much use of numpy. I haven't studied the code enough to know where else you can profitably use it.

 def strictly_better_than(self, other):
# Placeholder for similar inexpensive computation
if self.value < other.value:
return True
return False


can be simplified to:

 def strictly_better_than(self, other):
# Placeholder for similar inexpensive computation
return self.value < other.value