Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Iain Stewart

Dawson, L. & Stewart, I.A. (2013), Improving Ant Colony Optimization performance on the GPU using CUDA, 2013 IEEE Congress on Evolutionary Computation. Cancun, Mexico, IEEE, 1901-1908

Author(s) from Durham

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.