CS63 Lab 4: Genetic Algorithm

Due by 11:59pm Thursday, Nov. 3

A skeleton version of the programs will appear when you run update63 in a terminal window.


A genetic algorithm is an abstract simulation of some of the key ideas from biological evolution. A population of candidate solutions, where each candidate solution 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 candidate solution in the population is determined. Next, parents 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 genetic material of two parents to produce two children. Finally, with some low probability, mutation may occur on the children's' genetic material. 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 candidate solutions are created.

In this lab you will be given a skeleton definition of a GeneticAlgorithm class that you will complete. Then you will test the completed genetic algorithm on a simple problem of finding candidate solutions 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 your cs63/labs/4 directory when you did an update63. Read through the methods that you will need to implement. Recall that there are three main operators used in a genetic algorithm: selection, crossover, and mutation. Below is a review of how they should function.

Once you have implemented all of the class methods, test whether you can evolve a solution of all 1's using the class called SumGA provided at the bottom of the ga.py file.

If you cannot consistently evolve a solution of all 1's, then there may be a problem with your genetic operators or with your methods that control the evolutionary process.

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.

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.

from Grid import *
g = Grid(10,10)

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

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


Notice that 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 candidate solution and draws it in the Grid object. You should interpret 1's as white cells and 0's as black cells. For example, the following candidate solution 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 candidate solution 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. 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 (this is higher than is typical)

Optional extensions

Once you have successfully created a GA that can evolve images with vertical symmetry, feel free to try other ideas, such as:

In comments, be sure to give a clear explanation of your fitness function and your goal for the evolutionary process.


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