  The Ant Colony System (ACS) is, next to Ant Colony Optimization (ACO) and the
MAX-MIN Ant System (MMAS), one of the most efficient metaheuristic algorithms
inspired by the behavior of ants. In this article we present three novel
parallel versions of the ACS for the graphics processing units (GPUs). To the
best of our knowledge, this is the first such work on the ACS which shares many
key elements of the ACO and the MMAS, but differences in the process of
building solutions and updating the pheromone trails make obtaining an
efficient parallel version for the GPUs a difficult task. The proposed parallel
versions of the ACS differ mainly in their implementations of the pheromone
memory. The first two use the standard pheromone matrix, and the third uses a
novel selective pheromone memory. Computational experiments conducted on
several Travelling Salesman Problem (TSP) instances of sizes ranging from 198
to 2392 cities showed that the parallel ACS on Nvidia Kepler GK104 GPU (1536
CUDA cores) is able to obtain a speedup up to 24.29x vs the sequential ACS
running on a single core of Intel Xeon E5-2670 CPU. The parallel ACS with the
selective pheromone memory achieved speedups up to 16.85x, but in most cases
the obtained solutions were of significantly better quality than for the
sequential ACS.
