An adaptive quantum evolution algorithm for 0–1 knapsack problem
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2018.2.08Keywords:
quantum computing, quantum bit, quantum genetic algorithm, quantum gate operator, 0-1 knapsack problemAbstract
Quantum Genetic Algorithm (QGA) has a number of advantages in comparison with its classical version: operating speed, small population size and auto-balance between the global search and the local search. It is based on the ideas of traditional evolutionary algorithms, applied to the quantum computations technology, which operate with quantum bits, superposition of states and quantum measurements. This paper proposes a QGA with a new adaptive quantum gate operator and a restoring technology for the quantum chromosome during the process of solving combinatorial problems with constraints. Meta-optimization of the primary algorithm parameters is used for providing the algorithm efficiency. The productiveness of the suggested approach is proven by the model studies, carried out using a wide range of test 0–1 knapsack problems.References
Holland J.H. Adaptation in Natural and Arti_cial Systems: An Introductory Analysis with Applications to Biology, Control, and Arti_cial Intelligence / J.H. Holland. — Ann Arbor, MI: University of Michigan Press, 1975.
Whitley Darrell. A genetic algorithm tutorial / Darrell Whitley. — Statistics and computing. — 1994. —Vol. 4, N 2. — P. 65–85.
Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs / Z. Michalewicz // New York: Springer, 3rd (extended) edition, 1996.
Jantos P. Evolutionary algorithms for global parametric fault diagnosis in analogue integrated circuits / P. Jantos, D. Grzechca, J. Rutkowski // Bull. Pol. Ac.: Tech. — 2012. — Vol. 60, N 1. — P. 133–142.
Han K.-H. Genetic quantum algorithm and its application to combinatorial optimization problem / K.-H. Han, J.-H. Kim // Proceedings of IEEE Congress on Evolutionary Computation, USA. — 2000. — Vol. 2. — P. 1354–1360.
Nowotniak R. Higher-Order Quantum-Inspired Genetic Algorithms / R. Nowotniak, J. Kucharski // Federated Conference on Annals of Computer Science and Information Systems. — 2014. — P. 465–470.
Jopek Ł. Zastosowanie kwantowych algorytmów genetycznych do selekcji cech / Ł. Jopek, R. Nowotniak, M. Postolski et al. // Automatyka, Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. — 2009. — Vol.13, N 3. — P. 1219–1231.
Talbi H. A Quantum-Inspired Evolutionary Algorithm for Multiobjective Image Segmentation / H. Talbi, M. Batouche, A. Draa // International Journal of Mathematical, Physical and Engineering Sciences. — 2007. — Vol. 1, N 2. — P. 109–114.
Li B.B. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling / B.B. Li, L. Wang // IEEE Trans. Systems, Man, and Cybernetics, Part B: Cybernetics. — 2007. — Vol. 37, N 3. — P. 576–591.
Lau T. Quantum-inspired evolutionary algorithm approach for unit commitment / T. Lau, C. Chung, K. Wong, T. Chung, S. Ho // IEEE Trans. on Power Systems. — 2009. — Vol. 24, N 3. — P. 1503–1512.
Su-Hua L. Application of quantum-inspired evolutionary algorithm in reactive power optimization / L. Su-Hua, W. Yao-Wu, P. Lei, X. Xin-Yin // Relay. — 2005. —Vol. 33. — P. 30–35.
Narayanan A. Quantum-inspired genetic algorithms / A. Narayanan, M. Moore // IEEE Evolutionary Computation. — 1996. — Vol.1. — P. 61–66.
Wang H. The improvement of quantum genetic algorithm and its application on function optimization / H. Wang, J. Liu, J. Zhi, C. Fu // Math. Probl. Eng. — 2013. — Vol. 2013. — P. 1–10.
Kuk-Hyun Han. Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization / Kuk-Hyun Han, Jong-Hwan Kim // IEEE Transactions on Evolutionary Computation. — 2002. — Vol. 6, N 6. — P. 580–593.
