基于蚁群算法的TSP问题求解策略研究.docx

基于蚁群算法的TSP问题求解策略研究摘要 TSP问题是计算机网络、路由规划中的经典问题。而蚁群优化算法作为高效的计算智能的方法，在离散优化领域有着十分广泛的应用，其中最为经典的是最优回路求解问题。因此，本文在分析蚁群算法发展现状的基础上，针对TSP问题的求解策略，来深入分析蚁群基数的设置对收敛效率的影响。最后通过MATlAB编程工具运行相关代码，并得到相应的TSP问题解。实验结果表明：随着蚁群基数的增加，TSP问题求解的时间也会线性增加；当蚁群基数大于等于TSP问题的结点个数的时候，TSP问题的解才会保持稳定且趋近于蚁群基数与节点个数相等时的TSP问题的解。关键字 蚁群算法 蚁群基数 TSPResearch on the TSP Solution based on Ant Colony OptimizationAbstract The TSP problem is a classic problem in computer network, route planning. And the ant colony optimization algorithm as an efficient method of computational 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 strategy, 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; 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 The base of ant colony TSP目录1 引言.11.1 TSP问题简述及其历史.11.2 TSP问题的意义及求解方法.11.3 蚁群算法的前景和意义.21.4 蚁群算法的产生与发展.21.5 蚁群算法的现状.31.6 本文的研究内容.31.7 本文的组织结构.42 蚁群算法.52.1 蚁群算法的基本原理.52.2 蚁群算法的基本流程.62.3 蚁群优化算法的改进版本.73 实验设计与分析.11 3.1 实验假设.11 3.2 实验设计.11 3.3 实验结果及结果分析.12结论.19致谢语.20参考文献.21211 引言1.1 TSP问题简述及其历史旅行商问题（Traveling Salesman Problem,TSP）：假设一个旅行商人想要去拜访若干个城市，每个城市只经过一次，并且最终要回到他出发时所在的那个城市，为使整个拜访过程所走的路径最少，商人必须规划出一条最短的旅行路线。TSP问题的历史悠久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，如何做到每个方格都走访并只走访一次之后回到起点位置。TSP问题最早由美国RAND公司于1948年引入到计算机领域，目前已在网络路由、路径规划等有着十分广泛的应用。1.2 TSP问题的意义及其求解方法优化问题是信息领域的关注热点，其中组合优化问题是最常见的优化问题之一。目前很多工程上的问题都可以抽象为对应的组合优化问题，如：集成电路的布控、GPS导航、网络路由、交通网等都需要用到优化知识。TSP问题是组合优化问题的典范，对TSP问题的大部分研究成果可以成功地应用到其他的组合优化问题上，TSP问题已经成为测试新组合优化算法的标准问题。传统的TSP问题的解法只适用于小搜索空间的TSP问题，并且有的算法还表现出不错的精确性。这些方法主要有：迪杰斯特拉（dijkstra）算法、弗洛伊德（floyd）算法以及一些其他的算法。但是这些算法只适合在小搜索空间的TSP问题中才能得到有效的结果，随着TSP问题中城市数量的增加，搜索空间将呈指数增长，算法的复杂度亦呈指数增长，使我们不能再在有效的时间内得到有效的结果，因此，这些算法并不具备推广性。20世纪50年代中期以来，人们从生物进化的机理中受到启发提出了许多用以解决复杂优化问题的新方法，如遗传算法、模拟退火算法、禁忌搜索算法等，为NP-Hard问题1提供了一条新的路径，尤其是新型启发式算法蚁群算法(Ant Colony Optimization,ACO),以其分布式并发性、正反馈、鲁棒性强、收敛速度快、易获得全局最优解等特点引起越来越多国内外学者的关注，成为目前国内外启发式算法研究的热点和前沿问题2。目前 蚁群算法已成功将其应用在TSP问题的求解中。1.3 蚁群算法的前景和意义蚁群算法作为一种全局最优化的搜索算法，同遗传算法一样来源于大自然的启示，并且也同样拥有者良好的搜索性能。不同的是，蚁群算法通过模拟蚂蚁觅食的过程，是一种天然的解决离散组合优化问题的方法，在解决经典典型组合优化问题，如旅行商问题(Traveling Salesman Problem,TSP)、车辆路径问题(Vehicle Routing Problem,VRP)、车间作业调度问题(Job-shop Scheduling Problem,JSP)和动态组合规划问题如通信领域的路由器问题中均得到了成功的应用。目前针对蚁群算法在数学理论、算法改进、实际应用等方面的研究是当前国内外研究的热点。1.4 蚁群算法的产生与发展ACO是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo等人3于1991年在第一届欧洲人工生命会议(European Conference on Artificial Intelligence,ECAI)上提出，其灵感来源于蚂蚁在觅食过程中发现路径的行为。蚁群算法是一种模拟进化算法，与遗传算法、粒子群算法、免疫算法等同属于仿生优化算法。第一种ACO算法是蚂蚁系统(Ant System,AS)，该方法是以NP-Hard的TSP问题作为应用实例提出的。AS算法初步形成的时候虽然能够找到问题的优化结果，但是其算法的执行效率并不优于其他传统算法，因此ACO并未受到国际学术界的广泛认可，在刚提出的那五年时间里面有关方面的研究也处于停滞不前的状态。直到1996年Dorigo的Ant System：optimization by a colony of cooperating agents 一文4正式在IEEE Transaction on System，Man，and Cybernetics上发表。这篇文章详细的介绍了AS的基本原理和算法流程，并对AS提出了三个版本：蚂蚁密度(ant-density)、蚂蚁数量(ant-quantity)和蚂蚁圈(ant-cycle)。目前AS一般特指蚂蚁圈，前两者由于性能不佳导致关注度降低。Dorigo还在该文中将AS的性能与众多算法，如遗传算法、模拟退火、禁忌搜索等算法进行比较，发现在大多数的情况下AS的寻优能力是最佳的。这是蚁群优化算法发展历史上的一个里程碑，从此，ACO在国内外受到了越来越多的关注。1.5 蚁群算法的现状 蚁群算法的改进策略包括精华蚂蚁系统(Elitist AS,EAS)、最大最小蚂蚁系统(MAX-MIN AS,MMAS)、基于排列的蚂蚁系统(rank-based AS,ASrank)等，他们大多是在AS上直接操刀改进。在1997年，ACO的创始人Dorigo提出了一种大幅度改动AS特征的算法蚁群系统(Ant Colony System,ACS) 5。实验结果表明ACS的性能明显优于AS，之后蚁群算法继续发展，新的蚁群扩展算法不断出现。到了21世纪，各种连续算法的出现，更是扩大了蚁群算法的领域。1.6 本文的研究内容TSP问题作为蚁群算法诞生之初所研究的第一个典型的离散组合优化问题，在蚁群算法的发展史中占有不可替代的位置，本文主要基于ACO的蚁群基数来研究特定的TSP问题，通过实验分析得到求解该TSP问题的最佳蚁群基数。1.7 本文的组织结构本文主要由以下三个章节组成：第一章 引言。主要介绍TSP问题、TSP问题的意义及求解方法、蚁群算法的产生和发展、现在的研究情况、已经取得的成功和以后发展的方向，以及本文主要研究的内容。第二章 蚁群算法。介绍蚁群算法的基本原理和基本流程，然后再简要介绍一下当下的几种较流行的ACO改进算法和ACS的工作流程。第三章 实验设计与分析。包括实验假设的提出、实验步骤的设计、实验结果的处理分析、得出结论。在文章的最后，将会对本文做一个总结。2 蚁群算法2.1 蚁群算法的基本原理仿生学家通过长期的研究和实验得出：蚁群在觅食过程中会产生一种化学物质信息素(pheromone)。蚂蚁在寻找食物的过程中选择的路径往往是随机的，在沿着路径寻找的过程中，他们一边释放自身的信息素，一边感知当前地面上的信息素浓度，并倾向于向高信息素浓度的方向前进。因为信息素由蚂蚁自身释放，所以它就充当了蚁群内部间接通信的物质。由于较短路径上的蚂蚁往返时间比较短，所以在单位的挥发时间内，经过的蚂蚁数量比较多，留下的信息素自然也比较浓，因此后面的蚂蚁在经过的时候就会根据信息素的浓度而选择较短的路径前进。这种正反馈机制会使得蚁群所找到的最短路径上信息素的浓度越来越浓，而其他的路径则会随着信息素的慢慢挥发而被淘汰，最终所有的蚂蚁都会沿着最短路径前进。有生物学家将蚁群上述行为描述成以下三种机制：选择机制：信息素越多的路径，被选中的概率越大。更新机制：路径上面的信息素会随着蚂蚁的经过而增加，同样也会随着时间的推移而挥发消失。协调机制：蚂蚁之间实际是通过分泌物来相互通信、协同工作的。此外，蚁群的自适应能力特别强，假设在路径上突然出现障碍物，蚁群也能够绕过障碍并很快重新探索出一条新的最优路径。蚁群算法正是充分运用了这三种机制和一群的自适应力，使之具备强大的发现最优解的能力。2.2 蚁群算法的基本流程前面已经简要介绍了TSP问题，接下来我先将TSP问题以较专业的语言再进行简单描述，然后再详细介绍AS算法对TSP的求解流程。TSP问题是指在具有N个城市节点的集合中找到一条最短的回路，这条回路必须从一个节点出发，遍历该节点集里面的所有节点，并最终回到初始节点(已知任意两个节点之间的欧几里德距离)，这样的回路也称之为哈密顿回路，如下图所示：(a)属于较简单的TSP问题，(b)的节点较多，求解也相对复杂很多。（a）(b) 图2-1 TSP问题示意图AS算法对TSP问题求解主要有两大步骤：路径构建和信息素更新。1.路径构建每一只蚂蚁都随机选择一个城市节点作为出发城市，每到达一个城市后，更新自己的路径记忆向量，记，来存放该蚂蚁依次走过的城市节点，确保不会走已经走过的节点，对于还没有走过的城市节点按照随机比例规则： (2-1)随机选择出一个作为该蚂蚁下一步要到达的城市节点。其中，表示蚂蚁从城市节点走向城市节点的概率。表示当前城市节点可以直接到达且还未走过的城市节点集。表示能见度，表示城市节点与之间的距离。表示城市节点，连线间的信息素浓度，在算法的初始化时，问题空间上的信息素会被初始化为一个相同的值。和是两个预先设置好的参数，用来调节信息素浓度和能见度之间的相对重要程度6。2信息素更新当所有蚂蚁都遍历过这些城市节点后，问题空间上所有路径的信息素都会发生挥发，所以我们要对路径上的信息素进行更新，以突出较短的路径，摒弃较差的路径，信息素按照以下公式7进行更新：(2-2)这里，表示蚁群的数量，是信息素的挥发率，并有；表示蚂蚁在本次循环中经过城市节点和间的连线时留下的信息素量，在的计算公式中：是常数，表示蚂蚁本次循环所经过路径的总长度。2.3 蚁群优化算法的改进版本蚁群算法虽然具有并行式启发机制、鲁棒性强、搜索能力好、容易与其他启发式算法结合使用等优点，但同样也具有搜索时间过长、容易陷于局部最优解等突出的缺点。针对这些缺点，众多国内外学者在蚁群算法的改进上做了大量研究工作，也取得不菲的成果：1.精华蚂蚁系统(EAS)EAS是第一次基于基础AS上改进的ACO 8，它在原AS信息素更新的规则中增加了一个对至今最优路径的强化手段，即在每一轮搜索完成后，对当前搜索到的最优路径(用来表示)增加额外的信息素。EAS中信息素的更新公式如下：(2-3)式(2.3)中除了式(2.2)中的各个符号意义外，新增了并定义了参数作为的权值；表示至今最优路径的长度。可见，在EAS算法中每一次迭代后属于边的信息素的增量为。通过引入这种信息素强化的操作会起到引导蚂蚁搜索的功能，加快算法的收敛速度。Dorigo等人的实验也已经证明了EAS有着较AS求解更高的精度和更快的速度。2.基于排列的蚂蚁系统(ASrank)虽然EAS在解TSP问题上的求解质量较AS来之高，但解元素之间的相互联系也减少了，导致选择概率也相对减少了，使得在搜索过程中更容易聚集在局部最优解的附近，从而阻碍了对更优解的进一步探索9。ASrank较EAS的不同之处在于，在每一轮的迭代完成之后，选取至今最优蚂蚁和本轮排名前只蚂蚁，并且只允许它们释放信息素每只蚂蚁的信息素释放量则依赖于它们本轮的排名。具体的信息素更新公式如下：(2-4)从以上公式可以看出：至今最优路径的蚂蚁所释放的信息量最多，然后当前排名在前位的蚂蚁按照排名的下降，所释放的信息素也依次下降。Bullnheimer10的实验结果也表明ASrank较之AS和EAS具备更高的寻优能力和求解速度。3.最大最小蚂蚁系统(MMAS)MMAS也是在AS算法的基础上进行改进，改进的方面有以下四点：(1) 每次迭代完之后，只对本次迭代的最优解或者当前全局最优解进行信息素更新。(2) 为了避免迭代停滞，限制信息素的取值范围在区间内，当的时，取；当时，取11。(3) 信息素初始值为，并伴随着一个较小的信息素蒸发率，以确保算法初期能够尽可能多的搜索路径。(4) 每当系统进入停滞状态，问题空间上的所有边的信息素都将被重新初始化。改进(1)正是借鉴于EAS，但又有所不同，在MMAS中有权对信息素更新的不仅是至今最优的蚂蚁，也可以是本次迭代最优的蚂蚁，两者可能出现交替使用的情况。改进(1)可以确保寻优速度的加快，而改进(2)的原因正是害怕因为信息素的增长过快，而导致“早熟”现象，以至于搜索的是一条局部最优解而不是全局最优解。改进(3)，会使得算法刚开始执行的时候起点较高，信息素的蒸发又比较慢，且(2)很好的保证了信息素的增长不会过于迅速，因此在算法的初期，MMAS较AS、EAS、ASrank有着更好的搜索能力，视野更广阔，所搜结果为全局最优的机会更大。(1)、(2)、(3)的提出可以确保在单次算法执行过程的性能优于AS、EAS、ASrank ，而(4)的提出则更增强了MMAS的性能。不论AS、EAS还是ASrank，在算法执行陷入停滞状态时，就会终止运算，而MMAS在接近或已经进入停滞状态的时候会重新初始化问题空间上的信息素浓度，从而保证了算法的继续搜索。MMAS是目前最受关注的ACO算法之一，而它的四项改进规则也频繁地被后续的各种ACO算法所借鉴。4.蚁群系统(ACS)EAS、ASrank以及MMAS都是基于AS算法进行小量的修改得到的，蚁群算法则是在AS算法上大幅操刀而得到的一种具有全新机制的ACO算法，它与蚂蚁系统的不同之处主要表现在以下三点：(1) 从一个城市到另一个城市的过程中，运用的状态转移规则不同。在ACS中采用伪随机比例规则：对于每只蚂蚁,路径记忆向量顺序地记忆了已经走过的城市，设当前蚂蚁处于城市，则它要访问的下一个城市(2-5)其中，表示从城市可以直接到达但又不在中的城市集合。表示能见度，表示城市节点，连线间的信息素浓度，用来调节信息素浓度和能见度之间的相对重要程度。是一个随机数，是在内的参数，当时有：(2-6)(2) 信息素更新采用信息素全局更新规则。只在属于至今最优路径的边进行信息素的更新(蒸发和释放)。在每轮迭代中，当所有的蚂蚁均完成路径构建后，信息素全局更新规则才可以使用：(2-7)其中，和分别表示,之间的信息素和信息素的蒸发速率。在ACS算法中，信息素的更新只在至今最优路径上进行，故其信息素更新计算的复杂度也降低为。(3) 新增了信息素局部更新规则。蚂蚁每次经过问题空间的某一边，都会去除该边上一定量的信息素，通过这种方式来增加后续蚂蚁探索其他路径的可能性。局部更新的公式如下：(2-8)其中表示信息素的局部挥发率，满足；是信息素的初始值。局部更新规则大大增加了算法的探索能力，后续蚂蚁会倾向于探索未被探索过的边，有效避免了算法的停滞。3 实验设计与分析TSP问题虽然是蚁群算法所研究的主流方向和热门方向之一，但是由于蚁群算法的搜索时间长及容易陷于局部最优解等缺点，想要克服这些困难，除了可以选择当下比较先进的算法进行研究之外，还可以针对对应的TSP问题，去改变算法里面的参数的设置值，依次来达到优化解的效果。本文就是通过研究蚁群的基数变化对求解TSP问题的影响，以此来推断出求解该TSP问题的最佳蚁群基数。3.1 实验分析蚁群算法求解TSP问题：在保持其他条件因素不变的情况下，若改变蚁群的基数，会对求解和时间和解的精确性发生变化，并且变化遵循以下规则：(1) 当蚁群的基数增大时，求得的最优解的准确性增大，但求解的时间也会增加；(2) 当蚁群的基数减小时，求得的求得的最优解的准确性减小，但求解的时间也会减少；3.2 实验设计本实验的TSP问题的节点设置n=30个，蚁群基数初始值=10，增量k=10，最大值=80，其他因素的初始值如下表：表3-1 蚁群算法各因素对照表参数名对照蚁群算法中的因素初始值alpha1beta5rho0.1Q常系数1Eta除了以上那些可以影响求解结果的参数外，还有一些记录参数和常规参数。表3-2 其余参数对照表参数名参数含义参数取值D路径总距离zeros(n,n)Tau信息素矩阵ones(n,n)Table路径记录表zeros(m,n)iter/ iter_max迭代初始值/迭代最大值1/200Route_best各代最佳路径zeros(iter_max,n)Length_best各代最佳路径的长度zeros(iter_max,1)Length_ave各代路径的平均长度zeros(iter_max,1)对每个m值运行十次，得到十个最短路径d和时间t，记录数据，对这些数据进行处理：对d和t分别求平均，并指出当前基数下的最优路径。最后将十个平均值绘成图，通过分析得到求解该TSP问题的最佳蚁群数量。3.3 实验结果及结果分析将不同蚁群基数运行程序后得到的最短路径图列出如下：(a) m=10(b) m=20(c) m=30(d) m=40(e) m=50(f) m=60(g) m=70(h) m=80图3-1 蚁群基数与其对应最短路径图将分析完后的各组数据进行处理，得到以下结果：表3-3 蚁群基数及其对应的TSP问题解m10203040平均路径11027.7510907.6310815.0610818.59平均时间5.64210.95616.29520.138最优路径10659.6510735.3110475.6910321.33m50607080平均路径10785.7310800.3710838.5010793.18平均时间26.02531.08635.89541.121最优路径10435.359950.88610267.589608.489由上表可知，虽然随着蚁群基数的增大，最短路径也会呈减短的趋势，但是平均路径并未得到大幅度的减小，最优解具有更大的偶然性，所以无法确定所求的最优解是否有效，因此求解的最短路径不能作为求解TSP问题时考量最佳蚁群基数的一个指标。将最短路径之外的两个结果在MATLAB工具箱中绘制出来，由于两个结果的数量级相差较大，为方便观察，将两个结果分别绘图如下： (a) m-t (b)m-d 图3-2 蚁群基数与最优路径和搜索时间关系图分析图3-2：随着蚁群数量从10到80有规律地递增，算法的搜索时间也几乎呈线性增长；而在寻优方面，在蚁群数量从10递增到30的过程中，所寻的平均最优路径的质量有着明显的提高，但是当蚁群数量继续增加时(30-80)，所寻的平均最优路径基本保持在一定范围内上下波动，无明显变化。虽然在m=50和m=80两处的平均最优路径较m=30 处的平均最优路径有所改善，但变化不大，且所用搜索时间更长，因此，对于该TSP问题而言，最佳蚁群基数是m=30。据此可以得出：对于一个特定TSP问题，蚁群基数与求解该TSP问题所需时间呈线性相关的关系，即当蚁群基数增大时，求解TSP问题所需时长也会出现类似线性的增加，反之亦然。当蚁群基数所要研究的TSP问题的结点个数时，求解能力与蚁群基数呈负线性相关的关系（路径随着的增大而减小）；当蚁群基数超过了TSP问题的节点数之后，这种线性相关的关系将立即消失，并且此时的求解能力将在一定的范围内上下起伏，但逼近于时所得出的结果。因此，要想使一个TSP问题得到稳定有效的求解结果，必须满足：蚁群基数必须不小于所求的TSP问题的结点数；要想快速的求出稳定有效的解，可以使蚁群基数与TSP问题的节点数相等或相近。结论蚁群算法成立至今不过20多年，但它的发展却如此之迅速，从第一个蚁群算法AS的提出，到现在已经出现越来越多更为先进和高效的新一代的蚁群算法。此外蚁群算法的应用也从最初的TSP问题扩展到越来越多的层面。现在，蚁群算法俨然已经成为计算智能领域内不可或缺的一部分。本文通过求解TSP问题来研究蚁群基数对求解的影响，由于算法执行存在偶然性，因此实验的数据必须经过多次量取后求平均来作为该蚁群基数下的实验值，这样能够很大程度上减小偶然性对实验的影响。当然，对于偶然性的处理这并不是最优方法，还有很多更为严谨的方法，比如通过数据处理判断我们所采集的数据是否是可用的，在剔除掉不可用的数据之后在对剩下的数据求平均，以达到更佳的效果。当然，在数据大量的情况下，使用这种方法也会很大地加大对数据处理的工作，从而加强了数据分析的难度。蚁群基数只是蚁群算法中的诸多因素之一，要想在TSP问题上得到更好的解，就必须在其他因素不变的情况下，再研究其他因素的改变对解的影响，从而设定出解决问题的最佳参数，得到最理想的路径。致谢语十分感谢我的指导老师蔡国榕老师对本人悉心的帮助和指导。在该课题论文的完成过程中，从论文选题、文章结构，以及最后的反复修改定稿，这都是在蔡国榕老师细心的点拨指导下进行，这期间凝聚着蔡国榕老师辛勤的汗水和大量的心血。我不是您最出色的学生，而您却是我最尊敬的老师。您不仅是我的论文指导老师，还是我的任课老师，更是我的人生指导老师。您治学严谨，学识渊博，思想深邃，视野广阔，一丝不苟的工作态度以及谦逊和善的人格品质，都深深的影响了我，虽然我以后并不一定像您一样从事教学研究工作，但是您的这些优良品质必将在我的工作和生活中起到很大的帮助。在此，我谨向尊敬的蔡国榕老师致以最真诚的谢意！同时，我也感谢学校、学院为我完成毕业设计所提供的良好的环境。最后，我再一次感谢在我的毕业设计中所有给予我帮助的同学、良师和益友，以及在毕业设计中