基于模拟退火算法的旅行商问题求解

基于模拟退火算法的旅行商问题求解

ID:884303

大小:939.01 KB

页数:15页

时间:2017-09-23

基于模拟退火算法的旅行商问题求解_第1页
基于模拟退火算法的旅行商问题求解_第2页
基于模拟退火算法的旅行商问题求解_第3页
基于模拟退火算法的旅行商问题求解_第4页
基于模拟退火算法的旅行商问题求解_第5页
资源描述:

《基于模拟退火算法的旅行商问题求解》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、目录摘要II关键词IIAbstractIIKeywordsII引言11旅行商问题和模拟退火算法21.1旅行商问题21.1.1旅行商问题的描述21.1.2旅行商问题的应用31.2模拟退火算法31.2.1基本思想31.2.2关键技术41.3小结42TSP模拟退火算法的实现52.1TSP算法实现52.1.1TSP算法描述52.1.2TSP算法流程52.2TSP的MATLAB实现62.2.1加载数据文件62.2.2计算总距离的函数72.2.3绘制路线的函数72.2.4交换城市的函数82.2.5执行模拟退火的函数82.3小结93仿真实例103.1仿真分

2、析与评价103.2结论12总结与展望12致谢13参考文献1312基于模拟退火算法的旅行商问题求解光信息科学与技术董铸祥指导教师张明强摘要:旅行商问题是组合优化领域里的一个典型的、易于描述却难以处理的NP难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难。首先介绍了旅行商问题,给出了其数学描述以及实际应用,进而给出解决TSP的一种比较精确的算法——模拟退火算法。然后阐述了模拟退火算法的基本原理,重点说明了其基本思想及关键技术。最后运用MATLAB语言实现了该算法,并将其运用到解决旅行商问题的优化之中。数值仿真的结果表明了该方法能够对

3、数据进行全局寻优,有效克服了基于导数的优化算法容易陷入局部最优的问题。关键词:模拟退火旅行商NP组合优化SolutionofTravellingSalesmanProblemBacedonSimulatedAnnealingAlgorithmOpticalInformationScienceandTechnologyDongZhuxiangTutorZhangMingqiangAbstract:TravellingSalesmanProblemisoneofthetypicalNP-hardproblemsincombinatorialopt

4、imization,whichiseasytobedescribedbuthardtobesolved.Itspossibleamountsofpathincreaseexponentiallywiththeamountsofcity,soitisverydifficulttosolveit.FirstthispaperintroducesTravellingSalesmanProblem,givesTSPmathematicaldescriptionandpracticalapplication.Inturn,aprecisealgorit

5、hm——simulatedannealingalgorithmthetotheaddressofTSPisgiven.Andthenthispaperdescribesthebasicprincipleofsimulatedannealing,highlightsthebasicideasandkeytechnology.Finally,weuseMATLABlanguagetoimplementthealgorithm,andappliedittosolvethetravelingsalesmanproblemintotheoptimiza

6、tion.Numericalsimulationresultsshowthatthismethodcangloballyoptimizesdata,effectivelyovercomestheproblemofderivative-basedoptimizationalgorithmwhichiseasyfallintolocaloptimum.Keywords:simulatedannealing;travellingsalesmanproblem;Non-deterministicPolynomial;combinatorialopti

7、mization12引言旅行商问题(TravelingSalesmanProblem,TSP),也称为货郎担问题,是由爱尔兰数学家SirWilliamRowanHamilton和英国数学家ThomasPenyngtonKirkman在19世纪提出的数学问题,它是指给定n个城市并给出每两个城市之间的距离,旅行商必须以最短路径访问所有的城市一次且仅一次,并回到原出发地,现已证明它属于NP(Non-deterministicPolynomial---非确定多项式)难题[1]。历史上的第一个正式用来解决TSP问题的算法诞生于1954年,它被用来计算4

8、9个城市的TSP问题。到现在为止,运用目前最先进的计算机技术可解决找出游历24978个城市的TSP问题。TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。