蚁群算法基本原理及其应用综述.doc

1、蚁群算法基本原理及其应用综述计算机应用技术专业【摘要】蚁群算法（ACA）是一种广泛应用于优化领域的仿生进化算法。从ACA 发展背景着手，分析比较国内外ACA 研究团队与发展情况，立足于基本原理，分析其数学模型，介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。【关键词】蚁群算法；优化；改进；应用一、 引言专家发现单个蚂蚁只具有一些简单的行为能力，但整个蚁群却能完成一系列复杂的任务，这种现象是通过高度组织协调完成的。1991 年，意大利学者MDorigo 首次提出一种新型仿生算法ACA，研究了蚂蚁的行为，提出其基本原理及数学模型，并将之应用于寻求旅行

2、商问题（TSP）的解。通过实验及相关理论证明，ACA 有着优化的选择机制的本质，而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点，如较强的鲁棒性、分布式计算、易与其他方法结合等； 但同时也不应忽略其不足，如搜索时间较长， 若每步进行信息素更新， 计算仿真时所占用CPU 时间过长；若当前最优路径不是全局最优路径，但其信息素浓度过高时，靠公式对信息素浓度的调整不能缓解这种现象，会陷入局部收敛， 无法寻找到全局最优解；转移概率过大时， 虽有较快的收敛速度，但会导致早熟收敛，所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA，对一些已有的提

3、出自己的想法，并对其应用及发展前景提出了展望。二、 蚁群算法概述ACA 源自于蚁群的觅食行为。SGoss 的“双桥”实验说明蚂蚁总会选择距食物源较短的分支。蚂蚁之间通过信息素进行信息的传递，捷径上的信息素越多，吸引的蚂蚁越多，形成正反馈机制， 达到一种协调化的高组织状态，该行为称集体自催化。目前研究的多为大规模征兵，即仅靠化学追踪的征兵。2.1 蚁群算法基本原理图 2.1在图2.1 中, 设A 为食物, D 为巢穴, 一群蚂蚁将在A 和D 之间来回运送食物。从A 出发到D 有两条路径,ABYCD 较短, ABXCD 较长。当蚂蚁从A 点走到B 点后,对于第一只蚂蚁来说, 选择向X 点或选择向Y

4、 点行走的概率是一样的, 而后面的蚂蚁则根据BYC 和BXC 这两条路径上前面蚂蚁所遗留信息素的浓度来决定取向( 若两条路径浓度相同, 则被选择的概率相等) , 由于路径BYC 比BXC 短, 因此路径BYC 的信息素浓度比路径BXC 增加得快, 这样就导致后面的蚂蚁选择路径BYC的概率高于选择路径BXC, 随着时间推移, 选择路径BYC( 或CYB) 的蚂蚁将越来越多, 最终所有的蚂蚁都会选择这条较短的路径行走。三、 蚁群算法的发展蚁群优化（ACO） 是研究受到真实蚁群行为启发的智能系统，常用于解决离散优化问题。启发式ACO 是1991 年由Dorigo 和Gambardella 提出定义的

5、。31 国外蚁群算法的发展概况311 有关蚁群算法的研究团队从ACO 提出至今， 越来越多的专家投身于蚁群算法的研究之中，其中较为突出的有以下四个：（1）瑞士卢加诺IDSIA。1988 年建立的IDSIA 是非营利性研究人工智能研究所，2000 年成为公共研究机构，隶属于卢加诺大学的信息学院和瑞士意大利语区高等专业学院的科技创新系，主要负责人为Luca，Lepori，Carlo 和Schmidhuber。其中一研究主题是人工蚂蚁，该多代理方法是受基于信息素交流的生物蚂蚁启发而来，由前高级研究员Dorigo 和联合负责人Luca 领导研究的。其人工蚁和局部搜索算法的结合已经成为解决某些图形优化任

6、务的方法选择，如车辆路径和网络路径，其迅速发展促成许多商业应用和关于人工蚂蚁的专门会议。（2）比利时布鲁塞尔IRIDIA。IRIDIA是布鲁塞尔自由大学人工智能研究实验室，主要在理论上进行深入研究以及计算智能应用于优化。在Dorigo 和Bersini 领导下，其主要研究领域为群智能、组合问题的求解和连续空间优化问题的启发式、生物网络原理性研究以及商业智能应用四个方面，而有关于ACA的方向为群智能和元启发式。IRIDIA 在群智能的ACO 和群机器人这两方面处于世界领先地位，对于具体元启发式的研究聚焦于ACO，主要研究点是研发一套合理的实验方法论，一套经验学习和元启发式构建的发展工具的应用，特

