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

《群智能是近年来人工智能研究的一个热点话题蚁群算法作...41194.docx》由会员分享，可在线阅读，更多相关《群智能是近年来人工智能研究的一个热点话题蚁群算法作...41194.docx（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、和改进，使之能够更方便的用于几种算法性能比较和同种算法不同参数的比较。【关键词】 群群智能；蚁群群算法；参数数选择；TSSP；可视化化Experimmentall Analyssis annd Parameeter SSelecttion ffor thhe Ant Colonyy Optimiizatioon AlggorithhmXu HuiiAbstracct：Swarm iintellligencce hass beenn a hoot spoot in the ffield of arrtificcial iintellligencce in recennt yeaars. Amon

3、g the aalgoriithms of swwarm intellligennce, ant ccolonyy algoorithmm was preseented by ann Itally schholar M. Doriggo leaarningg from tthe beehavioor simmulatiing annt collony fforagiing. FFirstlly, this paperr has introoducedd the groupp inteelligeence aand prromoteed thee ant coolony algorrithm,

4、obtaiined tthe chhoice regullar off “m, , , , Q” baasing on thhe expperimeent, aand prroposeed an effecctive methood nammed “four stepss” in tthe fuundatiion off otheers sccholarrs “threee stepps” to cchoosee the most superrior ccombinnationn paraameterr of aant grroup aalgoriithm, then analiied thh

5、e sixx kindds impprovedd algoorithmm of aant coolony ant coolony algorrithm, at tthe saame tiime exxplainned thhe abiility of seeverall kindds of ant aalgoriithm tto sollve thhe TSPP quesstion accorrding to thhe expperimeents; obtaiined tthe moost suuperioor ressult aaccordding tto othher peerformma

6、nce (iterrativee numbber off timees, itteratiive tiime annd so on) wwhen tthe moost suuperioor ressult oof TSPP quesstion optimmal soolutioon is same. Finaally, this paperr alsoo has carriied onn the optimmizatiion annd thee imprrovemeent too the visibble prrogrammming of ChhenYes “ant colonny alggo

7、rithhm labboratoory” tto enaable iit morre connvenieent too use in seeverall algoorithmms perrformaance ccomparrison and tthe coompariison oof diffferennt parrameteer andd homoogeneoous allgoritthm. KEY WORRDS：SWARM IINTELLLIGENCCE; ANNT COLLONY AALGORIITHM; PARAMMETER SELECCTION; TSP; VISUALLIZATII

8、ON目 录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 总信信息量113.6 本章章小结124 蚁群算法法实验分析134.1 改进进的蚁群优化化算法134.1.1 最优解保留留策略蚂蚁系系统134.1.2 蚁群系统134.1.3 最大-最小蚂蚁系系统

9、134.1.4 基于排序的的蚂蚁系统144.1.5 The BBest-WWorst Ant SSystemm144. 2 实实验仿真及算算法性能比较较分析154.2.1 硬件/软件环境平平台154.2.2 重要参数设设置154.2.3 实验结果154.3 本章章小结175 可视化编编程185.1 “蚁群群算法实验室室”的优点与不不足185.2 最大最最小蚁群算法法的图形化演演示的改进185.3本章小小结226 结论与展望望23参考文献244致 谢225附 录22646江西财经大学本科毕业设计1 绪论自蚁群算法提出出以来,就引起了国国内外学者的的广泛关注，提出了很多多改进算法。参参数的设置直直

10、接影响到算算法的性能，所以对参数数设置的研究究越来越重要要，而目前对它它的研究大多多还处于实验验分析阶段。1.1 引言言随着人们对生命命本质的不断断了解，生命科学也也以前所未有有的速度迅猛猛发展，使人工智能能的研究开始始摆脱经典逻逻辑计算的束束缚，大胆探索起起新的非经典典计算途径。在这种背景下，社会性动物的自组织行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的“群智能”。受蚂蚁总能找到到一条从蚁巢巢到食物源的的最短路径的的启发，意大利学者者M. Doriigo与200世纪90年年代提出了一一种新型的智智能优化算法法蚁群优化算算法（Antt Col

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

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

