Homework 4: Genetic Search (aka Evolutionary Algorithms)

Homework 4: Genetic Search (aka Evolutionary Algorithms)#

Graphical Icon representing a genetic algorithm.

In a genetic algorithm, a population of candidate solutions (called individuals) are evolved to optimize performance on a specific problem. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual’s genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

  1. genetic representation of the solution domain,

  2. fitness function to evaluate the solution domain.

A standard representation of each candidate solution is as an array of bits. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case.

Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover and selection operators.

In this assignment, you are going to modify and improve the processing speed of a “REVERSE Conway’s Game of Life” program using MPI.

The Reverse Conway’s Game of life is when we have a target state which we want to reach using the forward Conway game of life rules (see HW3). The reverse problem is much harder because the math itself is not reversable. To solve this problem we will “guess” a state, forward propigate the game to the end state and then compare the target end state to our guess end state.

Consider a \(50 \times 50\) Conway’s GOL target. Brute force search is not possible since all possible states are \(2^{(50 \times 50)}\) or

2**(50*50)

This is a big number and it is impossible to find a solution in a reasonable amount of time using brute force. We are going to try to solve this problem using Genetic Algorithms.

✅ DO THIS: Copy the source code from D2L, transfer to your HPCC account, and compile and test the code.

  • Change to the repository directory on a development node and run the following commands to verify the code is working:

make clean
make
make test

Goals for this assignment:#

By the end of this assignment, you should be able to:

  • Debug and benchmark existing workflows serially.

  • Submit a job array to take advantage of a pleasantly parallel workflow.

  • Update an example to compile with MPI, Send/Recv messages and run it across nodes on the HPCC.

Homework Assignment#

For this assignment you will do the following parts:

  1. Establish Serial Benchmark

  2. Pleasantly Parallel Benchmark

  3. Consolidate the results at the end using MPI

  4. Share intermittent state using MPI.

  5. Final Report

  6. Deliverables

1. Establish Serial Benchmark#

✅ DO THIS: Benchmark the code provided using the “random” setting by using the following command:

SEED=1
time ./revROC cmse2.txt $SEED

