Cellular Genetic Algorithms (cGAs) are effective optimization techniques solving

Abstract. The availability of low cost powerful parallel graphic cards has estimu-lated a trend to implement diverse algorithms on Graphic Processing Units (GPUs). In this paper we describe the design of a parallel Cellular Genetic Algorithm (cGA) on a GPU and then evaluate its performance. Beyond the existing works on master-slave for fitness evaluation, we here implement a cGA exploiting data and instruc-tions parallelism at the population level. Using the CUDA language on a GTX-285 GPU hardware, we show how a cGA can profit from it to create an algorithm of im-proved physical efficiency and numerical efficacy with respect to a CPU implemen-tation. Our approach stores individuals and their fitness values in the global memory of the GPU. Both, fitness evaluation and genetic operators are implemented en-tirely on GPU (i.e. no CPU is used). The presented approach allows us benefit from the numerical advantages of cGAs and the efficiency of a low-cost but powerfu