TSP问题的求解

TSP问题的求解摘要旅行商问题（TravelingSalesmanProblem，TSP）代表一类组合优化问题，在计算机网络、公路交通分布等多种实际问题中都有重要意义。“旅行商问题”也常被称为“旅行推销员问题”，其实质为是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。针对该题求解经过30个城市旅行的最短路径问题，我们采用三种方法解决：法一：（模拟退火算法）借助Matlab程序采用模拟退火算法进行分析解决。即首先在固定温提条件下求出当前温度下的最短路径（局部最优解），然后改变温度后再次求局部最优后得到最终的最短路径（全局最优）法二：（遗传算法）借助Matlab程序采用遗传算法进行分析解决。即法三：（线性规划）找出该线性目标规划的目标函数及约束条件，借助Lingo软件求得该TSP问题的最短路径关键词：TSP问题模拟退火算法线性规划遗传算法一、问题重述1.1引言TSP是典型的组合优化问题,并且是一个NP-hard问题，TSP简单描述为:一名商人欲到n个不同的城市去推销商品,每2个城市i和j之间的距离为dij,如何选择一条路径使得商人每个城市走一遍后回到起点,所走的路径最短。用数学符号表示为:设n维向量s=(c1,c2,…,cn)表示一条路经,目标函数为:minC(c1,c2,…,cn)=11),1()1,(nicncdcicid。1.2问题提出题目给出30个城市的分布图象及具体坐标，要求出经过30个城市的最短旅行路径。本文依次解决以下问题：寻找目标函数；模拟退火算法中初始温度T0的确定；根据Metropolis准则（等温）的概率判断是否接受新状态；通过循环先求出局部最优解再得出最终的最短路径。二、问题分析2.1城市编号及坐标为方便问题说明，我们先给30个城市编号并给出坐标值如下表1所示：城市编号X坐标Y坐标城市编号X坐标Y坐标城市编号X坐标Y坐标14194116460218776237841218542218403546713226023134042562148346248275764159138256232629916253826583576858172442274521871441858692841269546219717119443510836920747830450表12.2对于该旅行中的最短路径问题，利用模拟退火算法解决问题的过程如下：（外循环）（内循环）即温度作为外循环利用Metropolis抽样稳定准则求出当前温度下的最短路径（局部最优解），然后改变温度后再次求局部最优后得到最终的最短路径（全局最优）2.3对于该旅行中的最短路径问题，利用遗传算法解决问题的流程如下：随机产生初始路径S0，令Sbest=S0,并计算初始距离L0设置初始温度Tk，且10,0,1kttkkMetropolis抽样稳定准则求相应温度下最优路径最短路径三、符号说明序号符号含义1diji和j之间的距离为dij2Tk初始温度为Tk3S0初始路径为S04i,j当前状态i，新状态j5Sj,Si当前状态路径Si，新状态路径Sj6Li路径S长度四、模型的建立与求解4.1模型基础（1）模拟退火算法模拟退火算法背景：模拟退火算法来源于固体物质降温原理，在高温条件下，粒子将自由运动，在达到稳定状态后，再缓慢的降低其温度，则固体物质最终会形成最低能量的状态。可以将这种思想应用于求解组合优化问题。将组合优化问题解空间中的一个解对应于固体降温过程中的一个状态，将目标函数对应于该状态下的能量。以控制参数T来模拟固体的温度。对于每一个T，进行迭代过程：“解变换产生新解——判别准则——新解的取舍”，采用Metropolis准则来决定解的取舍，随着温度的降低，该算法有可能从局部极值区域跳出，从而达到全局最优解。Boltzmann概率分布在温度T，分子停留在状态r满足Boltzmann概率分DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)}({子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随则在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。Metropolis准则（等温）——以概率接受新状态若在温度T，当前状态i→新状态j1.若EjEi，则接受j为当前状态；2.否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。即在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小。新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。（2）遗传算法遗传算法背景：遗传算法GeneticAlgorithm是基于进化论的原理发展起来的一种广为应用高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”开始搜索过程。种群中的每个个体是问题的一个解成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏,通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后算法收敛于最好的染色体它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律遗传算法实现步骤1.编码：把所需要选择的特征进行编号每一个特征就是一个基因一个解就是一串基因的组合。2.初始群体population的生成：随机产N个初始串结构数据每个串结构数据称为一个个体。N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。3.交换(crossover)交换：由交换概率(Pc)挑选的每两个父代通过将相异的部分基因进行交换,如果交换全部相异的就变成了对方而没什么意义.从而产生新的个体。可以得到新一代个体新个体组合了其父辈个体的特性。交换体现了信息交换的思想。4.适应度值(fitness)评估检测5.选择selection:选择的目的是为了从交换后的群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。6.变异mutation:变异首先在群体中随机选择一定数量个体对于选中的个体以一定的概率(成为变异概率Pm)随机地改变串结构数据中某个基因的值。同生物界一样GA中变异发生的概率很低,通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。7.中止4.2模型求解（1）法一：模拟退火算法初始温度T0的确定方法：在经过30个城市的所有路径中随机挑选10条路径S0计算路径的长度L0，根据10个距离计算出方差即设为初始温度。计算结果：T0=100最低温度Tmin的确定方法：随机产生一条路径S1，计算其路径长度L1，随机交换其中两个相邻城市顺序得到新的路径S1，并计路径长度L2。得到路径差值L，取该路径差的101得出最低温度度Tmin计算结果：Tmin=0.01温度的变化10,0,1kttkk，α越接近1温度下降越慢，且其大小可以不断变化。在该题中，取温度的衰减系数α=0.9，其中固定温度下最大迭代次数为：100次，固定温度下目标函数值允许的最大连续未改进次数为5次，即当算法搜索到的最优值连续若干步保持不变时停止迭代。④最短路径的确定借助Matlab通过模拟退火算法得出最短路径为：27—26—25—24—15—14—8—7—11—10—21—20—19—18—9—3—2—1—6—5—4—13—12—30—23—22—17—16—29—28—27，最短路径图如下图1图1最短距离为：423.7406（2）法二：遗传算法优化过程如下图2所示：图2初始种群中的一个随机值（初始路径）:22—6—3—16—11—30—7—28—17—14—8—5—29—21—25—27—26—19—15—1—23—2—4—18—24—13—9—20—10—12—22最终最短路径为：30—12—13—4—5—6—1—2—3—9—18—19—20—21—10—11—7—8—14—15—24—25—26—27—28—29—16—17—22—23—30最短距离为：423.7406，最短路径图如下图3：图3注：红色代表起点（3）线性规划方法：最短路径为：30—12—13—4—5—6—1—2—3—9—18—19—20—21—10—11—7—8—14—15—24—25—26—27—28—29—16—17—22—23—30最短距离为：423.7406五、模型评估5.1模拟退火算法优缺点（1）模拟退火算法的优点：质量高，可以解决贪心算法中易陷入局部最优的问题；初值鲁棒性（稳定性）强；简单、通用、易实现。（2）模拟退火算法的缺点：由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。5.2遗传算法优缺点（1）优点：遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索出，而不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以方便地进行分布式计算，加快求解速度；遗传算法相较于模拟退火算法：模拟退火算法虽具有摆脱局部最优解的能力，能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。但是，由于模拟退火算法对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，使得模拟退火算法的运算效率不高。模拟退火算法对参数（如初始温度）的依赖性较强，且进化速度慢。（2）缺点：但是遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低。在实际应用中，遗传算法容易产生早熟收敛的问题。采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。5.3线性规划优缺点：（1）优点：算法稳定，易得标准值（2）缺点：针对TSP问题，需要先计算出第i个城市到其余城市的距离，当城市数目较多时计算复杂。六．参考文献：[1]《模拟退火算法求解TSP问题》—任昊南[2]《TSP问题的几种解法对比》附录（1）模拟退火算法程序function[MinD,BestPath]=MainAneal(CityPosition,pn)%function[MinD,BestPath]=MainAneal2(CityPosition,pn)%此题以中国30个城市的最短旅行路径为例，给出TSP问题的模拟退火程序%CityPosition_31=[4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450];%T0=clockglobalpathp2D;[m,n]=size(CityPosition);%生成初始解空间，这样可以比逐步分配空间运行快一些TracePath=zeros(1e3,m);Distance=inf*zeros(1,1e3);D=sqrt((CityPosition(:,ones(1,m))-CityPosition(:,ones(1,m))').^2+(CityPosition(:,2*ones(1,m))-CityPosition(:,2*ones(1,m))').^2);%将城市的坐标矩阵转换为邻接矩阵（城市间距离矩阵）fori=1:pnpath(i,:)=randperm(m);%构造一个初始可行解endt=zeros(1,pn);p2=zeros(1,m);iter_max=100;%input('请输入固定温度下最大迭代次数iter_max=');m_max=5;%input('请输入固定温度下目标函数值允许的最大连续未改进次数m_nax=');%如果考虑到降温初期新解被吸收概率较大，容易陷入局部最优%而随着