A GPU-based parallel MAX-MIN Ant System algorithm with grouped roulette wheel selection
Wei Hong Zhou, Fazhi He, Zhengcheng Zhang · 2017
This paper presents a GPU-accelerated parallel MAX-MIN Ant System (MMAS) algorithm based on an approach named grouped roulette wheel selection (G-Roulette). A data parallel model is adapted in the proposed approach with special consideration for GPU architecture. We propose a G-Roulette strategy to enhance the parallel computation of fitness-proportionate selection. The G-Roulette strategy includes two hierarchical stages to choose the optimal city. Consequently the running time is decreased by the G-Roulette strategy. We modify the MMAS with dynamical evaporation factor in the stage of pheromone updating. Experimental results show that G-Roulette enhanced MMAS algorithm is competitive with other state-of-art parallel ACO algorithms.