群智能是近年来人工智能研究的一个热点话题蚁群算法作....doc

1、摘 要群智能是近年来人工智能研究的一个热点话题。蚁群算法作为群智能算法的一个热点，是意大利学者 M。 Dorigo 通过模拟蚁群觅食行为提出的。本文首先介绍了群智能，然后详细介绍蚁群算法原理及其优缺点。接着依据大量实验对参数 m、Q 的选择进行研究，得出其选择规律，并在以前学者“三步走”的基础上提出了一种“四步走的有效方法来选择蚁群算法最优组合参数，然后对蚁群改进算法进行分析，同时以实验的方式对这几种算法各自求解 TSP 问题的性能进行了对比分析，得出性能结果排名,并发现当 TSP 问题最优解相同时还可以依据其他性能(迭代次数、迭代时间等）得出最优结果，最后还对陈烨的“蚁群算法实验室”的可视化

2、编程进行了优化和改进，使之能够更方便的用于几种算法性能比较和同种算法不同参数的比较.【关键词关键词】 群智能；蚁群算法；参数选择；TSP；可视化Experimental Analysis and Parameter Selection for the Ant Colony Optimization AlgorithmXu HuiAbstract：Swarm intelligence has been a hot spot in the field of artificial intelligence in recent years。 Among the algorithms of swarm

3、intelligence, ant colony algorithm was presented by an Italy scholar M. Dorigo learning from the behavior simulating ant colony foraging. Firstly， this paper has introduced the group intelligence and promoted the ant colony algorithm, obtained the choice regular of “m， , , ， Q” basing on the experim

4、ent, and proposed an effective method named “four steps” in the fundation of others scholars “three steps” to choose the most superior combination parameter of ant group algorithm， then analied the six kinds improved algorithm of ant colony ant colony algorithm， at the same time explained the abilit

5、y of several kinds of ant algorithm to solve the TSP question according to the experiments； obtained the most superior result according to other performance (iterative number of times， iterative time and so on) when the most superior result of TSP question optimal solution is same。 Finally, this pap

6、er also has carried on the optimization and the improvement to the visible programming of ChenYes “ant colony algorithm laboratory” to enable it more convenient to use in several algorithms performance comparison and the comparison of different parameter and homogeneous algorithm。文档为个人收集整理，来源于网络本文为互

7、联网收集，请勿用作商业用途 Key words：Swarm intelligence; Ant colony algorithm； Parameter Selection; TSP； Visualization目 录1 绪论.11。1 引言.11.2 群智能.11。3 蚁群算法的提出.21。4 本文研究工作.22 蚁群算法概述.42.1 蚁群算法基本原理.42.2 蚁群算法的优点与不足.52。3 本章小结.63 蚁群算法的参数设置研究.73。1 硬件/软件环境平台.73。2 蚂蚁数目对基本蚁群算法的影响.73。3 信息启发式因子和期望值启发式因子.93.4 信息素残留系数 .103.5 总信息

8、量.113.6 本章小结.124 蚁群算法实验分析.134。1 改进的蚁群优化算法.134。1.1 最优解保留策略蚂蚁系统.134。1。2 蚁群系统.134.1。3 最大-最小蚂蚁系统 .134.1.4 基于排序的蚂蚁系统.144.1.5 The Best-Worst Ant System.144。 2 实验仿真及算法性能比较分析.154.2。1 硬件/软件环境平台.154。2.2 重要参数设置.154。2.3 实验结果.154。3 本章小结.175 可视化编程.185。1 “蚁群算法实验室”的优点与不足.185。2 最大最小蚁群算法的图形化演示的改进.185。3.本章小结226 结论与展望.

9、23参考文献.24致 谢.25附 录.261 绪论自蚁群算法提出以来,就引起了国内外学者的广泛关注，提出了很多改进算法。参数的设置直接影响到算法的性能，所以对参数设置的研究越来越重要,而目前对它的研究大多还处于实验分析阶段。1.1 引言随着人们对生命本质的不断了解，生命科学也以前所未有的速度迅猛发展，使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索起新的非经典计算途径.在这种背景下,社会性动物的自组织行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的“群智能” 。受蚂蚁总能找到一条从蚁巢到食物源的最短路径的启发，意大利学者 M. Dorigo

10、与 20 世纪 90 年代提出了一种新型的智能优化算法-蚁群优化算法（Ant Colony Optimization，ACO)1。在不长的时间里，蚁群算法得到了不断发展和完善，而且被用于解决大多数优化问题或者能够转化为优化求解的问题,现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信 QoS 管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面.1。2 群智能群智能指的是“无智能的主体通过合作表现出智能行为的特性”2，是一种基于生物群体行为规律的计算技术。它受社会昆虫,例如蚂蚁、蜜蜂和群居脊椎动物，又如鸟群、鱼群和兽群等的启发，解决分布式问题.