7、别着重研究的是发展能够设计和完善随机局部搜索算法和元启发式算法的方法论。近期研究ACA 项目有： 对ACA 的基础理论研究、复杂系统的智能计算方法、使用生物启发和软件计算的医学成像、自组织的蚁群、走向型机器人群和群智能系统的通信策略。（3）奥地利维也纳大学经济与统计商学院。由Richard 和Artner 等组成的团队，主要研究遗传算法、项目管理、最优控制、ACO 和电子装配等研究课题。其中， 关于ACO 方面的工作由Richard和Karl 负责，从1999 年开始至今。（4）德国莱比锡大学并行计算与复杂系统。Martin 领导的数学与计算机科学学院计算机科学研究所的并行计算与复杂系统团队，

8、 关于ACA 的主要研究是由人类前沿科学组织自主计划的自然系统优化，以及东风集团项目中的一些关于系统、模型和硬件算法等。312 有关蚁群算法的国际会议随着人们对ACA 越来越重视，相关会议也组织起来，来自世界各地的专家对ACA 及其应用展开研究讨论，其中以Dorigo 为大会总主席的ANTS 最为权威。1998年在比利时布鲁塞尔召开第一届ACA 研讨会：从蚁群到人工蚁，每隔两年召开一次蚁群优化和群智能国际会议。期间，2000 年召开第二届ACA国际专会： 从蚁群到人工蚁。另外，自2005 年在美国加利福尼亚州帕萨迪纳威斯汀召开了IEEE 群智能讨论会，2006 年、2007 年分别在美国印第安

9、州印第安纳波利斯和美国夏威夷檀香山希尔顿村延续召开此会。除以上较为权威的会议， 还有很多相关的国际会议，说明ACA 在国际范围内得到越来越多的重视，研究亦广泛展开。32 国内蚁群算法的发展概况国内对该算法研究最早的是张纪会博士和徐心和教授。1999 年3 月，他们首次简单引进ACA， 从其基本原理、模型、伪码流程进行说明， 对Oliver30TSP 问题分析说明， 但未对基本模型中的参数进行详细地理论说明，且停止条件的界定较含糊，主要靠经验决定。其后引入的变异机制加快了收敛速度，使得到较优解的周期缩短，并从计算机仿真层面上证明其有效性。2001 年，陈烨引入遗传算法中用到的杂交算子来改善蚁群搜

10、索速度慢、容易陷入局部最优。但随路程的增长，每次的代数显著增加，计算量较大。同年8月，郝晋等通过将转移概率设置为转移系数，结合扰动策略以防止漏选最优路径，能够节约计算时间，且能够很好的克服算法容易陷入局部最优的缺陷，计算精度也有提高。但在关于倒指数的扰动因子和均匀分布的随机数的选择并未解决，仍以实验为主要获取手段。而后李艳君等对自适应ACA 进行了进一步研究， 对信息素采取自适应更新，应用于连续空间优化问题的求解，并进行了证明。2002 年， 王颖等对自适应ACA 作出了改进，获得了很好的结果。该ACA在进化代数减少的情况下，解的质量也得到了一定提高，在一定程度上实现了收敛速度与解的质量的平衡

11、。但分析其复杂度可知，蚂蚁的数目与问题规模不相上下，蚂蚁数目增多会使收敛速度过快，为防止该现象而将信息素挥发悉数设置得比一般情况低一个数量级，而相关系数、 等则由实验设定。当蚂蚁数量与问题规模相当时，实验次数与时间是不容忽视的一个问题。ACA 除在原理层面进行模型改进，在应用方面也有一定发展， 如张宗永等将ACA 作出改进，配合随机分布技术，应用到分析上海市整个内河航道和集装箱运输的过程中，对内河航道进行规划，最终得出合理的分配方案并提出了满足最优分配的河道改造的建议。2003 年，陈崚等令人工蚁模仿真实蚂蚁的感觉和知觉行为，设置合理绝对感觉阈值以克服蚂蚁在初始选择时容易失去解的多样性，改进选

