3. Experimenting with a Genetic Algorithm

  • Having seen the GA, it is now time to tinker with one to see what happens

3.1. Plot

  • Below is a plot of the learning curve of the evolutionary search

  • One line shows the fitness of the best candidate solution within the population

  • The other line shows the average fitness of the population

../../_images/fitness_over_time.png

Plot of a the GA’s “learning curve” for the maximization of the integer value of an unsigned binary number.

  • The evolutionary algorithm was run with the following settings

17BIT_STRING_LENGTH = 10
18POPULATION_SIZE = 10  # Must be multiple of two
19TOURNAMENT_SIZE = 2
20GENERATIONS = 25
21CROSSOVER_RATE = 0.70
22MUTATION_RATE = 0.10

3.2. Experiment

  • For all the following questions, take the time to run the GA with several values and plot the results

Note

The easiest way to get the code up and running is to fork the github repository, download it, and run the setup described in the “README”.

Alternatively, the scripts can be downloaded individually to /src, but this may require some additional setup for the dependencies. It is recommended to make a virtual environment and download any required dependencies with pip.

  1. Increase the difficulty of the problem by increasing the bitstring length \(n\) (BIT_STRING_LENGTH)

  2. Change the number of generations (GENERATIONS) to see how it impacts the search

  3. Change the population size (POPULATION_SIZE) to see how it impacts the search

  4. Change the crossover rate (CROSSOVER_RATE) to see how it impacts the search

    • Be sure to include a value of 0.0 and 1.0 in your experimenting

  5. Change the mutation rate (MUTATION_RATE) to see how it impacts the search

    • Be sure to include a value of 0.0 and 1.0 in your experimenting

  6. Change the size of the tournament for selection (TOURNAMENT_SIZE) to see how it impacts the search

  7. Set the size of the tournament for selection (TOURNAMENT_SIZE) to the population size

    • What does this mean?

  8. Set the size of the tournament for selection (TOURNAMENT_SIZE) to 1

    • What does this mean?

  9. Add elitism to the algorithm

    • Elitism is when the top \(x\) candidate solutions are automatically copied to the subsequent generation

    • Typically, \(x\) is kept low (like 1), but try larger values to see how it impacts the search

  10. What is the best settings of the hyperparameters found?

3.3. A Change of Perspective

  • In the previous topic, the following candidate solutions were ranked by how close they are to the optimal solution

    • \(1111111111\) (1023)

    • \(1011001001\) (713)

    • \(0001111111\) (127)

    • \(0000000000\) (0)

  • This ranks them based on what the candidate solutions mean in terms of the problem’s objective — their integer value

    • The bitstring that means 713 is better than the one that means 127 since it is closer to the optimal solution

  • However, instead of thinking about their integer value, consider how close the chromosome is to the optimal solution

  • The optimal chromosome would be [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] where \(n=10\)

  • Which chromosome is better

    • [1, 0, 0, 0, 0, 0, 0, 0, 0, 0] (512)

    • [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] (511)

  • Before, the candidate solutions were ranked based on what they mean in the problem space

    • Phenotype space

  • By counting the number of ones in the chromosomes, the solutions can be compared based on their encodings

    • Genotype space

  • Below is an alternative fitness function that could be used

39def ones_fitness(chromosome: list) -> int:
40    """
41    Count the number of 1s (ones) in the chromosome (bitstring).
42
43    :param chromosome: Chromosome (bitstring) to evaluate
44    :return: The number of 1s (ones) in the chromosome (bitstring).
45    :raises ValueError: If the chromosome is empty
46    """
47    if len(chromosome) == 0:
48        raise ValueError(f"Empty chromosome cannot be evaluated: {chromosome}")
49    number_of_ones = 0
50    for bit in chromosome:
51        number_of_ones += bit
52    return number_of_ones

3.4. Experiment Again

  1. Switch out the use of value_fitness for ones_fitness in the fitness calculation of each chromosome

  2. Play with the hyperparameters and keep track of the best settings found

    • Are they different from before?

3.5. Non-Numerical Hyperparameters

  • The hyperparameters can be tuned, but so can the individual functional pieces of the GA

    • There is no rule saying the fitness function must work a certain way

    • There is no set way to do crossover or mutation

    • Selection can be done however one wants to

    • …

  • All that really matters is that it produces a working GA in the end that finds high-quality solutions to a problem

  • The ideas of evolutionary computation are truly only rough frameworks

  • The individual concrete pieces are flexible and can be whatever works

  1. Try to create your own crossover function

  2. Try to create your own mutation function

  3. Try to create your own selection strategy

  4. Did your changes improve the GA or not?

    • They do not need to

    • Just have fun and try to be creative

3.6. For Next Class