CECS 375 Assignment 3: Genetic Algorithms

Due Thursday, Oct. 23 by 5 p.m., Email your work to Matt Williams at mgw5a2@mizzou.edu. As before, include a log file that illustrates your program execution. And always use meaningful variable names and helpful comments.

The assignment is worth 10% of your semester grade.

This assignment builds on Assignment #2 and also uses Figure 3.22 in the text. You may use your language of choice; however, Lisp will probably be the easiest, especially for part 2, which will require the successor function from Assignment #2.

1. Implement a simple GA with fitness-proportionate selection (selection based on a fitness function), roulette-wheel (random) sampling, population size of 100, single-point crossover rate, p_c = 0.7, and bitwise mutation rate, p_m = 0.001. Try it on the following fitness function:

f(x) = number of ones in x, where x is a chromosome of length 20.

(a) Perform 20 runs and measure the average generation at which the string of all ones is discovered.

(b) Perform the same experiment with crossover turned off (i.e., p_c = 0).

(c) Do similar experiments, varying the mutation and crossover rates, to see how the variations affect the average time required for the GA to find the optimal string. If it turns out that mutation with crossover is better than mutation alone, why is that the case?

2. Apply your GA program to the problem in Fig. 3.22. Note the performance of the algorithm by displaying the number of generations required to find the path. Display also the best path found in each generation. Try it out with several starting and goal positions, as was done for Assignment #2. How do your GA results compare the searches used in Assignment #2?