КВАНТОВЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ВЫСШИХ ПОРЯДКОВ В ЗАДАЧАХ ФУНКЦИОНАЛЬНОЙ ОПТИМИЗАЦИИ

В.М. Ткачук, Н.И. Козленко, Н.В. Кузь, И.Н. Лазарович, М.С. Дутчак

È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.

Полный текст: PDF