Publication Details

Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU

POSPÍCHAL Petr, SCHWARZ Josef and JAROŠ Jiří. Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU. In: 16th International Conference on Soft Computing MENDEL 2010. Brno: Brno University of Technology, 2010, pp. 64-70. ISBN 978-80-214-4120-0.
Czech title
Paralelní genetický algoritmus řešící 0/1 Knapsack problém běžící na GPU
Type
conference paper
Language
english
Authors
Pospíchal Petr, Ing. (DCSY FIT BUT)
Schwarz Josef, doc. Ing., CSc. (DCSY FIT BUT)
Jaroš Jiří, doc. Ing., Ph.D. (DCSY FIT BUT)
Keywords

massively parallel, genetic algorithm, island model, CUDA, GPU, 0/1 Knapsack problem

Abstract
In this work, we show that consumer-level $100 GPU can be used to significantly speed-up optimization
of 0/1 Knapsack problem. We identify strong and weak points of GPU architecture and propose our parallel
genetic algorithm model implemented in CUDA running entirely on the GPU. We show that GPU must be utilized
for sufficiently long time in order to obtain reasonable program speedup. Then we compare results quality and
speed of our model with single-threaded CPU code implemented using Galib. Peak speedup of GPU GA execution
performance is 1340x resp. 134x for 4-bit resp. 40-bit problem instances while maintaining reasonable results
quality.
Published
2010
Pages
64-70
Proceedings
16th International Conference on Soft Computing MENDEL 2010
Conference
16th International Mendel Conference on Soft Computing, Brno, CZ
ISBN
978-80-214-4120-0
Publisher
Brno University of Technology
Place
Brno, CZ
UT WoS
000288144100010
EID Scopus
2-s2.0-79955114415
BibTeX 
@INPROCEEDINGS{FITPUB9253,
   author = "Petr Posp\'{i}chal and Josef Schwarz and Ji\v{r}\'{i} Jaro\v{s}",
   title = "Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU",
   pages = "64--70",
   booktitle = "16th International Conference on Soft Computing MENDEL 2010",
   year = 2010,
   location = "Brno, CZ",
   publisher = "Brno University of Technology",
   ISBN = "978-80-214-4120-0",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9253"
}
Files
Back to top