模拟退火算法在TSP求解中的应用.docx

模拟退火算法在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)的所有循环排列的集合，即S= [Sij]为(1…n)的排列，Si表示第i个城市第Si个被访问。(3)目标函数：目标函数为访问所有城市的回路长度或称为代价函数，需求其最小值，选d = 为最小。3模拟退火算法求解TSP求解T