Parallelization of binary and real-coded genetic algorithms on GPU using CUDA
Department of Mathematics and Scientific Computing, Indian Institute of Technology Kanpur, Kanpur, India
IEEE Congress on Evolutionary Computation (CEC), 2010
@inproceedings{arora2010parallelization,
title={Parallelization of binary and real-coded genetic algorithms on GPU using CUDA},
author={Arora, R. and Tulshyan, R. and Deb, K.},
booktitle={Evolutionary Computation (CEC), 2010 IEEE Congress on},
pages={1–8},
year={2010},
organization={IEEE}
}
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.
May 27, 2011 by hgpu