13、状态。(2) 没有中中心的控制与与数据，这样的系统统更具有鲁棒棒性(Robbust)，不会由于某某一个或者某某几个个体的的故障而影响响整个问题的的求解。(3) 可以不不通过个体之之间直接通信信，而是通过非非直接通信进进行合作，这样的系统统具有更好的的可扩充性(Scalaabilitty)。(4) 由于系系统中个体的的增加而增加加的系统通信信开销在这里里是十分小的的，系统中每个个个体的能力力十分简单，这样每个个个体的执行时时间比较短，并且实现也也比较简单，具有简单性性(Simpplicitty)。 1.3 蚁群群算法的提出出目前，群智能理理论研究领域域包括两种主主要算法：蚁蚁群算法(AAnt C

14、oolony Optimmizatiion，简记ACOO)和粒子群群算法(Paarticlle Swaarm Opptimizzationn，简记PSOO)。而以蚁群算法法为代表的群群体智能已成成为当今分布布式人工智能能研究的一个个热点，它是由意大利利学者M. Doriggo、V. Manieez-zo、AA. Coloorini3,4,5等人从生物进进化机制中受受到启发，通过模拟自自然界蚂蚁搜搜索路径的行行为后，于19911年首先提出出的，也叫蚂蚁系统（AAnt Syystem，AS）。M. Doriigo等人充充分利用蚁群群搜索食物的的过程与著名的旅行行商问题（TTravelling SS

15、alesmman Prroblemm）之间的相相似性，吸收了蚂蚁蚁的行为特征征，设计虚拟的的“蚂蚁”摸索不同的的路线，并留下会随随时间逐渐消消失的虚拟“信息量”2。虚拟的“信息量”会挥发，当蚂蚁每次随随机选择要走走的路径时，倾向于选择择信息量比较较浓的路径。根根据“信息量浓度度更近”的原则，既可选择出最佳路线。虽然蚁群算法的的研究时间不不长，但初步研究究已显示它在在求解复杂优优化问题方面面具有很大优优势，特别是19998年在比利利时布鲁塞尔尔专门召开了了第一届蚂蚁蚁优化国际研研讨会后，现在每两年年召开一次这这样的蚂蚁优优化国际研讨讨会。这标志志着蚁群算法法的研究已经经得到国际上上的广泛支持持，

16、使得这种新新兴的智能进进化仿生算法法展现出了勃勃勃生机6。1.4 本文文研究工作本文围绕蚁群算算法的原理、改进及其应用用展开研究，全文共分六章，各章内容安安排如下：第一章：绪论本章首先对群智智能进行介绍绍，然后阐述蚁蚁群算法产生生的背景。第二章：蚁群算算法概述本章详细介绍蚁蚁群算法原理理及其优缺点点。第三章：蚁群算算法的参数设设置研究本章针对参数设设置进行大量实验验，并对实验结结果做出研究究分析，得出参数mm，Q的选择规律律，在此基础上上，提出新的有效方法法对蚁群算法最最优组合参数数进行选择。第四章：蚁群算算法实验分析析本章分析几种改改进的蚁群算算法，并采用国际上通通用的测试问问题库TSPPL

17、IB中的的对称TSPP问题作为测测试对象，通过仿真试验对六种算算法各自求解解TSP问题题的性能进行行比较，得出当TSSP问题最优优解相同时，可依据其他他性能（迭代代次数、迭代代时间等）得出TSPP问题的最优优结果。 第五章：可视化编程程针对陈烨的“蚁蚁群算法实验验室”进行优化和改改进。第六章：结论与与展望总结本文工作，提出展望。 2 蚁群算法法概述 下面详细介绍蚁蚁群算法原理理及其优缺点点。2.1 蚁群算算法基本原理理现实生活中单个个蚂蚁的能力力和智力非常常简单，但他们能通通过相互协调调、分工、合合作来完成筑筑巢、觅食、迁迁徙、清扫蚁蚁穴等复杂行行为，尤其以蚂蚁蚁总能找到一一条从蚁巢到到食物源

