科研论文排版

基于GPU的共享信息素矩阵多蚁群算法* (二号黑体，居中) X X1； XXX2； X X X1 (四号仿宋居中) （1. 吉林大学 材料科学与工程学院， 长春 130022；2. 上海交通大学 机械工程学院 上海 200030）（五号宋体）

摘要：（小五黑体）在研究并行蚁群信息素交流方法的基础上，提出了一种适于GPU统一计算架构模型的多蚁群算法。采用多个同构和异构蚁群共享同一信息素矩阵的交流策略，解决信息素多样性和算法性能之间的矛盾。（小五宋体） 关键词：（小五黑体）蚁群优化 共享信息素矩阵 并行计算 图形处理器 统一计算架构（小五宋体） 中图分类号：（小五黑体）TP311; TP18（小五宋体）

Multi ant colonies sharing common pheromone matrix based on GPU（四号，加粗，居中） X X1； XXX2； X X X1（小四号）

(1. College of materials Science and Engineering, Jilin University,Changchun 130022,China 2. School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200030, China)

Abstract：（小五黑体）A new parallel algorithm of multi ant colonies on CUDA computation model of GPU is proposed in this paper, after investigating the exchange method of other parallel approaches. Several integrated different kind of ant colonies share common pheromone matrix during the process of solution construction and pheromone trail update steps. （小五） Key words：（小五黑体）Ant colony optimization Sharing common pheromone matrix Parallel computing Graphics processing unit Compute unified device architecture （小五） 0 前言（四号，宋体）

蚁群优化(Ant Colony Optimization，ACO)算法具有结构简单和适合分布式计算、易于与其他算法结合、鲁棒性强等优点，在科研和实际应用中得到了广泛的关注[1-2]。但ACO存在如下两个主要问题：其一，ACO的路径构建步骤本质上是综合启发式和信息素的随机概率选择，参数敏感，易陷入局部最优，难以稳定地获得高质量解；其二，随着待解问题规模的增大，算法性能下降也较为严重。这两个缺欠又是相互制约的，简单地增大信息素蒸发速率可提高算法的收敛速度，却易带来早熟的问题。

ACO的生态属性及设计思想决定了ACO的并行化是避免早熟收敛、提升效率的自然方向。并行策略可粗略地分为精细并行策略和粗糙并行策略两种。诸多文献和实验表明，庞大的通信开销是精细并行策略的主要瓶颈。对于更广泛采用的粗糙并行策略，多个蚁群并行地工作在不同的处理器中，各自拥有独立的信息素矩阵，子蚁群间交换信息，各算法的区别在于信息交换的时机和内容不同[3-5]，一种极端情况是完全不交换，独立运行，Stutzle等的计算结果也体现了该策略的高效性[6]。共享信息素矩阵是交换的另一种形式，吕强等[7]基于PThread提出了一种使用该策略的方法，以TSP问题进行测试，获得了性能的提升。尽管已经实现了一些ACO并行算法，但不同的交换策略会产生什么样的行为，以及相对于顺序版本算法的性能将得到何种程度的改进仍然是两个有待解决的问题。（五号宋体）

基金项目：国家自然科学基金重大项目基金(60496320, 60496321)。（六号宋体，此段为角注，和正文分开） 1 GMACs算法（四号宋体） 1.1 混合策略（五号黑体）

信息素矩阵是ACO的核心数据结构，是影响蚂蚁搜索方向的关键因素之一，几乎所有并行ACO的出发点皆是从构建和更新信息素的角度去影响整个算法的行为。多个蚁群可以拥有各自独立的信息素矩阵或共享同一个，前者是在恰当的时机选择其它蚁群的解路径对自身的状态进行优化，是一种显式的信息交流方式；而后者则是把多蚁群的进化结果反映到一个结构中，是隐式的。本文所研究的是一种共享信息素矩阵的方法。（五号宋体）

第1页下一页