基于GPU的共享信息素矩阵多蚁群算法*（二号黑体，居中）XX1;xxx2；xxx^H号仿宋居中）（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（ZJ、五）0前言（四号，宋体）蚁辟优化（AntColonyOptimization,ACO）算法M•有结构筋单和合分布式计算、鉍于与其他算法结合、鲁棒性强等优点，在科研和实际应用中得到了广泛的关注u_21。但ACO存在如卜‘两个主要问题：其-，ACO的路径构建步骤本质上足综合启发式和信息素的随机概率选择,参数敏感，易陷入局部最优，难以稳定地获得高质景解；M:二，随着待解M题规模的增人，算法性能下降也较为严重。这两个缺欠又是相互制约的，简单地增大信息素蒸发速率可提高算法的收敛速度，却易带来早熟的问题。AC◦的生态属性及设计思想决定了AC◦的并行化是避免早熟收敛、提升效率的A然方叫。并行策略可飢略地分为粘细并行策略和飢糙并行策略两种。诸多文献和实验表明，庞人的通倌开销是精细并行策略的主要瓶颈。对于更广泛采用的粗糙并行策略，多个蚁群并行地工作在不同的处理器中，各肖拥冇独立的信息素矩阵，子蚁群叫交换信息，各算法的区别在于信息交换的时机和内界不同|3_51，一种极端情况是完全不交换，独立运行，Stutzle等的计算结果也体现了该策略的高效性％。丼享信息素矩阵是交换的一种形式，□强等［7］基于PThread提!li了一种使用该策略的方法，以TSP问题进行测试，获得了性能的提升。尽管己经实现了一些ACO并行算法，似不同的交换策略会产生什么样的行为，以及相对于顺序版木算法的性能将得到何种程度的改进仍然足两个奋待解决的闷题。（五号宋体）基金项H:国家自然科学基金重大项㈠基金（60496320,60496321）。（六号宋体，此段为角注，和正文分开）1GMACs算法（四号宋体）1.1混合策略（五号黑体）倍息素矩阵足ACO的核心数裾结构，是影响蚂蚁搜索方向的关键因素之一，儿乎所有并行ACO的出发点皆是从构建和更新信息索的角度去影响整个算法的行为。多个蚁群可以拥冇各向独立的信息素矩阵或井享同一个，前者是在恰当的时机选择它蚁群的解路径对£1身的状态进行优化，是一•种显式的信息交流方式；而后者则是把多蚁群的进化结果反映到一个结构中，是隐式的。本文所研究的是一种共享信怠素矩阵的方法。（五号宋体）E［1!{paC\H{pC）］（用公式编辑器输入此公式），其中是一个常数或与问题规模冇关的参数，C&是至今最优路径长度，上卜界在算法执行过程中动态更新。差异化的目的；而ACS则刚好相反，以最小值为初值，不经常访问的边在临近最小值上徘徊，最优路径上的信息素则不断上升。不同的机制导致了混合的凼难，S强等7采取了取交集的方法，并用统一的公式进行全局和局部信息素更新。（五号宋体）3为预先给定的常数参数，0为迭代次数。该区叫随着至今最优路径的变化...