18、的最最短路径而令令人惊叹。根据仿生学家的的长期研究发发现：蚂蚁虽虽没有知觉，但运动时会会通过在路径径上释放出一一种特殊的分分泌物-信息素来寻寻找路径。蚂蚂蚁个体之间间就是利用信息素作为介质来来相互交流、合合作的。某条条路上经过的的蚂蚁越多，信息素的强度度就会越大，而蚂蚁能感知路路上信息素的的存在和强度度，它们倾向于于选择外激素素强度大的方方向，因为通过较较短路径往返返于食物和巢巢穴之间的蚂蚂蚁能以更短短的时间经过过这条路径上上的点，所以这些点点上的外激素素就会因蚂蚁蚁经过的次数数增多而增强强，这样就会有有更多的蚂蚁蚁选择此路径径，这条路径上上的外激素就就会越来越强强，选择此路径径的蚂蚁也越越来

19、越多。直到最后，几乎所有的的蚂蚁都选择择这条最短的的路径。蚁群算法可以表表述如下：在在算法的初始始时刻，将m只蚂蚁蚁随机地放到到 n 座城城市，同时，将每只蚂蚁蚁的禁忌表的的第一个元素素设置为它当当前所在的城城市。此时各各路径上的信信息素量相等等，设ij(0) = C（CC 为一较小小的常数），接下来，每只蚂蚁根根据路径上残残留的信息素素量和启发式式信息（两城城市间的距离离）独立地选选择下一座城城市，在时刻 tt，蚂蚁 k 从城市i转转移到城市jj 的概率(t)为： (2. 1)其中，Jk(ii)= 11，2，n- ttabuk 表示蚂蚁蚁 k 下一一步允许选择择的城市集合合。列表taabuk

20、记录了蚂蚁蚁 k 当前前走过的城市市。当所有 n 座城市市都加入到ttabuk中时，蚂蚁 k 便完成了一一次周游，此时蚂蚁 k 所走过过的路径便是是 TSP 问题的一个个可行解。(2. 1)式式中的ij 是一个个启发式因子子，表示蚂蚁从从城市 i 转移到城市市 j 的期期望程度。在在 AS 算算法中，ij 通常取取城市 i 与城市 jj 之间距离离的倒数。和分别表示信信息素和启发发式因子的相相对重要程度度。当所有蚂蚂蚁完成一次次周游后，各路径上的的信息素根据据（2. 2）式式更新。 (2. 2) (2. 3)其中(0 1)表表示路径上信信息素的蒸发发系数，1- 表示信息息素的持久性性系数；ij

21、表示本次次迭代边 iij 上信息息素的增量。kij表示第 k 只蚂蚁在本次迭代中留在边ij 上的信息素量。如果蚂蚁 k 没有经过边 ij，则kij的值为零。kij表示为： (2. 4)其中，Q 为正正常数，Lk 表示第 k 只蚂蚁蚁在本次周游游中所走过路路径的长度。M. Doriigo 提出出了 3 种种 AS 算算法的模型 7， 式 (2.4) 称称为 antt-cyclle，另外两个模模型分别称为为 ant-quanttity 和和 ant-densiity，其差别主要要在 (2. 4) 式，即：在 aant-quuantitty 模型中中为： (2. 5) 在 annt-dennsity

