Yu.P. Titov1

1 FIC «Informatics and Management» RAS (Moscow, Russia)
1 Moscow Aviation Institute (Moscow, Russia)
1 kalengul@mail.ru

This study investigates modifications of the Ant Colony Optimization (ACO) method when applied to parameter optimization tasks, particularly focusing on computational efficiency under varying hardware configurations. Traditional ACO algorithms are primarily designed for combinatorial problems like the Travelling Salesman Problem (TSP), but their application to parameter optimization introduces additional challenges due to the computationally intensive nature of analytical or simulation models used to evaluate target functions. To address these issues, this research explores sequential and parallel implementations of ACO tailored to different hardware setups – from single CPUs to GPUs and distributed systems.

Several parallelization strategies have been studied, including coarse-grained approaches where entire populations of ants run concurrently across separate threads or processors, and fine-grained methods that parallelize individual actions within each agent. Additionally, novel techniques such as matrix representations of pheromone trails, hash tables for intermediate storage, and specialized graph structures optimized for Single Instruction Multiple Data (SIMD) instructions were implemented to enhance scalability and reduce computational overhead.

The paper presents experimental results from simulations conducted on diverse hardware platforms ranging from personal computers and laptops equipped with modern multi-core CPUs and GPUs to high-performance servers and supercomputers. These experiments demonstrate significant improvements in execution times compared to traditional sequential implementations, especially for large-scale problems involving numerous parameters. Furthermore, it highlights how optimal configurations depend heavily on specific characteristics of both the problem domain and available hardware resources.

In conclusion, the proposed methodology provides valuable insights into designing efficient ACO-based solutions for real-world parameter optimization scenarios, offering practical guidance for selecting appropriate hardware architectures and implementation strategies. This is expected to facilitate more widespread adoption of ACO techniques in various scientific and engineering applications requiring robust optimization capabilities.

Titov Yu.P. Study of modifications of the ant colony method in solving parametric problems taking into account the search time for the values of the objective function. Highly Available Systems. 2025. V. 21. № 3. P. 46−57. DOI: https://doi.org/10.18127/ j20729472-202503-04 (in Russian)

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. P. 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. P. 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. P. 826–834.
5. Blum C., Dorigo M.  Hyper-heuristics based on ant colony optimization and tabu search for the multiple knapsack problem. In Procee­dings 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. P. 109–123.
9. Stützle T., Hoos H.H. MAX-MIN Ant System. Future Generation Computer Systems. 2000. V. 16. № 8. P. 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. P. 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. In: 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. Sinicyn I.N., Titov YU.P. Issledovanie algoritmov ciklicheskogo poiska dopolnitel'nyh reshenij pri optimizacii poryadka sledovaniya giperparametrov metodom murav'inyh kolonij. Sistemy vysokoj dostupnosti. 2023. T. 19. № 1. S. 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