Multiple ant colonies sharing common pheromone matrix based on CPU

作者：Bai Hong Tao; Ouyang Dan Tong^*; Li Xi Ming; He Li Li

来源：Journal of Jilin University (Engineering and Technology Edition), 2011, 41(6): 1678-1683.

• Ant colonies
• Ant-colony optimization
• Computation model
• Compute unified device architecture
• Compute unified device architectures
• Dual-core
• Graphics Processing Unit
• matrix
• Pheromone trails
• Solution quality

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.

• 出版日期2011