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

• Autorzy: Nowotniak R. , Kucharski J.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2012
• Tom: Vol. 60, nr 2
• Strony: 323--330
• Opis fizyczny: Bibliogr. 48 poz., rys., tab.

Twórcy

autor

Nowotniak R.

autor

Kucharski J.

• Computer Engineering Department, Technical University of Łódź, 18/22 Stefanowskiego St., 90-924 Łódź, Poland,

Bibliografia

• [1] A. Narayanan and M. Moore, “Quantum-inspired genetic algorithms”, Proc. IEEE Evolutionary Computation 1, 61–66 (1996).
• [2] K.H. Han and J.H. Kim, “Genetic quantum algorithm and its application to combinatorial optimization problem”, Proc. Congress on Evolutionary Computation 1, 1354–1360 (2000).
• [3] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, 1996.
• [4] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000.
• [5] P. Jantos, D. Grzechca, and J. Rutkowski, “Evolutionary algorithms for global parametric fault diagnosis in analogue integrated circuits”, Bull. Pol. Ac.: Tech. 60 (1), 133–142 (2012).
• [6] A. Slowik, “Application of evolutionary algorithm to design minimal phase digital filters with non–standard amplitude characteristics and finite bit word length”, Bull. Pol. Ac.: Tech. 59 (2), 125–135 (2011).
• [7] L. Chomatek and M. Rudnicki, “Application of genetically evolved neural networks to dynamic terrain generation”, Bull. Pol. Ac.: Tech. 59 (1), 3–8 (2011).
• [8] Ł. Jopek, R. Nowotniak, M. Postolski, L. Babout, and M. Janaszewski, “Application of Quantum Genetic Algorithms in Feature Selection Problem”, Scientific Bull. Ac. Sci. and Technology, Automatics 13 (3), 1219–1231 (2009).
• [9] H. Talbi, M. Batouche, and A. Draa, “A quantum-inspired genetic algorithm for multi-source affine image registration”, in: Image Analysis and Recognition, pp. 147–154, Springer, Berlin, 2004.
• [10] H. Talbi, M. Batouche, and A. Draa, “A quantum-inspired evolutionary algorithm for multiobjective image segmentation”, Int. J. Mathematical, Physical and Engineering Sciences 1, 109–114 (2007).
• [11] L.Wang, H. Wu, F. Tang, and D.Z. Zheng, “A hybrid quantuminspired genetic algorithm for flow shop scheduling”, in: Advances in Intelligent Computing, pp. 636–644, Springer, Berlin, 2005.
• [12] B.B. Li and L. Wang, “A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling”, IEEE Trans. Systems, Man, and Cybernetics, Cybernetics B 37, 576–591 (2007).
• [13] Y.W. Jeong, J.B. Park, J.R. Shin, and K.Y. Lee, “A thermal unit commitment approach using an improved quantum evolutionary algorithm”, Electric Power Components and Systems 37, 770–786 (2009).
• [14] T. Lau, C. Chung, K. Wong, T. Chung, and S. Ho, “Quantuminspired evolutionary algorithm approach for unit commitment”, IEEE Trans. Power Systems 24, 1503–1512 (2009).
• [15] L. Su-Hua, W. Yao-Wu, P. Lei, and X. Xin-Yin, “Application of quantum-inspired evolutionary algorithm in reactive power optimization”, Relay 33, 30–35 (2005).
• [16] J.G. Vlachogiannis and K.Y. Lee, “Quantum-inspired evolutionary algorithm for real and reactive power dispatch”, IEEE Trans. Power Systems 23, 1627–1636 (2003).
• [17] S. Jeżewski, M. Łaski, and R. Nowotniak, “Comparison of algorithms for simultaneous localization and mapping problem for mobile robot”, Sci. Bull. Ac. Sci. and Technology, Automatics 14, 439–452 (2010).
• [18] G. Zhang, “Quantum-inspired evolutionary algorithms: a survey and empirical study”, J. Heuristics 17, 1–49 (2010).
• [19] J.J. Grefenstette, “Optimization of control parameters for genetic algorithms”, IEEE Trans. Systems, Man and Cybernetics 16, 122–128 (1986).
• [20] R. Nowotniak and J. Kucharski, “Meta-optimization of quantum-inspired evolutionary algorithm”, Proc. XVII Int. Conf. on Information Technology Systems 1, CD-ROM (2011).
• [21] M.E.H. Pedersen, Tuning & Simplifying Heuristical Optimization, University of Southampton, Southampton, 2010.
• [22] NVidia Corporation, Compute Unified Device Architecture Programming Guide, NVIDIA, Santa Clara, 2007.
• [23] J. Owens, “GPU architecture overview”, ACM SIGGRAPH 1, 5–9 (2007).
• [24] J.D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A.E. Lefohn, and T.J. Purcell, “A survey of general-purpose computation on graphics hardware”, Computer Graphics Forum 26, 80–113 (2007).
• [25] R. Nowotniak and J. Kucharski, “Building blocks propagation in quantum-inspired genetic algorithm”, Sci. Bull. Ac. Sci. and Technology, Automatics 14, 795–810 (2010).
• [26] A.R. Khorsand and T.M.R Akbarzadeh, “Quantum gate optimization in a meta-level genetic quantum algorithm”, IEEE Int. Conf. Systems, Man and Cybernetics 4, 3055–3062 (2005).
• [27] R. Fernando, GPU Gems: Programming Techniques, Tips and Tricks for Real-Time Graphics, Addison-Wesley Professional, London, 2004.
• [28] J. Nickolls, I. Buck, M. Garland, and K. Skadron, “Scalable parallel programming with CUDA”, ACM Queue 6, 40–53 (2008).
• [29] J. Kr¨uger and R. Westermann, “Linear algebra operators for GPU implementation of numerical algorithms”, ACM SIGGRAPH 2005 Courses 1, 908–916 (2005).
• [30] S. Tomov, J. Dongarra, and M. Baboulin, “Towards dense linear algebra for hybrid GPU accelerated manycore systems”, Parallel Computing 36, 232–240 (2010).
• [31] O. Fialka and M. Cadik, “FFT and convolution performance in image filtering on GPU”, 10th Int. Conf. on Information Visualization 1, 609–614 (2006).
• [32] M.J. Harris, “Fast fluid dynamics simulation on the GPU”, GPU Gems 1, 637–665 (2004).
• [33] T. Preis, P. Virnau, W. Paul, and J.J. Schneider, “GPU accelerated Monte Carlo simulation of the 2D and 3D Ising model”, J. Computational Physics 228, 4468–4477 (2009).
• [34] M. Lee, J. Jeon, J. Bae, and H.S. Jang, “Parallel implementation of a financial application on a GPU”, Proc. 2nd Int. Conf. Interaction Sciences: Information Technology, Culture and Human 1, 1136–1141 (2009).
• [35] T. Preis, P. Virnau, W. Paul, and J.J. Schneider, “Accelerated fluctuation analysis by graphic cards and complex pattern formation in financial markets”, New J. Physics 11, 93–124 (2009).
• [36] K. Moreland and E. Angel, “The FFT on a GPU”, Proc. ACM SIGGRAPH/EUROGRAPHICS Conf. Graphics hardware 1, 112–119 (2003).
• [37] W. Banzhaf and S. Harding, “Accelerating evolutionary computation with graphics processing units”, Proc. 11th Annual Conf. Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers 1, 3237–3286 (2009).
• [38] F. Kr¨uger, O. Maitre, S. Jim´enez, L. Baumes, and P. Collet, “Speedups between 70x and 120x for a generic local search (memetic) algorithm on a single GPGPU chip”, Applications of Evolutionary Computation 1, 501–511 (2010).
• [39] K.L. Fok, T.T. Wong, and M.L. Wong, “Evolutionary computing on consumer graphics hardware”, IEEE Intelligent Systems 22, 69–78 (2007).
• [40] M.L. Wong, “Parallel multi-objective evolutionary algorithms on graphics processing units”, Proc. 11th Annual Conf. Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers 1, 2515–2522 (2009).
• [41] S. Luke, Essentials of metaheuristics lulu.com, 2009.
• [42] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Professional, London, 1989.
• [43] K.H. Han and J.H. Kim, “Quantum-inspired evolutionary algorithm for a class of combinatorial optimization”, IEEE Trans. Evolutionary Computation 6, 580–593 (2002).
• [44] C.S. Perone, “PyEvolve: a Python open–source framework for genetic algorithms”, ACM SIGEVOlution 4, 12–20 (2009).
• [45] R. Durrett, Probability: Theory and Examples, International Thomson Publishing Company, New York, 1996.
• [46] J.E. Stone, D. Gohara, and G. Shi, “OpenCL: A parallel programming standard for heterogeneous computing systems”, Computing in Science and Engineering 12, 66–73 (2010).
• [47] R. Tsuchiyama, T. Nakamura, T. Iizuka, A. Asahara, and S. Miki, The OpenCL Programming Book, Fixstars Corporation, London, 2009.
• [48] I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian, M. Houston, and P. Hanrahan, “Brook for GPUs: stream computing on graphics hardware”, ACM Trans. on Graphics 23, 777–786 (2004).