GPU-accelerated Ant Colony Optimization for the Traveling Salesman Problem

Abstract

The main contribution of this paper is to show a GPU implementation of ant colony optimization for the traveling salesman problem. In the ant colony optimization, many ants are deployed to cities and each ant independently visits cities one by one. The trace of an ant corresponds to one of the solution of the traveling salesman problem. The idea of the proposed GPU implementation is to adopt a hybrid technique, stochastic acceptance and tournament selection, stochastically to choose the next visiting cities. Also, to accelerate the computation, we have considered the characteristic of the GPU architecture, such as coalesced access of the global memory and the bank conflict of the shared memory, among others. We have implemented the proposed method on the NVIDIA GeForce GTX 1080. The experimental results show that our proposed GPU implementation for 1002 cities runs in 2065 milliseconds, while the sequential CPU implementation runs 98983 milliseconds. Thus, our GPU implementation attains a speed-up factor of 47.92.