Candidate set parallelization strategies for Ant Colony Optimization on the GPU

Dawson, L.; Stewart, I.A.

Abstract

For solving large instances of the Travelling Salesman Problem (TSP), the use of a candidate set (or candidate list) is essential to limit the search space and reduce the overall execution time when using heuristic search methods such as Ant Colony Optimisation (ACO). Recent contributions have implemented ACO in parallel on the Graphics Processing Unit (GPU) using NVIDIA CUDA but struggle to maintain speedups against sequential implementations using candidate sets. In this paper we present three candidate set parallelization strategies for solving the TSP using ACO on the GPU. Extending our past contribution, we implement both the tour construction and pheromone update stages of ACO using a data parallel approach. The results show that against their sequential counterparts, our parallel implementations achieve speedups of up to 18x whilst preserving tour quality.

Citation

Dawson, L., & Stewart, I. (2013, December). Candidate set parallelization strategies for Ant Colony Optimization on the GPU. Presented at 13th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP'13, Vietri sul Mare

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 13th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP'13
• Publication Date: 2013
• Deposit Date: Jan 27, 2014
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Volume: 8285
• Pages: 216-225
• Series Title: Lecture Notes in Computer Science
• Book Title: 13th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP'13: Vietri sul Mare, Italy, December 18-20, 2013, Proceedings, Part I
• ISBN: 9783319038582
• DOI: https://doi.org/10.1007/978-3-319-03859-9_18
• Public URL: https://durham-repository.worktribe.com/output/1155230