The parallel genetic algorithm uses fitness proportional selection,
one-point crossover, and one-point mutation.
I used Chris Miles' parallel GA code for this assignment.
The message MPI standard that I used was LAM MPI.
For the GA I used a population size of 40, with a chromosome size of 10,
probability of crossover of 0.75, probability of mutation of 0.1, and it
runs for 40 generations.
The fitness function is trivial, with the fitness being the sum of the bits
in the chromosome. The "complexity" of the fitness computation
is varied by using the usleep function to sleep for varied amounts of microseconds.
The results shown below are for approximate fitness computation times of
100 microseconds (0.0001 seconds), 0.1 seconds, 0.5 seconds, and 1 second.
Graph of speedup versus the number of processors with a fitness computation
time of approximately 100 microseconds.
Graph of speedup versus the number of processors with a fitness computation
time of approximately 0.1 seconds.
Graph of speedup versus the number of processors with a fitness computation
time of approximately 0.5 seconds.
Graph of speedup versus the number of processors with a fitness computation
time of approximately 1 second.
All graphs compared.
|
