Parallel GA Implementation

The objective of this project is to garner experience working with genetic algorithms (GAs) in a parallel processing environment while developing an understanding of the relationship between computation time and speedup. The UNR Research grid‘s massively-parallel computational power (720 processor cores!) was utilized to facilitate running a simple GA (proportional fitness selection, one-point crossover, and one-point mutation) with the following criteria:

  1. Populations: 500, 2500, 5000
  2. Generations: 1000, 5000, 10000
  3. Probability of Crossover: 0.9
  4. Probability of Mutation: 0.001

Chris Miles’ Parallel GA design was adapted for this experiment. The fitness calculation developed for the GA trials is very simple: A bit-string consisting of 50 bits is evaluated based upon its ability to adhere to successive inversion. That is, for each successive bit that is analyzed in a genotype, if the succeeding bit is a complement of the current bit, the genotype’s fitness is awarded a point. For each duplicate successive bit, fitness is deducted one point.

The first data point on the left represents 2 processors. Subsequent datapoints represent 4, 8, 16, and 32 processors respectively. One processor was not examined as I was having trouble meshing that scenario with OpenMPI. Time is measured as 1/Duration of run (inverse of the elapsed time) as instructed. As one can see, there are inconsistencies in the performance assumption that more processors would lead to a decrease in overall algorithm processing time. In the case of population values 500 and 2,500, there is a relative performance increase; however, in the 2,500 population, processing time does tick up marginally when at 16 and 32 processors after a huge drop from 4 to 8 processors. The trials with population 5,000 show a more clear distinction in performance decrease with 16 and 32 processors.

Leave a Reply

Your email address will not be published. Required fields are marked *