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.
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.
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.
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.