Parallelization of binary and real-coded genetic algorithms on GPU using CUDA

Abstract

Genetic Algorithms(GAs) are suitable for parallel computing since population members fitness maybe evaluated in parallel. Most past parallel GA studies have exploited this aspect, besides resorting to different algorithms, such as island, single-population master-slave, fine-grained and hybrid models. A GA involves a number of other operations which, if parallelized, may lead to better parallel GA implementation than those currently existing. In this paper, we parallelize binary and real-coded genetic algorithms using CUDA API's with C. Although, objective and constraint violations evaluations are embarassingly parallel, other algorithmic and code optimizations have been proposed and tested. The bottlenecks in a parallel GA implementation are identified and modified suitably. The results are compared with the sequential algorithm on accuracy and clock time for varying problems by studying the effect of a number of parameters, namely: (i) population sizes, (ii) number of threads, (iii) problem sizes, and (iv) problems of differing complexities. Significant speed-ups have been observed over the sequential GA.