模拟退火算法在TSP求解中的应用
摘要：模拟退火算法（Simulated Annealing， SA）是一种适合解大规模组合优化问题，特别是解NP完全问题的通用有效近似算法。它与以往的近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高等优点，而且特别适合并行计算。TSP问题即旅行商问题是一个组合优化问题，该问题被证明具有NPC计算复杂性。因此，研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。本文首先分析了SA的基本原理，针对TSP问题我们将SA应用到TSP上，并建立了TSP的数学模型，阐述了利用模拟退火算法解 TSP 的方法。最后通过实验证明了模拟退火算法的高效性。 关键词：模拟退火; 组合优化; TSP问题
1 引言
模拟退火的概念最初是人们为了研究组合优化问题而提出的，用于解决组合优化问题，其原理是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性：通过设定一初始温度和初始状态，伴随温度的不断下降，结合概率突跳特性在解空间中通过邻域函数进行随机搜索，最终得到全局近似最优解。SA算法在组合优化中取得了很好的效果，能解决传统的优化方法难于解决的许多问题。SA算法具有较好的全局收敛性和适应性，并隐含着较好的并行性。SA算法的一些变形方法还表明：利用Metropolis过程并适当地控制温度下降过程的SA算法，在连续变量和混合变量的全局优化问题中具有很强的竞争力。
TSP(Traveling salesman Problem，旅行商问题)是一个组合优化问题。具有NPC 计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的。以每秒 1 亿次的计算速度来估算，如果 TSP 问题包含 20 个城市时，求解时间长达 350 年；如果要处理 30 个城市，则求解时间更长达 1+10e16 年。如此长的时间，在实际中完成是不现实的。基于模拟退火算法在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的优势。
本文介绍了模拟退火算法的基本原理，并利用SA算法实验求解TSP问题，借此显现了SA算法比传统算法的优势。
2 算法理论分析
智能优化方法课程论文
2.1 模拟退火算法简介
模拟退火算法的思想最早由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成：
(1)加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。
(2)等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡状态。
(3)冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。
其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，我们要得到的最优解就是能量最低态。其中Metro-polis准则是SA算法收敛于全局最优解的关键所在， Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。 2.2 模拟退火算法的模型
模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想：
1．初始化：初始温度 T（充分大），初始解状态 S（是算法迭代的起点），每个 T 值的迭代次数 L；
2．对 k=1，…，L 做第（3）至第 6 步； 3．产生新解 S′；
4．计算增量Δt′=C（S′）-C（S），其中 C（S）为评价函数；
5．若Δt′<0 则接受 S′作为新的当前解，否则以概率exp（-Δt′/T）接受 S′作为新的当前解；
6．如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法；
7．T 逐渐减少，且 T->0，然后转第 2 步。 2.3 TSP 模型
(1)问题定义：设n为城市数目，D= [dij]为n×n阶距离矩阵，dij代表从城市i到城市j的距离(i，j=1， 2， 3…n)，则问题是要找出遍访每个城市恰好一次的一条回路，且其路径长度为最短。
(2)解空间：解空间S是遍访每个城市恰好一次的所有回路，可表示为(1…n)
第2页 共10页
智能优化方法课程论文
的所有循环排列的集合，即S= [Sij]为(1…n)的排列，Si表示第i个城市第Si个被访问。
(3)目标函数：目标函数为访问所有城市的回路长度或称为代价函数，需求其最小值，选d =
?D[S(k),S(k?1)]为最小。
k?1n?13 模拟退火算法求解TSP
求解TSP的模拟退火算法模型可描述如下：
Y 跳出外循环 Y 结 束 图1模拟退火算法的流程图
N N △f<=0 N Exp(-△f/Ti)> random(0，1) N 跳出内循环 当前温度Ti下降 Y Y 从Xi的邻域中随机选择Xi，计算Xi与Xj的路程差 △f=f(Xj)-f(Xi) 当前路径Xi=X0 当前温度Ti=T0 选择初始路径X0 确定初始温度T0 当前路径Xi=Xj 我们要求的最优路径为目标函数为最小值时对应的路径。新路径的产生：随
第3页 共10页
智能优化方法课程论文
机产生1和n之间的两相异数k和m，不妨假设k 图1展示了模拟退火算法的大体流程图。选定初始状态X0，作为当前解：并且确定初始温度T0，令当前的Xi=X0和Ti=T0。然后从Xi的邻域中随即选择Xj，计算Xi与Xi的路径差，比较差值。按一定方式将T降温，即令T(t+1)＝k×T(t)，i=i+1，然后检查退火过程是否结束，如果不是继续交换，如果是的话输出Si作为最优输出。 4 仿真实验 实验环境：MATLAB7.1.0 实验算例：20个城市TSP (自定义)，相对坐标如图2所示。 参数设定：初始温度：4000，冷却速率：0.95，阈值：3500 算法终止条件为控制参数t的值小于某个充分小的正数D。求解得到的最优路径图如图3所示。 图2 20座城市相对坐标 第4页 共10页 智能优化方法课程论文 图3 模拟退火算法得到的最优路径图 从实验结果看，利用模拟退火算法求解TSP问题是可行有效的， 但当TSP求解的城市规模增大时，找到最优解的次数也在降低。 5 结论 模拟退火算法是一种可行、有效的全局优化的数值计算方法，它在解决高维空间、高复杂度及非线性问题的优化中具有全局最优、效率高及易于并行计算等优点，有很强的解决实际问题的能力。近年来在模式识别、自动控制、机器学习、人工神经网络结构参数优化等许多领域受到重视，应用范围不断扩大。 本文给出了用SA算法求解TSP问题的流程，并详述了各参数的取值，程序是在MATLAB环境中编写的，该程序基本实现了该课题的任务目标，研究SA算法的基本原理以及TSP组合优化问题，用一种程序语言实现基于SA算法的TSP问题求解方法。并且本文说明了用SA算法能够较好地求解旅行商问题。因而理论上能够找到最优解，但所得结论与实际应用还有一定距离，特别是对连续变量函数的优化问题。目前，SA算法参数的选择仍然依赖于一些启发式准则和待求问题的性质。SA算法的通用性很强，算法易于实现，但要真正取得质量和可靠性高、初值鲁棒性好的效果，客服计算时间较长、效率较低的缺点，并适用于规模较大的问题，尚需进行大量的研究工作。 参考文献： [1]王大志， 汪定伟， 闫杨. 一类多旅行商问题的计算及仿真分析[J]. 系统仿真学报， 2009 (20)： 6378-6381. [2]汪定伟等编著. 智能优化方法[M]，北京：高等教育出版社，2007 第5页 共10页