2
\$\begingroup\$

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 = []
    added_count = 0
    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:
            added_count += len(front)
            new_numbers.append(front)
        # Then, add individuals from the last front based on their distance.
        else:
            new_numbers.append(front[:n - added_count])
            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()
\$\endgroup\$
  • \$\begingroup\$ Don't use assert. python -O file.py and they are all useless. \$\endgroup\$ – Peilonrayz Apr 27 '16 at 23:43
  • \$\begingroup\$ 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") \$\endgroup\$ – tsorn Apr 27 '16 at 23:50
  • \$\begingroup\$ That makes sense. Seemed like you were relying on them, on a re-read I understand your intent. \$\endgroup\$ – Peilonrayz Apr 27 '16 at 23:57
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.