В.М. Ткачук, М.І. Козленко, М.В. Кузь, І.М. Лазарович, М.С. Дутчак
Èlektron. model. 2019, 41(3):43-57
https://doi.org/10.15407/emodel.41.03.043
АННОТАЦИЯ
При побудові квантових генетичних алгоритмів (QGA) традиційним є представлення квантової хромосоми у вигляді системи незалежних кубітів. Це не дозволяє використати такий потужний механізм квантових обчислень, як заплутаність квантових станів. У роботі реалізовано QGA вищих порядків та проілюстровано його ефективність на прикладі задачі числової оптимізації з використанням ряду тестових функцій. Також запропоновано оператор квантового гейту із адаптивним характером роботи, що не вимагає використання таблиці пошуку. У порівнянні із традиційним QGA перехід до вищих (більше двох) порядків при реалізації алгоритму показує значно кращі результати як по часу виконання, так і по швидкості збіжності та точності знайденого розв’язку.
КЛЮЧЕВЫЕ СЛОВА:
функціональна оптимізація, заплутаність квантових станів, квантовий генетичний алгоритм, квантові обчислення, квантовий регістр.
СПИСОК ЛИТЕРАТУРЫ
1. Han, K.-H. and Kim, J.-H. (2000), “Genetic quantum algorithm and its application to combinatorial optimization problem”, Proceedings of the 2000 Congress on Evolutionary Computation,
USA, 2, pp. 1354-1360.
2. Roy, U., Roy, S. and Nayek, S. (2014), “Optimization with quantum genetic algorithm”, International Journal of Computer Applications, Vol. 102, no. 16, pp. 1-7.
3. Zhang, G. (2011), “Quantum-inspired evolutionary algorithms: a survey and empirical study“, Journal of Heuristics, Vol. 2011, no. 17, pp. 303-351, DOI: 10.1007/s10732–010–9136–0.
4. Wang, H., Liu, J., Zhi, J. and Fu, C. (2013), “The Improvement of Quantum Genetic Algorithm and Its Application on Function Optimization”, Mathematical Problems in Engineering, Vol. 2013.
5. Wang, L., Kowk, S.K. and Ip, W.H. (2012), “Design of an improved quantum-inspired evolutionary algorithm for a transportation problem in logistics systems”, Journal of Intelligent Manufacturing, pp. 2227-2236, DOI: 10.1007/s10845–011–0568–7.
6. Jantos, P., Grzechca, D. and Rutkowski, J. (2012), “Evolutionary algorithms for global parametric fault diagnosis in analogue integrated circuits”, Bull. Pol. Tech, Vol. 60, pp. 133-142, DOI:10.2478/v10175–012–0019–4.
7. Talbi, H., Batouche, M. and Draa, A. (2007), “A Quantum-Inspired Evolutionary Algorithm for Multiobjective Image Segmentation”, International Journal of Nuclear and Quantum Engineering, Vol. 1, pp. 109-114.
8. Qin, C., Liu, Y. and Zheng, J. (2008), “A real-coded quantum-inspired evolutionary algorithm for global numerical optimization”, 2008 IEEE Conference on Cybernetics and Intelligent Systems, pp. 1160-1164, DOI: 10.1109/ICCIS.2008.4670779.
9. Lin, D. and Waller, S. (2009), “A quantum-inspired genetic algorithm for dynamic continuous network design problem”, Transportation Letters: The International Journal of Transportation Research, Vol. 1, pp. 81-93, DOI: 10.3328/TL.2009.01.01.81—93.
10. Malossini, A., Blanzieri, E. and Calarco, T. (2008), “Quantum genetic optimization”, IEEE Trans. Evol. Comput, Vol. 12, pp. 231-241.
11. SaiToh, A., Rahimi, R. and Nakahara, M. (2014), “A quantum genetic algorithm with quantum crossover and mutation operations”, Quantum Information Process, Vol. 13, pp. 737-755.
12. Lahoz-Beltra, R. (2016), “Quantum Genetic Algorithms for Computer Scientists”, Computers, Vol. 5, no. 4, DOI: 10.3390/computers5040024.
13. Tkachuk, V. (2018). “Quantum Genetic Algorithm onMultilevel Quantum Systems”, Mathematical Problems in Engineering, Vol. 2018, DOI: 10.1155/2018/9127510.
14. Narayanan, A. and Moore, M. (1996), “Quantum-inspired genetic algorithms”, Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC’96), Nagoya, Japan, pp. 61-66, DOI:10.1109/ICEC.1996.542334.
15. Nowotniak, R. and Kucharski, J. (2014), “Higher-Order Quantum-Inspired Genetic Algorithms”, Federated Conference on Annals of Computer Science and Information Systems, Vol. 2, pp. 465-470, DOI: 10.15439/2014F99.
16. Ullah, S. and Wahid, M. (2015), “Topology Control of Wireless Sensor Network Using Quantum Inspired Genetic Algorithm”, International Journal of Swarm Intelligence and Evolutionary Computation, Vol. 4, DOI: 10.4172/2090–4908.1000121.
17. Tkachuk, V. (2018), “Quantum Genetic Algorithm Based on Qutrits and Its Application”, Mathematical Problems in Engineering, Vol. 2018, DOI :10.1155/2018/8614073.
18. Sun, Y. and Xiong, H. (2014), “Function Optimization Based on Quantum Genetic Algorithm”, Research Journal of Applied Sciences, Engineering and Technology, Vol. 7, no. 1, pp. 144-149, ISSN: 2040-7459; e-ISSN: 2040-7467.
19. Kuo, S.-Y. and Chou, Y.-H. (2017), “Entanglement-Enhanced Quantum-Inspired Tabu Search Algorithm for Function Optimization”, IEEE Access, Vol. 5, pp. 13236-13252, DOI: 10.1109/ACCESS.2017.2723538.
TKACHUK Valerii Mykhailovych, Ph.D. (Phys.-Math.), Associate professor of the Vasyl Stefanyk
Precarpathian National University, graduated from the Ivan Franko Lviv State University in 1984.
The field of scientific interests: machine learning and data mining, artificial intelligence, quantum information,
evolutionary algorithms.
KOZLENKO Mykola Ivanovych, Ph.D. (Eng.), Head of the Department of Information Technology
and Associate Professor at Vasyl Stefanyk Precarpathian National University, graduated from Ivano-
Frankivsk State Technical University of Oil and Gas in 1994. The field of scientific interests: robotics,
deep learning for computer vision, software design and development.
KUZ Mykola Vasyliovych, Dr.Sc. (Tech.), Professor of the Vasyl Stefanyk Precarpathian National
University, graduated from the Lviv Polytechnic National University in 1997. The field of scientific interests:
software quality, evolutionary algorithms.
LAZAROVYCH Ihor Mykolaiovych, Ph.D. (Tech.), Associate Professor of the Vasyl Stefanyk Precarpathian
National University, graduated from the Ivano-Frankivsk State Technical University of Oil
and Gas in 2000. The field of scientific interests: artificial intelligence, machine learning, noise-immune
data transmission, signal randomization, digital data processing.
DUTCHAK Mariia Stepanivna, Assistant of the Vasyl Stefanyk Precarpathian National University,
which graduated in 2007. The field of scientific interests: adaptive knowledge transfer system, data
mining, expert systems.