CS21 Lab 12: Genetic Algorithm

Due 11:59pm Thursday, May 1, 2008

A skeleton version of the programs will appear when you run update21 in a terminal window. The program handin21 will only submit files in this directory. You may work with a partner on this lab.

There are some optional components that allow you to further practice your skills in Python. These optional components will not be graded, but may be interesting for those wanting some extra challenges.



Introduction

A genetic algorithm is an abstract simulation of some of the key ideas from biological evolution. A population of chromosomes, where each chromosome is represented as a series of 1's and 0's, is randomly generated. Then evolution proceeds as a sequence of generations. Each generation, the fitness of every chromosome in the population is determined. Next, parent chromosomes are selected from the population based on their fitness. With some probability, a crossover operation is done on these parents. Crossover is a simple model of sexual reproduction that recombines the chromosomes of the two parents to produce two children. Finally, with some low probability, mutation may occur on the children chromosomes. In this way, a new population is produced on each generation. Over many generations, the average fitness of the population tends to increase and more highly fit chromosomes are created. Using biology as inspiration, genetic algorithms have been used to solve interesting problems such as how to adapt robot controllers for solving particular tasks.

In this lab you will be given a definition of a GeneticAlgorithm class that is nearly complete. You will need to implement two methods: crossover and mutation. Then you will test the completed genetic algorithm on a simple problem of finding chromosomes that maximize the sum of their values.

Once you are convinced that the genetic algorithm is working properly, you will then apply it to the more interesting problem of evolving symmetrical grid-based images. An example is shown below.





The GeneticAlgorithm class

Open the ga.py file that was copied into this week's directory when you did an update21. You can run this file, but because crossover and mutation methods have not yet been implemented it will be very unlikely to find the solution to the simple test problem of maximizing the sum of the chromosome values. Once you have read through the code and have a general sense of the methods and how they work, do the following:

  1. Implement crossover
    The crossover method takes two parent chromosomes as input. The variable self.pCrossover represents the probability that crossover will occur for those two parents. When crossover doesn't occur, copies of the two parent chromosomes should be returned. Recall that you can get a copy of a python list ls by creating a slice of the entire list ls[:]. When crossover does occur, a random crossover point between 1 and the length of the chromosome-1 should be determined. For example, if the the chromosome was 16 long, then the crossover point should be randomly chosen to be between 1 and 15. The first child should be created by taking parent1's chromosome values starting from the beginning and continuing up to, but not including the crossover point. The remainder of the first child should be created by taking parent2's chromosome values starting from the crossover point and continuing to the end. The second child should be created using the opposite portions of the two parents. An example is shown below.
    
              0  1  2  3  4  5  6  7
    parent1: [1, 1, 1, 0, 0, 0, 0, 0]
    parent2: [0, 1, 0, 1, 0, 1, 0, 1]
                      ^ 
    crossPoint:       3
    
    child1:  [1, 1, 1, 1, 0, 1, 0, 1]
    child2:  [0, 1, 0, 0, 0, 0, 0, 0]
    
    Test that your crossover method is working properly by printing out the parents, the selected crossover point, and the resulting children.
  2. Implement mutation
    The mutation method takes a child chromosome as input, and for each position in the chromosome it uses the probability stored in self.pMutation to determine whether that particular position should be modified. When making a mutation, if the current value is a 0 then it is changed to a 1, and if the current value is a 1 is is changed to a 0. An example is shown below.
    child before mutation:  [1, 1, 1, 1, 0, 1, 0, 1]
    child after  mutation:  [1, 0, 1, 1, 0, 1, 0, 1]
    
    Because the chromosome is represented as a list, any change you make will be permanent, so it does not need to be returned from the method.

    Test that your mutation method is working properly by printing out the incoming chromosome and the chromosome after mutation is completed. Remember that it is possible for none of the chromosome to be mutated and it is also possible for multiple positions on the chromsome to be mutated.
  3. Test the GeneticAlgorithm
    Once you have implemented the two methods described above, you should test whether you can now evolve a chromosome of all 1's using the class called SumGA provided at the bottom of the ga.py file.

    Notice that there are two ways that you can create this class (one way is commented out in the main program). There are two required parameters to the constructor: the length of the chromosome and the size of the population. There is a third optional parameter, which defaults to False. If you instead pass in True it will print additional information showing you which parents were selected and what children were produced. This may be helpful in verifying that your methods are working properly.

    If you cannot consistently evolve a chromosove of all 1's, then there may be a problem with either your crossover or mutation methods.


The Grid class

Before you begin evolving images, you'll need to understand how to use the Grid class to draw two-dimensional, grid-based images. The Grid class is based on the Picture class. If you are interested in seeing the implementations of theses classes they can be found here:

/usr/local/stow/cs21/lib/python2.4/site-packages/

To construct a Grid object, you'll need to pass the desired number of columns and rows as parameters. The origin (0,0) is located in the bottom left corner. Once you have a grid object you can set the color of particular cells as well as set the title. For example, try the following code to produce the picture shown below.

g = Grid(10,10)
g.setTitle("diagonals")

for i in range(g.getWidth()):
    g.setBlack(i, i)

for i in range(g.getWidth()):
    g.setWhite(i, g.getWidth()-i-1)

g.update()
g.done()

Notice that, just as in the Terrain class we used last week, you must call the update method to actually make the window update its color values.


Once you are comfortable using the Grid class and its methods, you can move on to the next section.



The GAImage class

Using the SumGA class given in the ga.py file as a model, complete the implementation of the ImageGA class given in the imageGA.py file. Your goal is to create a fitness function that can evolve images that are symmetrical across the vertical axis. Another example is shown below.



  1. Create a constructor for the GAImage class that takes the columns, rows, and population size as parameters. It should create a blank Grid object and save it as a class variable.
  2. Create a showImage method that takes a chromosome and draws the chromosome in the Grid object. You should interpret 1's in the chromosome as white cells and 0's in the chromosome as black cells. For example, the following chromosome of length 16,
    [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
    
    would represent this 4x4 image, where the the origin is in the lower-left corner:


  3. Create a fitness method that takes a chromosome and returns a score that represents how symmetrical the associated image would be. You can count the number of cells in symmetrical positions across the vertical axis which have the same value. As in the simpler SumGA example, you should base the fitness on a power of two of the count so as to speed up the process of evolution.
  4. Create an isDone method. It should use the showImage method to display the best member of the current generation so that you can watch the progress of the evolution. It should also test if the fitness of the best member of the current generation is equal to the optimal fitness for vertical symmetry. If so, it should return True, otherwise it should return False.
  5. Create a main program to test your class. The best way to test this program is to execute it from a terminal window rather than from within idle. To do this you'll need to use cd to change to the appropriate directory. Then type: python imageGA.py to run the program.

    Be sure that your main program includes a line that calls the done method of the grid associated with your genetic algorithm. This will wait for a mouse click before ending the program and will allow you to view the best image found.

    When testing on a 10 by 10 grid, you should be able to evolve symmetrical images with the following parameters:
    • population size 50
    • generations 100
    • probability of crossover 0.6
    • probability of mutation 0.01


Optional components

There are lots of possible extensions to this lab. You could:



Submit

Once you are satisfied with your program, hand it in by typing handin21 in a terminal window.