GPU Accelerated Genetic Algorithms
Rajvi Shah1,   P J Narayanan1   and  Kishore Kothapalli2
1CVIT, IIIT Hyderabad, India,  2CSTAR, IIIT Hyderabad 
Genetic algorithms are effective in solving many optimization tasks. However, the long execution time associated with it prevents its use in many domains. In this paper, we propose a new approach for parallel implementation of genetic algorithm on graphics processing units (GPUs) using CUDA programming model. We exploit the parallelism within a chromosome in addition to the parallelism across multiple chromosomes. The use of one thread per chromosome by previous efforts does not utilize the GPU resources effectively. Our approach uses multiple threads per chromosome, thereby exploiting the massively multithreaded GPU more effectively. This results in good utilization of GPU resources even at small population sizes while maintaining impressive speed up for large population sizes. Our approach is modeled after the GAlib library and is adaptable to a variety of problems. We obtain a speedup of over 1500 over the CPU on problems involving a million chromosomes. Problems of such magnitude are not ordinarily attempted due to the prohibitive computation times. For more details please read our paper.
Publications
Rajvi Shah, P J Narayanan, Kishore Kothapalli, GPU-accelerated Genetic Algorithms, Workshop on Parallel Architectures for Bio-inspired Algorithms in conjunction with Conference on Parallel Architectures and Compilation Techniques (PACT Workshop), 2010, Vienna, Austria.
| PDF | PPTBibTex |