CPSC 4XX Final Project

Parallel Genetic Algorithms

2018-12

Use parallel computing concepts to decrease the time on average for a genetic algorithm to find an optimal solution.

Abstract

 Our project idea is to create a general genetic algorithm engine that utilizes hardware acceleration and parallel computing to speed up the creation of future generations. Currently, the standard for genetic algorithms are run in a linear fashion which test the fitness of each candidate and then select the top candidates, perform crossover, and implement mutation all at one time, then continue with the next generation, repeating this process over and over. With our idea, a certain number of candidates can be tested and then the process of selecting top candidates for the crossover and mutation process can begin while other candidates are still being tested.

Using hardware acceleration and parallel computing, the process of creating the next generation can be sped up by (hopefully multiple times the rate of linear processing), due to the fact that mutations are being put into new generation candidates much faster. Hardware acceleration uses GPUs to perform fast matrix math, most commonly multiplication which GPUs are optimized for. This can be utilized to increase the speed of genetic algorithms by expressing the candidates as matrices and using GPUs to perform the math involved for crossover and mutation. Parallel computing can be used to increase the throughput of the selection, crossover, and mutation part of the genetic algorithm by running multiples of them at once and using results from candidate testing before the test is entirely completed. Just as functions in a CPU can be stacked to optimize the throughput, the selection, crossover, and mutation can be stacked candidate by candidate and sorted by fitness rather than by performing the selection, crossover, and mutation for an entire generation at one time only after the entire generation has been tested for fitness.

Implementing these new changes will ensure a faster way to reach the desired fitness for a specific candidate. The plan is to implement this genetic algorithm using a language like C# or C++ or something similar. These languages will give us a lot of flexibility in what we can do and also allow us to work with something we have been exposed to before in multiple classes. The end result of this project is to hopefully create a very efficient and fast genetic algorithm that reaches peak fitness in a candidate much faster than the algorithm standards we use today. The parallel processing will make all good mutations move more quickly through candidates and future generations and the hardware acceleration will ensure the fastest available method for any computation that needs to be done in the genetic algorithm. One way to test this new algorithm would be to set up the same starting conditions for this and a nonparallel / nonhardware accelerated algorithm and run them together to see which hits the end result for fitness level the fastest.