BULLETIN of the

POLISH ACADEMY of SCIENCES

TECHNICAL SCIENCES

BULLETIN of the POLISH ACADEMY of SCIENCES: TECHNICAL SCIENCES
Volume 60, Issue 2, June 2012

Issue Index Authors Index Scope Index  Web Info

Aims&Scope, Subscription Editors Authors' guide to read PDF files mirror: http://fluid.ippt.gov.pl/~bulletin/
pp 323 - 330

PDF -  733 KB

GPU-based tuning of quantum-inspired genetic algorithm for a combinatorial optimization problem

R. NOWOTNIAK and J. KUCHARSKI
This paper concerns efficient parameters tuning (meta-optimization) of a state-of-the-art metaheuristic, Quantum-Inspired Genetic Algorithm (QIGA), in a GPU-based massively parallel computing environment (NVidia CUDATMtechnology). A novel approach to parallel implementation of the algorithm has been presented. In a block of threads, each thread transforms a separate quantum individual or different quantum gene; In each block, a separate experiment with different population is conducted. The computations have been distributed to eight GPU devices, and over 400x speedup has been gained in comparison to Intel Core i7 2.93GHz CPU. This approach allows efficient meta-optimization of the algorithm parameters. Two criteria for the meta-optimization of the rotation angles in quantum genes state space have been considered. Performance comparison has been performed on combinatorial optimization (knapsack problem), and it has been presented that the tuned algorithm is superior to Simple Genetic Algorithm and to original QIGA algorithm.
Key words:

quantum-inspired genetic algorithm, evolutionary computing, meta-optimization, parallel algorithms, GPGPU


Issue Index Authors Index Scope Index  Web Info

Aims&Scope, Subscription Editors Authors' guide to read PDF files
Copyright ® Bulletin of the Polish Academy of Sciences: Technical Sciences