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

I / 30 摘要群智能是近年来人工智能研究的一个热点话题。蚁群算法作为群智能算法的一个热点，是意大利学者M. Dorigo 通过模拟蚁群觅食行为提出的。本文首先介绍了群智能，然后详细介绍蚁群算法原理及其优缺点。接着依据大量实验对参数 m、Q 的选择进行研究，得出其选择规律，并在以前学者“三步走”的基础上提出了一种“四步走”的有效方法来选择蚁群算法最优组合参数，然后对蚁群改进算法进行分析，同时以实验的方式对这几种算法各自求解 TSP问题的性能进行了对比分析，得出性能结果排名，并发现当TSP 问题最优解相同时还可以依据其他性能 when the most superior result of TSP question optimal solution is same. Finally, this paper also has carried on the optimization and the improvement to the visible programming of ChenYe s“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. Key words：Swarm intelligence。 Ant colony algorithm。 Parameter Selection 。 TSP。Visualization 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 30 页III / 30 目录1 绪论 1 1.1 引言 1 1.2 群智能 1 1.3 蚁群算法的提出 2 1.4 本文研究工作 2 2 蚁群算法概述 4 2.1蚁群算法基本原理4 2.2蚁群算法的优点与不足5 2.3 本章小结 6 3 蚁群算法的参数设置研究7 3.1 硬件/软件环境平台 7 3.2 蚂蚁数目对基本蚁群算法的影响7 3.3 信息启发式因子和期望值启发式因子9 3.4 信息素残留系数 10 3.5 总信息量 11 3.6 本章小结 12 4 蚁群算法实验分析 13 4.1 改进的蚁群优化算法13 4.1.1 最优解保留策略蚂蚁系统13 4.1.2 蚁群系统 13 4.1.3 最大-最小蚂蚁系统 13 4.1.4 基于排序的蚂蚁系统14 4.1.5 The Best-Worst Ant System14 4. 2 实验仿真及算法性能比较分析15 4.2.1 硬件/软件环境平台 15 4.2.2 重要参数设置 15 4.2.3 实验结果 15 4.3 本章小结 17 5 可视化编程 18 5.1“ 蚁群算法实验室 ” 的优点与不足 18 5.2最大最小蚁群算法的图形化演示的改进18 5.3本章小结 22 6 结论与展望 23 参考文献 24 致谢 25 附录 26 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 30 页1 / 30 1 绪论自蚁群算法提出以来 ,就引起了国内外学者的广泛关注，提出了很多改进算法。参数的设置直接影响到算法的性能，所以对参数设置的研究越来越重要，而目前对它的研究大多还处于实验分析阶段。1.1 引言随着人们对生命本质的不断了解，生命科学也以前所未有的速度迅猛发展，使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索起新的非经典计算途径。在这种背景下，社会性动物的自组织行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的“群智能”。受蚂蚁总能找到一条从蚁巢到食物源的最短路径的启发，意大利学者M. Dorigo 与 20 世纪 90 年代提出了一种新型的智能优化算法蚁群优化算法 群体中相互合作的个体是分布的(Distributed，这样更能够适应当前网络环境下的工作状态。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 30 页2 / 30 (2 没有中心的控制与数据，这样的系统更具有鲁棒性(Robust，不会由于某一个或者某几个个体的故障而影响整个问题的求解。(3 可以不通过个体之间直接通信，而是通过非直接通信进行合作，这样的系统具有更好的可扩充性(Scalability。(4 由于系统中个体的增加而增加的系统通信开销在这里是十分小的，系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性 (Simplicity 。1.3 蚁群算法的提出目前，群智能理论研究领域包括两种主要算法：蚁群算法(Ant Colony Optimization ， 简 记 ACO 和 粒 子 群 算法 (Particle Swarm Optimization ， 简 记PSO。而以蚁群算法为代表的群体智能已成为当今分布式人工智能研究的一个热点，它是由意大利学者M. Dorigo、V. Maniez-zo、A. Colorini3,4,5等人从生物进化机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为后，于1991年首先提出的，也叫蚂蚁系统Ant System，AS）。 M. Dorigo等人充分利用蚁群搜索食物的过程与著名的旅行商问题Traveling Salesman Problem）之间的相似性，吸收了蚂蚁的行为特征，设计虚拟的“蚂蚁”摸索不同的路线，并留下会随时间逐渐消失的虚拟“信息量”2。虚拟的“信息量”会挥发，当蚂蚁每次随机选择要走的路径时，倾向于选择信息量比较浓的路径。根据“信息量浓度更近”的原则，既可选择出最佳路线。虽然蚁群算法的研究时间不长，但初步研究已显示它在求解复杂优化问题方面具有很大优势，特别是1998年在比利时布鲁塞尔专门召开了第一届蚂蚁优化国际研讨会后，现在每两年召开一次这样的蚂蚁优化国际研讨会。这标志着蚁群算法的研究已经得到国际上的广泛支持，使得这种新兴的智能进化仿生算法展现出了勃勃生机6。1.4 本文研究工作本文围绕蚁群算法的原理、改进及其应用展开研究，全文共分六章，各章内容安排如下：第一章：绪论本章首先对群智能进行介绍，然后阐述蚁群算法产生的背景。第二章：蚁群算法概述本章详细介绍蚁群算法原理及其优缺点。第三章：蚁群算法的参数设置研究精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 30 页3 / 30 本章针对参数设置进行大量实验，并对实验结果做出研究分析，得出参数m，Q的选择规律，在此基础上，提出新的有效方法对蚁群算法最优组合参数进行选择。第四章：蚁群算法实验分析本章分析几种改进的蚁群算法，并采用国际上通用的测试问题库TSPLIB中的对称 TSP问题作为测试对象，通过仿真实验对六种算法各自求解TSP 问题的性能进行比较，得出当TSP 问题最优解相同时，可依据其他性能 = CC 为一较小的常数），接下来，每只蚂蚁根据路径上残留的信息素量和启发式信息为： (2. 1 其中， Jk(i= 1 ，2，n- tabuk表示蚂蚁 k 下一步允许选择的城市集合。列表 tabuk记录了蚂蚁k 当前走过的城市。当所有n 座城市都加入到tabuk中时，蚂蚁 k 便完成了一次周游，此时蚂蚁 k 所走过的路径便是 TSP 问题的一个可行解。 (2. 1式中的 ij是一个启发式因子，表示蚂蚁从城市 i 转移到城市 j 的期望程度。在 AS 算法中， ij通常取城市 i 与城市 j 之间距离的倒数。 和分别表示信息素和启发式因子的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据 (2. 3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 30 页5 / 30 其中(0 表示路径上信息素的蒸发系数，1- 表示信息素的持久性系数； ij表示本次迭代边 ij 上信息素的增量。 kij表示第 k 只蚂蚁在本次迭代中留在边ij 上的信息素量。如果蚂蚁k 没有经过边 ij，则 kij的值为零。kij表示为： (2. 4 其中， Q 为正常数， Lk表示第 k 只蚂蚁在本次周游中所走过路径的长度。M. Dorigo 提出了 3 种 AS 算法的模型 7，式(2.4 称为 ant-cycle，另外两个模型分别称为ant-quantity 和 ant-density，其差别主要在(2. 4 式，即：在 ant-quantity 模型中为：(2. 5 在 ant-density 模型中为：(2. 6 AS 算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。实验结果表明，ant-cycle 模型比 ant-quantity 和 ant-density 模型有更好的性能。这是因为ant-cycle 模型利用全局信息更新路径上的信息素量，而ant-quantity 和ant-density 模 型 使 用 局 部 信 息 。 AS 算 法 的 时 间 复 杂 度 为 (NC*n2*m ，算法的空间复杂度为S(n=O(n2+O(n*m ，其中 NC表示迭代的次数， n 为城市数， m 为蚂蚁的数目。2.2 蚁群算法的优点与不足众多研究已经证明AS 算法具有很强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质上并行的算法。它有如下优点8：(1 较强的鲁棒性：对蚁群算法模型稍加修改，便可以应用于其它问题。(2 分布式计算：蚁群算法是一种基于种群的进化算法，具有本质的并行性，易于实现。(3 易于与其他方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。同时它也存在一些缺陷：(1限于局部最优解，从算法解的性质而言，蚁群算法也是在寻找一个比较精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 30 页6 / 30 好的局部最优解，而不是强求是全局最优解。(2工作过程的中间停滞问题较长的搜索时间，尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但对于目前计算机网络的实际情况，还是需要较长的搜索时间。虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓解这一问题，但是对于大规模复杂的计算机网络，这还是一个很大的障碍。2.3 本章小结本章主要介绍了蚁群算法基本原理，并针对其优缺点，进行了介绍和讨论。蚂蚁通过释放一种特殊的分泌物- 信息素来寻找路径，蚂蚁个体之间也通过信息素进行交流与合作。蚁群算法的优势主要体现在鲁棒性，分布式，移植性等方面，而其缺陷，就目前来说，主要在局部最优，工作停滞，搜索时间长等方面。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 30 页7 / 30 3 蚁群算法的参数设置研究蚁群算法在 TSP 问题应用中取得了良好的效果，但也存在下列不足：(1如果参数 、 、 、m、Q等设置不当，会导致求解速度很慢且所得解的质量特别差；(2 基本蚁群算法计算量大，求解所需的时间较长；(3 基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环次数的条件下很难实现这种情况。另一方面，在其他的实际应用中，如图像处理中寻求最优模板问题，并不要求所有的蚂蚁都能找到最优模板，而只需要一只找到即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。目前，对基本蚁群算法的参数设置和属性的研究大多还处于实验阶段，M. Dorigo 3,4等人通过大量的实验对蚂蚁系统的参数和基本属性进行了探讨。讨论的参数包括：m 蚂蚁数目； 信息素的相对重要程度； 启发式因子的相对重要程度； 信息素蒸发系数 表示信息素的持久性系数）；Q 蚂蚁释放的信息素量。在实验中，为了观察某个参数对算法性能的影响，在测试该参数时，其它参数取缺省值。各参数的缺省值为m= n*1/4本文中为 21），=1， =5， = 0. 5，Q =100。在实验中，本实验每组数据实验5次取平均和最优作比较，实验中所用的TSP 问题数据来源于 Eil51 城市问题，迭代次数 100次。3.1 硬件/ 软件环境平台本实验采用的硬件 /软件环境分别为： CPU 2. 4GHz，内存 256 M ，硬盘容量80G，安装的是Microsoftwindows XP就可以提高蚁群算法的全局搜索能力以及算法的稳定性；但是，蚂蚁数目增大后，会使大量的曾被搜索过的解(路径上的信息量的变化比较平均，信息正反馈的作用不明显，搜索的随机性尽管得到了加强，但收敛速度减慢；反之，子集较小(即蚁群数量少 ，特别是当要处理的问题规模比较大时，会使那些从来未被搜索到的解(路径 上的信息量减小到接近于0，搜索的随机性减弱，虽然收敛速度加快，但会使算法的全局性能降低，算法的稳定性差，容易出现过早停滞现象。关于蚁群算法中蚂蚁数量m 的选择，也应该综合考虑算法的全局搜索能力和收敛速度两项指标，针对具体问题的应用条件和实际要求，在全局搜索能力和收敛速度两方面作出合理或折衷的选择。关于蚂蚁数目 m对算法性能的影响及其在实际应用中的选择，本文通过计算机仿真实验来分析和确定，本文使蚂蚁数目变化为5、7、9、11、13、15、17、19、21、23、25、27、29、31，蚂蚁数目 m对算法性能的影响仿真结果如表3-1和图3-1所示。表 3-1 蚂蚁数目 m对算法性能的影响的结果蚂蚁数目最优 最短）路径长度运行的时间 s）5463. 9870768. 8287 465. 009199 14. 11 9 457. 001478 9. 781 11 453. 741327 13. 187 13 452. 822716 14. 172 15 456. 116011 13. 531 17 451. 117321 12. 75 19 445. 624177 14. 187 21 446. 078695 13. 188 23 447. 001731 13. 921 25 452. 299202 13. 11 27 446. 078695 21. 468 29 451. 223204 14. 171 31 450. 776659 13. 515 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 30 页9 / 30 图 3-1 蚂蚁数目m 对算法性能的影响的仿真结果关于蚁群算法中蚂蚁数量m 的选择，要综合考虑算法的全局搜索能力和收敛速度两项指标，针对具体问题的应用条件和实际要求，在全局搜索能力和收敛速度两方面做出合理或折衷的选择，图3-1 为实验所得的结果，其中横轴表示蚂蚁数，纵轴表示发现最优解。从图中可以看出当m 在 1/42/5 之间时，蚁群算法可以找到最优解，通过本实验和其他学者的研究，本文最终得出蚂蚁数目应该在 1/42/5 之间，而且当城市数目规模较小时蚂蚁数目m 应该尽量靠近2/5在指导蚁群搜索中的相对重要程度，期望值启发式因子反映蚂蚁在运动过程中启发信息 (即期望值 ij在指导蚁群搜索中的相对重要程度9。期望值启发式因子 的大小反映了蚁群在路径搜索中先验性、确定性因素作用的强度，其值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大，虽然搜索的收敛速度得以加快，但是，蚁群在最优路径的搜索过程中随机性减弱易于陷入局部最优；而信息启发式因子的大小则反映了蚁群在路径搜索中随机性因素作用的强度，其值越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱，当 值过大也会使蚁群的搜索过早陷于局部最优。蚁群算法的全局寻优性能，首先要求蚁群的搜索过程必须有很强的随机性；而蚁群算法的快速收敛性能，又要求蚁群的搜索过程必须要有较高的确定性。因此两者对蚁群算法性能的影响和作用是相互配合、密切相关的。要想得到好的结果应该适当选择 和 的取值范围，一般 =0. 55，=159。因为两者相互配合、密切相关，本文对 和采用组合方式讨论其对蚁群算法性能的影响。取为0. 5、1、2、5，为1 、2、5，进行组合仿真实验，实验结果如表3-2和图3-2所示。表 3-2 和 组合方式对算法性能结果信息素浓度影响力参数a启发式信息影响力参数b最优 ，而就是信息素残留系数。蚁群算法与遗传算法等各种模拟进化算法一样，也存在着收敛速度慢、易于陷入局部最优等缺陷。而信息素挥发度1-的大小直接关系到蚁群算法的全局搜索能力及其收敛速度：由于信息素挥发度1-的存在，当要处理的问题规模比较大时，会使那些从来未被搜索到的路径(可行解 上的信息量减小到接近于 0，因而降低了算法的全局搜索能力，而且当1-过大时以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力；反之，通过减小信息素挥发度1- 虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低。蚁群算法中信息素挥发度1- 的选择，必须综合考虑算法的全局搜索能力和收敛速度两项性能指标，针对具体问题的应用条件和实际要求，在全局搜索能力和收敛速度两方面作出合理或折衷精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 30 页11 / 30 的选择。为了使算法的性能比较稳定和一致，搜索的全局性和收敛速度都比较好，本文通过计算机仿真实验来分析和确定，本文使信息素残留系数变化为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 信息素衰减因子对算法性能的结果路径上信息素衰减因子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图 3-3 信息素衰减因子对算法性能的仿真结果为了对蚁群算法中信息素挥发度1-进行选择，必须综合考虑算法的全局搜索能力和收敛速度两项性能指标，针对具体问题的应用条件和实际要求，在全局搜索能力和收敛速度两方面做出合理或折衷的选择。为了使算法的性能比较稳定和一致，搜索的全局性和收敛速度都比较好，通过上述实验可以知道要想得到好的结果本文建议=0. 5确定蚂蚁数目 m，根据 城市规模 / 蚂蚁数目 1/42/5 的选择策略来确定蚂蚁的总数目。(2参数微调，即调整数值范围较小的信息素残留因子1-参数中调，即调整数值范围适中的信息启发式因子、期望启发式因子参数粗调，即调整数值范围较大的信息素强度Q 参数以 10 或更大的数为单位调整），已得到较理想的解，要想得到好的结果本文建议Q=100。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 30 页13 / 30 4 蚁群算法实验分析下面对目前最流行的几种蚁群算法进行性能比较分析。4.1 改进的蚁群优化算法为了克服 AS的问题，很多学者对其进行研究，并提出了一些改进措施，下面将介绍五种蚁群优化算法。4.1.1 最优解保留策略蚂蚁系统通过使用最优蚂蚁可以提高蚂蚁系统中解的质量7。在最优解保留策略蚂蚁系统 (4. 1 (4. 2 (4. 3 (4. 4 其中 *ij为最优蚂蚁在边 (i, j 上增加的信息素量， 为最优蚂蚁数， Lgb为全局最优解。4.1.2 蚁群系统蚁群系统 Ant Colony System，简称 ACS）11是 AS 最成功的后续算法之一，与 AS 算法的主要区别在于： 1）在选择下一座城市时，ACS 算法更多地利用了当前的较好解；2）只在全局最优解所属的边上增加信息素；3）每次当蚂蚁从城市 i 转移到城市 j 时，边 ij 上的信息素将会适当的减少。4.1.3 最大-最小蚂蚁系统精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 30 页14 / 30 MAX-MIN Ant System12从另外的角度对AS 进行直接完善：修改了AS 的信息素更新方式，仅将每一代中的最好个体所走路径上的信息量进行调整，加快收敛速度，并将各条路径上的信息素浓度被限制在tmin,tmax范围内，这样就可以有效的避免某条路径上的信息量远大于或远小于其余路径情况的发生，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散，加快收敛速度。另外，信息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力，是目前解决TSP、QAO 等问题最好的蚁群算法。4.1.4 基于排序的蚂蚁系统基于排序的蚂蚁系统 L2(t Lm(t，并根据路径长度赋予不同的权重，路径长度越短权重越大。全局最优解的权重为w，第 r 个最优解的权重为max0,w-r ，按3. 19）式更新各路径上的信息素： 其中， rij(t=1/ Lr(t，gbij (t=1/ Lgb 4.1.5The Best-Worst Ant System,BWAS BWAS 模型试着用进化算法概念提高ACO 模型的性能，提出的BWAS 用的是 AS 转移规则：(4. 6 rs是边界 是留下来被蚂蚁K访问的节点集， ， 实值的权。常用的 AS挥发规则 rs (1- ? rs，? r,s, 0, 1，是信息素挥发参数。另外，BWAS考虑下面三个新进程的作用，下面就是对他们的深入分析5：性能更新规则：这种规则是基于PBIL 的概率数组更新规则，信息素更新如下所示： (4. 7 f(C(Sglobal-best 是要被全局最好的蚂蚁存放的信息素数量，随着全局最优蚂蚁算法聚集了大量的信息素，依靠形成的解决方案C(Sglobalbest。信息素痕迹突变 ：信 息 素 痕 迹 在 研 究 介 绍 相 异 性 时 遇 到 突 变 ， 就 像 Population-Based Incremental Learning(PBIL14这样，信息素矩阵的每一排被改变，概率Pm如精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 30 页15 / 30 下：(4. 8 它是 0 到 1 之间的随机值，也是当前的迭代，Tthreshold是组成全局最优解决方案的临界的信息素跟踪的平均值，mut(. 是随着迭代记数的增长，变异增强的函数。当与当前最优和最差解决方案不同的临界值的数字比特定的百分比少时，本文要把所有的信息素痕迹矩阵组成更新为T0，然后循环。4. 2 实验仿真及算法性能比较分析同 AS 算法相比，以上算法的共同之处在于加强了对最优解的利用。如在ACS算法和 MMAS 算法中，只有最优解 全局最优或本次迭代最优）所属路径上的信息素允许增强。在RAS算法中，根据每次迭代路经的长短赋予不同的权重，即对较短的路径赋予较大的权重。这样最优解包含的路径将会有更多的机会被下一次选中。但是，加强对最优解的利用将会导致搜索中的停滞现象。在ACS 算法中通过增加局部信息素更新来减少路径上的信息素量，从而使后面的蚂蚁选择该路径的可能性减少；在 MMAS 算法中，通过限制信息量的范围，使路径上的信息量不会小于某一最小值，从而避免了所有蚂蚁选择同一条路经的可能性，即避免了搜索中的停滞现象，下面我们用实验来比较各种算法的优越性。4.2.1 硬件/ 软件环境平台本实验采用的硬件 /软件环境分别为： CPU 3. 0 GHz ，内存 512 M ，硬盘容量 80G，安装的是 Microsoftwindows XPService Pack 2）操作系统，开发平台Microsoft Visual C+ 6. 0 。4.2.2 重要参数设置本实验中重要参数设置如下：信息素浓度影响力参数 ：所有算法 设为1.0 启发式信息影响力参数 ：所有算法 设为5.0 信息素蒸发系数 表示信息素的持久性系数）：所有算法设为0. 51-即为0. 5）。蚂蚁数目 m：本文将 m设为问题规模 n的1/4即m=n*1/4在算法开始时蚂蚁随机分布在各个城市上。此外，对于EAS，精英蚂蚁的数目的个数e取100n为其中TSP问题中后面的数字，如 Eil51中51即为n值）。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 30 页16 / 30 在MMAS 中初始信息素浓度 0设定为与 max相等，路经信息素浓度下限min设定为小于 max的一常数，并且根据式 4. 16进行更新。4.2.3 实验结果表4-1是MMAS ，ACS，EAS，RAS，BWAS 与 AS 算法求解不同 TSP 实例的比较结果 0. 003100 0. 001600 0. 001600 0. 006100 0. 003200 0. 001500 平均总时间 (s 0. 018800 0. 017100 0. 018190 0. 021700 0. 017200 0. 007900 KroA100 最优解21282 21282 21282 21282 21282 21282 迭代次数1 1 1 1 1 1 迭代时间0 0. 015000 0 0. 016000 0 0 平均解21311. 6 21317. 0 21285. 3 21317. 0 21307. 6 21323. 7 平均时间 0. 018800 0. 025000 0. 024900 0. 023500 0. 018800 0. 017200 d198 最优解15858 15853 15829 15836 15847 15847 迭代次数1 1 1 1 1 1 迭代时间0. 016000 0. 031000 0. 016000 0. 032000 0. 015000 0. 025000 平均解15952. 0 16093. 0 16037. 9 15959. 0 16075. 8 16113. 2 平均时间 0. 025000 0. 025000 0. 022000 0. 022000 0. 021800 0. 021800 Lin318 最优解42155 42029 42029 42029 42029 42029 迭代次数5 33 16 14 6 46 迭代时间0. 657000 3. 141000 1. 578000 1. 719000 0. 625000 5. 016000 平均解42209. 9 42088. 3 42098. 2 42087. 2 42101. 2 42117. 7 平均时间 10. 048400 9. 354700 6. 815600 7. 131400 14. 856300 11. 437500 Pcb422 最优解51134 51058 51000 50807 50785 51146 迭代次数45 29 50 50 34 24 迭代时间9. 562000 6. 312000 9. 843000 9. 734000 6. 000000 6. 844000 平均解51222. 0 51151. 1 51104. 7 50922. 9 50927. 4 51238. 9 平均时间 10. 075000 10. 087300 10. 117100 10. 103100 10. 103100 10. 140700 Att532 最优解28146 28113 28138 28055 28096 28112 迭代次数1 1 1 1 1 1 迭代时间0. 516000 0. 468000 0. 563000 0. 453000 0. 469000 0. 531000 平均解28205. 8 28195. 7 28199. 5 28170. 0 28218. 0 28216. 1 平均时间 0. 539000 0. 550000 0. 593280 0. 147000 0. 592200 0. 510300 Rat783 最优解9038 9023 9035 9026 9033 9014 迭代次数1 1 1 1 1 1 迭代时间0. 890000 0. 844000 0. 844000 0. 875000 0. 922000 0. 938000 平均解9066. 7 9063. 9 9062. 9 9050. 2 9054. 5 9053. 1 平均时间 0. 956200 0. 890600 0. 878200 0. 884400 0. 976500 0. 940600 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 30 页17 / 30 Vm1084 最优解242961 242840 242370 242706 240898 243314 迭代次数1 2 3 3 3 2 迭代时间4. 500000 8. 735000 13. 766000 2. 814400 11. 891000 9. 750000 平均解243367. 4 243149. 7 243462. 9 243879. 3 241922. 4 244079. 7 平均时间 12. 710900 12. 386000 11. 768800 10. 768800 10. 762600 12. 645000 Pcb1173 最优解58301 58228 57895 57995 57750 58435 迭代次数4 5 4 5 7 2 迭代时间7. 531000 9. 250000 7. 188000 9. 313000 11. 000000 4. 815000 平均解58443. 5 58401. 9 58217. 2 58295. 3 58002. 0 58660. 9 平均时间 10. 604000 11. 067200 11. 167900 11. 031300 10. 600000 11. 070500 d1291 最优解51555 51482 51213 51483 50997 51758 迭代次数5 4 6 5 5 5 迭代时间8. 359000 7. 314000 11. 087000 9. 125000 8. 652000 11. 641000 平均解51681. 7 51682. 1 51395. 7 51807. 5 51398. 2 52080. 5 平均时间 10. 860900 10. 685900 11. 021900 10. 856000 11. 106300 11. 187400 rl1304 最优解257189 256805 257359 257262 253938 258066 迭代次数2 2 3 1 3 3 迭代时间10. 930000 6. 969000 10. 500000 5. 329070 11. 328000 13. 938000 平均解258689. 6 258796. 4 258393. 7 259087. 8 255995. 6 259374. 5 平均时间 12. 232800 11. 284400 11. 018000 12. 220300 11. 033100 12. 645300 Vm1748 最优解345483 345589 345897 345017 346519 345857 迭代次数1 1 1 1 1 1 迭代时间10. 250000 16. 141000 16. 163000 13. 063000 14. 984000 12. 297000 平均解346484. 6 346600. 6 346851. 6 346660. 5 347064. 3 347207. 4 平均时间 10. 781400 15. 484300 15. 173500 12. 835800 11. 803010 12. 107800 由以上的数据本文可以看出：当问题规模比较小的时候，比较的各种算法的求解的结果比较接近且比较令人满意。但是随着问题规模的逐渐的变大，各算法与目前已知的最优结果的差距也逐渐的增大。但其中，MMAS 、BWAS的求解性能是较好，而没有采用精英策略的基本AS算法性能最差，使用了精英策略的 EAS的求解质量有很大的提高，但还是比MMAS 、ACS、BWAS以及 RAS的性能差。4.3 本章小结本章对 、的选择是依据实验和其他文献得到，m是通过了大量实验得到的规律；此外，本章还对六种蚁群算法原理进行了分析和比较，并以实验的方式阐述了几种蚁群算法各自求解TSP问题的性能，还对各算法的性能进行了对比分析，而且得出当TSP问题最优解相同时可以依据其他性能迭代次数、迭代时间等）得出 TSP问题的最优结果。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 30 页18 / 30 5 可视化编程在上一章中，主要是通过实验对蚁群算法及其优化算法进行性能比较分析，而我觉得用图形可视化来描述算法更直观，所以为了让学者更好的研究蚁群及其改进算法，我觉得可以把以上六种算法集成到一个图形化软件里，实现算法的可视化，下面将介绍我在陈烨设计的“蚁群算法实验室”的基础上做出的修改和完善。5.1 “蚁群算法实验室”的优点与不足陈烨的蚁群算法实验室主要介绍的是最大最小蚁群算法 当输入参数运行的时候，参数不能自动保存，而需要手动输入保存到文本文档中，这些都不方便以后调用这些参数在另外一种算法的集成环境下运行，从而对几种算法进行比较，也不方便在变动城市数目的时候调用这些参数运行，然后对同一算法不同城市之间的运行结果做出比较。(2 虽然在运行时绘出了一些需要研究的图形，但是这些图形也不能自动保存，在下次变动参数运行或者变动城市数目运行时，那些图形就没有了，这样也不便于对参数设置的研究和对几种算法的比较研究。5.2 最大最小蚁群算法图形化演示的改进对于这两个问题，我做出了一些改进，下面将结合截图界面详细介绍：(1 图 5-1 是启动界面。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 30 页19 / 30 图 5-1 启动界面设计此界面主要是为了设计几种算法的集成环境提供一个入口，但需要增加一种算法的时候可以直接在这个界面上加一个按扭，然后加一个模块就可以了。然后在这个界面上加了几个小功能，如一个动态的时钟和一个日历，可以让大家在研究蚁群算法的时候更方便.。(2 图 5-2 是当运行结束后，可以单击“打开抓图窗体”，然后就会弹出“抓图”窗体，以便可以捕捉自己想要保存的图片进行保存。图 5-2 打开抓图窗体(3 当单击抓图窗体中的“抓窗体”后，所抓的图会保存在抓图窗体中的Picture box 里，然后单击保存按扭，则可以自己选择想要保存的路径如图 5-3所示）。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 30 页20 / 30 图 5-3 保存图像4）如果只想抓最优路径演化图，可以单击“抓最优路径图”抓平均路径图、城市及路径状态图、蚂蚁运动图时方法同此图），然后所抓的图就会显示在此界面的图片框中 如图 5-4 所示）。图 5-4