《大型TSP问题的蚁群优化规则研究.doc》由会员分享，可在线阅读，更多相关《大型TSP问题的蚁群优化规则研究.doc（70页珍藏版）》请在三一办公上搜索。
1、硕士学位论文大型TSP问题的蚁群优化规则研究Research On Ant Colony Optimization Rules Of Large TSP Problem作者姓名： 专 业：管理科学与工程研究方向：管理科学指导教师： 培养单位：商学院摘要大型TSP问题的蚁群优化规则研究旅行商(Traveling Salesman Problem，TSP)问题，是一个古老并且典型的NP-hard组合优化问题。当TSP问题的规模较小时，通过很多方法都能够快速高效的求出问题的解，但是随着问题规模的不断扩大,所求解的数量也以指数的形式快速增加,因此想要获得理想的解集必然要付出巨大的时间代价或是在短时间内
2、根本无法得到一个理想的结果。TSP问题特别是大型TSP问题的有效求解，不但有着极其重要的理论价值、学术价值，更能帮助解决社会生活中的许多实际的问题，其实用性非常之高。因此，这一难题一直是中外众多研究学者们在不断研究的热点问题。为了在TSP问题的研究上有新的突破，人们开始尝试从一些新的角度来思考并提出新的思路来解决该问题。随着“群智能”思想的提出，一系列以研究TSP问题为基础的智能优化算法相继出现，比如神经网络、遗传算法、模拟退火算法、线性规划算法、蚁群算法等，在对TSP问题的解决上，这些算法都表现出一定的优势，也存在各自的缺点。其中，由于蚁群算法的理论原理和TSP问题的求解过程具有一定的相似性
3、，所以对TSP问题的处理与其他算法相比具有更好的效果。但人们的目标远不止如此，一切可以使该算法更加优化的研究一直在继续着。尽管蚁群算法已经表现出很好的求解性能，但是随着问题规模的放大，算法的弊端就显露无遗。当面对数据量较多的大型TSP问题时，基本蚁群算法或是各种改进算法还是在存着求解效率低、求解的精度小、易于陷入局部最优等问题。针对这一现象，本文通过优化蚁群算法的计算规则提出一了种改进的分段多功能蚁群算法，并以大型TSP问题为对象进行以下研究：（1）介绍并描述了TSP问题及大规模TSP问题的计算复杂性，对其现有的各种算法进行了对比介绍，并分析了他们各自存在的问题。（2）对蚁群算法的产生背景、原
4、理、模型和特征进行了详细的介绍，并针对其优缺点研究展望了它的发展前景与方向。（3）对传统蚁群算法的规则进行优化更新，通过对传统的蚁群算法中的概率选择模型和蚁群的分类规则进行了改进，提出了一种新的算法-分段多功能蚁群算法，并对算法中各个参数的设置做了研究讨论。然后分别选取了小规模TSP问题和大规模TSP问题进行仿真实验。实验结果表明，改进后的算法能够在合理的运行时间内获得较好的全局最优解。（4）对本文的研究工作进行了总结，指出了本文研究的缺点和不足，并展望了蚁群算法今后的研究内容与方向以及改进的蚁群算法在其他领域的应用。关键词：TSP问题，蚁群算法，规则优化AbstractResearch On
5、 Ant Colony Optimization Rules Of Large TSP ProblemThe traveling salesman problem (the Traveling salesman problem, TSP), is an old and typical NP-hard combinatorial optimization problems. If TSPs scale is smaller, many ways are able to quickly and efficiently find the solution of the problem, but as
6、 the expanding of the problems scale , the number of solution also increase rapidly in the form of index, so getting a ideal solution set is bound to spend huge time or in a short period of time there could hardly be a desirable outcome. TSP problem especially for large TSP, its effective problem so
7、lving, not only has an extremely important theoretical value and academic value ,but also of more help to solve many practical problems in social life, its usefulness is very high. Therefore, this problem has been a hot issue for the numerous Chinese and foreign scholars to research. In order to rea
8、lize new breakthroughs in the TSP, people began to think from some new angles and propose new ideas to solve the problem. With the arrival of swarm intelligence, a series of intelligent optimization algorithms which based on the study TSP problem have appeared, such as neural networks, genetic algor
9、ithms, simulated annealing, linear programming algorithm, ant colony algorithm and so on. In solving the TSP problem, these algorithms are certain advantages, but also defective. Because the theoretical principles of ant colony algorithm and TSP problem solving process has a certain similarity, comp
10、ared to other algorithms , ant colony algorithm could deal with the TSP problem with better results. The goal of the people is far more than it, any study that can make the algorithm more optimization has been continued. Although the ant colony algorithm has demonstrated good performance in solving
11、TSP problem, but with the enlarged scale of the problem, the drawbacks of the algorithm were revealed. When we are dealing with large amount of data from large-scale TSP problem, the basic ant colony algorithm, or a variety of improved algorithm still have some shortcomings,like the solution ineffic
12、iency, solving accuracy is small, easy to fall into local optimum, and so on. In allusion to this phenomenon, by optimizing the calculation rules of the ant colony algorithm, this paper proposes an improved Segmentation and multi-function ant colony algorithm, and around the large TSP problem the fo
13、llowing questions are discussed in this paper：（1）Introduction and describes the computational complexity of TSP problem and large scale TSP problem, the existing TSP problem solutions were compared to analyzing their problems. （2）Carried out a detailed introduction to the ant colony algorithm for th
14、e background, principles, models and features, and studying for the development of direction and outlook for its advantages and disadvantages.（3）Optimize and update the rules of traditional ant colony algorithm, With the improving of the probability select model and the classification rules of the a
15、nt colony in traditional ant colony algorithm，put forward a new sectional multifunctional ant colony algorithm. Research and discuss the settings of various parameter in ant colony algorithm. Then selected small-scale TSP problems and large-scale TSP problem doing simulation experiment. The experime
16、ntal results show that the improved algorithm can obtain better global optimal solution within a reasonable run time. （4）Summarize the main research work, pointing out the shortcomings and deficiencies of this study ，and prospect the content and area that ant colony algorithm will be further studied
17、 and the application of improved ant colony algorithm in other fields.Keywords：TSP problem, ant colony algorithm, optimization rules目 录第1章 绪论11.1 研究背景11.2 研究内容21.3 论文的组织结构3第2章TSP问题52.1 TSP问题概述52.2 TSP问题的定义和数学模型62.3 TSP问题的已知算法及存在的问题72.3.1精确求解方法72.3.2 近似求解方法92.4 TSP问题的应用122.5 本章小结13第3章 蚁群算法153.1 蚁群算法产
18、生背景153.2 蚁群算法的原理153.3 蚁群算法的模型193.4 蚁群算法的特征233.5 蚁群算法的前景展望243.6 本章小结25第4章 蚁群算法规则优化-分段多功能蚁群算法274.1 对基本蚁群算法的认知274.2 分段多功能蚁群算法294.2.1 多功能搜索策略294.2.2 信息素的设置294.2.3 转移概率与分段搜索策略304.2.4 信息素的更新规则324.2.5 改进算法的流程324.3 蚁群算法参数分析354.3.1 信息素残留因子1-的选择354.3.2 信息素启发因子的选择374.3.3信息素自启发因子的选择394.3.4 对与的组合选择414.3.5 蚂蚁数目的选
19、择424.4 仿真实验464.4.1 对小规模TSP问题的仿真实验464.4.2 对一类大规模TSP问题的仿真实验504.5 本章小结51第5章 总结与展望525.1 研究工作总结525.2 研究展望52参考文献54致谢60第1章 绪论1.1 研究背景由于计算机的发明与普及，使得优化理论有了坚实的发展后盾，优化理论与方法开始成为一门十分活跃的学科并被并开始受到广泛的关注与研究。他在经济计划、航天航空、生产管理、工程设计等各行各业都得到了十分广泛的应用。近几十年来，优化学术领域发生了重大的变化与改革，人工智能和人工生命技术的发展为该领域注入了新的力量。基于仿生学原理、通过模拟自然现象或过程的各种
20、优化方法如雨后春笋般相继被提出，如遗传算法(Genetic Algorithm,GA)、神经网络算法（Artificial Neural Network, ANN）、模拟退火(Simulated Annealing,SA)、蚁群算法（Ant Colony Optimization, ACO）等，他们对于经典的优化算法不能或者难以解决的复杂问题有较好的适用性，显示了无法比拟的优势，并且取得了令人瞩目的成就。旅行商（TSP）问题既是计算机科学中的一个典型问题，也是组合数学中的经典问题。TSP问题从1932年产生发展以来就一直受到各个领域众多学者们的研究与追捧。历经80年的研究，虽然获得了大量的研究
21、成果，但是对这个问题的有效求解至今仍是悬而未决，相信在将来相当长一段时间内也并不能被彻底解决。现在，旅行商问题被认为是组合优化领域里一个非常经典的NP难题，也已经证明出它具有NPC计算复杂性1。研究TSP问题的求解方法的意义在于：他对于解决一些数据量庞大且复杂的实际应用问题具有重要的参考价值，基于这一原因，只要是能够简化该问题的求解或者提高求解性能的理论与方法，都会受到各方面关注和并获得较高的赞扬。现实生活中有许许多多的问题比如旅游线路的规划与安排、邮递员问题、物流配送路线问题、产品的生产安排等问题都是TSP问题的一种。因此，TSP问题的求解具有重要的理论意义和实际意义2，所以对其最优路径的算
22、法研究自然而然的成为当前炙手可热的话题。虽然我们对于TSP问题已经做了大量的研究，但较好的研究成果仅限于小型TSP问题中，一旦遇到庞大的数据量，其运算结果往往不如人意。由此可见，大型TSP问题的研究仍是一项亟需处理而又艰巨无比的任务。蚁群算法（Ant Colony Optimization, ACO），又称蚂蚁算法, 是由意大利科学家Marco Dorigo等人在20世纪90年代初提出来的3，它一种受到自然界蚂蚁觅食行为过程中通过信息素的沟通来找到蚁穴到食物的最短路径的启发而提出的一种生物优化算法。蚂蚁通过自身释放的信息素来进行信息交流和相互的沟通，并能够以此来找到一条通往食物地的最短路径，蚁
23、群算法理论思想正是借鉴了蚁群的这种群体性能。由于蚁群算法模拟设计了正反馈机制与蚂蚁间的交互协作机制，利用了蚁群单个个体之间的简单信息传递来完成寻找最短路径搜索食物的特点来实现算法,使得该过程与TSP问题求解具有较大的的相似性，从而能够对具有NP难度的TSP问题给出较优的解答。蚁群算法在问题的快速求解基础上，又使全局优化特征以及较短时间内计算结果的合理性得到了保证（这只是同其他算法的比较而言），因此，蚁群算法成为了求解TSP问题最常见的算法之一。同时,该算法还被用于求解背包问题、车辆路径问题(Vehicle Routing Problem, VRP)等,显示了他在组合优化类问题求解中的优越性。蚁
24、群算法的持续优化与更新对进一步研究并解决大型TSP将有着十分重要的作用与意义。1.2 研究内容本文将优化的蚁群算法用于大型TSP问题的求解，主要研究工作包括：1.首先收集了国内外关于TSP问题和蚁群算法相关资料，并阅读了相关的文献，对TSP问题和蚁群算法的基本思想及理论有了初步的了解；其次从蚁群算法和TSP问题理论、模型、特点、算法实现、实际应用等方面着手做进一步的深入研究，并对他们的未来发展的方向与趋势做了预测与展望。 2.分析了大型TSP问题的处理难度以及基本蚁群算法在其应用中的缺陷，本文对基本蚁群算法的规则进行了优化并提出了一种改进的蚁群算法分段多功能蚁群算法。改进的基本思想主要是通过选
25、择概率模型和蚁群分类规则的优化来实现的，优化目标是使改进算法能够在快速合理的收敛到全局最优解的基础上保证解的质量，这样算法的搜索能力和性能都得到了显著提高（但是较之搜索速度，全局最优解仍是我们主要关注的问题）。改进内容主要包括：（1）改进传统蚁群算法单一蚂蚁种群的求解方法，实现蚁群的多功能分工。（2）在求解大型TSP问题时，通过分段搜索，适当放大蚁群初期选择概率，加快解的进化，提升搜索速度；待到一定阶段再恢复正常的选择概率，保证算法的全局搜索性。（3）进行模拟仿真实验。利用TSPLIB中的数据分小规模和大规模两类对改进后的分段多功能蚁群优化算法进行算法测验。通过实验测试结果及与基本蚁群算法的对
26、比我们得知，此优化算法在合理的运算时间内保证了较高求解质量，适宜求解大型TSP问题。1.3 论文的组织结构本文由四部分组成：研究背景，基础理论介绍，规则优化的分段多功能蚁群算法求解TSP问题的理论与实现，总结与展望。各章内容组织如下：第一章介绍了研究背景与研究内容，对论文进行综合性概述，简要介绍了 TSP问题和蚁群算法，给出了论文的组织结构。第二章首先对TSP问题进行概述，然后详细的介绍TSP问题的定义和数学模型。其次，列举了TSP问题现有的各种解决方案，并分析了每种方案存在的问题，为后文面向大型TSP问题时蚁群算法的改进提供依据。最后，介绍了TSP问题在现实生活中的一些应用。第三章从蚁群算法
27、的产生背景出发，详细的分析介绍了基本蚁群算法的理论原理并从TSP问题的角度详述了其它的数学模型、算法步骤和结构流程框架。本章内容是蚁群算法的基础理论分析，以便后文能在此基础上做深入的研究分析，针对关键点做作规则优化，是文章能够进入下一步研究的基础与保证。第四章针对基本蚁群算法在处理大型TSP问题时的缺陷，提出了一种基于规则优化的改进的蚁群算法分段多功能蚁群算法。其改进的思想主要是根据概率选择模型和蚁群分类规则的优化而实现的。然后利用TSPLIB数据分两类对改进的蚁群算法进行仿真测试，然后根据测试结果对算法的性能进行了分析。第五章主要是对全文进行总结，并对后续的研究提出展望。本文所提出的改进蚁群
28、算法只是针对TSP问题的应用进行了测验，实验证明该算法对于TSP问题的求解效用有了提高，但对于其他的领域该算法是否适用还有待进一步探讨。 第2章 TSP问题2.1 TSP问题概述TSP问题即旅行商问题，又被称为货郎担问题，是一个古老的组合优化问题4。TSP问题的最早研究始于欧拉，他经过研究在1759年提出了TSP问题的初始雏形，描述为以国际象棋棋盘中64个方格为路线，在走遍所有方块的前提下，如何建立一个从起点出发并最终返回的不重复回路。1948年，美国兰德公司开始积极并广泛的推进TSP问题的研究，他们在研究中发现该问题的求解复杂度十分之高，并且会随着原始数据的增加问题难度以指数的形式无限增长，
29、由此TSP问题便成为了在组合优化领域中一个典型的难题，这也吸引了各领域众多学者们的兴趣并开始积极投入研究。随着理论和科技的发展，对TSP问题的研究不断的深入并取得了较大的成果，它但是还是存在许多尚待解决的问题，目前已经被归入NP完全类问题的范畴5。 TSP问题有很多种类型，如对称型TSP、非对称型TSP、平面TSP、时间窗TSP问题等6。在现实社会领域中，TSP问题也开始被广泛的利用，由于其自身的特殊特点，它也经常被用来比较其他算法性能的优越性。TSP问题的历史可以分成以下几个阶段7：1800-1900年，首次描述TSP问题；1920-1930年，给出了TSP问题的普遍定义；1940-1950
30、年，研究者把TSP问题纳入NP-hard范畴；1954年， 第一次解出关于42个城市的TSP问题的最优解；1980年，Crowder和Padberg求解了318个城市的问题；1987年，Padberg和Rinaldi求解了2392个城市的问题；1992年，以3038个城市坐标为基础的TSP问题得到解决；1994年， TSP问题的求解能力不断扩展，已经达到了求解7397个城市的水平；2003年2月，Hisao Tamaki发现了TSPLIB中pla33810的一个次优解；2004年2月，找到了pla85900问题中的一个次优解。TSP问题作为一个具有重要的理论意义和广泛应用价值的组合优化问题，在
31、农业、工业、商业、国防，特别是交通路线等方面的存在大量的运用，因此受到了诸多领域研究者们的关注。由于遍历所有的路径排列组合数随着城市数N的增加呈指数形式增长，所以想要在短时间内精确的获得问题的最优解的是十分困难的，因此寻求一个有效的近似求解方法是十分必要且更合乎实际的。经过多年的研究总结，我们发现TSP问题的求解的需要克服两大难题：如何避免算法陷入局部最优；如何提高算法的运行效率。20世纪90年代，学者们提出了蚁群算法这一理论概念并将其应用于TSP问题，且取得了较之其他算法相对理想的研究成果，目前以至于未来该算法仍旧是众多研究人员的重点研究对象之一。在随后时间内，遗传算法、启发式搜索方法、模拟
32、退火算法、人工神经网络等一系列智能优化算法的方法也相继提出并应用到TSP问题中，同样得到了人们广泛的关注。2.2 TSP问题的定义和数学模型TSP问题可以定义为：在规模为n个城市集合中,要在给出每个城市之间的距离的条件下找出一条线路最短的路径使得该路径能够不重复的通过所有的城市并且最终回到出发地。如果某TSP问题中有个城市，便可以从中找出条回路，当很大时，回路的数目将成为天文数字，此时想要精准的求出其全局最优解以目前的技术条件来说是十分困难的。用图论的方法可以将TSP问题描述为：在一个正权图G =(W ,S)中，顶点的集合为W =1,2, n，各定点之间的连线集为S，已知各顶点连线之间的距离，
33、要找到一个权值最小的哈密尔顿回路，这称之为最佳哈密尔顿回路8。其数学模型为：设有n个城市V=V1,V2,Vn，访问顺序为T=T1,T2,Tn,其中TN+1=T1(TV,i1N),则问题就化为求其中表示遍历所有的的城市且每个城市不能重复访问，最后再回到起点的所有的回路的集合。可详细描述如下：其中，C,C= , , ,，i=1，2，3,l， 1,2,3,l,ij, i,j=1,2,3,l上述公式中C为城市集合, 为城市的编号，i=1,2,3,l；为编号为和的两城市之间的距离，且有= 。TSP问题的实质是对于n个城市（每个城市对应一个坐标），在城市之间相互连通的情况下，找到一条最短的路径=V1,V2
34、,Vn（其中Vi表示第i个城市），使得能取最小值。2.3 TSP问题的已知算法及存在的问题目前，求解TSP问题的主要方法有两大类9:一类是精确求解算法，另一类是近似求解算法或者称作启发式求解算法，部分近似求解算法也称作智能优化算法。2.3.1精确求解方法精确求解算法10是TSP问题研究初期使用比较多的一种算法，就是在毫无遗漏的在全局中进行搜索，对有可能的解全部进行一次计算，并在所有的计算结果中找到果最好的解即最优解。一般来说，传统的求解算法都属于精确求解算法的范畴。由于精确求解算法本身的特性使其对所求解的要求非常严格，因此会产生很大的计算强度，一旦遇到一些大规模的数据，算法的运行几乎是不可能的
35、。尽管精确求解算法存在很大的弊端，但是它还是有一定存在的价值，并可供其它算法借鉴其思路。常见的精确求解算法主要有：（1）穷举搜索法这是求解TSP问题最初使用的的一种方法。该方法思路清晰简单，但是却要花费大量的计算时间。因为它首先要将所有可能的路径组合都列举出来并分别计算出它们的长度，然后从中选择长度最短的一条路径，以此作为所求的最优解。如果要用它来解决城市数量为n的TSP问题，计算量将达到(n-l)!/2。因此，在数据量较大的实际问题中，运用该方法几乎没有任何实际意义。（2）动态规划法5记A为集合2,3,n的子集，为以1为起点为终点的将A中所有的点集都走遍的最佳规划线路。当|A|=1时，当|A
36、|1时， TSP问题的动态规划方程可以便可以写为：然后再按照上述方程进行迭代求解。因为动态规划算法的计算时间较长，n规模的TSP问题需要的时间度为，计算的空间范围也比较大，达到了，所以该算法一般都不用于处理大规模数据的问题。（3）分支定界算法分支定界法11是使用最为广泛的搜索算法之一。它通过建立一个约束条件对整个解的搜索过程加以控制，该约束条件使搜索解不断的在可控的范围内进行修改且逐渐向最优解靠近，并最终发现最优解。设定不同的约束条件，定界的方法和结果也不尽相同。如何设定约束条件是分支定界法最重要内容。现在最常用的约束限制条件包括以下几种：1以下属的分派问题为约束条件2以最小权为1的生成树问题
37、为限制界限3通过匹配问题约束限制在实际的应用当中，分支定界算法可以且易于与其它算法结合使用，结合之后的新算法在求解性能上可以进一步的提升。在处理小规模的TSP问题时，可以单独使用分支定界算法进行计算并保证解的有效性，但如果问题的规模过大，该方法一般只能求出一个模糊的近似解，这时便可以再通过其他算法对这个近似解加以优化从而获得更好的解集。（4）线性规划法线性规划法12作为一种早期的算法，在旅行商问题的研究起步阶段可以算是效用较高的，但是现阶段对该算法的单独使用已经微乎其微了，主要也是作为其他算法的一种辅助形式。它的首先根据求解目标确定一个规划问题，再为该规划问题设立一定得约束条件，在约束条件的限
38、制下产生新的规划范围并不断缩小规划目标，直至得到目标的最优解。同分支定界发与其他算法的结合相反，线性规划法是在其它求解算法求出问题近似解的基础下，将此此近似解作为线性规划的下限，再通过约束条件的控制计算求出精确解。2.3.2 近似求解方法由于精确求解算法的有效性只能在中小规模的问题中体现出来，所以在实际应用中求解大规模问题就显得力不从心。这时我们采用近似求解算法10或者智能优化算法来处理大规模的优化问题能获得更好的求解效果。我们通过公式来衡量比较算法的有效性，其中C表示通过近似求解算法得到的最优解，表示问题已知的最优解，代表可接受的最差情况的限制条件，若越小，则说明算法求解的有效性越高。我们所
39、熟知的神经网络法、插入算法、模拟退火算法、粒子群算法、遗传算法等都是较为典型的近似求解算法，但更确切的说，他们属于智能优化算法。（1）插入算法插入求解算法13的基本思想是先在众多城市中选出两个元城市，把他们之间的路径连接起来产生一个初始回路，然后将剩余的城市按一定的约束条件逐个插入到初始回路当中。约束条件必须要保证插入新的城市以后形成的新回路的路径是所有可能的路径中最短的。根据上述思想，插入求解算法的主要运算过程分为以下两步：1、首先确定一个初始回路(i,j)以及准备插入初始回路的目标元素s。然后根据设定好的约束条件将目标元素s插入到初始回路(i,j)之间，这样变形成一个新具有三个元素的回路,
40、i,s,j,；2、根据上述方法再次插入新的目标元素，直到所有待插入的元素都已经存在这个回路当中，这时包含所有目标元素的最优回路的解便产生了。 插入求解算法的回路解的主要受到两方面的影响，一是如何选取初始的目标元素，二是怎样确定下一步的插入过程需要插入的合适的目标元素即插入规则的设定。根据插入规则的不同可将插入算法分成不同的类别，最常用的插入算法包括:最小值插入法、顶点插入法、邻近域插入法、最远距离插入法等。每种方法都不是十全十美的，都存在一定的缺陷，在实际应用中需要具体问题具体分析，才能选出最适合的算法类型。（2）神经网络算法人工神经网络 (Artificial Neural Network,
41、 ANN) 12，是一种模拟人脑的组织和活动原理，以数据为驱动而构造的非线性映射模型。它类似人脑一样能处理分析出许多复杂的因果关系，通过对大量的因果关系的聚类和分析，从中发现目标行为的运动规律并加以利用。对于那些数学模型难以描述的系统它可以很轻松的进行处理，并具有强大的自组织、自适应、联想记忆、并行处理、任意逼近非线性和容错鲁棒等特性，在复杂问题的处理中特别适用。人工神经网络在函数逼近、专家系统、自适应控制、组合优化等众多领域都具有广泛的应用。在TSP问题得处理上神经网络技术已经日趋成熟，但是由于对该算法的参数设置没有一个统一的标准，想要获得一个相对理想的参数，必须要在事前对数据行进多次反复的
42、测试，所以在计算过程中还是存在着很大的缺陷，这是神经网络的发展过程中面临的最大阻碍。（3） 模拟退火算法模拟退火算法是一种将组合优化问题与统计力学的热平衡相结合的求解方法14，在该算法中我们通常会定义一个能量函数，以此来代替组合优化问题中的目标函数，在能量物体不断的退火及变化的过程中，其能量逐渐的趋于平衡，最优解便产生于这个平衡点。模拟退火算法在运行时对参数的设置要求也非常严格，参数设置的偏差对最优的计算结果会有很大的影响，用户要通过大量的数据测试和一些经验知识根据具体问题设置不同的参数，这样就造成了整个算法的庞大的工作量，影响了算法的实现。 （4）遗传算法遗传算法15（Genetic Alg
43、orithms，GA）是J.Holland于1975年受到生物进化理论的启发而提出的16。再生物进化过程中染色体是通过适者生存的形式来进化的，遗传算法正是模拟了染色体的这种生存过程来对TSP问题进行求解。在对环境最不断的适应和淘汰过程中，最终存活的下来染色体便是最优染色体，根据这一模式，我们可以通过模拟该过程对TSP问题中的全局最优解进行求解。遗传算法也是目前应用最为广泛的组合优化算法之一，他可以准确的模拟自然界中染色体的优胜劣汰模式过程。由于整个遗传算法运行过程几乎没有外界条件的限制干扰，所以整个遗传算法的操作实现过程是比较简单的6。这也是遗传算法最为显著的特点和优势。但是在求解TSP的过程
44、中遗传算法也同样的表现出自身的缺点:容易产生局部最优解以及算法的运行速度较慢。为了克服自身的缺点，遗传算法也经常与其他算法相结合使用，已达到更好的求解效果。（5）粒子群优化算法粒子群优化算法17 (Particle Swarm Optimization，PSO)最初是由Kennedy和Eberhart提出的，一种基于群智能的新兴迭代优化算法。该算法对自然界中鸟群的飞行觅食行为进行了模拟,粒子群通过合作与信息交流不断改变自己的寻优路线直至找到最优解。因为该算法的收敛速度快，对解决复杂优化问题有较好的效果，所以已被广泛的应用到信号处理、多目标优化和决策支持模式识别等领域中。将粒子群算法应用于求解T
45、SP问题可以是是目前以及未来的一个新的研究方向。（6）蚁群算法蚁群算法是人们在自然界真实蚁群觅食行为的启发下提出的一种群智能生物模拟算法，算法具有随机搜索性14。由于蚁群的觅食过程与TSP问题的行为模式的类似，因此，用蚁群算法来模拟蚂蚁搜索食物的过程并应用到TSP问题中是十分可取的。由于基本的蚁群算法是在局部搜索的基础上进行全局搜索，易于陷入局部最优解，影响算法结果的全局最优性，所以许多改进的蚁群算法相继被提出，本文所的分段多功能蚁群算法即是将蚁群算法的概率选择模型以及蚂蚁的分类规则进行了改进。详细内容将在下面的章节进行介绍。2.4 TSP问题的应用最初，TSP问题并不是直接应用于实际问题当中
46、的，因为TSP最开始仅是为其他的算法提供思维方向，这些算法通过对TSP问题的研究再大量地应用到各种现实优化问题中。随着研究的发展与成熟，TSP开始广泛的直接应用于实际问题，给研究领域带来了新的活力。对于校车路线的优化问题是TSP问题最早的应用。现在，TSP问题最常见的应用就是对旅游路线的规划设计6。首先计划好所有要经过的旅游城市，根据具体情况计算出各个城市之间的旅行距离和旅行费用以后，找出以最节省的时间和费用访问完所有的旅游城市的最优路径。随着网络的发展以及数字时代的到来，我们能够更方便快速的解决该问题。只需要找到所有旅行要经过的城市的网络地图，并利用网络地图的信息把所有要经过的城市的地理位置
47、数据化，建立一个TSP坐标数据，然后再用TSP问题的算法进行求解，就可以快速便捷的得到一条旅行最佳路径。除了旅游线路设计的应用， TSP问题在其他很多领域都有着广泛的实际应用11。如：在物流配送系统中的应用18。随着物流业的蓬勃发展，企业之间的竞争日益激烈，合理规划配送路线降低企业成本，提高效益，TSP问题的应用成为了各个企业提高竞争力的重要措施。其中包括多路径的配送问题、配送车辆的调度问题等。TSP问题的其他应用还包括：电路主板上钻孔顺序的安排，通过TSP运算找到最优解便可以找到最节省时间的钻头移动顺序；在基因工程中的应用等。目前TSP问题已经在很多领域中解决了许多的实际问题，但在时代快速发展的环境下，各个领域都会出现了信息量的快速增加，因此需要面对信息量庞大且复杂的决策问题。同时，人们对决策结果的要求也更加严格，这就为我们的决策带来了双重的困难度。因此，在未来发展的过程中，随着决策数据量的不断增加，如何快速有效的解决大型TSP问题将会是今后的重点研究课题。2.5 本章小结本章主要对TSP问题进行了概述，介绍了TSP问题的定义和数学模型，并例举了几种TSP问题的已知算法及各自的优缺点。对TSP问题的应用做了简要的介绍，在未来的实际决策中TSP问题将会被广泛应用。但是面对数据量较大的大型TSP问题，如何高效的完成决策运算还有待进一步研究。
