CS63 HW3: Genetic Algorithms

Due by noon Friday, October 5

You may work with a partner on this assignment. Be sure to add both names to the top of every file. Only one of the partners needs to turn in the code.

Before you begin do an update63 to get a copy of the files you'll need to complete this homework. They should appear in the directory cs63/homework/03.


Implementing a GA

Implement a basic Genetic Algorithm (as described on page 10 in the reading assigned from Melanie Mitchell's book) with fitness-proportionate selection based on roulette-wheel sampling, single-point crossover and bitwise mutation.

Implement your solution as a class called GeneticAlgorithm that takes the chromosome length and population size as parameters.

Your class should include methods to handle selection, crossover, mutation, and the evolution process. Evolution should end when a maximum number of generations is reached or when a solution to the given problem is found.

Test your GA on one of the fitness functions we used in class, the sum of the bits or the integer represented by the bits when interpreted as a binary number.


Applying the GA to a new problem

You may apply your GA to the graph coloring problem that we discussed in class on Tuesday or to a problem of your own choosing.

As we discussed, finding an optimal schedule is an NP-complete problem. We will consider the problem of how to schedule final exams for all of the courses being taken by students currently in the AI course. Any scheduling problem can be transformed into a graph coloring problem. For our particular problem, each unique course will be represented as a vertex in a graph. Any pair of courses that contains the same student will be connected by an edge. Our goal is to find a coloring of the graph (with as few colors as possible) such that no two connected vertices have the same color. Once this is accomplished, we will know the minimum number of final exam slots required so that no student will have conflicting exam times.

To try the graph coloring problem, do an update63. This will copy the following files to your cs63/homework/03 directory.

Here's some example output. The population size and maximum number of generations are both smaller than you would want to use in practice. Notice that it has not been able to find a solution using only 8 colors.
Creating graph
Total number of courses: 56
Total number of edges: 213

Initializing GraphColorGA
Maximum number of colors allowed: 8
Number of bits per color: 3

Executing genetic algorithm
Chromosome length: 168
Population size: 20
Maximum number of generations: 3
Crossover rate: 0.7
Mutation rate: 0.01
-------------------------------------------------------
Generation: 0 Total fitness: 3865 Avg fitness: 193.25 Best fitness: 200

Best gene: [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1,
0, 1, 0, 0, 0, 1, 0, 0 , 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0,
1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1,
1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1 , 1, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0,
1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0]
-------------------------------------------------------
Generation: 1 Total fitness: 3856 Avg fitness: 192.8 Best fitness: 198

Best gene: [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1,
0, 1, 0, 0, 0, 1, 1, 0 , 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1,
1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1,
0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1,
1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1 , 1, 0, 0, 1,
0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0,
0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
-------------------------------------------------------
Generation: 2 Total fitness: 3869 Avg fitness: 193.45 Best fitness: 201

Best gene: [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0,
1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 0 , 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1,
0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1,
1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1,
1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1 , 0, 0, 0, 0,
0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0,
0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0]
-------------------------------------------------------
Generation: 3 Total fitness: 3881 Avg fitness: 194.05 Best fitness: 199

Best gene: [0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0,
1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1,
0, 0, 1, 0, 0, 0, 1, 1 , 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1,
0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0,
0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0,
0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0 , 0, 1, 0, 1,
1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0,
0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1]

Max generations reached

BEST COLORING
[1, 0, 3, 7, 5, 2, 3, 4, 4, 0, 0, 7, 3, 7, 1, 7, 5, 7, 7, 3, 4, 2, 7,
0, 6, 7, 6 , 6, 5, 7, 4, 0, 5, 4, 1, 5, 7, 4, 3, 2, 7, 2, 6, 4, 0, 7,
5, 6, 3, 3, 2, 7, 1, 4, 3, 0]

Unresolved conflicts with current coloring:
CPSC063 MUSI043
CPSC063 ENGR072
CPSC063 GERM005
CPSC063 MATH027
CPSC063 PHYS115
ENGR015 ENGR011
MATH063 PHYS063
ENGR041 ENGR077
CPSC033 STAT061
ENGR082 LING050
ENGR082 PSYC001
MATH101 MATH059

Fitness
201

In this example the fitness function being used is the total number of edges minus the number of conflicts. This is not necessarily the best choice. You should consider other options. Also the GA will perform significantly better if crossover is restricted such that the crossover point can only occur between color boundaries on the bit string. Another option is to modify the GA to be more general so that it can use a restricted set of integers rather than just bits to represent the genes.


Submit
Once you are satisfied with your programs, hand them in by typing handin63 at the unix prompt.