A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP
IET Computers & Digital Techniques · 2023
DOI: 10.1049/2023/9915769 ↗Kurz gefasst
Fachartikel in der Zeitschrift IET Computers & Digital Techniques, 2023. Verfasst von Zhi Zeng und 4 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 38 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Department of Education of Guangdong Province, National Natural Science Foundation of China, Beibu Gulf University.
Abstract (Originalsprache)
In view of the known problems of parameter sensitivity, local optimum, and slow convergence in the ant colony optimization (ACO), we aim to improve the performance of the ACO. To solve the traveling salesman problem (TSP) quickly with accurate results, we propose a fully parallel ACO (FP‐ACO). Based on the max–min ant system (MMAS), we initiate a compensation mechanism for pheromone to constrain its value, guarantee the correctness of results and avoid a local optimum, and further enhance the convergence ability of ACO. Moreover, based on the compute unified device architecture (CUDA), the ACO is implemented as a kernel function on a graphics processing unit (GPU), which shortens the running time of massive iterations. Combined with the roulette wheel selection mechanism, FP‐ACO has powerful search capabilities and is committed to obtaining better solutions. The experimental results show that, compared with the effective strategies ACO (ESACO) that runs on CPU, the speed‐up ratio of the proposed algorithm reaches 35, and the running time is less than that of the max–min ant system‐roulette wheel method‐bitmask tabu (MMAS‐RWM‐BT) that runs on GPU. Furthermore, our algorithm outperforms the other two algorithms in the speed‐up ratio and less runtime, proving that the proposed FP‐ACO is more suitable for solving TSP.
Förderung
- Department of Education of Guangdong Province
- National Natural Science Foundation of China
- Beibu Gulf University
Zitieren
APA
Zeng, Z., Cai, Y., Chung, K. L., Lin, H., & Wu, J. (2023). A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP. IET Computers & Digital Techniques. https://doi.org/10.1049/2023/9915769
Vancouver
Zeng Z, Cai Y, Chung KL, Lin H, Wu J. A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP. IET Computers & Digital Techniques. 2023. doi:10.1049/2023/9915769
BibTeX
@article{Zeng2023,
author = {Zeng, Zhi and Cai, Yuxing and Chung, Kwok L. and Lin, Hui and Wu, Jinwei},
title = {A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSP},
journal = {IET Computers & Digital Techniques},
year = {2023},
doi = {10.1049/2023/9915769}
}
EUVIMED