МЕТОДИ РІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА НА ОСНОВІ ОБЧИСЛЮВАЛЬНОГО ІНТЕЛЕКТУ
Ключові слова:
задача комівояжера, маршрут, граф, генетичний алгоритм, кросовер, мутація, селекція, мурашиний алгоритм, штучні нейронні мережі, карта Кохонена
Анотація
Актуальність. На сьогоднішній день, задача комівояжера зберігає свою актуальність, оскільки потреба у пошуку найкоротших маршрутів наразі зустрічається в багатьох сферах людської діяльності. Із розвитком технологій та зростанням складності виробничих процесів та логістики, підвищуються вимоги до точності та швидкості пошуку, що зумовлює необхідність вибору доцільних методів рішення цієї задачі. Метою даної роботи є дослідження ефективності використання алгоритмів рішення задачі комівояжера на основі методів обчислювального інтелекту. Об’єктом дослідження є процес пошуку найкоротшого маршруту у графах великої розмірності. Предметом дослідження є алгоритми пошуку маршрутів для задачі комівояжера з використанням методів обчислювального інтелекту. Результати. У даній роботі розглядаються особливості застосування методів обчислювального інтелекту для вирішення задачі комівояжера, що полягають у використанні варіацій генетичного, мурашиного алгоритмів та штучних нейронних мереж, зокрема, карти Кохонена. Проведено аналіз збіжності генетичних алгоритмів при використанні різновидів генетичних операторів. Отримані результати проведених експериментальних досліджень дозволяють зробити висновки щодо переваг та недоліків окремих алгоритмів. Висновок. Запропонований підхід на основі штучної нейронної мережі демонструє найкращу швидкодію та найбільшу точність при вирішенні задач розмірністю приблизно 1000 вершин. Для задач з меншим числом вершин, точніші результати забезпечує використання генетичного алгоритму.Завантаження
Дані про завантаження поки що недоступні.
Посилання
1. Davendra D. (2010), “Travelling Salesman Problem, Theory and Applications”, InTech, P. 338, ISBN 978-953-307-426-9
2. 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
3. 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
4. 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
5. 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
6. Іващенко Г. С., Скляров А. С., Барковська О. Ю. (2023), “Гібридний метод рішення задачі маршрутизації транспорту з урахуванням додаткових обмежень”, Системи управління, навігації та зв’язку, №1, с. 75-79, doi: https://doi.org/10.26906/SUNZ.2023.1.075
7. 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
8. 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
9. 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
10. 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
11. 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
12. 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
13. 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
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
15. 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
16. 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
17. 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
18. 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
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
20. 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
21. 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
22. 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
2. 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
3. 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
4. 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
5. 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
6. Іващенко Г. С., Скляров А. С., Барковська О. Ю. (2023), “Гібридний метод рішення задачі маршрутизації транспорту з урахуванням додаткових обмежень”, Системи управління, навігації та зв’язку, №1, с. 75-79, doi: https://doi.org/10.26906/SUNZ.2023.1.075
7. 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
8. 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
9. 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
10. 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
11. 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
12. 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
13. 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
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
15. 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
16. 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
17. 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
18. 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
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
20. 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
21. 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
22. 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
Опубліковано
2024-04-30
Як цитувати
Ivashchenko Heorhii Методи рішення задачі комівояжера на основі обчислювального інтелекту / Heorhii Ivashchenko, Oleksandr Onyshchenko, Maksym Bondarenko, Nikita Zdoryk // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2024. – Т. 2 (76). – С. 99-105. – doi:https://doi.org/10.26906/SUNZ.2024.2.099.
Розділ
Інформаційні технології
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
