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.
Fulltext:
PDF file (1015 kB)
The content is published under the terms of the Creative Commons Attribution 4.0 International License