11、它在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了一种新的思路。 有些专家在研究自然界的生物群体系统时，惊奇地发现社会昆虫和群居的脊椎动物能发现新的食物源、在群体内部产生劳动分工，建筑庞大复杂的巢穴、跨越几千公里迁徙到指定地区和在狭窄的空间内协调调度等.这些社会性动物的自组织行为引起了人们广泛的关注，许多学者对这种行为进行数学建模并用计算机对其进行仿真，发现群智能有如下特点和优点2：（1) 群体中相互合作的个体是分布的（Distributed)，这样更能够适应当前网络环境下的工作状态。（2） 没有中心的控制与数据,这样的系统更具有鲁棒性（Robust），不会由于

12、某一个或者某几个个体的故障而影响整个问题的求解。（3） 可以不通过个体之间直接通信，而是通过非直接通信进行合作，这样的系统具有更好的可扩充性(Scalability）。（4) 由于系统中个体的增加而增加的系统通信开销在这里是十分小的，系统中每个个体的能力十分简单，这样每个个体的执行时间比较短,并且实现也比较简单，具有简单性(Simplicity）。 1。3 蚁群算法的提出目前，群智能理论研究领域包括两种主要算法:蚁群算法(Ant Colony Optimization，简记ACO）和粒子群算法(Particle Swarm Optimization，简记PSO)。而以蚁群算法为代表的群体智能已

13、成为当今分布式人工智能研究的一个热点，它是由意大利学者M。 Dorigo、V. Maniez-zo、A. Colorini3，4，5等人从生物进化机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为后,于1991年首先提出的,也叫蚂蚁系统（Ant System,AS).M. Dorigo等人充分利用蚁群搜索食物的过程与著名的旅行商问题（Traveling Salesman Problem）之间的相似性，吸收了蚂蚁的行为特征，设计虚拟的“蚂蚁”摸索不同的路线,并留下会随时间逐渐消失的虚拟“信息量”2。虚拟的“信息量”会挥发，当蚂蚁每次随机选择要走的路径时,倾向于选择信息量比较浓的路径。根据“信息量浓

14、度更近”的原则，既可选择出最佳路线。虽然蚁群算法的研究时间不长,但初步研究已显示它在求解复杂优化问题方面具有很大优势,特别是 1998 年在比利时布鲁塞尔专门召开了第一届蚂蚁优化国际研讨会后,现在每两年召开一次这样的蚂蚁优化国际研讨会。这标志着蚁群算法的研究已经得到国际上的广泛支持，使得这种新兴的智能进化仿生算法展现出了勃勃生机6。1.4 本文研究工作本文围绕蚁群算法的原理、改进及其应用展开研究,全文共分六章,各章内容安排如下：第一章：绪论本章首先对群智能进行介绍，然后阐述蚁群算法产生的背景.第二章:蚁群算法概述本章详细介绍蚁群算法原理及其优缺点。第三章：蚁群算法的参数设置研究本章针对参数设置

15、进行大量实验,并对实验结果做出研究分析,得出参数m，Q 的选择规律，在此基础上，提出新的有效方法对蚁群算法最优组合参数进行选择.第四章：蚁群算法实验分析本章分析几种改进的蚁群算法，并采用国际上通用的测试问题库 TSPLIB中的对称 TSP 问题作为测试对象，通过仿真试验对六种算法各自求解 TSP 问题的性能进行比较,得出当 TSP 问题最优解相同时，可依据其他性能（迭代次数、迭代时间等)得出 TSP 问题的最优结果. 第五章：可视化编程针对陈烨的“蚁群算法实验室”进行优化和改进。第六章:结论与展望总结本文工作，提出展望。 2 蚁群算法概述 下面详细介绍蚁群算法原理及其优缺点.2.1 蚁群算法基

16、本原理现实生活中单个蚂蚁的能力和智力非常简单，但他们能通过相互协调、分工、合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其以蚂蚁总能找到一条从蚁巢到食物源的最短路径而令人惊叹。根据仿生学家的长期研究发现：蚂蚁虽没有知觉，但运动时会通过在路径上释放出一种特殊的分泌物-信息素来寻找路径.蚂蚁个体之间就是利用信息素作为介质来相互交流、合作的。某条路上经过的蚂蚁越多，信息素的强度就会越大，而蚂蚁能感知路上信息素的存在和强度,它们倾向于选择外激素强度大的方向，因为通过较短路径往返于食物和巢穴之间的蚂蚁能以更短的时间经过这条路径上的点，所以这些点上的外激素就会因蚂蚁经过的次数增多而增强，这样就会有更多

