ВИКОРИСТАННЯ МУРАШИНОГО АЛГОРИТМУ ДЛЯ РОЗВ'ЯЗАННЯ НЕЧІТКОЇ ЗАДАЧІ КОМІВОЯЖЕРА
DOI:
https://doi.org/10.17721/3041-2323.2024.185-202Ключові слова:
нечітка задача комівояжера, оптимізаційний метод мурашиної колонії, трапецієподібні нечіткі числа, дефазифікація, оцінювання ефективностіАнотація
Задача комівояжера (TSP) – це класична комбінаторна задача оптимізації, яка передбачає пошук найкоротшого або найшвидшого маршруту серед набору міст. Щоб формалізувати невизначеність і неточність у вхідних даних, часто викликану суб'єктивними оцінками інтервалів часу подорожі, у цій статті використано нечіткі числа. Форма цих нечітких чисел базується на підході, подібному до гаусівського. Розглянуто особливості застосування алгоритму оптимізації мурашиної колонії (ASO) і запропоновано підхід до його оптимального використання. Проаналізовано вплив параметрів алгоритму на якість апроксимованого найкращого рішення. Задачу проілюстровано числовими прикладами з участю достатньо великої кількості міст у транспортній мережі.
Посилання
Bouamama, S., Blum, C., & Fages, J. (2019). An algorithm based on ant colony optimization for the minimum connected dominating set problem. Applied Soft Computing, 80, 672–686. https://doi.org/10.1016/j.asoc.2019.04.032
Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a largescale traveling salesman problem. Operations Research, 2, 393–410. https://doi.org/10.1287/opre.2.4.393
Dorigo, M. (1992). Optimization, learning and natural algorithms [Doctoral dissertation]. Politecnico di Milano.
Dorigo, M. (2004). Ant colony optimization. MIT Press.
Dorigo, M., & Di Caro, G. A. (1999). Ant algorithms for discrete optimization. Artificial Life, 5(2), 137–172. https://doi.org/10.1162/106454699568728
Dorigo, M., & Di Caro, G. A. (1998). AntNet: Distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research, 9, 317–365. https://doi.org/10.1613/jair.525
Dubois, D., & Prade, H. (1987). The mean value of a fuzzy number. Fuzzy Sets and Systems, 24(3), 279–300. https://doi.org/10.1016/0165-0114(87)90189-9
Ivohin, E. V., Gavrylenko, V. V., & Ivohina, K. E. (2023). On the recursive algorithm for solving the traveling salesman problem on the basis of the data flow optimization method. Radio Electronics, Computer Science, Control, 3, 141–147. https://doi.org/10.15588/1607-3274-2023-3-16
Karaboga, D. (2009). A new design method based on artificial bee colony algorithm for digital IIR filters. Journal of the Franklin Institute, 346(4), 328–348. https://doi.org/10.1016/j.jfranklin.2008.11.003
Kennedy, J., & Eberhart, R. C. (2001). Swarm intelligence. Morgan Kaufmann.
Stützle, T., & Hoos, H. (2000). MAX–MIN ant system. Future Generation Computer Systems, 16(8), 889–914. https://doi.org/10.1016/S0167-739X(00)00043-1
Yang, L., Wang, X., He, Z., Wang, S., & Lin, J. (2024). Review of traveling salesman problem solution methods. In Bio-Inspired Computing: Theories and Applications (pp. 3–16). Communications in Computer and Information Science. https://doi.org/10.1007/978-3-031-50887-5_1
Завантаження
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Прикладні інформаційні системи та технології в цифровому суспільстві
Ця робота ліцензується відповідно до ліцензії Creative Commons Attribution 4.0 International License.