22、 模型中为： (2. 6)AS算法实际上上是正反馈原原理和启发式式算法相结合合的一种算法法。在选择路路径时，蚂蚁不仅利利用了路径上上的信息素，而且用到了了城市间距离离的倒数作为为启发式因子子。实验结果果表明，ant-ccycle 模型比 aant-quuantitty 和 aant-deensityy 模型有更更好的性能。这这是因为 aant-cyycle 模模型利用全局局信息更新路路径上的信息息素量，而 antt-quanntity 和ant-densiity 模型型使用局部信信息。AS 算法的时间间复杂度为(NC*n2*m) ，算法的空间间复杂度为SS(n)=OO(n2)+O(nn*m)

23、，其中 NC 表示迭代代的次数，n 为城市市数，m为蚂蚁的的数目。2.2 蚁群算算法的优点与与不足众多研究已经证证明 AS 算法具有很很强的发现较较好解的能力力，这是因为该该算法不仅利利用了正反馈馈原理，在一定程度度上可以加快快进化过程，而且是一种种本质上并行行的算法。它它有如下优点点8：(1) 较强的的鲁棒性：对蚁蚁群算法模型型稍加修改，便可以应用用于其它问题题。(2) 分布式式计算：蚁群群算法是一种种基于种群的的进化算法，具有本质的的并行性，易于实现。(3) 易于与与其他方法结结合：蚁群算算法很容易与与多种启发式式算法结合，以改善算法法的性能。同时它也存在一一些缺陷：(1)限于局部部最优解

24、，从算法解的的性质而言，蚁群算法也也是在寻找一一个比较好的的局部最优解解，而不是强求求是全局最优优解。(2)工作过程程的中间停滞滞问题（sttagnattion bbehaviiour），和算法开始始时收敛速度度快一样，在算法工作作过程当中，迭代到一定定次数后，蚂蚁也可能能在某个或某某些局部最优优解的邻域附附近产生停滞。(3)较长的搜搜索时间，尽管和其他他算法相比，蚁群算法在在迭代次数和和解的质量上上都有一定的的优势，但对于目前前计算机网络络的实际情况况，还是需要较较长的搜索时时间。虽然计算机机计算速度的的提高和蚁群群算法的并行行性在一定程程度上可以缓缓解这一问题题，但是对于大大规模复杂的的计

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

26、算量大，求解所需的的时间较长；(3) 基本蚁蚁群算法中理理论上要求所所有的蚂蚁选选择同一路线线，该线路即为为所求的最优优线路；但在实际计计算中，在给定一定定循环次数的的条件下很难难实现这种情情况。 另一方面，在其其他的实际应应用中，如图像处理理中寻求最优优模板问题，并不要求所所有的蚂蚁都都能找到最优优模板，而只需要一一只找到即可可。如果要求求所有的蚂蚁蚁都找到最优优模板，反而影响了了计算效率。目前，对基本蚁蚁群算法的参参数设置和属属性的研究大大多还处于实实验阶段，M. Doriggo 3,4 等人通过过大量的实验验对蚂蚁系统统的参数和基基本属性进行行了探讨。讨讨论的参数包包括：m 蚂蚁数数目；

27、 信息素素的相对重要要程度； 启发式式因子的相对对重要程度； 信息素素蒸发系数（(1-)表示信息息素的持久性性系数）；Q 蚂蚁释释放的信息素素量。在实验中，为了了观察某个参参数对算法性性能的影响，在测试该参参数时，其它参数取取缺省值。各各参数的缺省省值为m = n*11/4（本文文中为21）， =1， =5， = 00. 5，Q =1000。在实验中，本实实验每组数据据试验5次取平均和和最优作比较较，试验中所用用的TSP 问题数据来来源于Eill51 城市市问题，迭代次数1100次。3.1 硬件件/软件环境平平台 本实验采用的硬硬件/软件环环境分别为：CPU 2. 4GHz，内存 2566 M

