A GPU-based Parallel Ant Colony Optimization Algorithm With Grouped Roulette Wheel Selection

Ant Colony Optimization(ACO)is a population-based computing method presented by Dorigo and Stiutzle to deal with complex problems.It has been used for complex optimization problems.But in the face of large scale problems,the run time of ACO algorithm is still long.The parallelization acceleration for ACO algorithms is one of the effective methods to solve the problem by using parallelism of individual behavior of ants.Among different kinds of parallelization acceleration approaches,the GPU-based approach is one of the most promising because of its high performance of price ratio and low power-consuming.In addition,GPUs are available on common PC platforms.GPU evolved from fixed pipeline for graphics rendering to a highly parallel and many-core device for general purpose computing that works as a Single Instruction Multiple Data(SIMD)manner.Since modern GPU devoted more transistors to data processing than to data caching and flow control,GPU architecture is more suitable for computing-intensive and highly parallel computation than CPU architecture.Although typical programming frameworks for GPU such as Common Unified Device Architecture(CUDA)are availabley how to develop a specialized algorithm on GPU is always a challenging work.In this paper,we propose an optimized parallel MMAS algorithm on GPUs based on Grouped Roulette Wheel Selection(G-Roulette),which enhances the parallel computation of fitness-proportionate selection.And we also modify the existing MMAS with the dynamical evaporation factor in the pheromone update stage.We evaluate the performance of proposed algorithms with the standard Traveling Salesman Problem(TSP).We obtain a good speedup factor compared to the CPU sequential version.We also compare our algorithm with two state-of-the-art GPU-based ACO algorithms in literature,and the results demonstrate our approach is effective.