2022年蚁群算法的TSP问题求解策略分析研究 .pdf

《2022年蚁群算法的TSP问题求解策略分析研究 .pdf》由会员分享，可在线阅读，更多相关《2022年蚁群算法的TSP问题求解策略分析研究 .pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、I / 24 基于蚁群算法的TSP问题求解策略研究摘要TSP 问题是计算机网络、路由规划中的经典问题。而蚁群优化算法作为高效的计算智能的方法，在离散优化领域有着十分广泛的应用，其中最为经典的是最优回路求解问题。因此，本文在分析蚁群算法发展现状的基础上，针对TSP 问题的求解策略，来深入分析蚁群基数的设置对收敛效率的影响。最后通过 MATlAB 编程工具运行相关代码，并得到相应的TSP问题解。实验结果表明：随着蚁群基数的增加，TSP 问题求解的时间也会线性增加；当蚁群基数大于等于 TSP 问题的结点个数的时候， TSP 问题的解才会保持稳定且趋近于蚁群基数与节点个数相等时的TSP问题的解。关键字

2、蚁群算法蚁群基数 TSP精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 24 页II / 24 Research on the TSP Solution based on Ant Colony OptimizationAbstractThe TSP problem is a classic problem in computer network, route planning.And the ant colony optimization algorithm as an efficient method of computational

3、 intelligence, has the extremely widespread application in the field of discrete optimization, the most classic is the optimal circuit to solve the problem. Therefore, this article on the basis of analyzing the current situation of the development of ant colony algorithm, TSP problem solving strateg

4、y, to analyze ant colony base Settings affect the convergence efficiency. Finally through MATlAB programming tools run the code, and get the corresponding TSP problem solution. The experimental results show that with the increase of base of ant colony, TSP problem solving linear time will also grow

5、。 when ant colony cardinality is greater than or equal to the node number of the TSP problem, the solution of the TSP problem will keep stable and tend to base of ant colony and TSP problem solution of node number is equal. Key Words Ant colony optimization Thebase of ant colony TSP 精选学习资料 - - - - -

6、 - - - - 名师归纳总结 - - - - - - -第 2 页，共 24 页III / 24 目录1引言.1 1.1TSP问题简述及其历史 .1 1.2TSP问题的意义及求解方法 .1 1.3蚁群算法的前景和意义 .2 1.4蚁群算法的产生与发展 .2 1.5蚁群算法的现状 .3 1.6本文的研究内容 .3 1.7本文的组织结构 .4 2蚁群算法 .5 2.1蚁群算法的基本原理 .5 2.2蚁群算法的基本流程 .6 2.3蚁群优化算法的改进版本 .7 3 实验设计与分析 .11 3.1 实验假设 .11 3.2 实验设计 .11 3.3 实验结果及结果分析 .12 结论.19 致谢语 .

7、20 参考文献 .21 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 24 页1 / 24 1引言1.1 TSP问题简述及其历史旅行商问题 Traveling Salesman Problem, TSP）：假设一个旅行商人想要去拜访若干个城市，每个城市只经过一次，并且最终要回到他出发时所在的那个城市，为使整个拜访过程所走的路径最少，商人必须规划出一条最短的旅行路线。TSP问题的历史悠久，最早的描述是1759 年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，如何做到每个方格都走访并只走访一次之后回到起点位置。 TSP 问题最

8、早由美国RAND 公司于 1948 年引入到计算机领域，目前已在网络路由、路径规划等有着十分广泛的应用。1.2TSP问题的意义及其求解方法优化问题是信息领域的关注热点，其中组合优化问题是最常见的优化问题之一。目前很多工程上的问题都可以抽象为对应的组合优化问题，如：集成电路的布控、 GPS导航、网络路由、交通网等都需要用到优化知识。TSP 问题是组合优化问题的典范，对TSP 问题的大部分研究成果可以成功地应用到其他的组合优化问题上，TSP 问题已经成为测试新组合优化算法的标准问题。传统的TSP问题的解法只适用于小搜索空间的TSP问题，并且有的算法还表现出不错的精确性。这些方法主要有：迪杰斯特拉d