✅ DO THIS: Write a script (called timecheck.sh to run the code 10 times with 10 different input seeds. Note the average time and the best result Fitness in your report. Save the best solution as serial_best.txt.

NOTE: this will take a while. Feel free to make the script a SLURM submission script and run it on the HPCC. Just make sure you give it plenty of time (4 hours?) to finish.

✅ DO THIS: Add the timecheck.sh and serial_best.txt files to your repository.

2. Pleasantly Parallel Benchmark#

We should be able to run this code on different cores using different random seeds. Basically create lots of workers that are each searching for the best answer at the same time (and not talking to each other). When they all are done we can see which of the workers “wins”.

✅ DO THIS: Write a job script (called job_array.sb) to run the program on 50 CPUs using a simple job array. Give each job the following:

  • Different random seed (Hint: use the SLURM jobarray id variable).

  • Request each job 2 times the average time found in step 1 to make sure each job has plenty of runtime.

  • Request each job 2gb of memory.

  • Run this on the cmse2.txt input target.

✅ DO THIS: Review the output for all 50 jobs and note the best result Fitness in your report. Save the best solution as pp_best.txt.

✅ DO THIS: Add the job_array.sb and pp_best.txt file to your repository.

3. Consolidate the results at the end using MPI#

To make things a little simpler, I would like to split up the MPI problem into two steps. This first step we are just going to use MPI to “Consolidate” all of the answers. Generally speaking the results will not be any different from the Pleasantly parallel runs but this is the “easier” step so I think it should go first.

✅ DO THIS: Make a copy of reverseGOL.c called reverseGOL-mpi.c. Modify the makefile to compile this program using mpicc (keep the compile for the baseline reverseGOL.c).

✅ DO THIS: Modify the end of reverseGOL-mpi.c to have workers share their best result with the lead worker (rank ==0) and then have the lead worker print out the overall best result to the screen. This will involve the following steps:

  1. Set up MPI communication at the beginning the main function before the main loop.

  2. After the main loop, write an if statement to check if the current worker is the lead working (i.e. rank==0):

    • if the current worker is NOT the lead worker then send the best fitness and individual to the lead worker using two MPI_Send commands.

    • if the current worker IS the lead worker then loop over the other workers and receive their best fitness and individual fitness using two MPI_RECV commands. If the worker’s fitness is better than the current best, replace the current best with the worker’s solution otherwise discard that worker’s solution. After the loop print out the final result.

✅ DO THIS: Write a job script (called mpi_job.sb) to run the program on 50 CPUs using MPI (mpirun). Give the job similar runtime to step 2, 100gb of memory (2gb per core). Run this on the cmse2.txt input target.

✅ DO THIS: Review the output and note the best result Fitness in your report. Save the best solution as mpi_basic_best.txt.

✅ DO THIS: Commit the mpi_job.sb, reverseGOL-mpi.c and mpi_basic_best.txt files to your repository. Also commit any changes to your makefile.

4. Share intermittent state using MPI#

Both step 2 and 3 are basically pleasantly parallel (although step 3 saves us a lot of time reviewing files). The problem with these Pleasantly parallel codes is that there is no cross-communication between the search workers. One of the strengths of genetic search is that it can chase down good solutions by modifying okay ones.

In this step we are going to modify the code using MPI so that each search program can “talk” to each other and share their best results so far. This way the workers can all chase down solutions together.

There are a lot of correct ways to do this. We are going to try something simple as a starting point. After each generation and before the mutation we will have each worker share its best result so far with it’s neighbor (using round robin). If the neighbor’s fitness is better than our own current best, we will replace our current best with our neighbors and set our second best sbest to what was our current best.

✅ DO THIS: Modify reverseGOL-mpi to do the following:

  1. Have each worker send the best fitness and best individual to the rank+1 neighbor. If the current worker is the last worker then have it send it’s best fitness and best individual to the 0 worker (aka lead worker).

  2. Have each worker receive the best fitness and best individual from the rank-1 neighbor. If the current worker is the first worker (rank 0 aka lead worker) then have it receive it’s best fitness and best individual from the last worker.

  3. Make sure you modify the program to avoid deadlock. Have the lead worker receive and then send and have all of the other workers send and then receive.

  4. If the neighbor’s worker fitness is better than our current fitness, add our neighbor’s individual to our population and update our best.

✅ DO THIS: Rerun our updated mpi program using the mpi-job.sh script. Review the output and note the best result Fitness in your report. Save the best solution as mpi_best.txt.

✅ DO THIS: Add the mpi_best.txt file to your repository. Also save any changes to your makefile.

5. Final Report#

✅ DO THIS: Write a report describing what you learned. The report should be written in either Markdown or Jupyter notebooks.

  • Start by describing how the provided serial code performed. Record the best Fitness value found in the 10 serial runs and the average run time (also describe the hardware where the test was run).

  • Report the best Fitness value found in by the job array.

  • Report the best fitness value found in the first consolidated MPI run.

  • Report the best fitness value found in the sharing MPI run.

Make a graph of the final fitness values to see what method “won” explain the graphs in your report text with a focus on any odd results you may see. Conclude with a general lessons learned.

6. Deliverables#

✅ DO THIS: Prepare your files for the instructor. I recommend having two versions of the code; original serial version, MPI version. You can also have a third version for the intermediate MPI code if you did not get the file code to work. Update the provided Makefile to build all executables.

When you are done, put all your files into a zip folder and upload them to D2L. Your instructor will use the following command to compile and test your code on the HPCC:

make clean
make 
make test
sbatch job_array.sh
sbatch mpi_job.sh

Congratulations, you are done!#

Submit your tgz file to the course Desire2Learn page in the HW4 assignment.

Written by Dr. Dirk Colbry, Michigan State University (Updated by Dr. Nathan Haut in Spring 2025) Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.