Due date: Thursday, February 28, 2008.

Ex. 1 Download the following files:
individual.py
ga.py

They contain the implementation of a simple genetic algorithm to solve the cryptarithmetic problem "SEND + MORE + MONEY". Add the following things to the code:

a. In the class Individual (and module by the same name), a class method called
mutation_rand(prob)
This mutation should work almost the same way as the mutation that replaces a gene with its opposite, but instead it should replace a gene with a random value between 0 and 9. You can use the function randint(a,b) that generation a random number r such that a <= r <= b.

Add a second case for mutt in the function new_generation such that if the parameter mutt is equal to 2, the function mutation_rand is called instead of the mutation_opp.

b. In the module ga.py add an evaluation function for the cryptarithmetic problem "EAT + THAT = APPLE". To make the algorithm solve this problem you will have to change the function eval_ind. Adapt the individual size to this problem.

c. Solve the two cryptarithmetic problems by hand and figure out what sequence of numbers should the chromosome contain when it represents the optimal solution.

Ex. 2. a. Experiment again with combinations of parameters to see if you can get closer to the optimal solution for the two problems. Make sure that you try the two forms of mutation, and the other parameter choices are up to you. The things you can vary are: the size of the population, the number of generations, the probability of crossover and of mutation.

b. Choose one set of parameters that you found appropriate and one of the problems, then modify the code for the function run_ga to output the fitness of the best individual in the new generation every 10 generations. Run the algorithm and store the output to a file using redirection (like, "python ga.py > result.txt"). Perform this experiment once with the elitist selection and once without it (store both numbers in separate files). Import (copy-paste or whatever else works) the evolution of the fitness in the two cases into an Excel or OpenOffice Cal spreadsheet and plot them as a flowchart with the horizontal axis being the generation number and using simple lines. Make sure that both sets of results are plotted on the same flowchart to be able to compare them. Save the flowchart as a GIF file.

Turn in: the two python files, your answer to the 2.a in a text file or as comments in the email, and the image created at 2.b.