Due date: Wednesday, October 15, 2025.
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) from the module randomthat 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. Implement two more crossover functions: for the 2-point crossover and for the uniform crossover. The latter should receive a parameter for the probability of exchanging the genes at each location in the two chromosomes.
The 2-point crossover selects two random locations and swaps the genes in between these locations.
The uniform crossover draws a random event of the given probability for each location in the two chromosomes and swaps them if the event is favorable. If prob is the probability of swap, passed in as parameter, then you can generate a random number r between 0 and 1. Then if r < prob, you can swap the genes at that location (chromosome[i]).
Change the function run_ga to add two more parameters for the crossover form with default value of 0, and a probability of swap in case we are using the uniform crossover, with a default value of 0.3. You will need to add these parameters to the function new_generation as well.
Modify the function new_generation so that it checks the parameter for the crossover form, and if it is 0, it calls the 1-point crossover, if it is 1, it calls the 2-point crossover, and if it is 2, it calls the uniform one with the probability given by the additional parameter.
c. 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.
d. Solve the two cryptarithmetic problems by hand and figure out what sequence of numbers should the chromosome contain when it represents the optimal solution.
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 three forms of crossover, 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 some other spreadsheet app 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 png file.
Turn in: the two python files to Canvas, Assignments, Homework 7, with your answer to point 2.a in a text file or as comments in the submission, and the image created at 2.b.