28、，硬盘容量 80G，安装的是Miicrosooft windoows XPP（Servvice PPack 22）操作系统统，开发平台是Microosoft Visuaal C+ 6. 0 。3.2 蚂蚁蚁数目对基本本蚁群算法的的影响对于 TSP 问题，单个蚂蚁在在一次循环中中所经过的路路径，表现为问题题可行解集中中的一个解，m 只蚂蚁蚁在一次循环环中所经过的的路径，则表现为问问题可行解集集中的一个子子集。显然，子集大(即即蚂蚁数量多多)就可以提提高蚁群算法法的全局搜索索能力以及算算法的稳定性性；但是，蚂蚁数目增增大后，会使大量的的曾被搜索过过的解(路径径)上的信息息量的变化比比较平均，信息正

29、反馈馈的作用不明明显，搜索的随机机性尽管得到到了加强，但收敛速度度减慢；反之之，子集较小(即蚁群数量量少)，特别是当要要处理的问题题规模比较大大时，会使那些从从来未被搜索索到的解(路路径)上的信信息量减小到到接近于 00，搜索的随机机性减弱，虽然收敛速速度加快，但会使算法法的全局性能能降低，算法的稳定定性差，容易出现过过早停滞现象象。关于蚁群群算法中蚂蚁蚁数量m 的的选择，也应该综合合考虑算法的的全局搜索能能力和收敛速速度两项指标标，针对具体问问题的应用条条件和实际要要求，在全局搜索索能力和收敛敛速度两方面面作出合理或或折衷的选择择。关于蚂蚁数目mm对算法性能能的影响及其其在实际应用用中的选择

30、，本文通过计计算机仿真实实验来分析和和确定，本文使蚂蚁蚁数目变化为为5、7、99、11、113、15、117、19、221、23、225、27、229、31，蚂蚁数目mm对算法性能能的影响仿真真结果如表33-1和图3-1所示。 表3-1 蚂蚁蚁数目m对算算法性能的影影响的结果蚂蚁数目最优（最短）路路径长度运行的时间（ss）5463. 98870768. 8287465. 000919914. 119457. 00014789. 78111453. 744132713. 187713452. 822271614. 172215456. 111601113. 531117451. 11173211

31、2. 7519445. 622417714. 187721446. 077869513. 188823447. 000173113. 921125452. 299920213. 1127446. 077869521. 468829451. 222320414. 171131450. 777665913. 5155图3-1 蚂蚁蚁数目m对算算法性能的影影响的仿真结结果关于蚁群算法中中蚂蚁数量mm 的选择，要综合考虑虑算法的全局局搜索能力和和收敛速度两两项指标，针对具体问问题的应用条条件和实际要要求，在全局搜索索能力和收敛敛速度两方面面做出合理或折折衷的选择，图 3-1 为实验验所得的结果果，其中

32、横轴表表示蚂蚁数，纵轴表示发发现最优解。从从图中可以看看出当m在11/42/5之间时，蚁群算法可可以找到最优优解，通过本实验验和其他学者者的研究，本文最终得得出蚂蚁数目目应该在1/42/55之间，而且当城市市数目规模较较小时蚂蚁数数目m应该尽尽量靠近2/5（如果很很小可以考虑虑m=n），当城市数目目规模较大时时蚂蚁数目mm应该尽量靠靠近1/4，因为这样综综合考虑了算算法的全局搜搜索能力和收收敛速度两项项指标，可以使得找找到最优解并并且全局搜索索能力和收敛敛速度都是比比较好，算法的各项项性能相对平平稳。3.3 信息息启发式因子子和期望值启启发式因子信息启发式因子子反映蚂蚁在在运动过程中中所积累的

