算法报告-基于对称TSP问题的研究.docxVIP

基于对称TSP问题的研究

摘要旅行商问题（简称TSP）是一个著名的NP-Hard问题，也是离散优化的一个经典的重要问题，对其相关求解算法的研究非常重要。本文在介绍了TSP问题本身相关的问题后，又详细讨论了求解TSP问题的动态规划方法、改良圈算法、二交换算法、模拟退火算法、蚁群算法、遗传算法，并通过整合各种优化方式，对遗传算法进行了少量优化。针对测试库中的的改良圈算法、模拟退火算法、蚁群算法、遗传算法。本文使用MATLAB软件实现这些算法，并对这些算法的运行时间和解进行比较分析等研究。结果表明在任何清空下改良圈算法的性能都最差，其余算法在小型TSP问题下差别不大，在较大型TSP问题下，模拟退火所用时间最短，蚁群算法所用时间最长，遗传算法的解最好。实验结果证明，改进后的遗传算法效果不明显，在解的大小上改善1%-3%，但时间提高了10%。

关键词对称TSP问题;算法研究;近似算法;模拟退火;遗传算法;蚁群算法

StudybasedonsymmetricTSPproblem

XuBu-FanYanYang-ShengDongXiu-LiangWangYou-WeiYuYong-Xun

Abstract Travellingsalesmanproblem(TSP)isbothawell-knownproblemasaNP-Hardproblemandaclassicalprobleminthefieldofdiscrete-optimization.Thispaperfirstintroducesomethingaboutitself,thendiscussesmanywayssuchasdynamicprogramming,2-opt,exchangealgorithm,simulatedannealingalgorithm,antcolonyoptimizationandgeneticalgorithmindetail.Afterthat,thispaperproposesanimprovedgeneticalgorithmbythemeansofintegratingmanypapers’methods.Finaly,thispaper.ExperimentsshowthatImprovedcyclealgorithmperFORmsworst,andwhenitcomestosmallTSPproblems,thosealgorithmsperFORmsfamiliar.However,whensolvingbigTSPproblems,simulatedannealingalgorithmsolvesquickestasantcolonyoptimizationtakeslongest,andYICHUANmakesthebestsolution.Experimentsalsoshowthattheimprovedalgorithmmakesapproximately3%~5%improvementFORthelastlengthbuttimetakes10%more.

KeywordsSymmetricTSPproblem;Algorithmresearch;approximatealgorithm;simulatedannealing;geneticalgorithm;antcolonyalgorithm

1引言

1.1TSP问题

TSP问题，即一个商人想要去n个城市推销商品，每两个城市i和j之间的的距离为,如何选择一条道路使得商人能够每个城市仅走一遍后回到起点且保证所求的路径最短。其中，当对所有的城市i和j都有=,则称为对称TSP问题，否则称为非对称TSP问题，本文主要讨论对称TSP的问题。

对NP问题，如果采用标准的穷举算法，复杂度会达到O(n!)的复杂度。所以目前学术界对这类问题经常使用近似算法来求解。但这种算法，大量的启发式的搜索算法不一定能求出最优解，往往会陷入局部收敛，如何跳出局部收敛得到最优解也是现在相关算法改进的方向。

为方便后序的讨论，我们可以将TSP问题转化为数学模型:

城市{,,…,}的一个访问顺序为(,,…,),其中,且,则TSP问题要求的就是,其中是所有的不重复排列中可能的回路，n+1代表的点。REF_Ref45991946