МЕТОДИ РІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА НА ОСНОВІ ОБЧИСЛЮВАЛЬНОГО ІНТЕЛЕКТУ
DOI:
https://doi.org/10.26906/SUNZ.2024.2.099Ключові слова:
задача комівояжера, маршрут, граф, генетичний алгоритм, кросовер, мутація, селекція, мурашиний алгоритм, штучні нейронні мережі, карта КохоненаАнотація
Актуальність. На сьогоднішній день, задача комівояжера зберігає свою актуальність, оскільки потреба у пошуку найкоротших маршрутів наразі зустрічається в багатьох сферах людської діяльності. Із розвитком технологій та зростанням складності виробничих процесів та логістики, підвищуються вимоги до точності та швидкості пошуку, що зумовлює необхідність вибору доцільних методів рішення цієї задачі. Метою даної роботи є дослідження ефективності використання алгоритмів рішення задачі комівояжера на основі методів обчислювального інтелекту. Об’єктом дослідження є процес пошуку найкоротшого маршруту у графах великої розмірності. Предметом дослідження є алгоритми пошуку маршрутів для задачі комівояжера з використанням методів обчислювального інтелекту. Результати. У даній роботі розглядаються особливості застосування методів обчислювального інтелекту для вирішення задачі комівояжера, що полягають у використанні варіацій генетичного, мурашиного алгоритмів та штучних нейронних мереж, зокрема, карти Кохонена. Проведено аналіз збіжності генетичних алгоритмів при використанні різновидів генетичних операторів. Отримані результати проведених експериментальних досліджень дозволяють зробити висновки щодо переваг та недоліків окремих алгоритмів. Висновок. Запропонований підхід на основі штучної нейронної мережі демонструє найкращу швидкодію та найбільшу точність при вирішенні задач розмірністю приблизно 1000 вершин. Для задач з меншим числом вершин, точніші результати забезпечує використання генетичного алгоритму.Завантаження
Посилання
Davendra D. (2010), “Travelling Salesman Problem, Theory and Applications”, InTech, P. 338, ISBN 978-953-307-426-9
Dahiya C., Sangwan S. (2018), “Literature Review on Travelling Salesman Problem”, International Journal of Research, Vol. 5(16), pp. 1152-1155, e-ISSN: 2348-6848, p-ISSN: 2348-795X
Toaza B, Esztergár-Kiss D. (2023), “A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems”, Applied Soft Computing, Vol. 148, pp. 1-24, doi: https://doi.org/10.1016/j.asoc.2023.110908
Crişan G. C., Iantovics L. B., Nechita E. (2019), “Computational Intelligence for Solving Difficult Transportation Problems”, Procedia Computer Science, Vol. 159, pp. 172-181, doi: https://doi.org/10.1016/j.procs.2019.09.172
Eskandari S., Rafsanjani M. K. (2023), “Two new selection methods and their effects on the performance of genetic algorithm in solving supply chain and travelling salesman problems”, International Journal of Bio-Inspired Computation (IJBIC), Vol. 22(3), pp. 176-184, doi: https://doi.org/10.1504/IJBIC.2023.135464
Іващенко Г. С., Скляров А. С., Барковська О. Ю. (2023), “Гібридний метод рішення задачі маршрутизації транспорту з урахуванням додаткових обмежень”, Системи управління, навігації та зв’язку, №1, с. 75-79, doi: https://doi.org/10.26906/SUNZ.2023.1.075
Wang, Y., Han. Z. (2021), “Ant colony optimization for traveling salesman problem based on parameters optimization”, Applied Soft Computing, Vol. 107, pp. 1-11, doi: https://doi.org/10.1016/j.asoc.2021.107439
Zhang J., Feng X., Zhou B., Ren D. (2012), “An overall-regional competitive self-organizing map neural network for the Euclidean traveling salesman problem”, Neurocomputing, Vol. 89, pp. 1-11, doi: https://doi.org/10.1016/j.neucom.2011.11.024
Shafie M. F., Ahmad F., Osman M. K, Ismail A.P., Ahmad K. A., Yahaya S. Z. (2023), “Optimization of Saleman Travelling Problem Using Genetic Algorithm with Combination of Order and Random Crossover”, 2023 IEEE 13th International Conference on Control System, Computing and Engineering (ICCSCE), pp. 255-258, doi: https://doi.org/10.1109/ICCSCE58721.2023.10237137
Deep K., Mebrahtu H. (2012), “Variant of partially mapped crossover for the Travelling Salesman problems”, International Journal of Combinatorial Optimization Problems and Informatics, Vol. 3(1), pp. 47-69, ISSN: 2007-1558
OuYang Q., Xu H. (2015), “The study of comparisons of three crossover operators in genetic algorithm for solving single machine scheduling problem”, International Conference on Manufacturing Science and Engineering (ICMSE 2015), Atlantis Press, pp. 293-297, doi: https://doi.org/10.2991/icmse-15.2015.55
Kumar R., Memoria M., Thapliyal M., Kirola M., Ahmad I., Gupta A., Tyagi S., Ansari N. (2022), “Analyzing The Performance Of Crossover Operators (OX, OBX, PBX, MPX) To Solve Combinatorial Problems”, 2022 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COM-IT-CON), pp. 817-821, doi: https://doi.org/10.1109/COM-IT-CON54601.2022.9850689
Singh D. R., Singh M. K., Singh T. (2016), “A Hybrid Algorithm with Modified Inver-Over Operator and Genetic Algorithm Search for Traveling Salesman Problem”, Advanced Computing and Communication Technologies, pp. 141-150, doi: https://doi.org/10.1007/978-981-10-1023-1_14
Chopard B., Tomassini M. (2018), “The Ant Colony Method”, An Introduction to Metaheuristics for Optimisation, pp. 81-96, doi: https://doi.org/10.1007/978-3-319-93073-2_5
Colorni A., Dorigo M., Maniezzo V. (1991), “Distributed Optimization by Ant Colonies”, Proceedings of ECAL91 – European Conference on Artificial Life, Elsevier Publishing, pp. 134-142
Dorigo M., Maniezzo V., Colorni A. (1996), “The Ant System: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol. 26(1), pp. 29-41, doi: https://doi.org/10.1109/3477.484436
Yaloveha, V., Hlavcheva, D., Podorozhniak, A. and Kuchuk, H. (2019), “Fire hazard research of forest areas based on the use of convolutional and capsule neural networks”, 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering, UKRCON 2019 – Proceedings, DOI: http://dx.doi.org/10.1109/UKRCON.2019.8879867
Yaloveha, V., Hlavcheva, D. and Podorozhniak, A. (2019), “Usage of convolutional neural network for multispectral image processing applied to the problem of detecting fire hazardous forest areas”, Сучасні інформаційні системи, Vol. 3, No 1, pp. 116–120, DOI: https://doi.org/10.20998/2522-9052.2019.1.19
Datsenko, S., and Kuchuk, H. (2023), “Biometric authentication utilizing convolutional neural networks”, Advanced Information Systems, vol. 7, no. 2, pp. 67–73. Doi: https://doi.org/10.20998/2522-9052.2023.3.10
Yaloveha, V., Podorozhniak, A., Kuchuk, H. (2022), “Convolutional neural network hyperparameter optimization applied to land cover classification”, Radioelectronic and Computer Systems, No. 1(2022), pp. 115–128, DOI: https://doi.org/10.32620/reks.2022.1.09
Sarikyriakidis S., Goulianas K., Margaris A. I. (2023), “Using Self-organizing Maps to Solve the Travelling Salesman Problem: A Review”, WSEAS transactions on systems, Vol. 22, pp. 131-159, doi: https://doi.org/10.37394/23202.2023.22.14
Faigl J., Hollinger, G. A. (2018), “Autonomous Data Collection Using a Self-Organizing Map”, IEEE Transactions on Neural Networks and Learning Systems, Vol. 29(5), pp. 1703-1715, doi: https://doi.org/10.1109/TNNLS.2017.2678482