17、的蚂蚁选择此路径,这条路径上的外激素就会越来越强，选择此路径的蚂蚁也越来越多.直到最后，几乎所有的蚂蚁都选择这条最短的路径.蚁群算法可以表述如下:在算法的初始时刻，将 m 只蚂蚁随机地放到 n 座城市，同时，将每只蚂蚁的禁忌表的第一个元素设置为它当前所在的城市.此时各路径上的信息素量相等，设 ij(0) = C(C 为一较小的常数)，接下来，每只蚂蚁根据路径上残留的信息素量和启发式信息（两城市间的距离）独立地选择下一座城市，在时刻 t,蚂蚁 k 从城市 i 转移到城市 j 的概率(t)为: kijp (2. k( )( )( ), if jJ ( )( )( ) 0, otherwisekij

18、ijkisisijsJittitpt1）其中，Jk(i）= 1,2，n- tabuk 表示蚂蚁 k 下一步允许选择的城市集合.列表 tabuk记录了蚂蚁 k 当前走过的城市。当所有 n 座城市都加入到 tabuk中时，蚂蚁 k 便完成了一次周游，此时蚂蚁 k 所走过的路径便是 TSP 问题的一个可行解。 （2. 1）式中的 ij 是一个启发式因子，表示蚂蚁从城市 i 转移到城市 j 的期望程度.在 AS 算法中,ij 通常取城市 i 与城市 j 之间距离的倒数.和 分别表示信息素和启发式因子的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据（2。 2)式更新。 (2. 2)ijij

19、ijtnt)()1 ( (2. 3)mkkijij1其中 （0 1）表示路径上信息素的蒸发系数，1- 表示信息素的持久性系数；ij表示本次迭代边 ij 上信息素的增量.kij表示第 k 只蚂蚁在本次迭代中留在边 ij 上的信息素量。如果蚂蚁 k 没有经过边 ij,则kij的值为零.kij表示为: （2. 4), kij0, kKijQL若蚂蚁在本次周游中经过边 否则其中，Q 为正常数，Lk 表示第 k 只蚂蚁在本次周游中所走过路径的长度.M。 Dorigo 提出了 3 种 AS 算法的模型 7, 式 （2。4) 称为 ant-cycle,另外两个模型分别称为 antquantity 和 ant

20、-density，其差别主要在 (2. 4） 式,即:在 ant-quantity 模型中为： , kij0, ijkijQd蚂蚁在时刻t 和t +1经过边否则（2。 5) 在 ant-density 模型中为： , kij0, kijQ蚂蚁在时刻t 和t +1经过边 否则 (2。 6)AS 算法实际上是正反馈原理和启发式算法相结合的一种算法.在选择路径时，蚂蚁不仅利用了路径上的信息素,而且用到了城市间距离的倒数作为启发式因子。实验结果表明，ant-cycle 模型比 ant-quantity 和 antdensity 模型有更好的性能.这是因为 antcycle 模型利用全局信息更新路径上的

21、信息素量，而 ant-quantity 和 ant-density 模型使用局部信息。AS 算法的时间复杂度为（NC*n2*m） ,算法的空间复杂度为 S(n)=O（n2)+O(nm) ，其中 NC 表示迭代的次数，n 为城市数，m 为蚂蚁的数目。2。2 蚁群算法的优点与不足众多研究已经证明 AS 算法具有很强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可以加快进化过程,而且是一种本质上并行的算法。它有如下优点8:(1） 较强的鲁棒性：对蚁群算法模型稍加修改,便可以应用于其它问题。(2) 分布式计算：蚁群算法是一种基于种群的进化算法,具有本质的并行性，易于实现。(3）

22、易于与其他方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能.同时它也存在一些缺陷：(1)限于局部最优解，从算法解的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解。（2)工作过程的中间停滞问题（stagnation behaviour）,和算法开始时收敛速度快一样，在算法工作过程当中，迭代到一定次数后，蚂蚁也可能在某个或某些局部最优解的邻域附近产生停滞。(3）较长的搜索时间,尽管和其他算法相比,蚁群算法在迭代次数和解的质量上都有一定的优势,但对于目前计算机网络的实际情况，还是需要较长的搜索时间.虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓

23、解这一问题，但是对于大规模复杂的计算机网络，这还是一个很大的障碍.2。3 本章小结 本章主要介绍了蚁群算法基本原理,并针对其优缺点，进行了介绍和讨论.蚂蚁通过释放一种特殊的分泌物-信息素来寻找路径，蚂蚁个体之间也通过信息素进行交流与合作。蚁群算法的优势主要体现在鲁棒性,分布式，移植性等方面，而其缺陷,就目前来说，主要在局部最优，工作停滞,搜索时间长等方面。3 蚁群算法的参数设置研究蚁群算法在TSP 问题应用中取得了良好的效果,但也存在下列不足： （1) 如果参数、m、Q等设置不当,会导致求解速度很慢且所得解的质量特别差;（2） 基本蚁群算法计算量大，求解所需的时间较长；（3) 基本蚁群算法中理

