《基于模拟退火算法的旅行商问题求解（精）》由会员分享，可在线阅读，更多相关《基于模拟退火算法的旅行商问题求解（精）（21页珍藏版）》请在金锄头文库上搜索。
1、摘要n关键词HAbstractITKeywordsII引言11旅行商问题和模拟退火算法21.1旅行商问题21.1.1旅行商问题的描述21.1.2旅行商问题的应用31.2模拟退火算法31.2.1基本思想31.2.2关键技术41.3小结42 TSP模拟退火算法的实现52TSP算法实现52.1.1 TSP算法描述52.1.2 TSP算法流程52.2 TSP 的 MATLAB 实现62.2.1加载数据文件62.2.2计算总距离的函数72.2.3绘制路线的函数72.2.4交换城市的函数82.2.5执行模拟退火的函数82.3小结93仿真实例103.1仿真分析与评价103.2结论12总结与展望12致谢13参
2、考文献13基于模拟退火算法的旅行商问题求解光信息科学与技术董铸祥张明强指导教师摘要：旅行商问题是组合优化领域里的一个典型的、易于描述却难以处理的NP难题，克可能的路径 数目与城市数目是呈指数型增长的，求解非常困难。首先介绍了旅行商问题，给出了其数学描述以 及实际应用，讲而给出解决TSP的一种比较精确的算法模拟退火算法。然示阐述了模拟退火算 法的基木原理，重点说明了其基木思想及关键技术。最后运）MATLAB语言实现了该算法，并将其 运用到解决旅行商问题的优化之中。数值仿真的结果表明了该方法能够对数据进行全局寻优，有效 克服了基于导数的优化算法容易陷入局部最优的问题。关键词：模拟退火旅行商NP组合
3、优化Solution of Travelling Salesman ProblemBaced on SimulatedAnnealing AlgorithmDong ZhuxiangOptical Information Science and TechnologyTutorZhang MingqiangAbstract: Travelling Salesman Problem is one of the typical NP-hard problems in combinatorial optimization, which is easy to be described but hard
4、to be solved Its possible amounts of path increase exponentially with the amounts of city, so it is very difficult to solve it. First this paper introduces Travelling Salesman Problem, gives TSP mathematical description and practical application.In turn, a precise algorithmsimulated annealing algori
5、thmthe to the address of TSP is given. And then this paperdescribes the basic principle of simulated annealing, highlights the basic ideas and key technology. Finally, wc use MATLAB language to implement the algorithm, and applied it to solve the traveling salesman problem into the optimization. Num
6、erical simulation results show that this method can globally optimizes data, effectively overcomes the problem of derivative-based optimization algorithm which is easy fall into local optimumKeywords: simulated annealing; travelling salesman problem;Non-deterministicPolynomial; combinatorial optimiz
7、atio n引言旅彳亍商问题(Traveling Salesman Problem,TSP),也称为货郎担问题，是由爱尔兰数学 家 Sir William Rowan Hamilton 和英国数学家 Thomas Penyngton Kirkman 在 19 1+t纪提出 的数学问题，它是指给定口个城市并给出每两个城市之间的距离，旅行商必须以最短路 径访问所有的城市一次且仅一次，并回到原出发地，现已证明它属于 NP(Non-deterministic Polynomial非确定多项式)难题。历史上的第一个正式用來解决 TSP问题的算法诞牛于1954年,它被用来计算49个城市的TSP问题。到现在
8、为止，运用 fi前最先进的计算机技术可解决找出游历24978个城市的TSP问题。TSP的历史很久， 最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格， 走访64个方格一次且仅一次，并且最终返回到起始点。旅行商问题(TSP)由美国RAND 公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个 他名且流行的问题习。旅行商问题是一个经典的图论问题：设有门个城市，用Ci.j=l, 2, n表示。城 市5之间的距离为gj, i, j=l, 2, n,设所有城市间两两连通，旅行商需要跑遍n 个城市去推销他的商站，而这些城市之间的距离都不一样，这推销
9、员需要从其小一个城 市出发，而他老板规定他必须把所有城市跑一遍，则TSP问题就是寻找让旅行商遍访每 个城市一次且恰好一次的一条回路，且要求其路径总长度为最短。该问题也可以归结为: 有N个城市由公路相互连通，从任一城市到另外城市都要支付相应的费用，一个销售商 从其中一城市出发，访问其他N1个城市且仅一次，如何规划一条路径，使该旅行商 的花费最少。当城市数量较小吋，通过枚举法就可以找出最短的路径，然而随着问题 规模的增加，很难找到一个多项式时间复杂度的算法来求解该问题。TSP是一个典型的 组合优化问题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且己成为 各种启发式的搜索、优化算法的问接
10、比较标准。因此，快速、有效地解决TSP有着重要 的理论价值和极高的实际应用价值。旅行商问题代表的一类组合优化问题,在物流配送、 计算机网络、电子地图、交通诱导、电气布线、VLSI单元布局等方面都有重要的工程 和理论价值，引起了许多学者的关注。TSP是典型的组合优化问题，并且是一个NP-hard问题。TSP描述起来很简单，早 期的研究者使用精确算法求解该问题，TSP问题最简单的求解方法是枚举法。它的解是 多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是门个点的所有排列的 集合，大小为(ml)!。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或 山谷的高度即是问题的极值。求解TSP
11、,则是在此不能穷尽的丘陵地带中攀登以达到山 顶或谷底的过程役 常用的方法包括：分枝定界法、线性规划法和动态规划法等，但可 能的路径总数随城市数H门是成指数型增长的，所以出城市数H在100个以上一般很难 精确的求出其全局最优解。随着人工智能的发展，出现了许多独立于问题的智能优化算 法，如蚁群算法、遗传算法、模拟退火、禁忌搜索、神经网络、粒子群优化算法、免疫 算法等，通过模拟或解释某些自然现象或过程而得以发展，为解决复杂组合优化问题提 供了新的思路和方法。模拟退火算法在迭代搜索过程以Boltzmann分布概率接受H标 函数的“劣化解”，具有突出的具有脱离局域最优陷阱的能力，同吋具有较强的局部搜索
12、能力，从而可以获取Fl标函数的全局最优解。因为模拟退火算法具有高效、通用、灵活 的优点，将模拟退火算法引入TSP求解，可以避免在求解过程中陷入TSP的局部最优 解。本文首先介绍传统的TSP问题，先对其进行数学描述，又列举TSP问题的应用。 之后介绍模拟退火算法，主要介绍其基本思想和关键技术，在此基础上将模拟退火的思 想引入TSP的求解，设计出TSP的一种模拟退火算法并用MATLAB语言编程予以实现。X旅行商问题和模拟退火算法1.1旅行商问题1.1.1旅行商问题的描述旅行商问题（Traveling Salesman Problem,简称TSP）又名货郎扌问题，是威廉哈 密尔顿爵士和英国数学家克克
13、曼（T.P.Kirkman）于19世纪初提出的一个数学问题，也是著 名的组合优化问题。问题是这样描述的：一名商人要到若干城市去推销商品，己知城市 个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个 城市只能访问一次，最后回到城市1的路线，使总的路程（或旅费）最小。TSP刚提出 时，不少人认为这个问题很简单。后来人们才逐步意识到这个问题只是表述简单，易于 为人们所理解，而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题。 这个问题数学描述为：假设有n个城市，并分别编号，给定一个完全无向图G=（V, E）, V=1, 2,n, nk其每一边（i,j）wE有一非
14、负整数耗费G,j（即上的权记为i,jeV）o并设1,0,边（i, j）在最优线路上其他(1-1)G的一条巡回路线是经过V中的每个顶点恰好一次的回路。一条巡回路线的耗费是 这条路线上所有边的权值之和。TSP问题就是姜找出G的最小耗费回路。人们在考虑解决这个问题吋，一般首先想到的最原始的一种方法就是汐IJ出每一条可 供选择的路线（即对给定的城市进行排列组合），计算出每条路线的总里程，最后从中选 出一条最短的路线。假设现在给定的4个城市分别为A、B、C和D,各城市Z间的耗 费为己知数，如图1所示。我们可以通过一个组合的状态空间图来表示所有的组合，如 图图ii顶点带权图图12TSP问题的解空间树从图中
15、不难看出，可供选择的路线共有6条，从中很快可以选出一条总耗费最短的 路线：顶点序列为(A,C,B,D,A)。由此推算，若设城市数H为n时，那么组合路径数则 为(n-1)!。很显然，当城市数H不多吋要找到最短距离的路线并不难，但随着城市数H 的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到尤法计算的地步，这就 是所谓的“组合爆炸问题S 假设现在城市的数1=1增为20个，组合路径数则为 (20-l)!1.216xl017,如此庞大的组合数H,若计算机以每秒检索1000万条路线的速度 计算，也需要花上386年的时间叫1.1.2旅行商问题的应用TSP是最有代表性的优化组合问题之一，其应用已逐步渗透到各个技术领域和我们 的日常牛活中。它一开始是为交通运输而提出的，比如飞机航线安排、送邮件、快递服 务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域，如在VLSI芯 片设计、电路板布局、机器人控制、车辆选路、物流配送等方而，下面举几个实例。1. 电路板钻孔进度的安排。机器在电路板上钻孔的调度问题是TSP应用的经典例 子，在一电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一 次巡游。把这个问题转化为TSP,孔相当于城市，转头从一个孔移到另一个孔所耗的时 间相当于TSP中的旅费。2. 车辆选路。一个经典的路由问题是在一个网络上发现从源节点到一个H的
