模拟退火算法对tsp问题的求解

《模拟退火算法对tsp问题的求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、模拟退火算法对TSP问题的求解柴涌（哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001）摘要：模拟退火算法在处理全局优化、离散变量优化等困难问题中具有传统优化算法无可比拟的优势。本文描述了模拟退火算法的原理及其基本框架结构，给出了用模拟退火算法求解TSP问题的具体实现方法，并分析说明了模拟退火算法的优缺点。关键词：模拟退火；组合优化；TSP问题中图分类号：TP273.1　　文献标识码：A　　文章编号：1001-005X(2008)01-0094-03SolvingTSPProblembyUs

2、ingSimulatedAnnealingAlgorithmCHAIYong(CollegeofInformationandCommunicationEngineering,HarbinEngineeringUniversity,Harbin150001,China)Abstract:Simulatedannealingalgorithmhasobviouslyunparalleledadvantagesinsolvingsomedifficultproblemsthanthetraditional

3、optimizationalgorithms,suchasglobaloptimizationanddiscretevariablesoptimization.Inthispaper,thebasicframeworkandprincipleofsimulatedannealingalgorithmweredescribed,andthespecificmethodtosolveTSPproblemwasgiven,finallytheadvantagesanddisadvantagesofsimu

4、latedannealingalgorithmwerealsoanalysised.Keywords:simulatedannealingalgorithm;combinatorialoptimization;TSPproblem　　在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路设计、代码设计、图像处理和电子工程等科技领域中，存在着大量的组合优化问题，其中的NP完全问题，其求解时间随着问题规模呈指数级增长，当规模稍大时就会因时间限制而失去可行性。以目前已成熟的数值计算理论和算法，或者

5、根本无法求解，或者其求解的计算量是爆炸性的，其花费的代价将是人们所不能接受的。旅行商问题（TravelingSalesmanProblem，简记为TSP）是一个典型的NP完全问题。它可简单地描述为：对于N个城市，它们之间的距离已知，有一旅行商要从某一城市出发走遍所有的城市，且每一个城市只能经过一次，最后回到出发城市，问如何选择路线可使他所走过的路程最短。TSP问题表面看很简单，其实不然。当TSP问题的规模为N个城市时，可行解集中的路径数为个，要从个可行解中找出哪条路径最短，若以路径间的比较为基本操作

6、，则需进行的基本操作数为次。当N较大时,其数量是惊人的。若用运算速度为1GFLOPS次的CrayⅡ型计算机进行搜索，当时,需要0.000025s；当时需要1.8h；当时则猛增到350a；当时则需要年！显然，如此求TSP问题的方法是不可行的。模拟退火算法（SimulatedAnnealing，简称SA）为求解上述传统方法难以处理的问题提供了一个有效的途径和通用框架，并逐渐发展成一种迭代自适应启发式概率性搜索算法，用以求解不同的非线性问题。对不可微甚至不连续的函数优化，SA能以较大概率求得全局优化解，具

7、有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性，并且能处理不同类型的优化设计变量（离散的、连续的和混合型的），不需要任何的辅助信息，对目标函数和约束函数没有任何要求。利用Metropolis算法并适当地控制温度下降过程，在优化问题中具有很强的竞争力，因此研究SA算法在优化中的应用显得尤为重要。本文就应用SA算法解决TSP优化问题。１模拟退火算法简介模拟退火算法的思想最早是由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火算法是一种通

8、用的优化算法，其物理退火过程由以下三部分组成：1.加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。2.等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡状态。3.冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参