用模拟退火算法求解TSP模拟退火原理

1、用模拟退火算法求解TSP_模拟退火原理论文导读：货郎担问题，即TSP(TravellingSalesmanProblem),是一个组合优化问题。具有NPC计算复杂性。木文分析了模拟退火算法模型，研究了用模拟退火算法求解TSP算法的可行性，并给出了用模拟退火算法求解TSP问题的具体实现方法。论文关键词：模拟退火原理，算法，TSP一、货郎担问题货郎担问题，即TSP(TravellingSalesmanProblem),也叫旅行商问题,是数学领域中著名问题之一。其一般提法为：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径

2、的选择目标是要求得的路径路程为所有路径之中的最小值。如图1所示，显然左边的路程要小于右边的路程。图1TSP的示意图货郎担问题(TSP问题)是一个组合优化问题。具有NPC计算复杂性发表论文。因此，任何能使该问题的求解得以简化的方法模拟退火原理，都将受到高度的评价和关注。一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的。以每秒1亿次的计算速度来估算，如果TSP问题包含20个城市时，求解时间长达350年；如果要处理30个城市，则

3、求解时间更长达1+10R16年。如此长的时间，在实际中完成是不现实的。基于模拟退火算法在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的优势。尝试用模拟退火算法求解。二、模拟退火算法(一)模拟退火算法原理模拟退火算法原理来源于固体退火：将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序模拟退火原理，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为eE/(kT),其中E为温度T时的内能，AE为其改变量，k为Boltzmann常数。用固体退火模拟组合优

4、化问题，将内能E模拟为目标函数值f,温度T演化成控制参数3即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复产生新解好计算目标函数差好接受或舍弃的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子t每个t值时的迭代次数L和停止条件So(二)模拟退火算法的模型模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想：1、初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)模拟退火原理，每个

5、T值的迭代次数L2、对k=l,，1_做第至第6步：3、产生新解S，4、计算增量At=C(S)C(S),其中C(S)为评价函数5、若AtO,然后转第2步。三、模拟退火算法求解TSP求解TSP的模拟退火算法模型描述如下：解空间：解空间S是遍访每个城市恰好一次的所有路经，解可以表示为wl,w2,wn,wl,wn是1,2,n的一个排歹U，表明wl城市出发，依次经过W2,.,wn城市，再返回wl城市。初始解可选为(L，n);目标函数：目标函数为访问所有城市的路径总长度；要求的最优路径为目标函数为最小值时对应的路径。新路径的产生：随机产生1和n之间的两相异数k和m,不妨假设krandom)ResultRo

6、uter=SelRouter;如果新路径长于当前路径，但exp(-Af/t)random(0,l),则仍然替换当前路径)if(JudgeOverlnnerLoop(0)break;判断内循环是否结束，结束则跳出当前温度的内循环elseNowlnnerlterNumber+;判断内循环是否结束，不结束则继续内循环)if(JudgeOverExternalLoop(0)break;判断外循环是否结束，结束则结束模拟退火计算else(NowTemperature=CountDownTemperature(NowTemperature,0);NowExternallterNumber+;NowInnerlterNumber=0;判断外循环是否结束，不结束则计算出下降后的温度，并继续循环)以上程序在WindowsXPProfessional、VisualC+6.0STLport4.6.2环境下调试完成。模拟退火算法一种新的随机搜索方法，经实验研究,能有效解决组合优化问题，与以往的近似算法相比，模拟退火算法具有使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点。参考文献：刘晓禹.张洪强，基于模拟退火算法的城市公交线路铺设分析臼；交通科技与经