Presentations

Research of Parallel Implementations of the Metaheuristic Ant Colony Optimization for Solving Parametric Problems

Titov Yu.P.

Moscow Aviation Institute (National Research University) Russia, 125993, Moscow, Volokolamskoe shosse, 4 E-mail:kalengul@mail.ru

This work is devoted to the research and development of matrix modifications of the ant colony optimization (ACO) method for the efficient solution of parametric problems on heterogeneous computing systems [1]. The work addresses a discrete optimization problem under conditions where the evaluation of the objective function acts as a "black box" and constitutes the primary computational cost. The foundation for solving this problem with ACO modifications lies in formalizing the parametric problem as a matrix of values and corresponding matrices of pheromones and visits. The developed algorithm is divided into three independent stages: matrix preparation and normalization, path search by a population of K ant agents, and pheromone weight update (evaporation and addition). Each stage can be executed in parallel—on either a CPU or a GPU.

To efficiently use AVX SIMD instructions, two approaches were proposed: working with transposed matrices, where inner loops iterate over the number of graph layers, and using a specialized parametric graph with 4 vertices per layer. Experiments on Intel 12th-13th generation and AMD Ryzen processors showed that the matrix modification with AVX and OpenMP provides a speedup of up to 13 times compared to classical ACO (e.g., the time per layer decreased from 143.52 ms ± 17.26 to 11.55 ms ± 2.30 on an Intel Core i5-12450H for parametric problems of varying dimensionality). Implementation on GPUs using CUDA on a server with an NVIDIA Tesla V100, the MatrixACO_Optimal modification executes one iteration per layer in 1.58 ms ± 0.08, which is 32.7 times faster than the base algorithm [1]. A heterogeneous modification was also developed, where matrix processing stages are executed on the CPU with AVX, while path searching is performed on the GPU, this resulted in a time of 5.78 ms ± 1.64 per layer, corresponding to a 24.8-fold speedup.

The proposed ACOCNI and ACOCCyN modifications, which utilize hash tables to eliminate repeated calculations of the objective function, were successfully applied to a practical task—optimizing the parameters of a SARIMA model for forecasting passenger and cargo air transportation, demonstrating high efficiency and scalability of the matrix modifications [2].

References

1. Sudakov V., Titov Y. Matrix-Based ACO for Solving Parametric Problems Using Heterogeneous Reconfigurable Computers and SIMD Accelerators // Mathematics. – 2025. – N13. – V1284. DOI:10.3390/math13081284

2. Titov Yu.P., Sinitsyn I.N. Control of Set of System Parameter Values by the Ant Colony Method // Automation and Remote Control – 2023. – Vol. 84, No. 8. – P. 893-903. DOI:10.1134/S0005117923080106.

• abstract in English (PDF)