Abstract:

A parallel algorithm of multiple ant colonies on Compute Unified Device Architecture (CUDA) computation model of CPU is presented. Several integrated different kind of ant colonies share common pheromone matrix during the process of solution construction and pheromone trail update steps. Multiple ants, corresponding to those iteration-so-far-tours, update pheromone matrix to obtain the diversity throughout explorative search phase; and the one, corresponding to the best-so-far-tours, deposits pheromone to accelerate constringency from exploitation phase. Ant colonies are mapped to the thread blocks and ants within colony correspond to massively threads of CUDA. The mix of MMAS and ACS is implemented that a new initializing method and the max and min pheromone trail limits are used. Convergences both in value and solution are proved and experiments on TSPLIB demonstrate that this algorithm can get good average solution quality, and outperform the sequential MMAS, ACS and parallel algorithm with a dual-core CPU.

Key words: computer software, ant colony optimization, sharing common pheromone matrix, graphics processing unit, compute unified device architecture