Accelerating ant colony optimisation for the travelling salesman problem on the GPU

Abstract

Recent graphics processing units (GPUs) can be used for general purpose parallel computation. Ant colony optimisation (ACO) approaches have been introduced as nature-inspired heuristics to find good solutions of the travelling salesman problem (TSP). In ACO approaches, a number of ants traverse the cities of the TSP to find better solutions of the TSP. The ants randomly select next visiting cities based on the probabilities determined by total amounts of their pheromone spread on routes. The main contribution of this paper is to present sophisticated and efficient implementation of one of the ACO approaches on the GPU. In our implementation, we have considered many programming issues of the GPU architecture including coalesced access of global memory and shared memory bank conflicts. In particular, we present a very efficient method for random selection of next cities by a number of ants. Our new method uses iterative random trial which can find next cities in few computational costs with high probability. This idea can be applied in not only GPU implementation but also CPU implementation. The experimental results on NVIDIA GeForce GTX 580 show that our implementation for 1002 cities runs in 8.71 s, while the CPU implementation runs in 190.05 s. Thus, our GPU implementation attains a speed-up factor of 22.11.

Keywords::

• ant colony optimisation
• travelling salesman problem
• GPU
• CUDA
• parallel processing