摘要
在研究并行蚁群信息素交流方法的基础上,提出了一种适于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.
出处
《吉林大学学报(工学版)》
EI
CAS
CSCD
北大核心
2011年第6期1678-1683,共6页
Journal of Jilin University:Engineering and Technology Edition
基金
国家自然科学基金项目(60973089)
教育部博士学科点专项科研基金项目(20100061110031)
吉林省科技发展计划项目基金(20101501)
吉林省科技发展计划青年基金项目(201101039)
吉林大学符号计算与知识工程教育部重点实验室开放项目(93K-17-2009-K05)
吉林大学科学前沿与交叉学科创新项目(201103134)
关键词
计算机软件
蚁群优化
共享信息素矩阵
图形处理器
统一计算架构
computer software
ant colony optimization
sharing common pheromone matrix
graphics processing unit
compute unified device architecture