CS63 Spring 2004
Lab 5: Experimenting with Genetic Algorithms
Due in lab Friday, March 26

CONTENTS

• Introduction
• Lab Instructions
• What to hand in

• There is a collection of materials available online to help you learn how to use Pyro's evolutionary algorithms. Read through PyroModuleEvolutionaryAlgorithms. For now, you can skip the example on using a GA to evolve a neural network robot brain, as well as the example of the N-Queens problem.

• EXPERIMENT 1:You will do a series of experiments for a problem, varying the mutation and crossover rates, to see how the variations affect the average time required for the GA to find the optimal string. Use a fitness function that sums the number of ones in the bit string. The string length should be 100. The population size should be 100. Use an elite percentage of 0.05. Use single-point crossover with a rate of 0.7. Use a bitwise mutation rate of 0.001. Perform 10 runs, and compute the average generation at which the string of all ones is discovered. Perform the same experiment with crossover turned off. Do several other similar experiments, varying the mutation and crossover rates. Create a table to display the average results for each variation you tried. What can you conclude from these results?

• EXPERIMENT 2:You will do a series of experiments for a problem, keeping the mutation rate and crossover rate fixed while varying the population size. Use a fitness function that interprets the bit string as a binary number. The string length should be 30. Start with a population size of 100. Use an elite percentage of 0.05. Use single-point crossover with a rate of 0.7. Use bitwise mutation with a rate of 0.001. Perform 10 runs for each variation of the population size. Create a table to display the average generation at which the string of all ones is discovered. Also plot the fitness of the best individual found at each generation as well as the average fitness of the population at each generation. You only need to turn in one graph from a typical run for each variation of the population size. You may want to try xgraph, a basic graphing tool that we recently added to the system. How do these plots change as you vary the population size? What can you conclude about how population size affects the speed of convergence of a GA?

• EXPERIMENT 3:Compare the GA's performance on the bit sum fitness function with that of the hill climbing algorithm given below:
  1. Start with a single randomly generated string. Calculate its fitness.
  2. Randomly mutate one bit of the current string.
  3. If the fitness of the mutated string is equal to or higher than the fitness of the original string, keep the mutated string. Otherwise keep the original string.
  4. Go to step 2.

  Iterate this algorithm for 10,000 steps. This is equal to the number of fitness function evaluations performed by a GA with a population size of 100 that is run for 100 generations. Plot the best fitness found so far at every 100 evaluation steps (equivalent to one GA generation), averaged over 10 runs. Compare this with a plot of the GA's best fitness found so far as a function of generation. Which algorithm finds better performing strategies? Which algorithm finds them faster? Comparisons like these are important if claims are to be made that a GA is a more effective search algorithm than other stochastic methods on a given problem.