Improving Ant Colony Optimization performance on the GPU using CUDA.

Dawson, L.; Stewart, I.A.

Abstract

We solve the Travelling Salesman Problem (TSP) using a parallel implementation of the Ant System (AS) algorithm for execution on the Graphics Processing Unit (GPU) using NVIDIA CUDA. Extending some recent research, we implement both the tour construction and pheromone update stages of Ant Colony Optimization (ACO) on the GPU using a data parallel approach. In this recent work, roulette wheel selection is used during the tour construction phase; however, we propose a new parallel implementation of roulette wheel selection called Double-Spin Roulette (DS-Roulette) which significantly reduces the running time of tour construction. We also develop a new implementation of the pheromone update stage. Our results show that compared to its sequential counterpart our new parallel implementation executes up to 82× faster whilst preserving the quality of the tours constructed, and up to 8.5× faster than the best existing parallel GPU implementation.

Citation

Dawson, L., & Stewart, I. (2013). Improving Ant Colony Optimization performance on the GPU using CUDA. In 2013 IEEE Congress on Evolutionary Computation (CEC 2013): Proceedings of a meeting held 20-23 June 2013, Cancun, Mexico (1901-1908). https://doi.org/10.1109/cec.2013.6557791

• Conference Name: 2013 IEEE Congress on Evolutionary Computation
• Conference Location: Cancun, Mexico
• Online Publication Date: Jul 15, 2013
• Publication Date: 2013
• Deposit Date: Jun 27, 2013
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 1901-1908
• Book Title: 2013 IEEE Congress on Evolutionary Computation (CEC 2013): Proceedings of a meeting held 20-23 June 2013, Cancun, Mexico
• ISBN: 9781479904532
• DOI: https://doi.org/10.1109/cec.2013.6557791