蚁群算法综述

《智能计算—蚁群算法基本综述》班级：研1102班专业：计算数学姓名：刘鑫学号：11070100362012年蚁群算法基本综述刘鑫（西安理工大学理学院，研1102班，西安市，710054）摘要:蚁群算法(ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。关键词:蚁群；算法；优化；改进；应用0引言专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。1蚁群算法概述ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。1.1蚁群算法的基本原理为便于研究提出以下基本假设：蚂蚁间通过信息素和环境进行间接通信：蚂蚁对环境的反应由其内部模决定：蚂蚁个体是独立的，但群体却呈现出一种随机性。蚂蚁通过适应和协作两个阶段的调整从无序到有序，得到最优解，完成对路径的搜索。对路径的选择，重点在转移概率，即某时刻蚂k在城市i选择城市i的概率的大小。)()()()()(),(]}),([]),(max{[arg)(0kallowedsisisijijkkijallowedjttttalloweduqqururtPk（1）其中，0q和q分别为]1,0[上的参数和均匀分布的随机数，其大小决定了利用先验知识与探索新路径之间的相对重要性。若0qq，则转移概率选取上面一个式子，即按照先验知识选择最好的边，否则，按照转移概率选择一条边，式1又被称为伪随机比例规则；kallowedj为蚂蚁k下一步允许选择的城市；)(tis为能见度因子；u为禁忌表；，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性；)(为信息素浓度的函数根据不同的模型，信息素做不同的调整，如全局更新规则和局部更新规则。2蚁群算法的发展蚁群优化（ACO）研究受到真实蚁群行为启发的智能系统，常用于解决离散优化问题启发式ACO是1991年由Dorigo和Gambardella提出定义的。2.1国外蚁群算法的发展概况2.1.1有关蚁群算法的研究团队从ACO提出至今,越来越多的专家投身于蚁群算法的研究之中,其中较为突出的有以下四个：（1）瑞士卢加诺IDSIA。1998年建立是IDSIA是非营利性研究人工智能研究所，2000年成为公共研究机构，隶属于卢加诺大学的信息学院和瑞士意大利语区高等专业学院的科技创新系，主要负责人为Luca,Lepori,Carlo和Schmidhuber。其中一研究主题是人工蚂蚁，该多代理方法是受基于信息素交流的生物蚂蚁启发而来，由前高级研究员Dorigo和联合负责人Luca领导研究的。其人工蚁和局部搜索算法的结合已经成为解决某些图形优化任务的方法选择，如车辆路径和网络路径，其迅速发展促成许多商业应用和关于人工蚂蚁的专门会议。（2）比利时布鲁塞尔IRIDIA。IRIDIA是布鲁塞尔自由大学人工智能研究实验室，主要在理论上进行深入研究以及计算智能应用于优化。在Dorigo和Bersini领导下，其主要研究领域为群智能、组合问题的求解和连续空间优化问题的启发式、生物网络原理性研究以及商业智能应用四个方面，而有关于ACA的方向为群智能和元启发式。IRIDIA在群智能的ACO和群机器人这两方面处于世界领先地位，对于具体元启发式的研究聚焦于ACO，主要研究点是研发一套合理的实验方法论，一套经验学习和元启发式构建的发展工具的应用，特别着重研究的是发展能够设计和完善随机局部搜索算法和元启发式算法的方法论。近期研究ACA项目有：对ACA的基础理论研究、复杂系统的智能计算方法、使用生物启发和软件计算的医学成像、自组织的蚁群、走向型机器人群和群智能系统的通信策略。（3）)奥地利维也纳大学经济与统计商学院由Richard和Artner等组成的团队，主要研究遗传算法、项目管理、最优控制、ACO和电子装配等研究课题其中，关于ACO方面的工作由Richard和Karl负责，从1999年开始至今。(4)德国莱比锡大学并行计算与复杂系统Martin领导的数学与计算机科学学院计算机科学研究所的并行计算与复杂系统团队，关于ACA的主要研究是由人类前沿科学组织自主计划的自然系统优化，以及东风集团项目中的一些关于系统、模型和硬件算法等。2.1.2有关蚁群算法的国际会议随着人们对ACA越来越重视，相关会议也组织起来，来自世界各地的专家对ACA及其应用展开研究讨论，其中以Dorigo为大会总主席的ANTS最为权威。1998年在比利时布鲁塞尔召开第一届ACA研讨会：从蚁群到人工蚁，每隔两年召开一次蚁群优化和群智能国际会议期间，2000年召开第二届ACA国际专会：从蚁群到人工蚁。另外，自2005年在美国加利福尼亚州帕萨迪纳威斯汀召开了IEEE群智能讨论会，2006年、2007年分别在美国印第安州印第安纳波利斯和美国夏威夷檀香山希尔顿村延续召开此会。除以上较为权威的会议，还有很多相关的国际会议，说明ACA在国际范围内得的重视，研究亦广泛展开。2.2国内蚁群算法的发展概况国内对该算法研究最早的是张纪会博士和徐心和教授1999年3月，他们首次简单引进ACA，从其基本原理、模型、伪码流程进行说明，对Oliver30TSP问题分析说明，但未对基本模型中的参数进行详细地理论说明，且停止条件的界定较含糊，主要靠经验决定其后引入的变异机制加快了收敛速度，使得到较优解的周期缩短，并从计算机仿真层面上证明其有效性。2001年，陈烨引入遗传算法中用到的杂交算子来改善蚁群搜索速度慢、容易陷入局部最优。但随路程，的增长每次的代数显著增加，计算量较大。同年8月，郝晋等通过将转移概率设置为转移系数，结合扰动策略以防止漏选最优路径，能够节约计算时间，且能够很好的克服算法容易陷入局部最优的缺陷，计算精度也有提高但在关于倒指数的扰动因子和均匀分布的随机数的选择并未解决，仍以实验为主要获取手段而后李艳君等对自适应ACA进行了进一步研究，对信息素采取自适应更新，应用于连续空间优化问题的求解，并进行了证明。2002年，王颖等对自适应ACA作出了改进，获得了很好的结果。该ACA在进化代数减少的情况下，解的质量也得到了一定提高，在一定程度上实现了收敛速度与解的质量的平衡。但分析其复杂度可知，蚂蚁的数目与问题规模不相上下，蚂蚁数目增多会使收敛。速度过快，为防止该现象而将信息素挥发悉数设置得比一般情况低一个数量级，而相关系数仪、B、P等则由实验设定。当蚂蚁数量与问题规模相当时，实验次数与时间是不容忽视的一个问题ACA除在原理层面进行模型改进。在应用方面也有一定发展。如张宗永等将ACA作出改进，配合随机分布技术。应用到分析上海市整个内河航道和集装箱运输的过程中对内河航道进行规划，最终得出合理的分配方案并提出了满足最优分配的河道改造的建议。2003年，陈岐等令人工蚁模仿真实蚂蚁的感觉和知觉行为，设置合理绝对感觉阈值以克服蚂蚁在初始选择时容易失去解的多样性，改进选择策略以自适应的修改路径上的信息量，通过对不同规模和不对称TSP的仿真说明算法具有较好的收敛性和稳定性新I叶J的启发式搜索方法——智能ACA，通过取消外激素、自动凋整选择最优路径的比例，改变选择目标城市的依据和引入扰动，仿真结果说明在减少计算量的同时，可取得更好的搜索结果，但也指出通过实验确定相关的物理系数不利于算法的推广但该文仅针对TSP，对其他问题能否应用仍不明确。2004年，黄国锐等提出采用不同于传统基本ACA所采用的蚁周模型，它采用了更贴近于真实蚂蚁行为的蚁量模型。建立信息素扩散模型，使相距较近的蚂蚁之间能够更好地进行协作，文中仿真结果表明该算法的有效性然而文中虽在达到收敛所需进化代数上较基本ACA有了很大的改进。减少约4倍。但最短路径长度的减少并不明显，且参数的设定仍是以试验为手段，缺乏理论支撑。针对基本ACA容易陷入局部最优、收敛慢等缺陷，许多新模型陆续提出，如基于云模型的ACA、对信息素的限制、回归型的等，甚至还有不少研究者试图从新的角度重新审视并尝试性研究ACA，较为新颖的有从蚁群社会的“多态性”出发，试图以更贴近真实世界中蚂蚁行为来研究ACA，发现更适应较大规模的问题，以及将着眼于蚁群整体的研究，角度转换到关注蚂蚁个体的速度对算法的影响。为从根本上解决ACA不足，其收敛性的分析也在不断展开，如用动态分阶段的方式，而具体影响ACA的参数也越来越得到关注，如有相关讨论，但参数如何设定并未有理论依据，如何建立通用标准来对参数进行最优设置仍是难点在研究的应用范围方面也从一开始的离散域扩展到连续域，连续域中有关于收敛性的研究，以及新模型的设计也在进行着。全国各高校及研究机构也对该算法展开了研究，如徐锋、杜军平的《改进蚁群算法在旅游路线规划中的应用研究》等1999年从首次引入ACA至今，相关研究蓬勃发展，下图为相关的论文题名和关键字的论文数量增长表。国内对于ACA的研究也越来越深人，基于各类模型的ACA层出不穷，研究域也从散域扩展到连续域，同时ACA在不断与其他算法结合以克服本身的缺陷但国内的研究起步较晚，对于影响收敛性的、B等相关参数至今无法确定一套相关的理论来进行设置，只能通过反复试验来大致确定一个参数范围，且研究较多地停留在理论仿真，应用到实践中仍较少。而国外对于这些范围的研究已经较为成熟。2.3蚁群算法的改进型ACA的收敛速度和最优解的全局性是一对矛盾体，收敛速度过快，会导致早熟，陷入局部最优解，而当信息素更新不及时或算法计算量过大时，则导致收敛速度过慢而应用不现实，为克服这些问题。相应的改进的ACA不断提出。（1）带精英策略的蚁群系统(AS)。在带精英策略的AS中，为了使到目前为止所找出的最优解在下一个循环中对蚂蚁更有吸引力，在每次循环之后给予最优解额外的信息素量它信息素的更新为：ijijijijtt)()1(（2）其中，ij表示经蚂蚁引起路径),(ji上的信息素量的增加；是精英蚂蚁的个数；L为所找出的最优解的路径长度。这种算法收敛速度快，且计算耗时短，但如果过大，搜索会局限于极值周围，导致搜索的早熟收敛。(2)基于优化排序的蚂蚁系统。基于优化排序的AS针对带精英策略的AS的缺点，通过排序很好地抑制了早熟，尤其当初始状态各解的差异性不大时，效果显著，但其中，第只最优蚂蚁引起的路径),(ji上信息素量的增加1kijij（3）ij为只最优蚂蚁引起的路径),(ji)上信息素量的增加；ij由精英蚂蚁引起的路径),(ji上的信息素量的增加。(3)最大一最小蚂蚁系统（MMAS)。MMAS是由德国学者T．Stuetzle和H.Hoos提出的，其目的主要在于防止