Paul Bodily About Courses Research Outreach Tips for Communicating Teaching Philosophy Vitae

Genetic Algorithms

The goal with a genetic algorithm is to find/create an optimal solution to a problem without anything (including training data) except a fitness function that can be used to evaluate a given solution (think of how natural selection naturally ascribes higher fitness to some individuals vs others). We call a particular solution a genome. At each generation, genomes are combined with other genomes to create new genomes. By always choosing genomes with high fitness, over time we end up with genomes that are "fit".

To get a feel for how this works, try out the following activity.

Example: String discovery problem

This activity is intended to be performed with a group of people.

  1. Randomly pick a 5-letter “word” from letters a-f (e.g., “dbdae”). Write it down.
  2. Get a fitness score below for your word (e.g., f(“dbdae”) = 0). Shout out or hold up fingers indicating your fitness.
  3. Repeat the following steps until you feel like you've found the solution (write down each generation):
    1. Find another person.
    2. Create a new word by crossing over the first two of yours and last three of theirs (e.g., “dbdae” + “eacdf” -> “dbcdf”).
    3. Randomly mutate one letter (e.g., “dbcdf” -> “dbadf”). Avoid the temptation to insert any strategy or intelligence here.
    4. Get a score for the new word (e.g., f(“dbadf”) = 1)
    5. Choose whether to keep the new or the old word

Follow-up Questions

  1. How did you decide when to stop? (This is a hard question anytime you use GAs)
  2. How much did your fitness score increase over time? Was it just you, or did everyone's scores go up?
  3. What do you think the fitness function was? (usually you have some idea of how the fitness function works)
  4. When you were looking for a partner, how did you choose who to partner up with?
  5. How important do you think that random mutation step was? Would you have found your final solution without it?
  6. At the beginning everyone had different words. How important do you think diversity is in a GA?
  7. Did your genome change at each generation? Did your score go up at each generation? Were there streaks with no change and then sudden improvements?