12、择策略以自适应的修改路径上的信息量，通过对不同规模和不对称TSP 的仿真说明算法具有较好的收敛性和稳定性。新提出的启发式搜索方法智能ACA，通过取消外激素、自动调整选择最优路径的比例，改变了选择目标城市的依据和引入扰动，仿真结果说明在减少计算量的同时，可取得更好的搜索结果，但也指出通过实验确定相关的物理系数不利于算法的推广。但该文仅针对TSP， 对其他问题能否应用仍不明确。2004 年，黄国锐等提出采用不同于传统基本ACA 所采用的蚁周模型，它采用了更贴近于真实蚂蚁行为的蚁量模型，建立信息素扩散模型，使相距较近的蚂蚁之间能够更好地进行协作，文中仿真结果表明该算法的有效性。然而文中虽在达到收敛所

13、需进化代数上较基本ACA 有了很大的改进， 减少约4倍， 但最短路径长度的减少并不明显，且参数的设定仍是以试验为手段，缺乏理论支撑。针对基本ACA 容易陷入局部最优、收敛慢等缺陷，许多新模型陆续提出，如基于云模型的ACA、对信息素的限制、回归型的等，甚至还有不少研究者试图从新的角度重新审视并尝试性研究ACA，较为新颖的有从蚁群社会的“多态性”出发，试图以更贴近真实世界中蚂蚁行为来研究ACA，发现更适应较大规模的问题，以及将着眼于蚁群整体的研究角度转换到关注蚂蚁个体的速度对算法的影响。为从根本上解决ACA不足， 其收敛性的分析也在不断展开，如用动态分阶段的方式， 而具体影响ACA 的参数也越来越

14、得到关注，如有相关讨论，但参数如何设定并未有理论依据，如何建立通用标准来对参数进行最优设置仍是难点。在研究的应用范围方面也从一开始的离散域扩展到连续域，连续域中有关于收敛性的研究，以及新模型的设计也在进行着。全国各高校及研究机构也对该算法展开了研究，如徐锋、杜军平的改进蚁群算法在旅游路线规划中的应用研究等。1999 年从首次引入ACA 至今，相关研究蓬勃发展，右图为相关的论文题名和关键字的论文数量增长表。图 3.2.1 研究ACA论文增长表国内对于ACA 的研究也越来越深入，基于各类模型的ACA 层出不穷，研究域也从离散域扩展到连续域， 同时ACA 在不断与其他算法结合以克服本身的缺陷。但国内

15、的研究起步较晚，对于影响收敛性的、 等相关参数至今无法确定一套相关的理论来进行设置，只能通过反复试验来大致确定一个参数范围， 且研究较多地停留在理论仿真，应用到实践中仍较少，而国外对于这些范围的研究已经较为成熟。33 蚁群算法的改进型ACA 的收敛速度和最优解的全局性是一对矛盾体，收敛速度过快，会导致早熟，陷入局部最优解，而当信息素更新不及时或算法计算量过大时，则导致收敛速度过慢而应用不现实，为克服这些问题， 相应的改进的ACA 不断提出。（1）带精英策略的蚁群系统（AS）。在带精英策略的AS 中， 为了使到目前为止所找出的最优解在下一个循环中对蚂蚁更有吸引力，在每次循环之后给予最优解额外的信

16、息素量。它信息素的更新为：ij（t1）ij（t）ijij* （1）其中，ij* 表示经蚂蚁引起路径（i，j） 上的信息素量的增加； 是精英蚂蚁的个数；L* 为所找出的最优解的路径长度。这种算法收敛速度快，而且计算耗时短，但如果 过大，搜索会局限于极值周围，导致搜索的早熟收敛。（2）基于优化排序的蚂蚁系统。基于优化排序的AS 针对带精英策略的AS 的缺点， 通过排序很好地抑制了早熟，尤其当初始状态各解的差异性不大时，效果显著，但其中，第 只最优蚂蚁引起的路径（i，j）上信息素量的增加ijk=1 ij （2）ij 为第 只最优蚂蚁引起的路径（i，j） 上信息素量的增加；ij* 由精英蚂蚁引起的路径

