Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Том 61 >>> № 1 СІЧЕНЬ — ЛЮТИЙ 2025
-->


DOI 10.34229/KCA2522-9664.25.1.4
УДК 519.8

Л.Ф. ГУЛЯНИЦЬКИЙ
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
 leonhul.icyb@gmail.com


ДИВЕРСИФІКАЦІЯ ПОШУКУ В АЛГОРИТМАХ ОМК
ТА ЇЇ ЗАСТОСУВАННЯ

Анотація. Наведено підхід до розроблення диверсифікованих алгоритмів оптимізації мурашиними колоніями — одного з найпоширеніших методів комбінаторної оптимізації. Диверсифікація в алгоритмах ОМК основана на розгляді варіантів продовження побудови поточного фрагмента розв’язку, що враховують не одну, як зазвичай, а декілька вершин графу задачі, які можуть бути включені в цей маршрут. Можливість перегляду мурахами варіантів пошуку на декілька кроків вперед дає змогу підвищити ймовірність уникнення субоптимальних розв’язків та знаходити більш точні розв’язки. Запропонований підхід використовується для створення метаевристичних алгоритмів розв’язування різних задач комбінаторної оптимізації. Наведено результати проведених обчислювальних експериментів із розв’язування серії прикладних задач комбінаторної оптимізації з різних класів, які підтвердили можливість успішної модифікації відомих мурашиних алгоритмів.

Ключові слова: комбінаторна оптимізація, оптимізація мурашиними колоніями, маршрутизація, задача комівояжера, БпЛА, оптимізація авіаперельотів, обчислювальні експерименти.


повний текст

