旅行商问题毕业论文 (2).doc
《旅行商问题毕业论文 (2).doc》由会员分享,可在线阅读,更多相关《旅行商问题毕业论文 (2).doc(27页珍藏版)》请在三一文库上搜索。
1、 摘 要摘要旅行商问题(Travelling Salesman Problem,简称TSP)是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目n 是成指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义。遗传算法(GA)是求解旅行商问题(TSP)的常用方法之一。针对中国旅行商问题(CTSP),本文利用遗传算法的全局搜索能力进行组合优化问题求解,设计一种大比例的优秀个体保护的大变异遗传算法,并使用MATLAB语言进行了实际的编程求解,编程中的各个模块分别实现了选择、交叉、变异等关键环节。用编制的程序快速求解出了满足的结果,用本文设计的遗
2、传算法的思路和编程程序是正确的。用该策略迅速找到了CTSP最优解,该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方案。关键词:遗传算法;CTSP;最短路径;MATLABAbstractThe traveling salesman problem (TSP) is a well-known NP complete problem, Its increased by exponential n. So, it is hard to find a precision result, and it is very important to searc
3、h for the near result. The genetic algorithm (GA) is one of the ideal methods in solving it. For CTSP,According to genetic algorithms global searching proterty, a kind of big probability variations genetic algorithm is put forward, which copies big proportion of fittest. In MATLAB, the typical Chine
4、se traveling salesman problem is computed and the result shows the thought and program is correct. The best path for CTSP is found quickly through the algorithm. The best path 15378km is get, the result is the best so far.Key words: The Genetic Algorithm (GA); Chinese Traveling Salesman Problem (CTS
5、P); The Shortest Path; MATLAB III 目 录目 录摘要IAbstractII绪论11 CTSP数学模型及常用算法211 TSP的数学模型212 TSP问题的常用求解方法2121 遗传算法(GA)2122 模拟退火算法(SA)3123 蚁群算法(ACO)3124 禁忌搜索(TS)4125 粒子群优化算法(PSO)413 CTSP问题的数学模型,目前最优解5131 CTSP的数学建模5132 CTSP目前最优解52 用遗传算法SGA求解CTSP问题721 遗传算法求解框架722 种群初始化和计算适应度8221 种群初始化8222 计算适应度823 遗传算子8231 选
6、择算子8232 交叉算子8233 变异算子9234 终止判断93 MATLAB简介与特点1031 MATLAB简介1032 MATLAB的特点104 用MATLAB求解CSTP问题1241 种群初始化1242 计算适应度1243选择算子12431 计算选择算子的过程12432选择算子计算的代码实现1344 交叉算子15441 交叉概率的选择15442 交叉算法实现1645 变异算子16451 变异概率的选择16452 变异算法实现1746 路径输出175 实验结论及分析1951 实验结论1952 需要进一步解决的问题20致 谢21主要参考文献22III 绪 论绪 论旅行商问题(Travelli
7、ng Salesman Problem,简称TSP)是一个典型的组合优化问题,并且是一个NP难题,遗传算法(GA)、模拟退火算法(SA)等算法是求解这类问题的常用方法。首先,提出了CTSP问题,并建立CTSP问题的数学模型,列举常用的几种求解旅行商问题的解法,给出目前求解出这个问题的最优解。其次,用遗传算法求解CTSP问题。针对中国旅行商问题(CTSP),设计了选择 (Selection)交叉 (Crossover)变异 (Mutation)遗传算法的改进策略。用该策略迅速找到了CTSP最优解,该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方
8、案。再次,选择工具实现用遗传算法求解旅行商问题,在这次设计过程中,我们选择了MATLAB作为我们处理这个问题的工具,因为旅行商问题是一个数学问题,MATLAB是一个专门解决数学问题的数学软件,并且提供了遗传算法工具箱(我们程序中用到的很多代码都来自于遗传算法工具箱中的函数),而且它有很强的绘图功能,所以,我们选择MATLAB作为我们解决旅行家问题的工具。最后,对我们事先得到的结果进行分析,最终求得最优解,得到最优路径。在以下的文章中,介绍这一过程的具体实现。23 1 CTSP问题常用解法,建立CTSP的数学模型1 CTSP数学模型及常用算法旅行商问题(Travelling Salesman P
9、roblem,简称TSP)可描述为某旅行商欲往n个城市推销货物,从某个城市出发,沿途经过各个城市一次后返回到出发城市,要确定一条行走的路线,使得总路径最短。11 TSP的数学模型假设有一个图G= ( V,E) , 其中V是顶点集,E是边集,设D=()是由顶点i和顶点j之间的距离所组成的距离矩阵,旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短路径的回路。若对于城市V=, 的一个访问顺序为T=t1,t2,t3,ti,tn,其中 V(i=1,2,3,n)tiV(i=1,2,3,n),且记tn+1=t1,则旅行商问题的数学模型为: (1)12 TSP问题的常用求解方法TSP问题求解方
10、法目前有好几种,下面介绍几种求解TSP问题比较成熟的几种算法,遗传算法(GA)、模拟退火算法(SA)、蚁群算法(ACO)、禁忌搜索(TS)和粒子群优化算法(PSO)。121 遗传算法(GA)遗传算法是JHolland于1975年受生物进化论启发而提出的源于自然界生物进化过程,生物是通过自然选择和有性繁殖两个基本过程如图1所示不断进化的,通过自然淘汰变异、遗传进化,以适应环境的变化产生适合个体。人们将搜索和优化过程模拟生物进化过程,用搜索空间的点模拟自然界中的生物个体,将求解过程的目标函数度量或生物体对环境的适应能力,将生物的优胜劣汰过程类比为搜索和优化过程中好的可行取代交叉的可行解的迭代过程。
11、群体变异子群竞争婚配淘汰的群体群体胜出者图1生物进化循环图122 模拟退火算法(SA)模拟退火算法最早由Metropolis等(1953)提出,Kirkpatrick于1983 年将其用于组合优化。SA算法是基于Mente Carlo迭代求解策略的一种随即优化算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。算法的基本思想是从一给定解开始的,从邻域中随机产生另一个解,接受准则允许目标函数在有限范围内变坏。它由一控制参数t决定,其作用类似于物理过程中的温度T,对于控制参数t的每一取值,算法持续进行“产生新解-判断-接受或舍弃”的迭代过程,对应着固体在某一恒定温度下趋于热
12、平衡的过程。经过大量的解变换后,可以求得给定控制参数t值时优化问题的相对最优解。然后减小控制参数t的值,重复执行上述迭代过程。当控制参数逐渐减小并趋于零时,系统亦越来越趋于平衡状态,最后系统状态对应于优化问题的整体最优解。该过程也称冷却过程。由于固体退火必须缓慢降温,才能使固体在每一温度下都达到热平衡,最终趋于平衡状态,因此,控制参数的值必须缓慢衰减,才能确保模拟退火算法最终趋于优化问题的整体最优解。模拟退火算法要从邻域中随机产生另一个解,对于TSP问题,它的邻域是指两条路径除局部有差别外,大多数路径相同。123 蚁群算法(ACO) 蚁群算法是Colorni和Dorigo等于20世纪90年代对
13、蚁群行为的研究受启发而提出的,仿生学家发现蚂蚁个体之间通过一种外激素(pheromone)的物质信息传递。蚂蚁在移动中能在所经路径中遗留外激素,而且蚂蚁会在移动中能够感知这种物质,并以次指导自己的运动方向。因此,有大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。某一路径上走过的蚂蚁越多,则后来选择该路径的概率就越大,蚂蚁个体之间就是通过这种信息的交流达到搜索失误的目的,人们通过模拟蚂蚁搜索失误的过程来求解一些组合优化问题。124 禁忌搜索(TS)禁忌搜索思想最早由Glover于1986年提出的,它是模拟人的思维的一种只能搜索算法。即人们对已搜索的地方不会立即去搜索,而去对其他地方进行搜
14、索,若没能找到可再搜索已去的地方。禁忌搜索算法从一个初始可能解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现使目标函数值减少最多的移动。为了避免陷入局部最优解,禁忌搜索中采用了一种灵活“记忆”技术,即对已经进行的优化过程进行记录和选择,指导下一步的搜索方向,这就是tabu表的建立。tabu表中保存了最近若干次迭代过程中所实现的移动,凡是处于tabu表中的移动,在当前迭代过程中是不允许实现的,这样可以避免算法重新访问在最近若干次迭代过程中已经访问的解群。从而防止了循环,帮助算法摆脱局部最优解。另外,为了尽可能不错过产生最优解的“移动”,禁忌搜索孩采用“释放准则”的策略。125 粒子群优
15、化算法(PSO)粒子群优化算法一种基于群体智能方法的演化计算技术,最早有Konnedy和Eberhart于1995年提出,受到人工生命的研究结果的启发,PSO的基本概念源于对鸟群捕食行为的研究。PSO中,每个优化问题的潜在解都是搜索空间的一只鸟,称之为“粒子”。所有粒子都有一个又被优化的函数决定他们的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己。另一个极值。另外也可以不用整个种群而知识用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。13 CTSP问题的数
16、学模型,目前最优解TSP问题有两类,即对称与不对称。对称即第i个城市到第j城市的距离与第j个城市到第i城市的距离相等;不对称即第i城市和第j城市的距离与第j个城市到第i城市的距离不相等。中国旅行商问题(CTSP)是一个真实的地理问题,由勒藩教授提出,可以简单描述为从北京出发经过中国的31个省会、直辖市又回到北京的最短路径。 131 CTSP的数学建模在中国31个城市之间寻找最优路径,共有(31- 1) ! /2= 1.326条路径。CTSP问题中31个城市编号及平面图中相对坐标如下所示:1拉萨(1304,2312) 2北京(3639,1315) 3上海(4177,2244) 4天津(3712,
17、1399) 5石家庄(3488,1535) 6太原(3326,1556) 7呼和浩特(3238,1229) 8沈阳(4196,1004) 9长春(4312 ,790) 10哈尔滨(4386,570) 11西安(3007,1970) 12兰州(2562,1756) 13银川(2788,1491) 14 西宁(2381,1676) 15乌鲁木齐(1332,695) 16济南(3715,1678) 17南京(3918,2179) 18杭州(4061,2370) 19合肥 3780,2212) 20南昌(3676,2578) 21福州(4029,2838) 22台北(4263,2931) 23郑州(3
18、429,1908) 24武汉(3507,2367) 25长沙(3394,2643) 26广州(3439,3201) 27南宁(2935,3240) 28海口(3140,3550) 29成都(2545,2357) 30贵阳(2778,2826) 31昆明(2370,2975)132 CTSP目前最优解CTSP问题求解;最优路径为:(21 福州22 台北18 杭州3 上海17 南京19 合肥23 郑州11 西安6 太原5 石家庄16 济南4 天津2 北京8 沈阳9 长春10哈尔滨7 呼和浩特13 银川12 兰州14 西宁15 乌鲁木齐1 拉萨29 成都31 昆明30 贵阳27 南宁28 海口26
19、广州25 长沙24 武汉20 南昌)获得结果的总路程为15378km,这也是CTSP问题的最短路径。所得路径图形如图2所示:图2最优路径图 2 用遗传算法SGA求解CTSP问题2 用遗传算法SGA求解CTSP问题21 遗传算法求解框架遗传算法根据适者生存,优胜劣汰等自然进化原则,从候选解中一代一代地优选适应性函数 ( FitnessFunction) 的解,重组后构成新的参数组合,而逐渐取得最优解 。适应性函数与传统优化算法中的目标函数和成本函数相对应,父辈个体 ( Individual ) 对子代的贡献与适应性函数成正比。它通常使用3种操作符 (Operator):选择 (Selection
20、)交叉 (Crossover)变异 (Mutation) 。相关执行过程如图3所示:图3 GA流程图是否满足验收条件输出结果并结束遗传算子随即产生初始种群,并计算各个体的适应度计算新一代适应度选择运算产生新一代种群交叉运算变异运算22 种群初始化和计算适应度221 种群初始化以遍历城市的次序排列进行编码。如码串1 2 3 4 5 6 7 8表示自城市l开始,依次经城市2,3,4,5,6,7,8,最后返回城市1的遍历路径。显然,这是一种针对TSP问题的最自然的编码方式。222 计算适应度遗传算法对一个个体(解)的好坏用适应度函数值来评价,适应度函数值越大,解的质量越好。此处适应度函数取路径长度的
21、倒数,即: (2)23 遗传算子遗传算子包括:选择算子、交叉算子、变异算子三种算子。231 选择算子开始,我们用随机方法产生初始解群。随着遗传算法的执行,我们保留M个较优的个体作为样本群体,采用轮盘赌选择算法。轮盘赌选择又称比例选择算子,它的基本思想是:各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ,个体的适应度为,则个体被选中遗传到下一代群体的概率为: (3)232 交叉算子旅行商问题对交叉算子的设计要求是:对任意两条巡回路线进行交叉操作之后,都能够得到另外两条新的并且具有实际意义的巡回路线。旅行商问题中常用的交叉算子包括:常规单点交叉或多点交叉、部分影射交叉、顺序交叉、循
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 旅行商问题毕业论文 2 旅行 问题 毕业论文
链接地址:https://www.31doc.com/p-3933611.html