17、（i，j）上的信息素量的增加。（3） 最大最小蚂蚁系统（MMAS）。MMAS 是由德国学者T Stuetzle 和HHoos 提出的，其目的主要在于防止过早的算法停滞现象，性能改进在以下几方面：只允许其中的一个路径更新信息素。该路径通常是最优路径，可以是所有或当前周游中的最优路径。即只有一只蚂蚁进行信息素更新，而用于信息素更新的蚂蚁可能是迭代最优蚂蚁，也可能是全局最优蚂蚁；为了避免搜索的停滞，在每个解的元素上的信息素轨迹量的值被限制在一个固定范围内min，max；为了尽可能的扩大搜索范围，信息素轨迹初始值设为max。该法的轨迹更新规则为ij（t+1）=ij+bestij （4）其中，besti

18、j1 f（sbest），f（sbest）表示迭代最优解或全局最优解的值。这也保证了在初始的搜索中，能够保证最优解的多样性。尽管在算法中对信息素浓度进行了最大和最小值的限制，但此限制还不足以在较长的运行时间里持久消除停滞现象， 故采用信息素的平滑机制：按照比例更新的方法来调整信息素的浓度， 使信息素浓度的增加值正比于max与边（i，j）上的信息素浓度的差值。基本做法是：限定信息素浓度允许值的上下限，且采用了平滑机制，也就是不同点中的。在当前路径上的信息素浓度远远高于其它路径时， 会导致过度收敛，为了降低运行时间，可增加候选解集合的选择概率， 不仅能降低算法的运行时间，还可提高该算法的性能。这些改

19、进模式可以通过对一些较大规模的巡游问题求解加以证明。在全局修正规则中，只让实现最好周游的蚂蚁释放信息素。它和改进的状态转移规则相结合的搜索模式，保证了蚂蚁在优秀父辈完成的周游领域内进行更多搜索，这就使得相应的求解速度大大提高。（4）蚁群算法的社会应用 交通、航运：交通工具流量最大的道路最“短”最通畅，物流应选择这样的路径。直到流量增大到引起交通堵塞，导致流量减小，剩下的次短路径即成最佳路径。 网络路由器工作原理：信息流量最大的网路最通畅，应该尽量把需要发送的信息分送给最繁忙的网路去传输，直到引起“堵塞” 邮件发送：规则同交通、航运、网络路由器。同样，人最多的餐馆综合服务最好蚁群算法的根本逻辑是

20、：最繁忙的路径是最“短”而且最通畅的。由蚁群算法，推导本能的形成和家畜驯化 以非洲大草原瞪羚和亚洲山羊为例。假设逃跑的本能反应还没有形成前，动物行为全部由大脑指挥。草食的非洲瞪羚和亚洲山羊远祖，遇到肉食动物攻击的时候，大脑反应的逻辑是“听到声音或闻到气味，看到肉食动物，确定逃跑路线，再拔腿而逃。 ”非洲大草原是空旷而无障碍的，瞪羚远祖逐渐发现，根本就可以省略“看到肉食动物，确定逃跑路线”的大脑处理步骤，这个“蚂蚁算法”不断强化，“最便捷路径”是不经大脑反应，一有风吹草动拔腿就逃的条件反射类似人的手被烫了先本能缩回来，反应完成后痛感才传到大脑，再由大脑做后继行为最后瞪羚形成一旦受惊，即以最高速度

21、先跑起来，再由大脑反应过来后确定逃跑路线的本能。与非洲草原相反，亚洲山羊的先祖发现，在这个到处是障碍物的亚洲山地环境里，这个“ 听到声音或闻到气味，看到肉食动物，确定逃跑路线，再拔腿而逃。 ”的逻辑一步也不能省略，否则即使没有被肉食动物抓住，也是“ 守株待兔”中那只兔子的下场。于是，山羊反而要逐渐放弃有风吹草动就拔腿而逃的不经济选择，最后形成受惊后马上停止一切活动，包括进食和呼吸，再由大脑反应过来后确定逃跑路线的本能。这个由环境和“ 蚂蚁算法 ”演化出来的本能的假说非常有意思，回答了瞪羚与山羊是否能够被人类驯化的问题。可以设想，非洲的人类先祖和亚洲的人类先祖各自捉到自己环境里的瞪羚与山羊，关在

