Ant colony optimization method for solving parametric problems on vector SIMT accelerators

Cover Page

Cite item

Full Text

Abstract

This study investigates the potential of parallel implementation of the Ant Colony Optimization (ACO) method on SIMT accelerators. Known modifications of the parallel ant colony method have demonstrated effectiveness in solving Traveling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP). However, the need for data synchronization and exchange limits performance, achieving maximum efficiency in coarse-grained algorithms where each thread executes a complete ACO version. With the development and increasing availability of SIMT accelerators, this study proposes a modification of the numerical ant colony optimization method based on matrix formalization of the computational process. The proposed approach extends the applicability of the method to parametric problems aimed at finding optimal parameter values that minimize or maximize the objective function. A parallel computing algorithm has been developed that minimizes information exchange between agents. The algorithm consists of three stages: preparation of matrices for ant-agent movement, determination of ant-agent paths, and updating matrices based on found solutions. Computational complexity reduction is achieved by representing the optimization problem as a parametric graph with decomposition of parameter value sets into sublayers. Among the studied modifications of the ant colony method, ACOCNI and ACOCCyI were considered with an improved probability formula for algorithmic efficiency and hash table application for enhanced exploration phase. The proposed modifications were implemented on GPUs using CUDA technology. Experimental results show more than 15-fold acceleration of the parallel ant colony method when searching for optima of multimodal functions. Future research directions include implementation of the proposed algorithm on heterogeneous computing systems combining SIMT and MIMD components.

About the authors

Vladimir A. Sudakov

Moscow Aviation Institute (National Research University); Keldysh Institute of Applied Mathematics of Russian Academy of Sciences

Author for correspondence.
Email: sudakov@ws-dss.com
ORCID iD: 0000-0002-1658-1941
SPIN-code: 1614-4760
Scopus Author ID: 7006296922
ResearcherId: I-2573-2018
https://www.mathnet.ru/rus/person112232

Dr. Techn. Sci., Associate Professor; Professor; Dept. of Computational Mathematics and Programming; Leading Researcher

Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4; 125047, Moscow, Miusskaya pl., 4

Yurii P. Titov

Moscow Aviation Institute (National Research University)

Email: kalengul@mail.ru
ORCID iD: 0000-0002-9093-6755
SPIN-code: 8866-5903
Scopus Author ID: 56549731400
ResearcherId: AAO-7748-2020
https://www.mathnet.ru/rus/person111602

Cand. Techn. Sci., Associate Professor; Associate Professor; Dept. of Computing Machines, Systems and Networks

Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4

