1038

Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study

Shigeyoshi Tsutsui, Noriyuki Fujimoto
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}

}

Download Download (PDF)   View View   Source Source   

767

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: