搜索
基于GPU的共享信息素矩阵多蚁群算法*(二号黑体，居中)XX1；XXX2；XXX1(四号仿宋居中)（1.吉林大学材料科学与工程学院，长春130022；2.上海交通大学机械工程学院上海200030）（五号宋体）摘要：（小五黑体）在研究并行蚁群信息素交流方法的基础上，提出了一种适于GPU统一计算架构模型的多蚁群算法。采用多个同构和异构蚁群共享同一信息素矩阵的交流策略，解决信息素多样性和算法性能之间的矛盾。（小五宋体）关键词：（小五黑体）蚁群优化共享信息素矩阵并行计算图形处理器统一计算架构（小五宋体）中图分类号：（小五黑体）TP311;TP18（小五宋体）MultiantcoloniessharingcommonpheromonematrixbasedonGPU（四号，加粗，居中）XX1；XXX2；XXX1（小四号）(1.CollegeofmaterialsScienceandEngineering,JilinUniversity,Changchun130022,China2.SchoolofMechanicalEngineering,ShanghaiJiaotongUniversity,Shanghai200030,China)Abstract：（小五黑体）AnewparallelalgorithmofmultiantcoloniesonCUDAcomputationmodelofGPUisproposedinthispaper,afterinvestigatingtheexchangemethodofotherparallelapproaches.Severalintegrateddifferentkindofantcoloniessharecommonpheromonematrixduringtheprocessofsolutionconstructionandpheromonetrailupdatesteps.（小五）Keywords：（小五黑体）AntcolonyoptimizationSharingcommonpheromonematrixParallelcomputingGraphicsprocessingunitComputeunifieddevicearchitecture（小五）0前言（四号，宋体）蚁群优化(AntColonyOptimization，ACO)算法具有结构简单和适合分布式计算、易于与其他算法结合、鲁棒性强等优点，在科研和实际应用中得到了广泛的关注[1-2]。但ACO存在如下两个主要问题：其一，ACO的路径构建步骤本质上是综合启发式和信息素的随机概率选择，参数敏感，易陷入局部最优，难以稳定地获得高质量解；其二，随着待解问题规模的增大，算法性能下降也较为严重。这两个缺欠又是相互制约的，简单地增大信息素蒸发速率可提高算法的收敛速度，却易带来早熟的问题。ACO的生态属性及设计思想决定了ACO的并行化是避免早熟收敛、提升效率的自然方向。并行策略可粗略地分为精细并行策略和粗糙并行策略两种。诸多文献和实验表明，庞大的通信开销是精细并行策略的主要瓶颈。对于更广泛采用的粗糙并行策略，多个蚁群并行地工作在不同的处理器中，各自拥有独立的信息素矩阵，子蚁群间交换信息，各算法的区别在于信息交换的时机和内容不同[3-5]，一种极端情况是完全不交换，独立运行，Stutzle等的计算结果也体现了该策略的高效性[6]。共享信息素矩阵是交换的另一种形式，吕强等[7]基于PThread提出了一种使用该策略的方法，以TSP问题进行测试，获得了性能的提升。尽管已经实现了一些ACO并行算法，但不同的交换策略会产生什么样的行为，以及相对于顺序版本算法的性能将得到何种程度的改进仍然是两个有待解决的问题。（五号宋体）基金项目：国家自然科学基金重大项目基金(60496320,60496321)。（六号宋体，此段为角注，和正文分开）1GMACs算法（四号宋体）1.1混合策略（五号黑体）信息素矩阵是ACO的核心数据结构，是影响蚂蚁搜索方向的关键因素之一，几乎所有并行ACO的出发点皆是从构建和更新信息素的角度去影响整个算法的行为。多个蚁群可以拥有各自独立的信息素矩阵或共享同一个，前者是在恰当的时机选择其它蚁群的解路径对自身的状态进行优化，是一种显式的信息交流方式；而后者则是把多蚁群的进化结果反映到一个结构中，是隐式的。本文所研究的是一种共享信息素矩阵的方法。（五号宋体）（用公式编辑器输入此公式），其中是一个常数或与问题规模有关的参数，bsC是至今最优路径长度，上下界在算法执行过程中动态更新。差异化的目的；而ACS则刚好相反，以最小值为初值，不经常访问的边在临近最小值上徘徊，最优路径上的信息素则不断上升。不同的机制导致了混合的困难，吕强等[7]采取了取交集的方法，并用统一的公式进行全局和局部信息素更新。（五号宋体）为预先给定的常数参数，为迭代次数。该区间随着至今最优路径的变化而动态更新，信息素初值为：（用公式编辑器输入此公式）如此，我们继承了MMAS上下界限制的同时也符合ACS对信息素的约束。与标准MMAS的下界不同，本文的下界融入了迭代次数，使得下界随迭代次数增大而缓慢趋近于0。（五号宋体）1.2算法流程（五号黑体）充分发挥大量处理器或处理器核心的效能是当今高性能计算发展中的关键问题。尽管GPU有比CPU高得多的浮点峰值计算能力和存储器带宽，但要获得算法的高性能也并非易事。主要困难有:(1)GPU的绝大多数晶体管被计算单元所占据，其计算能力强大而流程控制能力薄弱；(2)GPU只能作为CPU的协处理器，由此带来CPU和GPU之间的额外通信开销；(3)GPU的体系结构决定了其存储器的非合并访问效率较低，易形成存储墙瓶颈。如图2所示，当在[6,9]区间内，经过较少的若干次发散后迅速收敛，我们选用等于蚁群个数。过大则导致算法长时间执行在路径探索阶段，同样，标准MMAS在较多的迭代次数后才进入收敛状态。若干其它TSP问题的测试也反应了同样的效果。（五号宋体）（用公式编辑器输入此公式和）01020304050600100300500700900NumberofiterationsAverageλ-branchingfactorGMACs(ξ=8)GMACs(ξ=12)GMACs(ξ=16)GMACs(ξ=4)MMASGMACs(ξ=10)GMACs(ξ=6)图2分支因子平均值变化曲线(eil51)Fig.2Behaviorsofaverage-branchingfactors(eil51)1.3并行ACO的横向比较（五号黑体）表2中给出了GMACs与文献[5]的多种并行蚁群的比较结果，算法运行次数，迭代次数2000。解的均值和标准差的比较皆显示GMACs有一定的优势。特别说明的是，本文致力于ACO本身机制的探讨和改进，而不是以改善求解能力为唯一目标，ACO与其它方法如遗传算法或局部搜索相结合在某些问题上能够获得更好的结果。表2GMACs与PACS和M-ACS实验比较Table2ComparisonamongGMACs,PASandM-ACS(绘制此表格)4结论与讨论（四号，宋体）本文在研究并行蚁群信息素交流方法的基础上，提出了一种新的多蚁群交流策略。以最大最小蚂蚁系统MMAS和蚁群系统ACS混合为例，给出了信息素初始化和动态界限的新方法，进而给出了基于GPU的共享信息素矩阵多蚁群算法，证明了其是值收敛和解收敛的。在标准TSP问题实例下的实验评测表明，该算法不仅提升了性能，在充分收敛条件下获得了更高质量的解。（五号宋体）参考文献（五号黑体）1.李静,刘学,赵健.基于蚁群寻优的汽车牵引力PID控制参数整定[J].吉林大学学报:工学版,2008,38(4):769-772.LiJing,LiuXue,ZhaoJian.RegulationofPIDcontrollerparametersbasedonantcolonyoptimizationalgorithminvehicletractioncontrolsystem[J].JournalofJilinUniversity(EngineeringandTechnologyEdition),2008,38(4):769-772.2.陈谋,肖健,姜长生.基于改进蚁群算法的无人机三维航路规划[J].吉林大学学报:工学版,2008,38(4):991-995.3.ChenMou,XiaoJian,JiangChang-sheng.ThreedimensionalpathplanningofUAVwithimprovedantalgorithm[J].JournalofJilinUniversity(EngineeringandTechnologyEdition),2008,38(4):991-995.4.TsaiCheng-Fa,TsaiChun-Wei,TsengChing-Chang.Anewhybridheuristicapproachforsolvinglargetravelingsalesmanproblem[J].InformationSciences,2004,166(1-4):67-81.（从0前言至文章末尾，分二栏排版，栏宽：22.07字符，栏间距2.02字符）吉林大学学报（工学版）第34卷第2期（页眉）期注：页面设置：上边距、下边距为：2.15cm，左边距、右边距为：1.95cm；页眉为：1.35cm，页脚：1.27cm；