2. Implementing a Genetic Algorithm

  • The purpose of this topic is to see a simple genetic algorithm (GA)

  • Although simple, it includes all the necessary parts to make it a complete GA

  • Despite never seeing a GA before, or knowing the intuition behind the underlying ideas, the topic should be manageable

2.1. Problem

Note

The problem being solved is deliberately kept very simple. This is because (a) the purpose of this topic is to see a working GA, not solve a complex problem, and (b) well understood problems are often much simpler to reason about. Knowing what a good/bad solution is, and having an idea of why certain solving strategies work or not, will help with building the intuition around how GAs work.

  • The problem being solved is to maximize the integer value of an unsigned binary number

    • Find the largest binary number representable with \(n\) bits

  • For this problem, the search space is all possible unsigned binary numbers of length \(n\)

  • Given this problem description, the best solution is obviously a string of \(n\) ones

  • Consider an example with \(n=10\), how would these candidate solutions be ranked in terms of goodness?

    • \(1111111111\) (1023)

    • \(1011001001\) (713)

    • \(0001111111\) (127)

    • \(0000000000\) (0)

  • Thus, the GA being written will evolve bit strings to maximize the integer value of an unsigned binary number

  • Realistically, one would not use a GA to solve such a problem

    • GAs are typically used for very challenging problems with no other effective means of solving

  • However, this problem provides an opportunity to consider how the GA can and must work to find the best solution

2.2. Initialization

  • Before evolution can begin, an initial population of candidate solutions needs to be created

  • A single candidate solution is a potential solution to the problem being solved

  • For example, \(1011001001\) is a valid candidate solution for finding the largest binary value where \(n=10\)

2.2.1. Representation

  • It is sometimes non-trivial to determine how a candidate solution should be represented, or encoded, in the program

    • An encoded candidate solution is called a chromosome

  • For the integer maximization of an unsigned binary number, there are some obvious reasonable and simple encodings

  • Here, a list of 0s and 1s will be used

  • Thus, the candidate solution \(1011001001\) can be encoded as the chromosome [1, 0, 1, 1, 0, 0, 1, 0, 0, 1]

  • A single chromosome can be created by generating random lists of 0s and 1s of some predetermined length

    • For the example used here, the length was \(n=10\)