24、论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路;但在实际计算中，在给定一定循环次数的条件下很难实现这种情况. 另一方面，在其他的实际应用中，如图像处理中寻求最优模板问题，并不要求所有的蚂蚁都能找到最优模板，而只需要一只找到即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。目前，对基本蚁群算法的参数设置和属性的研究大多还处于实验阶段,M。 Dorigo 3,4 等人通过大量的实验对蚂蚁系统的参数和基本属性进行了探讨。讨论的参数包括：m 蚂蚁数目； -信息素的相对重要程度； 启发式因子的相对重要程度; 信息素蒸发系数（1-）表示信息素的持久性系数）;Q -蚂蚁释放的信息素量。在

25、实验中，为了观察某个参数对算法性能的影响，在测试该参数时，其它参数取缺省值。各参数的缺省值为 m = n1/4(本文中为 21）， =1， =5， = 0。 5，Q =100.在实验中,本实验每组数据试验5次取平均和最优作比较，试验中所用的TSP 问题数据来源于Eil51 城市问题，迭代次数100次.3.1 硬件/软件环境平台 本实验采用的硬件/软件环境分别为：CPU 2。 4GHz，内存 256 M,硬盘容量 80G,安装的是 Microsoft windows XP(Service Pack 2）操作系统，开发平台是Microsoft Visual C+ 6。 0 。3.2 蚂蚁数目对基本

26、蚁群算法的影响对于 TSP 问题，单个蚂蚁在一次循环中所经过的路径，表现为问题可行解集中的一个解，m 只蚂蚁在一次循环中所经过的路径，则表现为问题可行解集中的一个子集。显然，子集大（即蚂蚁数量多）就可以提高蚁群算法的全局搜索能力以及算法的稳定性；但是，蚂蚁数目增大后，会使大量的曾被搜索过的解（路径)上的信息量的变化比较平均，信息正反馈的作用不明显，搜索的随机性尽管得到了加强，但收敛速度减慢；反之，子集较小（即蚁群数量少） ，特别是当要处理的问题规模比较大时，会使那些从来未被搜索到的解（路径）上的信息量减小到接近于 0，搜索的随机性减弱，虽然收敛速度加快，但会使算法的全局性能降低，算法的稳定性差

27、，容易出现过早停滞现象.关于蚁群算法中蚂蚁数量m 的选择，也应该综合考虑算法的全局搜索能力和收敛速度两项指标,针对具体问题的应用条件和实际要求，在全局搜索能力和收敛速度两方面作出合理或折衷的选择。关于蚂蚁数目m对算法性能的影响及其在实际应用中的选择，本文通过计算机仿真实验来分析和确定,本文使蚂蚁数目变化为5、7、9、11、13、15、17、19、21、23、25、27、29、31,蚂蚁数目m对算法性能的影响仿真结果如表3-1和图3-1所示。 表 31 蚂蚁数目 m 对算法性能的影响的结果蚂蚁数目最优(最短）路径长度运行的时间（s）5463。 9870768。 8287465。 00919914

28、. 119457. 0014789. 78111453. 74132713。 18713452. 82271614. 17215456. 11601113. 53117451。 11732112。 7519445。 62417714。 18721446. 07869513。 18823447. 00173113。 92125452。 29920213。 1127446. 07869521. 46829451。 22320414. 17131450。 77665913。 515最优（最短）路径长度435440445450455460465470579 11 13 15 17 19 21 23 2

29、5 27 29 31蚂蚁数目最优（最短）路径长度图 3-1 蚂蚁数目 m 对算法性能的影响的仿真结果关于蚁群算法中蚂蚁数量 m 的选择,要综合考虑算法的全局搜索能力和收敛速度两项指标，针对具体问题的应用条件和实际要求,在全局搜索能力和收敛速度两方面做出合理或折衷的选择,图 31 为实验所得的结果，其中横轴表示蚂蚁数，纵轴表示发现最优解。从图中可以看出当 m 在 1/42/5 之间时,蚁群算法可以找到最优解，通过本实验和其他学者的研究，本文最终得出蚂蚁数目应该在 1/42/5 之间，而且当城市数目规模较小时蚂蚁数目 m 应该尽量靠近2/5（如果很小可以考虑 m=n）,当城市数目规模较大时蚂蚁数目

30、 m 应该尽量靠近 1/4,因为这样综合考虑了算法的全局搜索能力和收敛速度两项指标，可以使得找到最优解并且全局搜索能力和收敛速度都是比较好，算法的各项性能相对平稳。3.3 信息启发式因子和期望值启发式因子信息启发式因子反映蚂蚁在运动过程中所积累的信息量(即残留信息量ij（t）)在指导蚁群搜索中的相对重要程度,期望值启发式因子反映蚂蚁在运动过程中启发信息（即期望值ij ）在指导蚁群搜索中的相对重要程度9.期望值启发式因子的大小反映了蚁群在路径搜索中先验性、确定性因素作用的强度，其值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大,虽然搜索的收敛速度得以加快,但是,蚁群在最优路径的搜索过程中随

31、机性减弱易于陷入局部最优；而信息启发式因子的大小则反映了蚁群在路径搜索中随机性因素作用的强度，其值越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱，当值过大也会使蚁群的搜索过早陷于局部最优。蚁群算法的全局寻优性能，首先要求蚁群的搜索过程必须有很强的随机性；而蚁群算法的快速收敛性能，又要求蚁群的搜索过程必须要有较高的确定性。因此两者对蚁群算法性能的影响和作用是相互配合、密切相关的.要想得到好的结果应该适当选择 和 的取值范围，一般=0。 55，=159。因为两者相互配合、密切相关，本文对和采用组合方式讨论其对蚁群算法性能的影响。取为0。 5、1、2、5，为1、2、5，进行组合仿真实验，

32、实验结果如表32和图3-2所示。本文为互联网收集，请勿用作商业用途个人收集整理，勿做商业用途表 3-2 和 组合方式对算法性能结果信息素浓度影响力参数 a启发式信息影响力参数 b最优（最短)路径长度运行的时间0. 51703. 90315614. 2650. 52531. 14289119。 2030. 55458. 38247917。 79711481. 41578817. 71812461。 26314915。 6415447。 00173112。 09321475。 70565223. 70322458. 0605112。 06225459。 59041712. 40651538。 12

33、448712。 70352465。 84123324. 2555465. 76743524. 375最优（最短）路径长度02004006008001251251251250.5 0.50.5 111222555和组合最优（最短）路径长度图 3-2 和组合方式对算法性能的仿真结果以上实验告诉我们，如果要增加蚁群算法的快速收敛性能,而且又要求蚁群的搜索过程必须要有较高的确定性，就要同时选择好 和 ,因为它们对蚁群算法性能的影响和作用是相互配合、密切相关的。而本文在大量实验的基础上得出，要想得到更优的结果则选择 =1, =5.3。4 信息素残留系数在蚁群算法中，随着时间的推移，蚂蚁留下的信息素会逐渐

34、消逝。在算法模型中用参数 1- 表示信息消逝程度（或称信息素挥发度)，而 就是信息素残留系数。蚁群算法与遗传算法等各种模拟进化算法一样,也存在着收敛速度慢、易于陷入局部最优等缺陷。而信息素挥发度 1 的大小直接关系到蚁群算法的全局搜索能力及其收敛速度：由于信息素挥发度 1- 的存在，当要处理的问题规模比较大时,会使那些从来未被搜索到的路径（可行解）上的信息量减小到接近于 0,因而降低了算法的全局搜索能力，而且当 1 过大时以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力;反之，通过减小信息素挥发度 1- 虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛

