Due by class time Tuesday, February 14
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 pc = 0.7, and bitwise mutation rate pm = 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 (pc = 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 will organize your program as a collection of smaller functions, rather than implementing everything in a single large function. Write and test each of the functions listed below separately, in the order shown, and then use them as building blocks in your main function. You are free to write any additional helper functions that you like, but your program must include the functions below. You should represent genomes as ordinary Python strings containing the characters '0' or '1'.
random_genome(length) returns a random genome (bit string) of a given length.
make_population(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.
evaluate_fitness(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, mutation_rate) returns a new mutated version of the given genome.
select_pair(population) selects and returns two genomes from the given population using fitness-proportionate selection. This function should use weighted_choice, which we wrote in class, as a helper function.
main(population_size, crossover_rate, mutation_rate, logfile="") is the main GA program, which takes the population size, crossover rate (pc), and mutation rate (pm) 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 number at which the string of all ones was found.
Here is an example of the type of output your program should produce:
>>> main(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
An automated tester program is available for testing your functions random_genome, make_population, fitness, evaluate_fitness, crossover, mutate, and select_pair. 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 main 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: random_genome, make_population, fitness, evaluate_fitness, crossover, mutate, or select_pair. For example:
>>> GAinspector.test(random_genome)
Submit your Python source code file and a 3-4 page written report in PDF format of the experiments that you performed using the Homework Upload Site (I will show you how to do this during class). Your report should be as clear and complete as possible, and should include a brief introduction, a description of the experiments you performed, tables or graphs summarizing the results of your experiments, and a short discussion of your conclusions. Please also make sure to proofread your report carefully for correct spelling and grammar.
If you have questions about anything, don't hesitate to ask!