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:
- 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.
- 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.
- 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.
- 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.
- 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:
- 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.
- 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.
-
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:
-
Evolve images with horizontal symmetry.
-
Evolve images to fit some other pattern of your choice.
- Evolve images with more than two colors. The Grid class
includes the method setColor that allows you to set a cell to
any combination of red, green, and blue values. Read
help(Grid) to find out more. In order to use the GA to
evolve images with more than two colors, you will need to interpret
the chromosome differently. Rather than having one bit represent the
color of one cell, you would need to use several bits to represent the
color of one cell.
-
Evolve solutions to something completely different. As long as you
can represent your task as a series of 1's and 0's and can define a
fitness function that can return a relative measure of success, you
can apply the genetic algorithm to that task.
Submit
Once you are satisfied with your program, hand it in by typing
handin21 in a terminal window.