Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study
Department of Management and Information, Science, Hannan University, 5-4-33 Amamihigashi, Matsubara, Osaka 580-8502, Japan
In GECCO ’09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (2009), pp. 2523-2530.
@conference{tsutsui2009solving,
title={Solving quadratic assignment problems by genetic algorithms with gpu computation: a case study},
author={Tsutsui, S. and Fujimoto, N.},
booktitle={Proceedings of the 11th Annual Conference Companion on Genetic and EvolutionaryComputation Conference: Late Breaking Papers},
pages={2523–2530},
year={2009},
organization={ACM}
}
This paper describes designing a parallel GA with GPU computation to solve the quadratic assignment problem (QAP) which is one of the hardest optimization problems in permutation domains. For the parallel method, a multiple-population, coarse-grained GA model was used. Each subpopulation is evolved by a multiprocessor in a GPU (NVIDIA GeForce GTX285). At predetermined intervals of generations all individuals in subpopulations are shuffled via the VRAM of the GPU. The instances on which this algorithm was tested were taken from the QAPLIB benchmark library. Results were promising, showing a speedup ration from 3 to 12 times, compared to the Intel i7 965 processor.
October 30, 2010 by hgpu
