tsp旅行包商问题算法研究

题目：TSP旅行商问题的算法研究学号：姓名：班级：日期：2015年1月11.研究背景旅行商问题(TravelingSalesmanProblem,简称TSP)是一个易于描述但难于解决的著名难题之一。TSP问题可描述为:已知n个城市各城市间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,怎样安排才使其所走路线最短。TSP问题的数学描述即为：如何在一个赋权图中，寻求权和最小哈密尔顿回路问题。现实生活中有很多问题可以归结为旅行商问题,比如邮路问题、装配线上的螺帽问题和产品的生产安排问题等。TSP问题在电路板钻孔进度的安排、基因测序和机器人控制等方面有着重要的应用。因此,TSP问题的求解具有重要的理论意义和实际意义。几十年前就已找到的一些指数级算法虽然能精确地求解TSP问题,但随着问题规模的变大,这些算法完全失效(组合爆炸)。近似算法或启发式算法尽管不能精确求解,但能够把误差控制在可以容忍的范围内并且能够快速地得到答案。计算机科学是一种创造性思维活动的科学。计算机算法设计与分析是面向设计的、处于核心地位的一门学科。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。它由有限条可执行的、有确定结果的程序指令组成。算法设计是一件非常困难的工作，常用的算法设计方法有：分治法、贪心方法、动态规划、回溯法、分枝－限界法、基本检索与周游方法、遗传算法等。本文将分别就贪心方法、动态规划、回溯法、遗传算法这几种算法设计方法研究0/1背包问题的求解方法进行分析，并对各种算法的复杂度进行分析。2.求解TSP问题常用算法2.1传统的确定性算法2.1.1动态规划法动态规划法DM(DynamicProgramming,简称DM)是美国数学家BellmanRE等人在20世纪50年代初在研究多阶段决策过程的优化问题时提出的,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法———动态规划。该方法运用到TSP问题的求解过程如下:记S为集合{2,3,⋯,n}的子集,k∈{2,3,⋯,n},C(k,S)为从k出发遍历S中的结点并终止于结点1的最短距离。当|S|=0时,C(k,S)=dk1,当|S|≥1时,根据最优性原理,可将TSP的动态规划方程写成:C(k,s)=min𝑗∈𝑠,𝑘∩𝑠=∅{dkj+C(j,s−{j})}假设我们规定周游路线开始于结点1,所要求的最短周游距离为:Min{C1k+C(k,V)}且V={2,3,⋯,n},k∈V可按方程逐步迭代求解。该算法是一个递归算法,它的时间复杂度为O（𝑛22𝑛），空间复杂度为0（n2𝑛）。随着问题规模的扩大，其所需要的空间会急剧增加，故一般除了很小的规模问题外，几乎不予采用。2.1.2分枝限界法分枝限界法LC(BranchandBoundMethod,简称LC)是由达金RJ和兰德2多伊格在20世纪60年代初提出的。为了避免盲目搜索,人们提出了改进的分枝限界方法——LC分枝限界法。该方法的基本思想是:根据智能化的判定函数^c(·),只产生解的部分状态空间树,从而加速搜索过程,即通过计算一小部分可行解即可以找到最优解。用分枝限界法求解TSP问题的过程如下；Step1选取一初始出发点作为根结点,该结点作为E2结点,求出此结点的智能化的判断函数^c(·)。Step2E2结点扩展它的所有儿子结点(分枝)。Step3计算所有儿子结点的智能化的判断函数^c(·)。Step4从所有活结点中选择一个最小的^c(·)。Step5把该结点作为新的E2结点;Step6判断从根结点到E2结点是否是一条完整路径,如果是,则结束,输出这条完整路径;否则转向Step2。该算法时间复杂度的最坏情况也是O(𝑛22𝑛),而且为了计算智能化的判断函数^c(·),必须为每个结点附带一个归约矩阵。所以,在实际中该方法同样很少运用于大规模的问题。2.2现代流行的智能算法2.2.1简单的遗传算法遗传算法通过模拟生物学的自然选择和自然遗传机制模拟生命进化的原理来寻求问题的最优解,自HollandJ等提出以来,获得了广泛的应用。用该算法求解TSP问题的基本思想是:把问题的解表示成“染色体”,在求解TSP问题时通常用一条周游路径来表示“染色体”,在执行遗传算法之前,随机地给出一群初始“染色体”(种群),即假设解。然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉、变异过程产生更适应环境的新一代“染色体”群。这样,经过一代一代的进化,最后收敛到最适应环境的一个“染色体”上,它就是问题的最优解。其求解TSP问题算法描述如下:Step1初始化种群规模size、交叉概率pc、变异概率pm和迭代次数t=0。Step2随机产生初始种群;计算初始种群的适应度。Step3根据一定的选择策略选择父体1和父体2。Step4产生一个0～1随机数p1、p2。Step5判断p1pc是否成立,如果成立,把父体1和父体2按一定交叉方法生成子个体1和子个体2;否则把父体1和父体2作为新的子个体1和子个体2。Step6判断p2pc,如果成立把子个体1和子个体2按一定变异方法变异。Step7判断产生子个体数是否等于种群规模,如果是则转向Step8;否则转向Step3。Step8评估种群的适应度;新产生的子代成为父代。Step9判断是否满足终止条件,如果满足则终止;否则转向Step3。遗传算法的优点是算法简单、易于实现,能够并行化,具有强鲁棒性和全局搜索能力。其缺点则表现为早熟现象、局部寻优能力较差等。所以,一些常规遗传算法并不一定是针对某一问题的最佳求解。2.2.2模拟退火算法1982年,PatrickK将退火思想引入组合优化领域,提出一种求解大规模组合优化问题的算法。模拟退火算法(SimulatedAnnealing,简称SA)的核心是模拟物理中固体物质的退火过程,它的基本思想是:用热力学系统来模拟求解的优化问题,把系统的能量看成是优化问题的目标函数,用系统逐步降温以达到最低能量状态的退火过程去模拟优化过程。它从一定初始解开始,从邻域中随机产生另一个解,接受准则允许目标函数在有限范围内变坏。该方法求解TSP问题的算法描述如下:Step1初始化起始“温度”T、终止“温度”T0、退火速度α和初始化一条路径c。Step2通过随机热扰动,在c的邻域内产生另一条路径c1。Step3计算两条路径所引起的目标函数(能量)值的变化ΔE。若ΔE≤0,令c=c1,T=αT;否则,产生0～1随机数rand,若exp(-ΔE/T)rand,令c=c1,T=αT。Step4判断TT0是否成立,如果成立转向Step2;否则结束。模拟退火算法具有较强的局部寻优能力,并能使搜索过程避免陷入局部最优解。但是,它把握整个搜索过程的能力不够,不便于使搜索过程进入最有希望的搜索区域,从而使得模拟退火的运算效率不高,而且对参数温度T的初始值、退火速度问题、温度管理问题也难于控制。2.2.3蚁群算法蚁群算法(AntColonyOptimization,简称ACO)由意大利学者DorigoM等在1996年首先提出。该算法通过模拟蚂蚁的觅食行为,蚂蚁觅食的时候会在所走过的路径上留下信息激素,同时信息激素会随时间而挥发。一条路径走过的蚂蚁越多,留下的信息激素越多;反过来,信息激素浓度高的路径上会吸引更多的蚂蚁。通过这种正向反馈,最终将找到一条最优路径。为了避免蚂蚁两次走上同一条路径(非法路径),为每个蚂蚁设置一个禁忌表以记录它已走过的路径。其算法可描述如下:Step1初始每条路径上的信息激素浓度。Step2把m只蚂蚁随机地放置在n个城市上,并把已访问的城市写入禁忌表。Step3如果第k(k=1,2,⋯,m,)只蚂蚁还有未访问的城市,则该只蚂蚁根据概率Pij决策选择下一个城市(i是该蚂蚁当前所在城市,j(N-禁忌表),Pij是一个由城市i到城市j之间的路径长度和信息激素浓度构成的函数),把选择的城市j写入禁忌表,直到所有的城市访问完。Step4计算k(k=1,2,⋯,m,)条路径的路径长度,选出本次最优路径。Step5根据本次蚂蚁的访问情况更新每一条边上的信息激素浓度,清空禁忌表。Step6判断是否满足结束条件,如果不满足,转到Step2;否则结束。该算法的优点是:它是一种自适应、自组织、本质上并行的方法,而且是一种正向反馈的方法,可以促使整个系统向最优解进化,而且参数少、易于调整,易于移植到其他组合优化问题。但是,它同样存在收敛慢、易于陷入局部最优的缺点。3.各种算法的比较算法时间复杂度优点缺点适用动态规划法O（𝑛22𝑛）可以求得最优解不太适合解决TSP问题，时间太长小规模的问题分枝界限法O(𝑛22𝑛)可以求得最优解、平均速度快花费很多内存空间、界值设定是该算法成功的关键可应用于大量组合优化问题遗传算法O（2𝑛）隐含并行性和全局搜索性，速度快，能获得最优解局部寻求能力较差、算法不是很成熟提供了一种求解复杂系统问题的通用框架，广泛用于许多科学，模拟退火算法求解速度快，全局优化概率性算法广泛应用于全局优化问题蚁群算法O（𝑛3）最优解的收敛速度快、运算结果具有稳定性信息素的选取及初期信息激素的匮乏，致使求解速度缓解离散组合优化问题4.TSP问题算法实现4.1问题的提出某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。设G=(V,E)是一个带权图。图中各边的费用(权)为正数。图中的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题要在图G中找到费用最小的周游路线。4.2动态规划解TSP问题由于货郎担问题经过的路线是一条经过所有城市的闭合回路，因此从哪一点出发是无所谓的，因此不妨设从城市1出发。问题的动态规划模型构造如下：阶段k：已经历过的城市个数，包括当前所在的城市。k=1,2,…,n,n+1，k=1表示出发时位于起点，k=n+1表示结束时回到终点。状态变量：xk=(i,Sk)，其中i表示当前所在的城市，Sk表示尚未访问过的城市的集合。很明显S1={2,3,…,n}，…，Sn=Sn+1=F其中F表示空集。并且有xn=(i,F)i=2,3,…,n，xn+1=(1,F)决策变量：dk=(i,j)，其中i为当前所在的城市，j为下一站将要到达的城市。状态转移方程：若当前的状态为xk=(i,Sk)采取的决策为dk=(i,j)则下一步到达的状态为xk+1=T(xk,dk)=(j,Sk\{j})阶段指标：vk(xk,dk)=Cij最优指标函数：fk(xk)=fk(i,Sk)表示从城市i出发，经过Sk中每个城市一次且仅一次，最后返回城市1的最短距离。终端条件：fn+1(xn+1)=fn+1(1,F)=0对于如图3.7.1所示的一个五个城市的货郎担问题，求解步骤如下：对于k=5，有f5(i,F)=min{Cij+f6(1,F)}=Ci1i=2,3,4,5d5?(i,1)f5(I,F)的值列表如下：1243if5(i,F)22374255对于k=4，有f4(i,S4)=min{Cij+f5(j,S5)}j?S4f4(i,S4)的值列表如下：(i,S4)jCijS5Cij+f5(j,S5)f4(i,S4)j*(2,{3}){3}3F3+f5(3,F)=3+7=10103(2,{4}){4}5F5+f5(4,F)=5+2=774(2,{5}){5}1F1+f5(5,F)=1+5=665(3,{2}){2}3F3+f5(2,F)=3+2=552(3,{4}){4}4F4+f5(4,F)=4+2=664(3,{5}){5}6F6+f5(5,F)=6+5=11115(4,{2}){2}5F5+f5(2,F)=5+2=772(4,{3}){3}4F4+f5(3,F)=4+7=11113(4,{5}){5}3F3+f5(5,F)=3+5=885(5,{2})