35、速度降低.蚁群算法中信息素挥发度 1 的选择，必须综合考虑算法的全局搜索能力和收敛速度两项性能指标，针对具体问题的应用条件和实际要求，在全局搜索能力和收敛速度两方面作出合理或折衷的选择。为了使算法的性能比较稳定和一致,搜索的全局性和收敛速度都比较好，本文通过计算机仿真实验来分析和确定,本文使信息素残留系数 变化为0. 1、0。 2、0。 3、0。 4、0。 5、0. 6、0. 7、0。 8、0。 9、0。 95、0。 99,信息素残留系数 对算法性能的影响仿真结果如表 3-3 和图 3-3 所示。文档为个人收集整理,来源于网络本文为互联网收集，请勿用作商业用途表 3-3 信息素衰减因子对算法性

36、能的结果路径上信息素衰减因子 p最优（最短）路径长度运行的时间0. 1448. 31777722。 50. 2453。 84862338. 0460。 3444. 56850716。 0160。 4455. 27027115。 9530。 5445. 62417714。 1870。 6448。 12365612. 7030. 7454。 30351917。 6560。 8448. 31777714。 0470. 9448. 38414111。 9070. 95449. 377717150。 99449. 79384313. 125最优（最短）路径长度4384404424444464484504

37、524544564580.10.20.30.40.50.60.70.80.90.950.99最优（最短）路径长度图 3-3 信息素衰减因子对算法性能的仿真结果为了对蚁群算法中信息素挥发度 1- 进行选择，必须综合考虑算法的全局搜索能力和收敛速度两项性能指标，针对具体问题的应用条件和实际要求，在全局搜索能力和收敛速度两方面做出合理或折衷的选择。为了使算法的性能比较稳定和一致，搜索的全局性和收敛速度都比较好，通过上述实验可以知道要想得到好的结果本文建议 =0。 5（1=0。 5）.3.5 总信息量在蚁群模型中总信息量 Q 为蚂蚁循环一周时释放在所经过的路径上的信息素总量一般的理解是：总信息量 Q

