資源描述：
《基于模擬退火算法的旅行商問題求解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、目錄摘要II關(guān)鍵詞IIAbstractIIKeywordsII引言11旅行商問題和模擬退火算法21.1旅行商問題21.1.1旅行商問題的描述21.1.2旅行商問題的應(yīng)用31.2模擬退火算法31.2.1基本思想31.2.2關(guān)鍵技術(shù)41.3小結(jié)42TSP模擬退火算法的實(shí)現(xiàn)52.1TSP算法實(shí)現(xiàn)52.1.1TSP算法描述52.1.2TSP算法流程52.2TSP的MATLAB實(shí)現(xiàn)62.2.1加載數(shù)據(jù)文件62.2.2計(jì)算總距離的函數(shù)72.2.3繪制路線的函數(shù)72.2.4交換城市的函數(shù)82.2.5執(zhí)行模擬退火的函數(shù)82.3小結(jié)93仿真實(shí)例103.1仿真分析與評(píng)價(jià)103
2、.2結(jié)論12總結(jié)與展望12致謝13參考文獻(xiàn)1312基于模擬退火算法的旅行商問題求解光信息科學(xué)與技術(shù)董鑄祥指導(dǎo)教師張明強(qiáng)摘要:旅行商問題是組合優(yōu)化領(lǐng)域里的一個(gè)典型的、易于描述卻難以處理的NP難題，其可能的路徑數(shù)目與城市數(shù)目是呈指數(shù)型增長的，求解非常困難。首先介紹了旅行商問題，給出了其數(shù)學(xué)描述以及實(shí)際應(yīng)用，進(jìn)而給出解決TSP的一種比較精確的算法——模擬退火算法。然后闡述了模擬退火算法的基本原理，重點(diǎn)說明了其基本思想及關(guān)鍵技術(shù)。最后運(yùn)用MATLAB語言實(shí)現(xiàn)了該算法，并將其運(yùn)用到解決旅行商問題的優(yōu)化之中。數(shù)值仿真的結(jié)果表明了該方法能夠?qū)?shù)據(jù)進(jìn)行全局尋優(yōu)，有效克服了
3、基于導(dǎo)數(shù)的優(yōu)化算法容易陷入局部最優(yōu)的問題。關(guān)鍵詞:模擬退火旅行商N(yùn)P組合優(yōu)化SolutionofTravellingSalesmanProblemBacedonSimulatedAnnealingAlgorithmOpticalInformationScienceandTechnologyDongZhuxiangTutorZhangMingqiangAbstract:TravellingSalesmanProblemisoneofthetypicalNP-hardproblemsincombinatorialoptimization,whichiseasy
4、tobedescribedbuthardtobesolved.Itspossibleamountsofpathincreaseexponentiallywiththeamountsofcity,soitisverydifficulttosolveit.FirstthispaperintroducesTravellingSalesmanProblem,givesTSPmathematicaldescriptionandpracticalapplication.Inturn,aprecisealgorithm——simulatedannealingalgori
5、thmthetotheaddressofTSPisgiven.Andthenthispaperdescribesthebasicprincipleofsimulatedannealing,highlightsthebasicideasandkeytechnology.Finally,weuseMATLABlanguagetoimplementthealgorithm,andappliedittosolvethetravelingsalesmanproblemintotheoptimization.Numericalsimulationresultsshow
6、thatthismethodcangloballyoptimizesdata,effectivelyovercomestheproblemofderivative-basedoptimizationalgorithmwhichiseasyfallintolocaloptimum.Keywords:simulatedannealing;travellingsalesmanproblem;Non-deterministicPolynomial;combinatorialoptimization12引言旅行商問題(TravelingSalesmanProblem
7、,TSP)，也稱為貨郎擔(dān)問題，是由愛爾蘭數(shù)學(xué)家SirWilliamRowanHamilton和英國數(shù)學(xué)家ThomasPenyngtonKirkman在19世紀(jì)提出的數(shù)學(xué)問題，它是指給定n個(gè)城市并給出每兩個(gè)城市之間的距離，旅行商必須以最短路徑訪問所有的城市一次且僅一次，并回到原出發(fā)地，現(xiàn)已證明它屬于NP(Non-deterministicPolynomial---非確定多項(xiàng)式)難題[1]。歷史上的第一個(gè)正式用來解決TSP問題的算法誕生于1954年,它被用來計(jì)算49個(gè)城市的TSP問題。到現(xiàn)在為止,運(yùn)用目前最先進(jìn)的計(jì)算機(jī)技術(shù)可解決找出游歷24978個(gè)城市的TSP
8、問題。TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周游問
