1

I'm learning python and trying to implement a genetic algorithm with simulated annealing. I've created a class describing my population, which contains a list of individuals as well as as some other attributes and methods. When I try to create the next generation of a population, I want to remove the parent's genotypes from my population, then perform simulated annealing to see whether I shall reinclude the parents or the children individually to the population. The problem occurs when trying to remove the parents from the population.

I've checked that the genotypes of the parents are indeed in the population. I've created a minimal working example by building upon a very minimal example and expanding it until the error is occuring.

import random
from math import factorial

class Genotype(object):

    def __init__(self, data_list):
        self.__genotype = data_list
        # fitness is a complicated long function depending on modules,
        # replaced by random for simplicity
        self.fitness = random.random()

    def __eq__(self, other):
        """
        Comparing if two genotypes are equal
        :param other: Other Genotype object
        :type other: Genotype
        :return: True if they are equal, False otherwise
        :rtype: Boolean
        """
        if self.get_genotype() == other.get_genotype():
            return True
        else:
            return False

    def get_genotype(self):
        """ 
        Return the genotype.
        """
        return self.__genotype

class Population(object):

    def __init__(self, genotype_list):
        self.individuals = genotype_list
        self.fitness = self.get_fitness()

    def __getitem__(self, key):
        return self.individuals[key]

    def get_fitness(self):
        return [x.fitness for x in self.individuals]

    def next_generation(self):
        parent_indices = list()
        childs = list()
        # define the number of parents
        number_of_parents = 12
        # Roulette-wheel selection
        eff_fit = self.fitness
        s = sum(eff_fit)
        eff_fit_with_indices = list(enumerate(eff_fit))
        eff_fit_sorted = sorted(eff_fit_with_indices, key=lambda i: i[1])
        for rep in range(number_of_parents):
            r = random.uniform(0, s)
            partial_sum = 0
            for idx, val in enumerate(eff_fit_sorted):
                partial_sum += val[1]
                if partial_sum >= r:
                    parent_indices.append(val)
                    break

        parent_genotypes = [self[x[0]] for x in parent_indices]

        for parent in parent_genotypes:
            self.individuals.remove(parent)

        return self

individuals = 120
rectangle_number = 79
max_permutations = factorial(rectangle_number)

master_genotype = range(0, rectangle_number)

# creating initial genotypes
initial_genotypes = list()
for idx in range(0, individuals):
    unique = False
    temp_seed = random.randint(1, max_permutations)
    random.seed(temp_seed)
    while not unique:
        temp_genotype_data_list = list(master_genotype)
        random.shuffle(temp_genotype_data_list)
        temp_genotype = Genotype(temp_genotype_data_list)
        if temp_genotype not in initial_genotypes:
            initial_genotypes.append(temp_genotype)
            unique = True

population = Population(initial_genotypes) 
population.next_generation()

I expected self to have less members as the parents are removed, however, I get the following error:

Exception has occured: ValueError
list.remove(x): x not in list
Iridium
  • 113
  • 1
  • 8
  • 1
    Possible duplicate of [How to clone or copy a list?](https://stackoverflow.com/questions/2612802/how-to-clone-or-copy-a-list) – Devesh Kumar Singh Jun 05 '19 at 16:31
  • 5
    Please give a [mcve]. If I had to guess, you are running into an aliasing problem (where different elements of your population are references to the same object), but without seeing more code it is impossible to say more. – John Coleman Jun 05 '19 at 16:31
  • 1. Read https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ for tips on debugging your code 2. If you still need help, provide a [mcve] that duplicates the behavior you are asking about. – Code-Apprentice Jun 05 '19 at 16:32
  • It might be interesting to dive into this, and it might affect bugs that crop up later, but you could just wrap this in a `try/except` block to catch the `ValueError` here. You're trying to delete something that's already deleted. What you want to happen has happened already (or didn't need to), so you might be able to just move on. – Two-Bit Alchemist Jun 05 '19 at 19:42
  • @Two-BitAlchemist: Yes, I can prevent the error by just adding a `if parent in self:` condition, however it is important that the number of the elements in population decreases by exactly the number of parents, so skipping one is unfortunately not an option. Doing as you suggested actually yields a population that exactly has one element too much (hence the error). – Iridium Jun 05 '19 at 19:48
  • I am voting to reopen this question. What if in `__getitem__` the line `return self.individuals[key]` is replaced by `return self.individuals[key][:]`? A child should receive a *copy* of the parents genome, not the parent genome itself. – John Coleman Jun 05 '19 at 21:09
  • @JohnColeman: Replacing the line `return self.individuals[key]` by the the line `return self.individuals[:][key]` did the trick, but I'm not sure why. What is the difference? Is the latter one a pass by value whereas the first one is by reference? – Iridium Jun 06 '19 at 07:33
  • Something like `a = b[:]` makes `a` a (shallow) copy of `b` but `a = b` would simply make `a` and `b` point to the same element. Look at the link that @DeveshKumarSingh gave. Your code strikes me as convoluted. Why not make the next generation a brand new list of mutated copies of the previous generation rather than adding new elements and removing the old? Also, I don't see the motivation of `random.seed(temp_seed)`. For one thing, there isn't any good motivation to set a seed to a random seed. The only real point of `random.seed` is to make things reproducible, which isn't the case here. – John Coleman Jun 06 '19 at 11:24
  • In my implementation, I've now done as you suggested and created a brand new list. I experimented with this before, but since I only wrote `new_list = old_list`, it did not work as they pointed to the same element. Additionally, I have removed the temporary seed. – Iridium Jun 06 '19 at 12:58

0 Answers0