9、ijkstra）算法、弗洛伊德,以其分布式并发性、正反馈、鲁棒性强、收敛速度快、易获得全局最优解等特点引起越来越多国内外学者的关注，成为目前国内外启发式算法研究的热点和前沿问题2。目前 蚁群算法已成功将其应用在 TSP问题的求解中。1.3蚁群算法的前景和意义蚁群算法作为一种全局最优化的搜索算法，同遗传算法一样来源于大自然的启示，并且也同样拥有者良好的搜索性能。不同的是，蚁群算法通过模拟蚂蚁觅食的过程，是一种天然的解决离散组合优化问题的方法，在解决经典典型组合优化问题，如旅行商问题(Traveling Salesman Problem, TSP、车辆路径问题 (Vehicle Routing P

10、roblem, VRP、车间作业调度问题(Job-shop Scheduling Problem, JSP 和动态组合规划问题如通信领域的路由器问题中均得到了成功的应用。目前针对蚁群算法在数学理论、算法改进、实际应用等方面的研究是当前国内外研究的热点。1.4 蚁群算法的产生与发展ACO 是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo等人3于 1991 年在第一届欧洲人工生命会议( European Conference on Artificial Intelligence, ECAI上提出，其灵感来源于蚂蚁在觅食过程中发现路径的行为。蚁群算法是一种模拟进化算法，与遗传算

11、法、粒子群算法、免疫算法等同属于仿生优化算法。第一种 ACO 算法是蚂蚁系统 (Ant System, AS，该方法是以NP-Hard 的TSP 问题作为应用实例提出的。AS 算法初步形成的时候虽然能够找到问题的优精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 24 页3 / 24 化结果，但是其算法的执行效率并不优于其他传统算法，因此ACO 并未受到国际学术界的广泛认可，在刚提出的那五年时间里面有关方面的研究也处于停滞不前的状态。直到1996 年 Dorigo 的 Ant System：optimization by a colony

12、 of cooperating agents 一 文4正 式 在 IEEE Transaction on System， Man， and Cybernetics 上发表。这篇文章详细的介绍了AS 的基本原理和算法流程，并对AS 提出了三个版本：蚂蚁密度(ant-density、蚂蚁数量 (ant-quantity和蚂蚁圈( ant-cycle。目前 AS 一般特指蚂蚁圈，前两者由于性能不佳导致关注度降低。Dorigo 还在该文中将AS 的性能与众多算法，如遗传算法、模拟退火、禁忌搜索等算法进行比较，发现在大多数的情况下AS 的寻优能力是最佳的。这是蚁群优化算法发展历史上的一个里程碑，从此，A

13、CO 在国内外受到了越来越多的关注。1.5蚁群算法的现状蚁群算法的改进策略包括精华蚂蚁系统( Elitist AS, EAS、最大最小蚂蚁系统( MAX-MIN AS , MMAS 、基于排列的蚂蚁系统 ( rank-based AS , ASrank等，他们大多是在 AS 上直接操刀改进。在1997 年，ACO 的创始人 Dorigo 提出了一种大幅度改动 AS 特征的算法蚁群系统(Ant Colony System, ACS5。实验结果表明 ACS 的性能明显优于AS，之后蚁群算法继续发展，新的蚁群扩展算法不断出现。到了 21世纪，各种连续算法的出现，更是扩大了蚁群算法的领域。1.6本文的

14、研究内容TSP 问题作为蚁群算法诞生之初所研究的第一个典型的离散组合优化问题，在蚁群算法的发展史中占有不可替代的位置，本文主要基于ACO 的蚁群基数来研究特定的 TSP问题，通过实验分析得到求解该TSP问题的最佳蚁群基数。1.7 本文的组织结构精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 24 页4 / 24 本文主要由以下三个章节组成：第一章引言。主要介绍TSP 问题、 TSP 问题的意义及求解方法、蚁群算法的产生和发展、现在的研究情况、已经取得的成功和以后发展的方向，以及本文主要研究的内容。第二章蚁群算法。介绍蚁群算法的基本原理和

15、基本流程，然后再简要介绍一下当下的几种较流行的ACO 改进算法和 ACS 的工作流程。第三章实验设计与分析。包括实验假设的提出、实验步骤的设计、实验结果的处理分析、得出结论。在文章的最后，将会对本文做一个总结。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 24 页5 / 24 2蚁群算法2.1 蚁群算法的基本原理仿生学家通过长期的研究和实验得出：蚁群在觅食过程中会产生一种化学物质信息素 (pheromone 。蚂蚁在寻找食物的过程中选择的路径往往是随机的，在沿着路径寻找的过程中，他们一边释放自身的信息素，一边感知当前地面上的信息素浓度

16、，并倾向于向高信息素浓度的方向前进。因为信息素由蚂蚁自身释放，所以它就充当了蚁群内部间接通信的物质。由于较短路径上的蚂蚁往返时间比较短，所以在单位的挥发时间内，经过的蚂蚁数量比较多，留下的信息素自然也比较浓，因此后面的蚂蚁在经过的时候就会根据信息素的浓度而选择较短的路径前进。这种正反馈机制会使得蚁群所找到的最短路径上信息素的浓度越来越浓，而其他的路径则会随着信息素的慢慢挥发而被淘汰，最终所有的蚂蚁都会沿着最短路径前进。有生物学家将蚁群上述行为描述成以下三种机制：选择机制：信息素越多的路径，被选中的概率越大。更新机制：路径上面的信息素会随着蚂蚁的经过而增加，同样也会随着时间的推移而挥发消失。协调

17、机制：蚂蚁之间实际是通过分泌物来相互通信、协同工作的。此外，蚁群的自适应能力特别强，假设在路径上突然出现障碍物，蚁群也能够绕过障碍并很快重新探索出一条新的最优路径。蚁群算法正是充分运用了这三种机制和一群的自适应力，使之具备强大的发现最优解的能力。2.2蚁群算法的基本流程精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 24 页6 / 24 前面已经简要介绍了TSP问题，接下来我先将TSP 问题以较专业的语言再进行简单描述，然后再详细介绍AS 算法对 TSP的求解流程。TSP 问题是指在具有N 个城市节点的集合中找到一条最短的回路，这条回路

18、必须从一个节点出发，遍历该节点集里面的所有节点，并最终回到初始节点( 已知任意两个节点之间的欧几里德距离，这样的回路也称之为哈密顿回路，如下图所示： ( a属于较简单的TSP 问题， ( b的节点较多，求解也相对复杂很多。图 2-1 TSP问题示意图AS 算法对 TSP问题求解主要有两大步骤：路径构建和信息素更新。1. 路径构建每一只蚂蚁都随机选择一个城市节点作为出发城市，每到达一个城市后，更新自己的路径记忆向量，记kR，来存放该蚂蚁依次走过的城市节点，确保不会走已经走过的节点，对于还没有走过的城市节点按照随机比例规则：otherjiJjuiuijijijipkiJkk,0,)(2-1随机选择

19、出一个作为该蚂蚁下一步要到达的城市节点。其中，jipk,表示蚂蚁k从i城市节点走向j城市节点的概率。iJk表示当前城市节点i可以直接到达 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 24 页7 / 24 且还未走过的城市节点集。ji,表示能见度，ijdji1,，ijd表示城市节点i与j之间的距离。ji,表示城市节点i，j连线间的信息素浓度，在算法的初始化时，问题空间上的信息素会被初始化为一个相同的值。和是两个预先设置好的参数，用来调节信息素浓度和能见度之间的相对重要程度6。2信息素更新当所有蚂蚁都遍历过这些城市节点后，问题空间上所有

20、路径的信息素都会发生挥发，所以我们要对路径上的信息素进行更新，以突出较短的路径，摒弃较差的路径，信息素按照以下公式7进行更新：(2-2 这里，m表示蚁群的数量，是信息素的挥发率，并有10；),(jik表示蚂蚁k在本次循环中经过城市节点i和j间的连线时留下的信息素量，在jik,的计算公式中：Q是常数，kL表示蚂蚁k本次循环所经过路径的总长度。2.3蚁群优化算法的改进版本蚁群算法虽然具有并行式启发机制、鲁棒性强、搜索能力好、容易与其他启发式算法结合使用等优点，但同样也具有搜索时间过长、容易陷于局部最优解等突出的缺点。针对这些缺点，众多国内外学者在蚁群算法的改进上做了大量研究工作，也取得不菲的成果：

21、1. 精华蚂蚁系统 ( EAS EAS 是第一次基于基础AS 上改进的 ACO8，它在原 AS 信息素更新的规则中增加了一个对至今最优路径的强化手段，即在每一轮搜索完成后，对当前搜索到的最优路径 ( 用bT来表示 增加额外的信息素。 EAS 中信息素的更新公式mkkjijiji1,).().1 (),(其他, 0),( ,/,kkkRjiLQji精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 24 页8 / 24 otherTjiLQjiotherRjiLQjijijikjijibbbkkkbkk，上在路径0),( ,/),(, 0)

22、,( ,/),(),(),()(),().1 (),(1otherTjiLQjiotherRjiLQjijiejijijibbbkkkmkbk,0,0,.1,1上在路径如下：(2-3 式(2.3中除了式 (2.2中的各个符号意义外，新增了jib,并定义了参数e作为jib,的权值；bL表示至今最优路径的长度。可见，在EAS 算法中每一次迭代后属于bT边的信息素的增量为bLeQ。通过引入这种信息素强化的操作会起到引导蚂蚁搜索的功能，加快算法的收敛速度。 Dorigo 等人的实验也已经证明了EAS 有着较 AS 求解更高的精度和更快的速度。2.基于排列的蚂蚁系统 (ASrank虽然 EAS 在解 T

23、SP问题上的求解质量较AS 来之高，但解元素之间的相互联系也减少了，导致选择概率也相对减少了，使得在搜索过程中更容易聚集在局部最优解的附近，从而阻碍了对更优解的进一步探索9。ASrank较 EAS 的不同之处在于，在每一轮的迭代完成之后，选取至今最优蚂蚁和本轮排名前1w只蚂蚁，并且只允许它们释放信息素每只蚂蚁的信息素释放量则依赖于它们本轮的排名。具体的信息素更新公式如下：(2-4 从以上公式可以看出：至今最优路径的蚂蚁所释放的信息量最多，然后当前排名 在 前1w位的 蚂蚁 按照排 名的 下降 ，所 释放 的信 息素 也依 次下 降。精选学习资料 - - - - - - - - - 名师归纳总结

24、 - - - - - - -第 11 页，共 24 页9 / 24 Bullnheimer10的实验结果也表明ASrank较之 AS 和 EAS 具备更高的寻优能力和求解速度。3. 最大最小蚂蚁系统 (MMASMMAS 也是在 AS 算法的基础上进行改进，改进的方面有以下四点：(1 每次迭代完之后，只对本次迭代的最优解或者当前全局最优解进行信息素更新。(2 为了避免迭代停滞，限制信息素的取值范围在区间,maxmin内，当max的时，取max；当min时，取min11。(3 信息素初始值为max，并伴随着一个较小的信息素蒸发率，以确保算法初期能够尽可能多的搜索路径。(4 每当系统进入停滞状态，问

25、题空间上的所有边的信息素都将被重新初始化。改进(1正是借鉴于EAS，但又有所不同，在MMAS 中有权对信息素更新的不仅是至今最优的蚂蚁，也可以是本次迭代最优的蚂蚁，两者可能出现交替使用的情况。改进 (1可以确保寻优速度的加快，而改进(2的原因正是害怕因为信息素的增长过快，而导致“早熟”现象，以至于搜索的是一条局部最优解而不是全局最优解。改进(3，会使得算法刚开始执行的时候起点较高，信息素的蒸发又比较慢，且 (2很好的保证了信息素的增长不会过于迅速，因此在算法的初期， MMAS 较 AS、EAS、ASrank有着更好的搜索能力，视野更广阔，所搜结果为全局最优的机会更大。(1、(2、(3的提出可以

26、确保在单次算法执行过程的性能优于AS、EAS、ASrank，而(4的提出则更增强了MMAS 的性能。不论 AS、EAS 还是 ASrank，在算法执行陷入停滞状态时，就会终止运算，而MMAS 在接近或已经进入停滞状态的时候会重新初始化问题空间上的信息素浓度，从而保证了算法的继续搜索。MMAS 是目前最受关注的ACO 算法之一，而它的四项改进规则也频繁地被后续的各种 ACO 算法所借鉴。4. 蚁群系统 (ACSEAS、ASrank以及 MMAS 都是基于AS 算法进行小量的修改得到的，蚁群精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共

27、24 页10 / 24 other,),(),(maxarg0)(SqqjijijiJjk算法则是在 AS 算法上大幅操刀而得到的一种具有全新机制的ACO 算法，它与蚂蚁系统的不同之处主要表现在以下三点：(1 从一个城市到另一个城市的过程中，运用的状态转移规则不同。在ACS 中采用伪随机比例规则：对于每只蚂蚁k, 路径记忆向量kR顺序地记忆了已经走过的城市，设当前蚂蚁k处于城市i，则它要访问的下一个城市(2-5其中，)(iJk表示从城市i可以直接到达但又不在kR中的城市集合。ji,表示能见度，ji,表示城市节点i，j连线间的信息素浓度，用来调节信息素浓度和能见度之间的相对重要程度。q是一个随机

28、数，0q是在1 ,0内的参数，当0qq时有：(2-6 (2 信息素更新采用信息素全局更新规则。只在属于至今最优路径的边进行信息素的更新 (蒸发和释放 。在每轮迭代中，当所有的蚂蚁均完成路径构建后，信息素全局更新规则才可以使用：(2-7 其中，),(bji和分别表示i,j之间的信息素和信息素的蒸发速率。在ACS算法中，信息素的更新只在至今最优路径上进行，故其信息素更新计算的复杂度也降低为nO。(3 新增了信息素局部更新规则。蚂蚁每次经过问题空间的某一边，都会去除该边上一定量的信息素，通过这种方式来增加后续蚂蚁探索其他路径的可能性。局部更新的公式如下：(2-8 其中表示信息素的局部挥发率，满足10

29、；0是信息素的初始值。局部otheriJjuiuijijijipSkiJkk,0,bTjijijiji),(),(.),().1(),(b0.),().1 (),(jiji精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 24 页11 / 24 更新规则大大增加了算法的探索能力，后续蚂蚁会倾向于探索未被探索过的边，有效避免了算法的停滞。3 实验设计与分析TSP 问题虽然是蚁群算法所研究的主流方向和热门方向之一，但是由于蚁群算法的搜索时间长及容易陷于局部最优解等缺点，想要克服这些困难，除了可以选择当下比较先进的算法进行研究之外，还可以针对

30、对应的TSP 问题，去改变算法里面的参数的设置值，依次来达到优化解的效果。本文就是通过研究蚁群的基数变化对求解TSP问题的影响，以此来推断出求解该TSP问题的最佳蚁群基数。3.1实验分析蚁群算法求解TSP 问题：在保持其他条件因素不变的情况下，若改变蚁群的基数，会对求解和时间和解的精确性发生变化，并且变化遵循以下规则：(1 当蚁群的基数增大时，求得的最优解的准确性增大，但求解的时间也会增加；(2 当蚁群的基数减小时，求得的求得的最优解的准确性减小，但求解的时间也会减少；3.2实验设计本实验的TSP 问题的节点设置n=30 个，蚁群基数初始值0m=10，增量精选学习资料 - - - - - -

31、- - - 名师归纳总结 - - - - - - -第 14 页，共 24 页12 / 24 k=10，最大值MAXm=80，其他因素的初始值如下表：表 3-1 蚁群算法各因素对照表参数名对照蚁群算法中的因素初始值alpha1beta5rho0.1Q常系数1Eta1路径长度除了以上那些可以影响求解结果的参数外，还有一些记录参数和常规参数。表 3-2 其余参数对照表参数名参数含义参数取值D路径总距离zeros(n,n Tau 信息素矩阵ones(n,n Table 路径记录表zeros(m,n iter/iter_max 迭代初始值 / 迭代最大值1/200 Route_best 各代最佳路径z

32、eros(iter_max,n Length_best 各代最佳路径的长度zeros(iter_max,1 Length_ave 各代路径的平均长度zeros(iter_max,1 对每个 m 值运行十次，得到十个最短路径d 和时间 t，记录数据，对这些数据进行处理：对d 和 t 分别求平均，并指出当前基数下的最优路径。最后将十个平均值绘成图，通过分析得到求解该TSP问题的最佳蚁群数量。3.3实验结果及结果分析精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 24 页13 / 24 将不同蚁群基数运行程序后得到的最短路径图列出如下：(a

33、 m=10 (b m=20 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 24 页14 / 24 (c m=30 (d m=40 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 24 页15 / 24 (e m=50 (f m=60 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 24 页16 / 24 (g m=70 (h m=80 图 3-1 蚁群基数与其对应最短路径图将分析完后的各组数据进行处理，得到以下结果

34、：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 24 页17 / 24 表 3-3 蚁群基数及其对应的TSP问题解m10 20 30 40 平均路径11027.75 10907.63 10815.06 10818.59 平均时间5.642 10.956 16.295 20.138 最优路径10659.65 10735.31 10475.69 10321.33 m50 60 70 80 平均路径10785.73 10800.37 10838.50 10793.18 平均时间26.025 31.086 35.895 41.121 最优路

35、径10435.35 9950.886 10267.58 9608.489 由上表可知，虽然随着蚁群基数的增大，最短路径也会呈减短的趋势，但是平均路径并未得到大幅度的减小，最优解具有更大的偶然性，所以无法确定所求的最优解是否有效，因此求解的最短路径不能作为求解TSP 问题时考量最佳蚁群基数的一个指标。将最短路径之外的两个结果在MATLAB工具箱中绘制出来，由于两个结果的数量级相差较大，为方便观察，将两个结果分别绘图如下：(a m-t (bm-d 图 3-2 蚁群基数与最优路径和搜索时间关系图分析图 3-2：随着蚁群数量从10到 80 有规律地递增，算法的搜索时间也几乎呈线性增长；而在寻优方面，在

36、蚁群数量从10 递增到 30 的过程中，所寻的平均最优路径的质量有着明显的提高，但是当蚁群数量继续增加时(30-80，所寻的平均最优路径基本保持在一定范围内上下波动，无明显变化。虽然在m=50和 m=80 两处的平均最优路径较m=30 处的平均最优路径有所改善，但变化不大，且所用搜索时间更长，因此，对于该TSP 问题而言，最佳蚁群基数是m=30。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 24 页18 / 24 据此可以得出：对于一个特定TSP问题，蚁群基数与求解该TSP问题所需时间呈线性相关的关系，即当蚁群基数增大时，求解TSP

37、 问题所需时长也会出现类似线性的增加，反之亦然。当蚁群基数m所要研究的TSP 问题的结点个数n时，求解能力与蚁群基数呈负线性相关的关系, 2005，33(2： 139-143. 3 A Colorni,MDorigo,VManiezzo. Distributed optimazation by ant coloniesC.Peoceedings of 1st European Conference on Artificial Life,1991：134-142. 4 M Dorigo,VManiezzo,AColorni.Ant System ： optimization by a colon

38、y of cooperating agentsJ.IEEE Trans. on System，Man,and Cybernetics-part B Cybernetics,1996,26(2 ：19-41. 5 M Dorigo,L M Gambardella. Ant colonies for the traveling salesman problem.J Bio Systems,1997,43(2）： 73-81. 6 高海昌 ,冯博琴 , 朱利 . 智能优化算法求解TSP 问题 J . 控制与决策 , 2006,21(3： 241-247. 7 董萍 . 基于蚁群算法求解TSPJ. 无

39、锡职业技术学院学报, 2008,7(5：34-36.精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 24 页21 / 24 8 M Dorigo. Optimization,Learning and Natural AlgorithmsD. Department of Electronics ，Politecnicodi Milano,1992. 9任瑞春 . 基于排序加权的蚁群算法D . 大连：大连海事大学，2006. 22-25.10 BBullnheimer,R F Hartl,C Strauss. A new rank based version of the Ant System:a computational studyJ. Central European Journal for Operations Research and Economics,1999,7(1 ：25-38. 11 唐 增 明 , 蒋 泰 . 一 种 改 进 的 动 态 自 适 应 最 大 - 最 小 蚁 群 算 法 J . 计 算 机 与 现 代化, 2008,15(3：90-92.精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 24 页