References

  1. Karpenko A. P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi [Modern Search Optimization Algorithms. Nature-Inspired Algorithms]. Moscow, Bauman Moscow State Technical Univ., 2017, 446 pp. (In Russian)
  2. Simon D. Evolutionary Optimization Algorithms. Biologically Inspired and Population-Based Approaches to Computer Intelligence. Hoboken, NJ, John Wiley & Sons, 2013, xxx+742 pp.
  3. Colorni A., Dorigo M., Maniezzo V. Distributed optimization by ant colonies, In: Proc. of the 1st European Conference on Artificial Life (ECAL) (Paris, France, 1991); eds. F. Varela, P. Bourgine. Amsterdam, Elsevier, 1991, pp. 134–142.
  4. Dorigo M., Stützle T. Ant Colony Optimization. Cambridge, MA, MIT Press, 2004, xiv+305 pp.
  5. Uslu M. O., Erdoğdu K. Ant colony optimization and beam-ant colony optimization on traveling salesman problem with traffic congestion, Dokuz Eylül Univ. Fen Müh. Derg., 2024, vol. 26, no. 78, pp. 519–527. DOI: https://doi.org/10.21205/deufmd.2024267820.
  6. Sagban R. F., Ku-Mahamud K. R., Abu Bakar M. S. Reactive max-min ant system with recursive local search and its application to TSP and QAP, Intell. Autom. Soft Comput., 2017, vol. 23, no. 1, pp. 137–134. DOI: https://doi.org/10.1080/10798587.2016.1177914.
  7. Yukhimenko B. I., Titov N. A., Ushakov V. O. Development and research of ant colony algorithms for solving some combinatorial optimization problems, Aktual. Nauch. Issled. Sovrem. Mire, 2020, no. 11-2, pp. 101–115 (In Russian). EDN: BFJRTF.
  8. Črepinšek M., Liu S.-H., Mernik M. Exploration and exploitation in evolutionary algorithms: A Survey, ACM Comput. Surv., 2013, vol. 45, no. 3, pp. 1–33. DOI: https://doi.org/10.1145/2480741.2480752.
  9. Dorigo M., Birattari M. Swarm intelligence, Scholarpedia, 2007, vol. 2, no. 9, pp. 1462.
  10. Pellegrini P., Stützle T., Birattari M. A critical analysis of parameter adaptation in ant colony optimization, Swarm Intell., 2012, vol. 6, no. 1, pp. 23–48. EDN: FTMJFE. DOI: https://doi.org/10.1007/s11721-011-0061-0.
  11. Danesh M., Danesh S. Optimal design of adaptive neuro-fuzzy inference system using PSO and ant colony optimization for estimation of uncertain observed values, Soft Comput., 2024, vol. 28, no. 1, pp. 135–152. EDN: EENMCA. DOI: https://doi.org/10.1007/s00500-023-09194-6.
  12. Semenkina O. E., Semenkin E. S. On comparison of the efficiency of ant and genetic algorithms for solving combinatorial optimization problems, Aktual. Probl. Aviatsii Kosmonavt., 2011, vol. 1, no. 7, pp. 338–339 (In Russian). EDN: TAOYPR.
  13. Bullnheimer B., Kotsis G., Strauß C. Parallelization strategies for the ant system, In: High Performance Algorithms and Software in Nonlinear Optimization, Applied Optimization, 24. Boston, MA, Springer, 1998, pp. 87–100. DOI: https://doi.org/10.1007/978-1-4613-3279-4_6.
  14. Randall M., Lewis A. A parallel implementation of ant colony optimization, J. Parallel Distrib. Comput., 2002, vol. 62, no. 9, pp. 1421–1432. DOI: https://doi.org/10.1006/jpdc.2002.1854.
  15. Cecilia J. M., Nisbet A., Amos M., et al. Enhancing GPU parallelism in nature-inspired algorithms, J. Supercomput., 2013, vol. 63, no. 3, pp. 773–789. EDN: LUDHWA. DOI: https://doi.org/10.1007/s11227-012-0770-1.
  16. Bai H., OuYang D., Li X., et al. MAX-MIN ant system on GPU with CUDA, In: Innovative Computing, Information and Control (ICICIC) (Fourth International Conference, 2009). Kaohsiung, Taiwan, 2009, pp. 801–804. DOI: https://doi.org/10.1109/ICICIC.2009.255.
  17. Zhou Y., He F., Hou N., Qiu Y. Parallel ant colony optimization on multi-core SIMD CPUs, Future Gener. Comput. Syst., 2018, vol. 79, pp. 473–487. DOI: https://doi.org/10.1016/j.future.2017.09.073.
  18. Semenkina O. E., Popov E. Adaptive ant colony optimization algorithm for hierarchical scheduling problem, In: Proc. Intern. Conf. on Information Technologies. Varna, Bulgaria, 2019. EDN: SIXIXY. DOI: https://doi.org/10.1109/InfoTech.2019.8860897.
  19. Khakhulin G. F., Titov Yu. P. Decision support system for spare parts supply of military aircraft, Izv. Sam. Nauch. Tsentra RAN, 2014, vol. 16, no. 1–5, pp. 1619–1623 (In Russian). EDN: TJFAUB.
  20. Akbari S., Ramazi H., Ghezelbash R. A novel framework for optimizing the prediction of areas favorable to Porphyry-Cu mineralization: Combination of ant colony and grid search optimization algorithms with support vector machines, Nat. Resour. Res., 2025, vol. 34, no. 2, pp. 703–729. EDN: MGWCVY. DOI: https://doi.org/10.1007/s11053-024-10431-4.
  21. Sinitsyn I. N., Titov Yu. P. Investigation of cyclic search algorithms for additional solutions in hyperparameter sequence optimization using ant colony methods, Sist. Vys. Dostup., 2023, vol. 19, no. 1, pp. 59–73 (In Russian). EDN: GBHNJK. DOI: https://doi.org/10.18127/j20729472-202301-05.
  22. Sinitsyn I. N., Titov Yu. P. Control of set of system parameter values by the ant colony method, Autom. Remote Control, 2023, vol. 84, no. 8, pp. 893–903. EDN: MQLYDX. DOI: https://doi.org/10.1134/s0005117923080106.
  23. Sudakov V. A., Titov Yu. P. Investigation of the parametric graph model in the ant colony method, Mat. Model., 2024, vol. 36, no. 6, pp. 21–37. EDN: TLNAPZ. DOI: https://doi.org/10.20948/mm-2024-06-02.
  24. Mishra S. K. Some new test functions for global optimization and performance of repulsive particle swarm method, MPRA Paper no. 2718, 2006. https://mpra.ub.uni-muenchen.de/2718/. DOI: https://doi.org/10.2139/ssrn.926132.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Figure 1. Parametric graph structure

Download (119KB)
Indexing metadata
3. Figure 2. Graph information layer partitioning in the ant colony optimization method

Download (285KB)
Indexing metadata

Copyright (c) 2025 Authors; Samara State Technical University (Compilation, Design, and Layout)

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).