22、自己简陋的圈里养起来。亚洲人的原始山羊在人工环境中的众多异常声音和刺激下先吓得瑟瑟发抖，安安静静，最后发现有吃有喝，住下来不是坏事；而倒霉的非洲人的原始瞪羚一受到刺激，不经大脑考虑，拔腿就以六十公里以上的时速冲向栅栏所以，亚洲人几乎驯养了人类所有的主要家畜，而非洲人一种也没有驯养成功。南美洲也只有安第斯山脉地区的印第安人驯养了两种羊驼，而北美洲的印第安人什么都没有。从人类大迁徙得到的交流成果来看，非洲人也是非常喜欢牛羊狗等等，而印第安人也特别喜欢马可是，非洲人不可能以非洲的野牛、斑马、疣猪、瞪羚、鬣狗等为基础驯养成功自己的牛马猪羊狗，印第安人也驯化不了驯鹿和北美野牛。今天人类的主要畜禽，都在一

23、万年前已经完成驯化，而即使以人类今天这样的丰富知识和手段，重要的畜禽也没有增加哪怕一种。继续根据“ 蚂蚁算法”的逻辑，要驯化非洲野牛、斑马、疣猪、瞪羚、鬣狗这样一些动物，只要将其“最短最有效路径” 堵死，即受惊即不顾一切冲突狂奔的本能反应改造为亚洲山羊的反应即受惊后先安静下来，停止吃喝呼吸，减缓心跳，再确定危险的方向和逃跑的方向的本能。这样的改造是可以进行的，手段无非是建立繁育基地，亦即将“圈” 尽可能做大些，免得瞪羚刚跑起来就自己撞死。繁育基地建立成多树和多石环境，给瞪羚等的刺激从轻微到高强度，并且放养较弱的肉食动物如狼，对驯化动物群进行自然选择也许几代下来，瞪羚等非洲动物的本能反应范式，就

24、能大大向亚洲山羊的本能反应范式改变，驯化的目标就接近了。 由蚁群算法推导的本能的形成和家畜驯化逻辑，解释社会文化、组织结构和律法的形成 这个解释非常简单，就是社会其实给了所有的可能性，每一种可能性都有一定数量的成员去实践，就像众多可能的道路都有蚂蚁去走一样。所以社会中有鸡鸣狗盗之辈、男盗女娼之流、谬种卫道之徒，也有真知求索之贤、痛心世风日下之“遗老遗少 ”都能找到实例。但是，这些道路中必然只有少数是目的的“最短路径” ，也只有这些“最短路径”才“流量最大” ，惟此才是主流文化。三品之士，志道法、志功名、志富贵，都能使社会可持续发展下去，但效果逐渐降低，而“ 志富贵” 成为主流，还会导致王朝更替

25、的历史大循环，仅仅是循环的长短有别而已。四、 蚁群算法展望近年研究ACA 的研究人员和研究成果成几何级数增长，蚁群算法表现出了其强大的生命力和广阔的前景。在模型改进方面， 注意思维变换，比如尝试逆向思维，试图建立一个具有普遍适应性的ACA 模型， 而不仅仅是针对某一类特定的问题。对于从自然界真实蚁群的行为研究，进一步剖析深层原因，提出更加智能化的蚁群混合行为模型。此外，很重要的一点就是摆脱已有框架， 提出更具有创新性的ACA 模型，尤其是与智能融合方面。在理论分析方面， 由于ACA 是一种概率搜索算法，从数学理论上对其正确性与可靠性进行严密的证明相对于确定性算法而言， 是比较困难的。而Guti

26、jahr W J 首次利用有向图论对ACA进行其收敛性方面的证明。现阶段ACA 的众多模型并没有归统于共同的框架之下， 并且对于ACA 在连续域的研究相对离散域而言还相对较少，所以对于收敛性的证明和理论分析值得进一步深入研究。而对于蚁群方法的并行实现而言，ACA 本身隐含着一定的并行性，单只蚂蚁在一次循环中独立于其他蚂蚁。因此从本质上说，ACA 应以分布式的协同优化计算方式为特征，而在串行计算机上对ACA 的并行模拟并不能真正体现蚁群算法的本质特征，因此，进一步的研究工作还应该开展ACA 的并行机实现。从目前的发展趋势来看，最优并行化将会成为发展重点。关于硬件实现，ACA 能够处理的电路规模不及常规电路综合方法。算法的运行时间时间、硬件功能以及电路规模之间的协调平衡。同时，对蚁群算法的仿真硬件产品的可靠性、可测试性、普适性和鲁棒性问题也需要进行进一步的