Parallel Ant Colony Optimization on Graphics Processing Units

The purpose of this paper is to propose effective parallelization strategies for the Ant Colony Optimization (ACO) metaheuristic on Graphics Processing Units (GPUs). The Max–Min Ant System (MMAS) algorithm augmented with 3-opt local search is used as a framework for the implementation of the parallel ants and multiple ant colonies general parallelization approaches. The four resulting GPU algorithms are extensively evaluated and compared on both speedup and solution quality on a state-of-the-art Fermi GPU architecture. A rigorous effort is made to keep parallel algorithms true to the original MMAS applied to the Traveling Salesman Problem. We report speedups of up to 23.60 with solution quality similar to the original sequential implementation. With the intent of providing a parallelization framework for ACO on GPUs, a comparative experimental study highlights the performance impact of ACO parameters, GPU technical configuration, memory structures and parallelization granularity.

► We propose efficient parallelization strategies for Ant Colony Optimization on GPUs.
► Speedups of 19.47 for parallel ants MMAS and 12.48 for MMAS with 3-opt local search.
► Speedups of 23.60 for multiple ant colonies MMAS.
► Speedups obtained by keeping state-of-the-art solution quality of original MMAS.
► We provide an extensive comparative algorithmic, parametric and technical study.