2.2.2. Population

  • A population is a collection of candidate solutions

  • A population can be created by creating a list of randomly generated chromosomes

  • In this example, a single chromosome is a list of 0s and 1s

    [1, 0, 1, 1, 0, 0, 1, 0, 0, 1]

  • A population is a list of chromosomes

    [[1, 0, 1, 1, 0, 0, 1, 0, 0, 1],
 [0, 0, 0, 1, 1, 0, 1, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
 ...
 ...
 [0, 1, 1, 1, 1, 0, 0, 0, 0, 1]]

  • Each chromosome is randomly generated

  • Below is an example of how one could create a population for this problem

61    population = []
62    for _ in range(POPULATION_SIZE):
63        chromosome = choices([0, 1], k=BIT_STRING_LENGTH)
64        population.append(chromosome)

  • The number of chromosomes within the population is defined by a hyperparameter called POPULATION_SIZE

  • The number of bits in the binary number (\(n\)) is called BIT_STRING_LENGTH

2.3. Evaluation

  • After generating the population, the candidate solutions are often not particularly good

  • However, some will likely be better than others

  • Regardless, a mechanism for evaluating the quality, or fitness, of candidate solutions is needed

  • This mechanism is called the fitness function

  • Below is an example fitness function for this problem

26def value_fitness(chromosome: list) -> int:
27    """
28    Calculate the decimal value of the chromosome (bitstring).
29
30    :param chromosome: Chromosome (bitstring) to evaluate
31    :return: The decimal value of the chromosome (bitstring)
32    :raises ValueError: If the chromosome is empty
33    """
34    if len(chromosome) == 0:
35        raise ValueError(f"Empty chromosome cannot be evaluated: {chromosome}")
36    return int("".join(str(bit) for bit in chromosome), 2)

  • With this fitness function, the fitness of each candidate solution within the population can be calculated and stored

70        population_fitness = []
71        for chromosome in population:
72            fitness = value_fitness(chromosome)
73            population_fitness.append(fitness)

2.4. Selection

  • Ideally, more fit candidate solutions should be more likely to persist within the population

    • And less fit candidate solutions should be more likely to die off

  • However, it is not as simple as always selecting the best candidate solutions

    • Doing so would cause the population to converge too early

    • This can result in finding sub-optimal solutions

  • This is where it becomes important to think about the population, not individual candidate solutions

  • The fitness function is a metric for the ultimate goal — finding a candidate solution that best solves the problem

  • But focusing on this metric is detrimental to the population

  • Instead, the population should also emphasize diversity

  • This can be done in any way someone wants

    • There are no hard rules on how selection is to be done

  • A simple and popular selection technique is tournament_selection

    • Randomly select a subset of chromosomes within the population

    • Select the best of the subset

    • Repeat until the next generation’s population is full

23def tournament_selection(
24    population: list, population_fitness: list, selected_indices: list[int], direction: int = 1
25) -> list:
26    """
27    Select the chromosome with the maximum/minimum fitness value of the chromosomes in the tournament. The chromosomes
28    in the tournament if its index is contained within the selected_indices list. By default, the function selects for
29    maximum fitness.
30
31    :param population: Population of chromosomes to select from
32    :param population_fitness: Fitness values of the population
33    :param selected_indices: List of indices in the tournament
34    :param direction: +1 for maximizing fitness, -1 for minimizing fitness
35    :return: A copy of the selected chromosome
36    :raises ValueError: If the list of selected indices is empty or contains an out-of-bounds index
37    """
38    if len(selected_indices) == 0:
39        raise ValueError(f"List of indices in the tournament must be non empty: {selected_indices}")
40    for index in selected_indices:
41        if index < 0 or index > len(population_fitness) - 1:
42            raise ValueError(f"List of indices in the tournament contains out-of-bounds index: {index}")
43    max_value = population_fitness[selected_indices[0]] * direction
44    max_index = selected_indices[0]
45    for index in selected_indices:
46        if population_fitness[index] * direction > max_value:
47            max_value = population_fitness[index] * direction
48            max_index = index
49    return population[max_index][:]

  • This tournament_selection function returns a single chromosome

  • This function must be run multiple times until the next generation’s population is full

81        mating_pool = []
82        for _ in range(POPULATION_SIZE):
83            tournament_indices = choices(range(POPULATION_SIZE), k=TOURNAMENT_SIZE)
84            chromosome = tournament_selection(population, population_fitness, tournament_indices)
85            mating_pool.append(chromosome)

  • In the above code, the list mating_pool will ultimately become the next generation’s population

  • The size of the tournament is defined by a hyperparameter called TOURNAMENT_SIZE

2.5. Variation Operators

  • Variation operators, sometimes called genetic operators, are used to alter the chromosomes

    • With only selection, the chromosomes will never change

  • Like most things with GAs, there are no real hard rules on how this is done

  • Typically there should be a way to exploit what is already known to be good

  • And there should be a way to add some new information to the chromosomes to better explore the search space

2.5.1. Crossover

  • Crossover is a variation operator that acts on two chromosomes

  • The idea is, if two candidate solutions are relatively good, then mixing them together may produce something good

  • Again, there is no one correct way to perform crossover

  • A simple crossover one could use is one_point_crossover

    • Given two chromosomes

    • Select an arbitrary index

    • Swap the contents of the chromosomes from that index to the end

  • For example, selecting index 2 for the following chromosomes

           v                    v
[0, 0, 0, 0, 0]      [0, 0, 1, 1, 1]
                 ->
[1, 1, 1, 1, 1]      [1, 1, 0, 0, 0]
       ^                    ^

50def one_point_crossover(parent_1: list, parent_2: list, index: int) -> tuple[list, list]:
51    """
52    One point crossover. All elements at and after the crossover index are swapped between the two chromosomes.
53    For example, with a crossover index of 2, [0,0,0,0,0], [1,1,1,1,1] -> [0,0,1,1,1], [1,1,0,0,0]. A crossover index of
54    0 is allowed, but results in all contents being swapped.
55
56    :param parent_1: Chromosome to be used in crossover
57    :param parent_2: Chromosome to be used in crossover
58    :param index: The index of the starting point of where all elements will be swapped between chromosomes
59    :return: The two chromosomes after the crossover is applied
60    :raises ValueError: If the parents are not the same length of if the index is out-of-bounds
61    """
62    if len(parent_1) != len(parent_2):
63        raise ValueError(f"chromosomes must be the same length: {len(parent_1)}, {len(parent_2)}")
64    if index < 0 or index > len(parent_1) - 1:
65        raise ValueError(f"Index out-of-bounds: {index}")
66    child_1 = parent_1[:]
67    child_2 = parent_2[:]
68    child_1[index:], child_2[index:] = child_2[index:], child_1[index:]
69    return child_1, child_2

  • This function only returns two chromosomes, so it must be run multiple times

89        for i in range(0, POPULATION_SIZE, 2):
90            if random() < CROSSOVER_RATE:
91                crossover_point = randrange(BIT_STRING_LENGTH)
92                chromosome_1, chromosome_2 = one_point_crossover(mating_pool[i], mating_pool[i + 1], crossover_point)
93                mating_pool[i] = chromosome_1
94                mating_pool[i + 1] = chromosome_2

  • Notice that the crossover is applied to adjacent candidate solutions within the mating_pool list

    • The fact that they are adjacent is arbitrary

  • Also notice random() < CROSSOVER_RATE

  • Crossover is typically not always applied

  • Thus, this provides a way for selected candidate solutions to persist in the next generation unchanged

  • The probability of crossover being applied is defined by a hyperparameter called CROSSOVER_RATE

    • Value would be 0 <= CROSSOVER_RATE <= 1

2.5.1.1. Potential Problem

  • There is a potential problem with this crossover on this problem

  • Consider the following population on a smaller version of the problem where \(n=5\)

    [[1, 0, 1, 1, 1],
 [1, 0, 0, 0, 1],
 [0, 0, 1, 1, 1],
 [1, 0, 1, 1, 1],
 [0, 0, 0, 1, 0]]

  • Notice how there exists no 1 in any of the chromosomes’ index 1

  • Because of this, it is actually not possible to ever find the optimal solution through crossover

  • This is because there is no way to add new information to the candidate solutions

  • It is only possible to transfer the existing information between the candidate solutions

2.5.2. Mutation

  • Mutation is a variation operator that acts on a single chromosome

  • It is also great for adding new information to the candidate solutions

  • Like crossover, there is no correct way to perform mutation

  • Here, a bit_flip_mutation will be used

    • Given a chromosome

    • Select an arbitrary index

    • Flip the bit at the selected index (0 -> 1/1 -> 0)

  • For example, selecting index 2 for the following chromosome

    [0, 0, 0, 0, 0]  ->  [0, 0, 1, 0, 0]
       ^                    ^

 1def bit_flip_mutation(parent: list, index: int) -> list:
 2    """
 3    Bit flip mutation. Flip the bit at the specified index. In other words, if the bit is a 0, change it to be a 1, and
 4    if the bit is a 1, change it to be a 0. For example, with mutation index of 2, [0,0,0,0,0] -> [0,0,1,0,0].
 5
 6    :param parent: Chromosome to be mutated
 7    :param index: Index of the bit to be flipped
 8    :return: The chromosome after the mutation is applied
 9    :raises ValueError: If the index is out-of-bounds
10    """
11    if index < 0 or index > len(parent) - 1:
12        raise ValueError(f"Index out-of-bounds: {index}")
13    child = parent[:]
14    child[index] = (child[index] + 1) % 2
15    return child

  • Similar to crossover, the application of mutation is probabilistic based on a hyperparameter called MUTATION_RATE

    • Where 0 <= MUTATION_RATE <= 1

 98        for i in range(POPULATION_SIZE):
 99            if random() < MUTATION_RATE:
100                mutation_point = randrange(BIT_STRING_LENGTH)
101                chromosome = bit_flip_mutation(mating_pool[i], mutation_point)
102                mating_pool[i] = chromosome

2.6. Termination Requirement

  • The above describes a single generation of the GA

  • For this algorithm to work, many generations will need to be executed

  • This then begs the question, when does one stop the algorithm

    • After some set number of generations?

    • After the optimal solution is found?

    • After there have been no improvements in the population?

    • …

  • Again, like most things with GAs, there really is no correct answer

  • Here, for ease, the algorithm is run for some number of generations specified by the hyperparameter GENERATIONS

 68    for generation in range(GENERATIONS):
 69        # [begin-evaluation]
 70        population_fitness = []
 71        for chromosome in population:
 72            fitness = value_fitness(chromosome)
 73            population_fitness.append(fitness)
 74        # [end-evaluation]
 75
 76        # Bookkeeping
 77        generation_max_fitness.append(max(population_fitness))
 78        generation_average_fitness.append(sum(population_fitness) // len(population_fitness))
 79
 80        # [begin-selection]
 81        mating_pool = []
 82        for _ in range(POPULATION_SIZE):
 83            tournament_indices = choices(range(POPULATION_SIZE), k=TOURNAMENT_SIZE)
 84            chromosome = tournament_selection(population, population_fitness, tournament_indices)
 85            mating_pool.append(chromosome)
 86        # [end-selection]
 87
 88        # [begin-crossover]
 89        for i in range(0, POPULATION_SIZE, 2):
 90            if random() < CROSSOVER_RATE:
 91                crossover_point = randrange(BIT_STRING_LENGTH)
 92                chromosome_1, chromosome_2 = one_point_crossover(mating_pool[i], mating_pool[i + 1], crossover_point)
 93                mating_pool[i] = chromosome_1
 94                mating_pool[i + 1] = chromosome_2
 95        # [end-crossover]
 96
 97        # [begin-mutation]
 98        for i in range(POPULATION_SIZE):
 99            if random() < MUTATION_RATE:
100                mutation_point = randrange(BIT_STRING_LENGTH)
101                chromosome = bit_flip_mutation(mating_pool[i], mutation_point)
102                mating_pool[i] = chromosome
103        # [end-mutation]
104
105        population = mating_pool

  • Notice that this generation loop performs

    • Evaluation

    • Selection

    • Variation Operators

  • Also notice the bookkeeping variables storing some values from evolution

    • generation_max_fitness and generation_average_fitness

    • These are not required, but help with visualizing what happened

  • Also notice the tags like # [begin-evaluation]

    • These can be ignored

    • They are only there for making it easier to reference the code in the course notes

  • Once the loop terminates, the population should be evaluated one last time to find the best candidate solution

109    population_fitness = []
110    for chromosome in population:
111        fitness = value_fitness(chromosome)
112        population_fitness.append(fitness)
113    print(population_fitness)
114    print(population)
115    generation_max_fitness.append(max(population_fitness))
116    generation_average_fitness.append(sum(population_fitness) // len(population_fitness))

2.7. For Next Class