C&SA | Contents

Volume 61 >>> № 1 JANUARY — FEBRUARY 2025

-->

UDC 519.8

L.F. Hulianytskyi¹

¹ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

SEARCH DIVERSIFICATION IN ACO ALGORITHMS AND ITS APPLICATION

Abstract. This paper presents a novel approach to the development of diversified ant colony optimization (ACO) algorithms, which are among the most widely used methods in combinatorial optimization. The proposed diversification in ACO algorithms is based on considering multiple options for extending the current solution fragment by incorporating several vertices of the problem graph into the route instead of just one, as is typically done. The ability of ants to foresee multiple search steps ahead increases the likelihood of avoiding suboptimal solutions and finding more accurate ones. This approach is applied to create metaheuristic algorithms for solving various combinatorial optimization problems. The results of computational experiments on a series of applied combinatorial optimization problems across different classes demonstrate the successful modification of the known ACO algorithms.

Keywords: ccombinatorial optimization, Ant Colony Optimization, routing, traveling salesman problem, UAV, optimization of flight routes, computational experiment.

full text

REFERENCES

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. Hulianytskyi L.F. Search diversification in OMC algorithms. Abstracts of Int. Conf «Problems of Decision Making under Uncertainties (PDMU–2011)» (Sept. 19–23, 2011, Yalta, Ukraine). Kyiv, 2011. P.66–67.

10. Hulianytskyi L.F. Search diversification in ant colony optimization algorithms. Theory of optimal solutions. 2017. P. 47–57.

11. Hulianytskyi L.F., Mulesa O.Yu. Applied methods of combinatorial optimization [in Ukrainian]. Kyiv: Publishing and printing center "Kyiv University", 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. Hulianytskyi L.F., Rybalchenko O.V. Formalization of the problem of optimization of UAV group bases and routes. Cybernetics and computer technologies. 2021. Iss. 4. P. 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. Sergienko I.V. Mathematical models and methods for solving discrete optimization problems [in Russian]. Kyiv: Nauk. Dumka, 1998. 472 p.

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. Hulianytskyi L.F., Pavlenko A.I. Optimization of paths in a dynamic flight graph using a modified ant systems algorithm. Mathematical modeling in economics. 2018. N 2.P. 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. Hulianytskyi L.F., Rybalchenko O.V. Route optimization in mission planning of hybrid transport systems “Drone+Vehicle”. 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.