基于GPU的共享信息素矩阵多蚁群算法

Multiple ant colonies sharing common pheromone matrix based on CPU

在研究并行蚁群信息素交流方法的基础上,提出了一种适于GPU统一计算架构模型的多蚁群算法。采用多个同构和异构蚁群共享同一信息素矩阵的交流策略,解决信息素多样性和算法性能之间的矛盾。在路径探索阶段,多只获得迭代最优解且差异较大的蚂蚁共同释放信息素,以利群体多样性;在路径开发阶段,获得唯一全局最优解的蚂蚁释放信息素,以利迅速收敛。多蚁群映射到GPU的线程块而群内蚂蚁对应块内多线程。以MMAS和ACS混合为例给出了该策略下信息素初始化和动态界限的新方法,证明了算法是值收敛和解收敛的。在标准TSP问题实例上的实验评测表明,该算法不仅提升了性能,在充分收敛条件下获得了更高质量的解。

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.