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

@inproceedings{citeulike:6072737, abstract = {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.}, address = {New York, NY, USA}, author = {Tsutsui, Shigeyoshi and Fujimoto, Noriyuki}, booktitle = {GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference}, citeulike-article-id = {6072737}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1570355}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1570256.1570355}, doi = {10.1145/1570256.1570355}, isbn = {978-1-60558-505-5}, keywords = {2009, cuda, ga, genetic-algorithm, gpu, np-hard, optimization, quadratic\_assignment\_problem}, location = {Montreal, Qu\'{e}bec, Canada}, pages = {2523--2530}, posted-at = {2009-11-05 09:22:21}, priority = {0}, publisher = {ACM}, title = {Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study}, url = {http://dx.doi.org/10.1145/1570256.1570355}, year = {2009} }

TY - CONF ID - citeulike:6072737 L3 - citeulike-article-id:6072737 N2 - 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. CY - Montreal, Qu\'{e}bec, Canada SN - 978-1-60558-505-5 AD - New York, NY, USA EP - 2530 TI - Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study PB - ACM T2 - GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference SP - 2523 KW - 2009 KW - cuda KW - ga KW - genetic-algorithm KW - gpu KW - np-hard KW - optimization KW - quadratic_assignment_problem AU - Tsutsui, Shigeyoshi AU - Fujimoto, Noriyuki PY - 2009/// UR - http://dx.doi.org/10.1145/1570256.1570355 ER -