Ю.П. Титов1

1 ФИЦ «Информатика и управление» РАН (Москва, Россия)
1 Московский авиационный институт (Москва, Россия)
1 kalengul@mail.ru

Постановка проблемы. Классический алгоритм ACO предназначен для решения комбинаторных задач, таких как задача коммивояжера (TSP), однако при применении к параметрическим задачам возникают дополнительные ограничения, связанные с временем расчета целевой функции. Это особенно актуально, когда используются сложные аналитические или имитационные модели, расчеты в которых занимают значительную долю общего времени выполнения алгоритма. Поэтому возникает потребность в разработке эффективных механизмов распределения вычислительных ресурсов и организации параллельных вычислений, минимизируя временные задержки и увеличивая общую производительность процесса оптимизации.

Цель. Разработка методологического подхода и программного обеспечения выбора оптимальной модификации метода муравьиных колоний и структуры вычислительного комплекса на основе различных подходов к организации последовательных и параллельных вычислений.

Результаты. Предложены и изучены подходы к реализации последовательного выполнения оптимизации и вычислении значений целевой функции, а также различных параллельных реализаций. Проведено исследование различных параллельных модификаций: на одном вычислителе в многопоточном режиме, на одном гетерогенном вычислителе и для распределенной системы различной топологии. Приведены исследования оценки эффективности применения различных модификаций метода муравьиных колоний на различном аппаратном обеспечении, персональных компьютеров и ноутбуках и специализированных вычислителей.

Практическая значимость. Предложенная методология легла в основу автоматизированной системы оптимизации, способной на основе имеющегося аппаратного обеспечения и вычисленных временных характеристик в процессе работы метода муравьиных колоний переконфигурировать оптимизационную систему.

Титов Ю.П. Исследование модификаций метода муравьиных колоний при решении параметрических задач с учетом времени поиска значений целевой функции // Системы высокой доступности. 2025. Т. 21. № 3. С. 46−57. DOI: https://doi.org/10.18127/ j20729472-202503-04

1. Colorni A., Dorigo M., Vittorio M. Distributed Optimization by Ant Colonies / Proceedings of the First European Conference on Artificial Life. 1991 V. 142. Paris, France. Р. 134–142.
2. Dorigo M., Gambardella L.M. Ant Colony System: a cooperative learning approach to the Traveling Salesman Problem // Evolutionary Computation, IEEE Transactions. 1997. V. 1.1. Р. 53–66.
3. Reimann M., Doerner K., Hartl H. An improved ant system algorithm for solving vehicle routing problems with time windows / In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). 2002.
4. Lee J.S., Kim Y.H., Ha I.Y. A hybrid genetic algorithm using quadratic assignment problem solver for task allocation in grid computing environments // Future Generation Computer Systems. 2007. V. 23. № 6. Р. 826–834.
5. Blum C., Dorigo M.  Hyper-heuristics based on ant colony optimization and tabu search for the multiple knapsack problem / In Proceedings of the International Workshop on Hybrid Metaheuristics (HM’03). 2003.
6. Dorigo M., Maniezzo V., Colorni A. Positive feedback as a search strategy // Technical Report 91-016. Politecnico di Milano, Italy. 1991.
7. Gambardella L. M., Dorigo M. Has-Q: An Ant Q-Learning Approach to Combinatorial Optimization Problems / In Proceedings of MICAI '95: Second Mexican International Conference on Artificial Intelligence. Mexico City, Mexico. 1995.
8. Bullnheimer B., Hartl R.F., Strauss C. Applying the Ant System to Routing Problems // Annals of Operations Research. 1998. V. 79. Р. 109–123.
9. Stützle T., Hoos H.H. MAX-MIN Ant System // Future Generation Computer Systems. 2000. V. 16. № 8. Р. 889–914. DOI:10.1016/S0167-739X(00)00043-1
10. Cordon García O., Fernández de Viana I., Herrera Triguero F. A New Algorithm Based on Ant Colony Optimization for Solving Traveling Salesman Problems Using Memory Mechanisms // Applied Soft Computing Journal. 2002. V. 2. Iss. 1. Р. 63–77.
11. Randall M., Lewis A. A Parallel Implementation of Ant Colony Optimization. // Journal of Parallel and Distributed Computing. 2002. V. 62. Iss. 9. P. 1421–1432.
12. Bai H., OuYang D., Li X., He L., Yu H. MAXMIN Ant System on GPU with CUDA / 2009 Fourth International Conference on Innovative Computing, Information and Control (ICICIC). IEEE. 2009. P. 801–804.
13. Chitty D. M. Applying ACO to Large Scale TSP Instances / In: UK Workshop on Computational Intelligence. Springer, 2017. P. 104–118.
14. Skinderowicz R. The GPU-based parallel Ant Colony System // Journal of Parallel and Distributed Computing 98. 2016. V. 98. P. 48–60. DOI:10.1016/j.jpdc.2016.04.014
15. Zhang D., You X., Liu S., Yang K. Multi-Colony Ant Colony Optimization Based on Generalized Jaccard Similarity Recommendation Strategy // IEEE Access. 2019. V. 7. P. 157303–157317. DOI:10.1109/ACCESS.2019.2949860
16. Skinderowicz R. Implementing a GPU-based parallel MAX-MIN Ant System // Future Generation Computer Systems. 2020. V. 106. P. 277–295. DOI:10.1016/j.future.2020.01.011
17. Huan Z.B., Fu G.T., Fa T.H., Dong D.Y., Bai P., Xiao C. High performance ant colony system based on GPU warp specialization with a static-dynamic balanced candidate set strategy // Future Generation Computer Systems. 2021. V. 125. P. 136–150. DOI:10.1016/j.future.2021.06.041
18. Sudakov V. Titov Y. Matrix-Based ACO for Solving Parametric Problems Using Heterogeneous Reconfigurable Computers and SIMD Accelerators // Mathematics. 2025. V. 13. № 1284. DOI:10.3390/math13081284
19. Синицын И.Н., Титов Ю.П. Исследование алгоритмов циклического поиска дополнительных решений при оптимизации порядка следования гиперпараметров методом муравьиных колоний // Системы высокой доступности. 2023. Т. 19. № 1. С. 59–73. DOI:10.18127/j20729472-202301-05
20. Sudakov V.A., Titov Y.P. Investigation of the Parametric Graph Model in the Ant Colony Method // Math. Models Comput. Simul. 2025. V. 17. P. 126–136. DOI:10.1134/S2070048224700996