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

Bulletin of the Polish Academy of Sciences. Technical Sciences

R. NowotniakComputer Engineering Department, Technical University of ?ód?, 18/22 Stefanowskiego St., 90-924 ?ód?, PolandOther articles by this author:De Gruyter OnlineGoogle Scholar¹  J. KucharskiComputer Engineering Department, Technical University of ?ód?, 18/22 Stefanowskiego St., 90-924 ?ód?, PolandOther articles by this author:De Gruyter OnlineGoogle Scholar¹ 

[1] Computer Engineering Department, Technical University of ?ód?, 18/22 Stefanowskiego St., 90-924 ?ód?, Poland

关键词: Keywords: : quantum-inspired genetic algorithm;    evolutionary computing;    meta-optimization;    parallel algorithms;    GPGPU.;   

DOI  :  10.2478/v10175-012-0043-4

学科分类：工程和技术（综合）

来源: Polska Akademia Nauk * Centrum Upowszechniania Nauki / Polish Academy of Sciences, Center for the Advancement of Science

【 摘 要 】

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 400× 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.

【 授权许可】

Unknown