Ant Colony Optimisation (ACO) is an effective population-based meta-heuristic for the solution of a wide variety of problems. As a population-based algorithm, its computation is intrinsically massively parallel, and it is therefore theoretically well-suited for implementation on Graphics Processing Units (GPUs). The ACO algorithm comprises two main stages: textit Tour construction and textit Pheromone update . The former has been previously implemented on the GPU, using a task-based parallelism approach. However, up until now, the latter has always been implemented on the CPU. In this paper, we discuss several parallelisation strategies for it both stages of the ACO algorithm on the GPU. We propose an alternative it data-based parallelism scheme for textit Tour construction , which fits better on the GPU architecture. We also describe novel GPU programming strategies for the textit Pheromone update stage. Our results show a total speed-up exceeding 28x for the textit Tour construction stage, and 20x for textit Pheromone update , and suggest that ACO is a potentially fruitful area for future research in the GPU domain.
@cite_15: 
@cite_21: An algorithm of fine-grained parallel ant colony optimization algorithm(ACO) based on graphics process unit(GPU) accelerated is proposed to improve the performance of ACO for application to large-scale TSP problems.The process of parallel ACO is convert into that of parallel compute unified device architecture(CUDA) thread blocks,which makes PACO speed up.The experimental results show that the algorithm improves the ability of global search,increases the ant population in the PACO,speeds up its running and provides ordinary user with a feasible PACO solution.
@cite_7: Ant colony algorithm is an efficient intelligent algorithm to solve NP hard problem. This paper presents a parallel computing solution based on General Purpose GPU (GPGPU) to solve Traveling Salesman Problem (TSP) with Max-Min Ant System (MMAS). The experimental result shows it is more efficient than pure CPU computing.
@cite_16: Ant Colony Optimization (ACO) is a new population oriented search metaphor that has been successfully applied to NP-hard combinatorial optimization problems. In this paper we discuss parallelization strategies for Ant Colony Optimization algorithms. We empirically test the most simple strategy, that of executing parallel independent runs of an algorithm. The empirical tests are performed applying MAX-MIN Ant System, one of the most efficient ACO algorithms, to the Traveling Salesman Problem and show that using parallel independent runs is very effective.
In terms of GPU-specific designs for the ACO algorithm, Jiening @cite_7 propose an implementation of the Max-Min Ant System (one of many ACO variants) for the TSP, using C++ and NVIDIA Cg. They focus their attention on the tour construction stage, and compute the shortest path in the CPU. In @cite_15 You discusses a CUDA implementation of the Ant System for the TSP. The tour construction stage is identified as a CUDA kernel, being launched by as many threads as there are artificial ants in the simulation. The tabu list of each ant is stored in shared memory, and the pheromone and distances matrices are stored in texture memory. The pheromone update stage is calculated on the CPU. You reports a 20x speed-up factor for benchmark instances up to 800 cities. Li @cite_21 propose a method based on a fine-grained model for GPU-acceleration, which maps a parallel ACO algorithm to the GPU through CUDA. Ants are assigned to single processors, and they are connected by a population-structure @cite_16 .