Accelerating Genetic Algorithm Using General Purpose GPU and CUDA

Genetic Algorithm (GA) is one of most popular swarm based evolutionary search algorithm that simulates natural phenomenon of genetic evolution for searching solution to arbitrary engineering problems. Although GAs are very effective in solving many practical problems, their execution time can become a limiting factor for evolving solution to most of real life problems as it involve large number of parameters that are to be determined. Fortunately, the most time-consuming operators like fitness evaluations, selection, crossover and mutation operations that involves multiple data independent computations. Such computations can be made parallel on GPU cores using Compute Unified Design Architecture (CUDA) platform. In this paper, various operations of GA such as fitness evaluation, selection, crossover and mutation, etc. are implemented in parallel on GPU cores and then performance is compared with its serial implementation. The algorithm performances in serial and in parallel implementations are examined on a testbed of well-known benchmark optimization functions. The performances are analyzed with varying parameters viz. (i) population sizes, (ii) dimensional sizes, and (iii) problems of differing complexities. Results shows that the overall computational time can substantially be decreased by parallel implementation on GPU cores. The proposed implementations resulted in 1.18 to 4.15 times faster than the corresponding serial implementation on CPU.