Simple Genetic Algorithm

Implementing a Simple Genetic Algorithm

In this assignment, you will implement a simple genetic algorithm in Python with fitness-proportionate selection (roulette-wheel sampling), population size 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 genome of length 20. Perform 50 runs, and measure the average generation at which the string of all ones is discovered. Perform the same experiment with crossover turned off (p_c = 0). If it turns out that mutation with crossover is better than mutation alone, why do you think that is the case? Do similar experiments, systematically varying the mutation and crossover rates, and population size, to see how the variations affect the average time required for the GA to find the optimal string.

Your GA program should print out, on each generation cycle, the fitness of the best individual in the current population and the average fitness of the population as a whole. It should also give the user the option of recording this output data in a text file. This will enable you to plot the results of each run for easy comparison.

To make implementing your GA easier, you should break up your program into the following smaller pieces, rather than trying to implement everything as one large program. Write and test each of the functions listed below separately, and then use them as building blocks in your main GA program. Feel free to write any other helper functions that you like.

randomGenome(length) returns a random genome (bit string) of a given length.
makePopulation(size, length) returns a new randomly created population of the specified size, represented as a list of genomes of the specified length.
fitness(genome) returns the fitness value of a genome.
evaluateFitness(population) returns a pair of values: the average fitness of the population as a whole and the fitness of the best individual in the population.
crossover(genome1, genome2) returns two new genomes produced by crossing over the given genomes at a random crossover point.
mutate(genome, mutationRate) returns a new mutated version of the given genome.
selectPair(population) selects and returns two genomes from the given population using fitness-proportionate selection. This function should use weightedChoice, which we wrote in class, as a helper function.
runGA(populationSize, crossoverRate, mutationRate, logFile="") is the main GA program, which takes the population size, crossover rate (p_c), and mutation rate (p_m) as parameters. The optional logFile parameter is a string specifying the name of a text file in which to store the data generated by the GA, for plotting purposes. When the GA terminates, this function should return the generation at which the string of all ones was found.

Here is an example of the type of output your program should produce:

>>> runGA(100, 0.7, 0.001, "run1.txt")
Population size: 100
Genome length: 20
Generation    0: average fitness 10.07, best fitness 15.00
Generation    1: average fitness 10.91, best fitness 15.00
Generation    2: average fitness 11.45, best fitness 16.00
Generation    3: average fitness 12.02, best fitness 16.00
...
Generation   18: average fitness 16.09, best fitness 19.00
Generation   19: average fitness 16.38, best fitness 20.00
Results saved in file run1.txt
19
>>>

The contents of the resulting text file run1.txt should look something like this:

0 10.07 15.00
1 10.91 15.00
2 11.45 16.00
3 12.02 16.00
...
18 16.09 19.00
19 16.38 20.00

Testing Your Program

An automated tester program is available for testing your functions randomGenome, makePopulation, fitness, evaluateFitness, crossover, mutate, and selectPair. I can't guarantee that this program will detect all possible bugs that may exist in your code, but it should catch the most egregious ones. This program cannot be used to test runGA or any other helper functions you may have defined (you'll have to do that on your own), but if the aforementioned functions all pass their tests, you can be reasonably certain that they are working correctly.

Download the file GAinspector.py and put it in the same folder as your Python program file.
Put the line import GAinspector at the top of your Python file.
After loading your file into Python, type GAinspector.test() at the Python prompt to test everything, or GAinspector.test(function_name) to test individual functions, where function_name is one of: randomGenome, makePopulation, fitness, evaluateFitness, crossover, mutate, or selectPair. For example:
```
>>> GAinspector.test(randomGenome)
```

What to Turn In

Turn in a printout of your Python program file and a 1-2 page written summary of your experimental results in PDF or Word format. If you have questions about anything, don't hesitate to ask!