СПИСОК ЛІТЕРАТУРИ

  • 1. Gendreau M., Potvin J.Y. (Eds.). Handbook of metaheuristics. International Series in Operations Research & Management Science. Vol. 272. Cham: Springer, 2019.

  • 2. Stegherr H., Heider M., Hhner J. Classifying metaheuristics: Towards a unified multi-level classification system. Natural Computing. 2022. Vol. 21, N 2. P. 155–171. https://doi.org/ 10.1007/s11047-020-09824-0.

  • 3. Sergienko I.V., Hulianytskyi L.F., Sirenko S.I. Classification of applied methods of combinatorial optimization. Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 732–741. https://doi.org/10.1007/s10559-009-9134-0.

  • 4. Pintea C. Advances in bio-inspired computing for combinatorial optimization problems. Springer, 2014. 188 p.

  • 5. Yang X.S. Nature-inspired optimization algorithms. 2nd ed. Academic Press, 2021. 290 р.

  • 6. Kumar A., Nadeem M., Banka H. Nature inspired optimization algorithms: A comprehensive overview. Evolving Systems. 2023. Vol. 14, N 1. P. 141–156.

  • 7. Dorigo M., Sttzle T. Ant colony optimization. Cambridge (MA): MIT Press, 2004. 348 p. https://doi.org/10.7551/mitpress/1290.001.0001.

  • 8. Dorigo M., Sttzle T. Ant colony optimization: Overview and recent advances. Handbook of metaheuristics. Cham: Springer, 2019. P. 311–352. https://doi.org/10.1007/978-3-319-91086-4_10.

  • 9. Гуляницький Л.Ф. Диверсифікація пошуку в алгоритмах ОМК. Abstracts of Int. Conf «Problems of Decision Making under Uncertainties (PDMU–2011)» (Sept. 19–23, 2011, Yalta, Ukraine). Київ, 2011. P.66–67.

  • 10. Гуляницький Л.Ф. Диверсифікація пошуку в алгоритмах оптимізації мурашиними колоніями. Теорія оптимальних рішень. 2017. C. 47–57.

  • 11. Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Київ: Видавничо-поліграфічний центр «Київський університет», 2016. 142 с.

  • 12. Reinelt G. TSPLIB 95. Technical report. Universitt Heidelberg, 1995. URL: http://comopt.ifi.uni -heidelberg.de/software/ .

  • 13. Stutzle T., Hoos H.H. MAX-MIN ant system. Future Gen. Comput. Systems. 2000. Vol. 16, N 8. P. 889–914.

  • 14. Applegate D.L., Bixby R.E., Chvatїl V., Cook W.J. The traveling salesman problem: A computational study. Princeton Series in Applied Mathematics. Princeton University Press, 2006. 606 p.

  • 15. Toaza B., Esztergїr-Kiss D. A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems. Applied Soft Computing. 2023. Vol. 148, 110908. https://doi.org/10.1016/j.asoc.2023.110908.

  • 16. Гуляницький Л.Ф., Рибальченко О.В. Формалізація проблеми оптимізації місць базування та маршрутів групи БПЛА. Кібернетика та комп’ютерні технології. 2021. Вип. 4. C. 12–26. https://doi.org/10.34229/2707-451X.21.4.2. .

  • 17. Hulianytskyi L., Rybalchenko O. Optimization of decisions when planning a UAV group mission with alternative depots. Selected Papers of the III International Scientific Symposium “Intelligent Solutions” (IntSol-2023). Symposium Proc. (Sept. 27-28, 2023, Kyiv, Ukraine). CEUR Workshop Proceedings. 2023. Vol. 3538. P. 245–256. URL: https://ceur-ws.org/Vol-3538/ Paper_22.pdf. .

  • 18. Horbulin V.P., Hulianytskyi L.F., Sergienko I.V. Optimization of UAV team routes in the presence of alternative and dynamic depots. Cybernetics and Systems Analysis. 2020. Vol. 56, N 2. P. 195–203. https://doi.org/10.1007/s10559-020-00235-8.

  • 19. Kuo RJ, Lu SH, Lai PY, Mara STW. Vehicle routing problem with drones considering time windows. Expert Systems with Applications. 2022. Vol. 191, 116264. https://doi.org/10.1016/ j.eswa.2021.116264.

  • 20. Li J., Xiong Y., She, J. UAV path planning for target coverage task in dynamic environment. IEEE Internet of Things Journal. 2023. Vol. 10, Iss. 20. P. 17734–17745. https://doi.org/10.1109/ jiot.2023.3277850.

  • 21. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев.: Наук. думка, 1998. 472 с.

  • 22. Lässig J., Sudholt D. The benefit of migration in parallel evolutionary algorithms. Proc. of the 12th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2010. P.1105–1112.

  • 23. Lässig J., Sudholt D. Experimental supplements to the theoretical analysis of migration in the island model. Intern. Conf. on Parallel Problem Solving from Nature. Berlin; Heidelberg: Springer, 2010. P. 224–233. https://doi.org/10.1007/978-3-642-15844-5_23.

  • 24. Martí R., Martínez-Gavara A., Glover F. Tabu search. In: Discrete Diversity and Dispersion Maximization. Martí R., Martínez-Gavara A. (Eds.). Springer Optimization and Its Applications. Cham: Springer, 2023. Vol. 204. P. 137–149. https://doi.org/10.1007/978-3-031-38310-6_7.

  • 25. Hulianytskyi L., Pavlenko A. Ant colony optimization algorithms with diversified search in the problem of optimization of airtravel itinerary. Cybernetics and Systems Analysis. 2019. Vol. 55, N 6. P. 978–987. https://doi.org/10.1007/s10559-019-00208-6.

  • 26. Гуляницький Л.Ф., Павленко А.І. Оптимізація шляхів у динамічному графі перельотів модифікованим алгоритмом мурашиних систем. Математичне моделювання в економіці. 2018. № 2. С. 26–39.

  • 27. Zografos K.G., Androutsopoulos K.N. Algorithms for itinerary planning in multimodal transportation networks. IEEE Transactions on Intelligent Transportation Systems. 2008. Vol. 9, N 1. P. 175–184.

  • 28. Travel APIs. URL: URL: https://partners.skyscanner.net/affiliates/travel-apis.

  • 29. QPX Express API. URL: URL: https://developers.google.com/qpx-express.

  • 30. Poikonen S., Golden B. Multi-visit drone routing problem. Computers & Operations Research. 2020. Vol. 113, 104802. https://doi.org/10.1016/j.cor.2019.104802.

  • 31. Horbulin V.P., Hulianytskyi L.F. Sergienko I.V. Planning of logistics missions of the “UAV+vehicle” hybrid systems. Cybernetics and Systems Analysis. 2023. Vol. 59, N 5. P. 733–742. https://doi.org/10.1007/s10559-023-00609-8. .

  • 32. Гуляницький Л.Ф., Рибальченко О.В. Оптимізація маршрутів при плануванні місій гібридних транспортних систем “Дрон+Транспортний засіб”. Cybernetics and Computer Technologies. 2023. Iss. 3. С. 44–58. https://doi.org/10.34229/2707-451X.23.3.4.

  • 33. Stoyan Y.G., Yakovlev S.V. Theory and methods of euclidian combinatorial optimization: current status and prospects. Cybernetics and Systems Analysis. 2020. Vol. 56, N 3. P. 366–379. https://doi.org/10.1007/s10559-020-00253-6.

  • 34. Talbi E.G. Metaheuristics: from design to implementation. Hoboken, N.J.: John Wiley & Sons, Inc., 2009. 593 p.

  • 35. Raidl G.R., Puchinger J., Blum C. Metaheuristic hybrids. In: Handbook of Metaheuristics. Gendreau M., Potvin J.Y. (Eds.). International Series in Operations Research & Management Science. 2019. Vol. 272. P. 385–417.

  • 36. Tezel B.T., Mert A. A cooperative system for metaheuristic algorithms. Expert Systems with Applications. 2021. Vol. 165, 113976. https://doi.org/10.1016/j.eswa.2020.113976.

  • 37. Hulianytskyi L.F., Sirenko S.I. Hybrid metaheuristic combining ant colony optimization and H-method. Swarm intelligence. Proc. 7th International Conference ANTS 2010 (Brussels, Belgium, Sept. 8–10, 2010). M. Dorigo et. al. (Eds.). Lecture Notes in Computer Science. Berlin; Heidelberg: Springer-Verlag, 2010. Vol. 6234. P. 568–569. https://doi.org/10.1007/978-3-642-15461-4_64.

  • 38. Hulianytskyi L.F., Sirenko S.I. Cooperative model-based metaheuristics. Electronic Notes in Discrete Mathematics. 2010. Vol. 36. P. 33–40. https://doi.org/10.1016/j.endm.2010.05.005.

  • 39. Martín-Santamaría R., López-Ibáñez M., Stützle T., Colmenar J.M. On the automatic generation of metaheuristic algorithms for combinatorial optimization problems. European Journal of Operational Research. 2024. Vol. 318, Iss. 3. P. 740–751. https://doi.org/ 10.1016/j.ejor.2024.06.001.




Інформація редакції Аннотації статей Автори Архів
Журнал Тематичні Розділи Редакція Редакційна колегія Приклади документів Передплата Контакти
© 2025 Kibernetika.org. All rights reserved.