Higher-order quantum genetic algorithm for 0-1 knapsack problem

Authors

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2018.3.05

Keywords:

quantum genetic algorithm, 0-1 knapsack problem, quantum gate operator, quantum register, entanglement of quantum states

Abstract

In order to enhance the effectiveness of the quantum genetic algorithm (QGA), it is proposed to switch to higher-order quantum registers in the quantum chromosome representation. Such representation makes it possible to apply a powerful quantum computations mechanism – quantum state entanglement. In the algorithm implementation, we also use an adaptive quantum gate operator and propose a quantum chromosome recovery technology for solving constrained combinatorial optimization problems. The influence of the quantum register size on the algorithm efficiency has been investigated. The advantages of the suggested approach in comparison with the QGA traditional implementation are demonstrated on the example of multidimensional 0–1 knapsack problem and different levels of input data correlation.

Author Biographies

Valerii M. Tkachuk, Vasyl Stefanyk Precarpathian National University, Ivano-Frankivsk

Valerii Mikhailovich Tkachuk,

Ph.D., an associate professor at the Department of Information Technology of Faculty of Mathematics and Computer Science of Vasyl Stefanyk Precarpathian National University, Ivano-Frankivsk, Ukraine.

Orysya M. Tkachuk, Vasyl Stefanyk Precarpathian National University, Ivano-Frankivsk

Tkachuk Orysya Mikolaivna,

Ph.D., an associate professor at the Department of Pedagogy of Elementary Education of Faculty of Pedagogy of Vasyl Stefanyk Precarpathian National University, Ivano-Frankivsk, Ukraine.

References

Holland J.H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence / J.H. Holland. — London: Bradford book edition, 1994. — 211 p.

Simon D. Evolutionary Optimization Algorithms: Biologically Inspired and Population-Based Approaches to Computer Intelligence / D. Simon. — John Wiley & Sons, 2013. — 742 p.

Narayanan A. Quantum-inspired genetic algorithms / A. Narayanan, M. Moore // Proce­edings of the IEEE International Conference on Evolutionary Computation (ICEC’96), Nagoya, Japan, 1996. — P.61–66.

Han K.–H. Genetic quantum algorithm and its application to combinatorial optimization problem / K.–H. Han, J.–H. Kim // Proc.Congress on Evolutionary Computation. — Vol. 2. — La Jolla, CA, July 2000. — P. 1354–1360.

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. — P.1–10.

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.

Tkachuk V. Quantum Genetic Algorithm Based on Qutrits and Its Application / V. Tkachuk // Mathematical Problems in Engineering. — Vol. 2018, Article ID 8614073, 8 p.

Zhang G. Quantum-inspired evolutionary algorithms: a survey and empirical study / G. Zhang // Journal of Heuristics. — 2010. — P. 1–49.

Han K. Quantum-inspired evolutionary algorithms with a new termination criterion, h-epsilon gate, and two-phase scheme / K. Han, J. Kim // IEEE Trans. Evol. Comput. — 2014. — 8 (2). — P. 156–169.

Iimura I. Integer-Type Gene-Coding Method Based on Quantum Bit Representation in Quantum-Inspired Evolutionary Algorithm: Application to Integer Knapsack Problem / I. Iimura // Journal of Signal Processing. — 2012. — Vol. 16, N 6. — P. 495–502.

Takata T. Performance Analysis of Quantum-Inspired Evolutionary Algorithm / T. Takata, T. Isokawa, A. Saitoh et al // SCIS & ISIS 2010, Dec. 8-12, Okayama Convention Center, Okayama, Japan.

Downloads

Published

2018-10-16

Issue

No. 3 (2018)

Section

Problem- and function-oriented computer systems and networks

License

This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles in this journal without asking prior permission from the publisher or the author. This is in accordance with the BOAI definition of open access.