基于模拟退火算法的TSP研究.pdf

《基于模拟退火算法的TSP研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、l学术探讨算藩侪究f2012率第4嬲基于模拟退火算法的TSP研究黄丽韶(湖南科技学院计算机与通信工程系，湖南永州425100)[摘要]多项式复杂程度的非确定性(NP)问题是一种纽合优化问题，模拟退火算法(sA)是其中的一种搜索方法。同其它通用的有效近似算法相比，SA应用的范围较广，运行的效率也较高，还具有描述较简单、能够实现灵活使用的优点。本文首先分析了sA的基本原理，针对TSP问题，我们将sA应用到TSP上，并建立了TSP的数学模型，阐述了利用模拟退火算法解TSP的方法。最后通过实验实现了求解TSP的模拟退火算法。[关键词]模拟退火；TSP；组合优化决此问题的

2、。到了2003年，HisaoTamaki发现了TSPHB中1．意义和目标pla33810的一个次优解，当时使用了Lin—Kemigh~an启发和1．1意义路径融合的变种相结合的方法。之后，由KeldHelsgaun在TSP(TravelingSalesmanProblem)是优化技术领域中一2004年获得了plas5900问题的次优解。同年12月又获得了个具有代表性的问题，它经常被用来测试很多新型算法的目前为止已知的求解规最大的7，516，353，779个节点的世性能，是优化技术一种成功的体现。在优化算法及其启发式界TSP问题中一条比较好的解。搜索中，TSP已经

3、成为了一种标准。研究TSP，加深对TSPTSP可能的路径总数与城市数目n是成阶乘数增长算法的理解，对我们继续学习优化理论知识有很大帮助。的，故一般很难精确地求出其最优解。对于这个问题，不论模拟退火算法是一种高效的全局优化方法，其基本思是传统的动态规划、分枝定界法、贪婪法等方法，还是在近想来源于固体的退火过程。目前该算法已经在自然科学、工些年的研究过程中采用的各种智能优化算法如：模拟退火、程技术和管理等诸多领域得到广泛应用。研究模拟退火算遗传算法、人工神经网络、蚁群算法等都存在解的质量不高法，有助于我们解决更多的应用于组合优化的问题。或者需要的时空开销太大等问题圆

4、。1．2目标2．2模拟退火算法的研究现状本文是基于模拟退火算法的TSP的研究，使用模拟退在理论上，受到广大学者与专家青睐的模拟退火算法火算法解决TSP。了解TSP和模拟退火算法的国内外研究能够达到全局极小值，这是已经得到证明的。近些年，有两现状，实现模拟退火算法，并使该算法应用于TSP中，最终类关于模拟退火算法的研究。其一，是基于有限状态奇异马求出TSP问题的结果。尔可夫链的有关理论，给出模拟退火算法的某些关于理想2．国内外研究现状收敛模型的充分条件或充要条件，这些条件在理论上证明2．1TSP的研究现状了当退火三个原则f初始温度足够高、降温速度足够慢、终止求解T

5、SP问题是具有一定难度的，但是，随着优化理论温度足够低)满足时，模拟退火算法以概率1达到全局最优和技术的不断发展，及其计算机技术的飞速进步，人们在解；其二，是针对某些具体问题，给出了模拟退火算法的很TSP问题上面取得了一个又一个的突破『l1。多成功应用。事实上，正是由于专家和学者对该算法的钻1980年，对于318座城市的TSP问题是～个难题，但研，才使该算法从经典的模拟退火算法走到了今天的多样是由Padberg、Crowder成功地求解出了最优解。1987年，性的模拟退火算法：快速模拟退火算法，使得该算法的速度2392座城市的TSP问题由Rinaldi、Padb

6、erg求解。1992年，和收敛性都得到较大提高；适应性的模拟退火算法，使得该城市数达到3038座的TSP问题也由美国莱斯大学的算法具有一定的智能性：现在有学者提到的遗传一模拟退CRPC小组成功得到解决，这是用50台工作站和一种基于火算法，就是将遗传算法和模拟退火算法二者的优越性结“切平面”的算法来求解的，当年此次成绩还被《发现杂志》合起来；带有单调升温的模拟退火算法[31，使得搜索跳出局评为50大科学新闻之一。1994年，由Applegate、Chvatal和部最优变得相对会容易。其实，每种算法都是在应用中被提Bixby等人解决了TSP中7397座城市的问题，他

7、们花了出的，它是同应用进行结合的，不能分开，这样，算法才能更3．4年的CPU时间，利用的是若干台SPARC作站组成的机好地适应于应用的领域，才能为应用服务。正是因为模拟退群。1995年，TSP中的13509座城市问题由CRPC研究小组火算法能够达到全局极小值，而且是在理论上的，所以，在成功解决，他们当时是拿三台DigitalAlphaServer4100s(12实际意义上，对该算法进行研究才更加具有意义，许多的专个处理器)组成的集群和32台Pentinrn．I1个人计算机来解家和学者都在非常努力地将这个问题进行普遍化一般化，作者简介：黄丽韶，女，湖南永州人，硕士

8、研究生，助教，研究方向：