38、越大则在蚂蚁已经走过的路径上信息素的累积加快,可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。由于在蚁群算法中各个算法参数的作用实际上是紧密耦合的,其中对算法性能起着主要作用的应该是信息启发式因子 、期望启发式因子 和信息残留常数 等三个参数。总信息量 Q 对算法性能的影响则有赖于 、 和 三个参数的配置以及算法模型的选取，例如在蚁周模型和蚁密模型中总信息量 Q 对算法性能的影响情况有较大的差异.总信息量对蚁周模型蚁群算法的性能没有明显的影响，一般取 Q =10010.3。6 本章小结本章通过大量实验说明了信息素残留因子 1-、信息启发式因子 、期望启发式因子 、信息素强度 Q、蚂蚁数目

39、 m 等都是非常重要的参数，其选区方式和选区原则直接影响到蚁群算法的全局收敛性和求解效率，还通过实验得出这些参数的选择规律，并提出了这种“四步走”来选择蚁群算法最优组合参数的有效方法：（1）确定蚂蚁数目 m,根据 城市规模 / 蚂蚁数目 1/42/5 的选择策略来确定蚂蚁的总数目.(2)参数微调，即调整数值范围较小的信息素残留因子 1（以 0. 1 为单位调整）,要想得到好的结果本文建议 1= 0。 5。(3)参数中调，即调整数值范围适中的信息启发式因子 、期望启发式因子（以 1 为单位调整)，并且 和 要使用组合方式才可以得到较理想的解，要想得到好的结果本文建议 =1, =5。(4)参数粗调

40、，即调整数值范围较大的信息素强度 Q 参数（以 10 或更大的数为单位调整） ，已得到较理想的解,要想得到好的结果本文建议 Q=100。4 蚁群算法实验分析 下面对目前最流行的几种蚁群算法进行性能比较分析。4.1 改进的蚁群优化算法为了克服AS的问题，很多学者对其进行研究，并提出了一些改进措施，下面将介绍五种蚁群优化算法。 4。1.1 最优解保留策略蚂蚁系统通过使用最优蚂蚁可以提高蚂蚁系统中解的质量7。在最优解保留策略蚂蚁系统（Elitist Ant System,简称 EAS）中,每次迭代完成后,全局最优解得到更进一步的利用，即在对信息素进行更新时，就好像有许多的最优蚂蚁选择了该路径.与 A

