A parallel Ant Colony Optimization algorithm with GPU-acceleration based on All-In-Roulette selection

Abstract

Ant Colony Optimization is computationally expensive when it comes to complex problems. The Jacket toolbox allows implementation of MATLAB programs in Graphics Processing Unit (GPU). This paper presents and implements a parallel MAX-MIN Ant System (MMAS) based on a GPU+CPU hardware platform under the MATLAB environment with Jacket toolbox to solve Traveling Salesman Problem (TSP). The key idea is to let all ants share only one pseudorandom number matrix, one pheromone matrix, one taboo matrix, and one probability matrix. We also use a new selection approach based on those matrices, named AIR (All-In-Roulette). The main contribution of this paper is the description of how to design parallel MMAS based on those ideas and the comparison to the relevant sequential version. The computational results show that our parallel algorithm is much more efficient than the sequential version.