33、信信息量(即残残留信息量ij(t)在指导蚁群群搜索中的相相对重要程度度，期望值启发发式因子反映蚂蚁在在运动过程中中启发信息(即期望值ij )在指指导蚁群搜索索中的相对重重要程度9。期望值启启发式因子的大小反映映了蚁群在路路径搜索中先先验性、确定定性因素作用用的强度，其值越大，蚂蚁在某个个局部点上选选择局部最短短路径的可能能性越大，虽然搜索的的收敛速度得得以加快，但是，蚁群在最优优路径的搜索索过程中随机机性减弱易于于陷入局部最最优；而信息息启发式因子子的大小则反反映了蚁群在在路径搜索中中随机性因素素作用的强度度，其值越大，蚂蚁选择以以前走过的路路径的可能性性越大，搜索的随机机性减弱，当值过大也会

34、会使蚁群的搜搜索过早陷于于局部最优。蚁蚁群算法的全全局寻优性能能，首先要求蚁蚁群的搜索过过程必须有很很强的随机性性；而蚁群算算法的快速收收敛性能，又要求蚁群群的搜索过程程必须要有较较高的确定性性。因此两者者对蚁群算法法性能的影响响和作用是相相互配合、密密切相关的。要要想得到好的的结果应该适适当选择 和 的取值范范围，一般=0. 55，=159。因为两者相相互配合、密密切相关，本文对和采用组合方方式讨论其对对蚁群算法性性能的影响。取取为0. 5、1、22、5，为1、22、5，进进行组合仿真真实验，实验结果如如表3-2和图3-2所示。表3-2 和和组合方式对对算法性能结结果信息素浓度影响响力参数a

35、启发式信息影响响力参数b最优（最短）路路径长度运行的时间0. 51703. 900315614. 26550. 52531. 144289119. 20330. 55458. 388247917. 797711481. 411578817. 718812461. 266314915. 6415447. 000173112. 093321475. 700565223. 703322458. 06605112. 062225459. 599041712. 406651538. 122448712. 703352465. 844123324. 2555465. 766743524. 3755图3-2

36、 和和组合方式对对算法性能的的仿真结果以上实验告诉我我们，如果要增加蚁蚁群算法的快快速收敛性能能，而且又要求求蚁群的搜索索过程必须要要有较高的确确定性，就要同时选选择好和，因为它们对蚁蚁群算法性能能的影响和作作用是相互配配合、密切相相关的。而本本文在大量实实验的基础上上得出，要想得到更更优的结果则选择择 =1， =5。3.4 信息息素残留系数数在蚁群算法中，随着时间的的推移，蚂蚁留下的信信息素会逐渐消逝逝。在算法模模型中用参数数1-表示信息消消逝程度(或或称信息素挥挥发度)，而就是信息素素残留系数。蚁蚁群算法与遗遗传算法等各各种模拟进化化算法一样，也存在着收收敛速度慢、易易于陷入局部部最优等缺

37、陷陷。而信息素素挥发度1-的大小直接接关系到蚁群群算法的全局局搜索能力及及其收敛速度度：由于信息息素挥发度11-的存在，当要处理的的问题规模比比较大时，会使那些从从来未被搜索索到的路径(可行解)上上的信息量减减小到接近于于 0，因而降低了了算法的全局局搜索能力，而且当1-过大时以前前搜索过的路路径被再次选选择的可能性性过大，也会影响到到算法的随机机性能和全局局搜索能力；反之，通过减小信信息素挥发度度1- 虽然可以以提高算法的的随机性能和和全局搜索能能力，但又会使算算法的收敛速速度降低。蚁蚁群算法中信信息素挥发度度1- 的选择，必须综合考考虑算法的全全局搜索能力力和收敛速度度两项性能指指标，针对

38、具体问问题的应用条条件和实际要要求，在全局搜索索能力和收敛敛速度两方面面作出合理或或折衷的选择择。为了使算算法的性能比比较稳定和一一致，搜索的全局局性和收敛速速度都比较好好，本文通过计计算机仿真实实验来分析和和确定，本文使信息息素残留系数数 变化为00. 1、0. 2、0. 3、0. 4、0. 5、0. 6、0. 7、0. 8、0. 9、0. 95、00. 99，信息素残留留系数 对算法性能能的影响仿真真结果如表33-3和图3-3所示。表3-3信息素素衰减因子对算法性能能的结果路径上信息素衰衰减因子p最优（最短）路路径长度运行的时间0. 1448. 311777722. 50. 2453. 8

39、44862338. 04660. 3444. 566850716. 01660. 4455. 277027115. 95330. 5445. 622417714. 18770. 6448. 122365612. 70330. 7454. 300351917. 65660. 8448. 311777714. 04770. 9448. 388414111. 90770. 95449. 3777717150. 99449. 799384313. 1255图3-3 信息息素衰减因子子对算法性能能的仿真结果果为了对蚁群算法法中信息素挥挥发度1-进行选择，必须综合考考虑算法的全全局搜索能力力和收敛速度度两

40、项性能指指标，针对具体问问题的应用条条件和实际要要求，在全局搜索索能力和收敛敛速度两方面面做出合理或折折衷的选择。为为了使算法的的性能比较稳稳定和一致，搜索的全局局性和收敛速速度都比较好好，通过上述实实验可以知道道要想得到好好的结果本文文建议=0. 5（1-=0. 5）。3.5 总信信息量在蚁群模型中总总信息量Q为为蚂蚁循环一一周时释放在在所经过的路路径上的信息息素总量一般般的理解是：总信息量QQ越大则在蚂蚂蚁已经走过过的路径上信信息素的累积积加快，可以加强蚁蚁群搜索时的的正反馈性能能，有助于算法法的快速收敛敛。由于在蚁蚁群算法中各各个算法参数数的作用实际际上是紧密耦耦合的，其中对算法法性能起

41、着主主要作用的应应该是信息启启发式因子 、期望启启发式因子 和信息残留留常数等三个参数数。总信息量量Q对算法性性能的影响则则有赖于、和三个参数的的配置以及算算法模型的选选取，例如在蚁周周模型和蚁密密模型中总信信息量Q对算算法性能的影影响情况有较较大的差异。总总信息量对蚁蚁周模型蚁群群算法的性能能没有明显的的影响，一般取Q =10010。3.6 本章章小结本章通过大量实实验说明了信信息素残留因因子1-、信息启发发式因子、期望启发发式因子、信息素强强度Q、蚂蚁蚁数目m等都都是非常重要要的参数，其选区方式式和选区原则则直接影响到到蚁群算法的的全局收敛性性和求解效率率，还通过实验验得出这些参参数的选择

42、规规律，并提出了这种“四步走”来选择蚁群群算法最优组组合参数的有有效方法：(1)确定蚂蚁蚁数目m，根据 城市市规模 / 蚂蚁数目 1/422/5的选择择策略来确定定蚂蚁的总数数目。(2)参数微调调，即调整数值值范围较小的的信息素残留留因子1-（以0. 1为单位位调整），要想得到好好的结果本文文建议1-= 0. 5。(3)参数中调调，即调整数值值范围适中的的信息启发式式因子、期望启发发式因子（以1为单单位调整），并且和要使用组合合方式才可以以得到较理想想的解，要想得到好好的结果本文文建议 =1， =5。(4)参数粗调调，即调整数值值范围较大的的信息素强度度Q参数（以以10或更大大的数为单位位调整

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

44、算法法相比，ASelitte算法在信信息素更新时时加强了对全全局最优解的的利用，其信息素更更新策略为： (0, 1) (4. 1) (4. 2) (4. 3) (4. 4)其中*ijj 为最优蚂蚂蚁在边(ii, j)上上增加的信息息素量，为最优蚂蚁蚁数，Lgb 为全局局最优解。4.1.2 蚁群系统蚁群系统（Annt Collony SSystemm，简称 ACCS）11是 AS 最成功的后后续算法之一一，与 AS 算法的主要要区别在于：（1）在选择下下一座城市时时，ACS 算算法更多地利利用了当前的的较好解；（2）只在全局最优解所属的边上增加信息素；（3）每次当蚂蚁从城市 i 转移到城市 j 时，边 ij 上的信息素将会适当的减少。4.1.3 最大-最小小蚂蚁系统MAX-MINN Ant Systeem 12从另外的角角