41、S 算法相比,ASelite算法在信息素更新时加强了对全局最优解的利用，其信息素更新策略为： (0, 1） *)(*)1 () 1(ijijijijtt（4。 1） (4. 1mkijijk2） （4. , k ij 0, kKijQL如 果 蚂 蚁 经 过 边 否 则3） (4。 *, 0, gbijQL如 果 边 （i j ） 是 当 前 最 优 解 的 一 部 分 否 则4）其中ij 为最优蚂蚁在边(i, j）上增加的信息素量， 为最优蚂蚁数，Lgb 为全局最优解。4.1.2 蚁群系统蚁群系统（Ant Colony System，简称 ACS）11是 AS 最成功的后续算法之一，与 AS

42、 算法的主要区别在于：（1）在选择下一座城市时，ACS 算法更多地利用了当前的较好解；(2）只在全局最优解所属的边上增加信息素；（3)每次当蚂蚁从城市 i 转移到城市 j 时，边 ij 上的信息素将会适当的减少。4.1.3 最大最小蚂蚁系统MAX-MIN Ant System 12从另外的角度对 AS 进行直接完善：修改了 AS的信息素更新方式，仅将每一代中的最好个体所走路径上的信息量进行调整，加快收敛速度，并将各条路径上的信息素浓度被限制在tmin, tmax 范围内,这样就可以有效的避免某条路径上的信息量远大于或远小于其余路径情况的发生,使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩

43、散,加快收敛速度。另外，信息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力，是目前解决 TSP、QAO 等问题最好的蚁群算法。4.1。4 基于排序的蚂蚁系统基于排序的蚂蚁系统（Rankbased Version of Ant System，简称 RAS）是Bernd Bullnheimer13等提出的 AS 的又一扩展算法。RAS 在每次迭代完成后，蚂蚁所经路径将按从小到大的顺序排列，即 L1（t） L2(t)Lm（t）,并根据路径长度赋予不同的权重，路径长度越短权重越大。全局最优解的权重为 w，第 r 个最优解的权重为 max0, wr ，按（3。 19）式更新各路径上的信

44、息素: （0, 1） )()()()()1 () 1(11twtrwttgbijrijwrijij（4。 5）其中,rij(t)=1/ Lr（t） ，gbij (t)=1/ Lgb4。1.5 The Best-Worst Ant System,BWASBWAS 模型试着用进化算法概念提高 ACO 模型的性能,提出的 BWAS 用的是 AS 转移规则： （4。 k( ), if sJ ( , )0, otherwise KrsrsrrJrPS6）rs是边界（r， s)的信息素值，rs使启发值，Jk（r) 是留下来被蚂蚁K访问的节点集，, 实值的权。常用的AS挥发规则rs (1）rs, r， s，

45、 0, 1，是信息素挥发参数。另外，BWAS考虑下面三个新进程的作用，下面就是对他们的深入分析5：性能更新规则：这种规则是基于 PBIL 的概率数组更新规则，信息素更新如下所示: （4. ( (), ( , ), where 0, otherwiseglobal bestglobal bestrsrsrsrsf c Sif r sS7)f（C(Sglobalbest)） 是要被全局最好的蚂蚁存放的信息素数量，随着全局最优蚂蚁算法聚集了大量的信息素，依靠形成的解决方案C(Sglobalbest） 。信息素痕迹突变: 信息素痕迹在研究介绍相异性时遇到突变,就像PopulationBased Inc

46、remental Learning（PBIL）14这样，信息素矩阵的每一排被改变，概率Pm如下: (4. ( ,), if =0 ( ,), if 0 rsthresholdrsrsthresholdmut itmut it8）它是 0 到 1 之间的随机值，也是当前的迭代，Tthreshold 是组成全局最优解决方案的临界的信息素跟踪的平均值，mut(。 ）是随着迭代记数的增长,变异增强的函数. 当与当前最优和最差解决方案不同的临界值的数字比特定的百分比少时,本文要把所有的信息素痕迹矩阵组成更新为 T0，然后循环。4. 2 实验仿真及算法性能比较分析同 AS 算法相比，以上算法的共同之处在于

47、加强了对最优解的利用。如在 ACS算法和 MMAS 算法中，只有最优解（全局最优或本次迭代最优）所属路径上的信息素允许增强。在 RAS算法中，根据每次迭代路经的长短赋予不同的权重，即对较短的路径赋予较大的权重。这样最优解包含的路径将会有更多的机会被下一次选中.但是，加强对最优解的利用将会导致搜索中的停滞现象。在 ACS 算法中通过增加局部信息素更新来减少路径上的信息素量,从而使后面的蚂蚁选择该路径的可能性减少；在 MMAS 算法中,通过限制信息量的范围，使路径上的信息量不会小于某一最小值，从而避免了所有蚂蚁选择同一条路经的可能性，即避免了搜索中的停滞现象，下面我们用实验来比较各种算法的优越性。

48、4。2。1 硬件/软件环境平台 本实验采用的硬件/软件环境分别为：CPU 3。 0 GHz，内存 512 M，硬盘容量 80G，安装的是Microsoft windows XP(Service Pack 2）操作系统，开发平台 Microsoft Visual C+ 6. 0 。4.2。2 重要参数设置本实验中重要参数设置如下：信息素浓度影响力参数：所有算法设为1。0启发式信息影响力参数：所有算法设为5。0信息素蒸发系数（1-)表示信息素的持久性系数）：所有算法设为0. 5(1即为0. 5)。蚂蚁数目m：本文将m设为问题规模n的1/4即m=n*1/4在算法开始时蚂蚁随机分布在各个城市上.此外，

49、对于EAS，精英蚂蚁的数目的个数e取100（n为其中TSP问题中后面的数字，如Eil51中51即为n值）。在MMAS中初始信息素浓度 0设定为与max相等, 路经信息素浓度下限min设定为小于max的一常数,并且根据式4. 16进行更新。4。2.3 实验结果表41是MMAS，ACS,EAS，RAS,BWAS 与 AS 算法求解不同 TSP 实例的比较结果(问题的最优解用黑体加粗显示），各算法迭代 100次，再重复迭代10次，取10次中的最优进行比较后再进行平均。表41 MMAS，ACS,EAS,RAS，BWAS 与 AS 算法求解不同 TSP 实例的结果比较问题问题ASEASRASMMASBW

50、ASACS最优解最优解426426426426426426迭代次数迭代次数111111迭代时间迭代时间000000平均解平均解428。 3427. 8428. 0428. 0427。 9428。 5平均迭代时间（平均迭代时间（s)0。 0031000。 0016000。 0016000。 0061000. 0032000. 001500Eil51平均总时间（平均总时间（s）0. 0188000。 0171000。 0181900. 0217000. 0172000. 007900最优解最优解212822128221282212822128221282迭代次数迭代次数111111迭代时间迭代时间

51、00。 01500000。 01600000平均解平均解21311。 621317. 021285. 321317. 021307. 621323. 7平均时间（平均时间（s)0. 0126000。 0156000。 0124000。 0141000。 0079000。 014100KroA100平均总时间（平均总时间（s)0. 0188000. 0250000. 0249000. 0235000。 0188000. 017200最优解最优解158581585315829158361584715847迭代次数迭代次数111111迭代时间迭代时间0. 0160000。 0310000. 0160

52、000。 0320000。 0150000. 025000平均解平均解15952. 016093. 016037. 915959. 016075. 816113. 2平均时间（平均时间（s）0. 0186000。 0173000. 0175000。 0190000。 0180000。 015400d198平均总时间（平均总时间（s）0。 0250000. 0250000。 0220000。 0220000. 0218000. 021800最优解最优解421554202942029420294202942029迭代次数迭代次数5331614646迭代时间迭代时间0。 6570003。 14100

53、01. 5780001. 7190000。 6250005。 016000平均解平均解42209. 942088。 342098. 242087。 242101. 242117。 7平均时间（平均时间（s)4。 6924005. 5423001。 5423003. 2844002。 6297006。 282700Lin318平均总时间平均总时间(s）10. 0484009。 3547006。 8156007. 13140014。 85630011. 437500最优解最优解511345105851000508075078551146迭代次数迭代次数452950503424迭代时间迭代时间9。

54、5620006. 3120009. 8430009. 7340006. 0000006。 844000平均解平均解51222。 051151。 151104. 750922. 950927. 451238. 9平均时间（平均时间（s）6。 9653006。 2342007。 2342007。 4293004。 3124005. 634500Pcb422平均总时间平均总时间(s)10. 07500010. 08730010. 11710010. 10310010。 10310010。 140700最优解最优解281462811328138280552809628112迭代次数迭代次数111111

55、迭代时间迭代时间0。 5160000. 4680000。 5630000. 4530000。 4690000. 531000平均解平均解28205. 828195. 728199. 528170。 028218。 028216. 1平均时间（平均时间（s)0。 5142000. 5030000。 5181200。 4561000。 5814000. 548900Att532平均总时间平均总时间(s)0. 5390000。 5500000。 5932800。 1470000. 5922000。 510300最优解最优解903890239035902690339014迭代次数迭代次数111111迭

56、代时间迭代时间0. 8900000. 8440000。 8440000。 8750000. 9220000. 938000平均解平均解9066. 79063。 99062. 99050。 29054。 59053。 1平均时间（平均时间（s）0. 9298000。 8720000。 8657000。 8707000。 9625000。 935800Rat783平均总时间平均总时间(s）0. 9562000. 8906000. 8782000。 8844000. 9765000。 940600最优解最优解242961242840242370242706240898243314迭代次数迭代次数12

57、3332迭代时间迭代时间4。 5000008。 73500013. 7660002。 81440011。 8910009。 750000平均解平均解243367。 4243149。 7243462. 9243879。 3241922。 4244079。 7平均时间（平均时间（s）9. 12500010. 55310010. 9313009。 45320010. 7376008。 733000Vm1084平均总时间平均总时间(s)12。 71090012。 38600011。 76880010. 76880010. 76260012. 645000最优解最优解583015822857895579

58、955775058435迭代次数迭代次数454572迭代时间迭代时间7. 5310009. 2500007. 1880009。 31300011。 0000004。 815000平均解平均解58443. 558401。 958217. 258295. 358002. 058660. 9平均时间平均时间(s）7。 5486007。 2281008。 64060010。 52040010. 2982007. 715700Pcb1173平均总时间（平均总时间（s)10. 60400011。 06720011。 16790011. 03130010. 60000011. 070500最优解最优解515

59、555148251213514835099751758迭代次数迭代次数546555迭代时间迭代时间8。 3590007。 31400011. 0870009. 1250008。 65200011. 641000平均解平均解51681。 751682. 151395。 751807。 551398。 252080. 5平均时间平均时间(s)6。 9875007。 7469009. 40140010。 04850010。 3189008。 906000d1291平均总时间平均总时间(s)10. 86090010。 68590011。 02190010. 85600011. 10630011。 18

60、7400最优解最优解257189256805257359257262253938258066迭代次数迭代次数223133迭代时间迭代时间10。 9300006. 96900010. 5000005。 32907011。 32800013. 938000平均解平均解258689。 6258796。 4258393. 7259087。 8255995。 6259374。 5平均时间（平均时间（s）9。 8064009. 2045009. 2340008。 46720010。 51400010. 267300rl1304平均总时间（平均总时间（s）12。 23280011。 28440011。 01