基于模擬退火算法的旅行商問(wèn)題求解

目錄TOC\o"1-3"\h摘要II關(guān)鍵詞IIAbstractIIKeywordsII引言11旅行商問(wèn)題和模擬退火算法21.1旅行商問(wèn)題2旅行商問(wèn)題的描述2旅行商問(wèn)題的應(yīng)用31.2模擬退火算法3根本思想3關(guān)鍵技術(shù)4小結(jié)42TSP模擬退火算法的實(shí)現(xiàn)52.1TSP算法實(shí)現(xiàn)5TSP算法描述5TSP算法流程52.2TSP的MATLAB實(shí)現(xiàn)62.2.1加載數(shù)據(jù)文件6計(jì)算總距離的函數(shù)7繪制路線的函數(shù)7交換城市的函數(shù)8執(zhí)行模擬退火的函數(shù)8小結(jié)93仿真實(shí)例10仿真分析與評(píng)價(jià)10結(jié)論12總結(jié)與展望12致謝13參考文獻(xiàn)13基于模擬退火算法的旅行商問(wèn)題求解光信息科學(xué)與技術(shù)董鑄祥指導(dǎo)教師張明強(qiáng)摘要:旅行商問(wèn)題是組合優(yōu)化領(lǐng)域里的一個(gè)典型的、易于描述卻難以處理的NP難題，其可能的路徑數(shù)目與城市數(shù)目是呈指數(shù)型增長(zhǎng)的，求解非常困難。首先介紹了旅行商問(wèn)題，給出了其數(shù)學(xué)描述以及實(shí)際應(yīng)用，進(jìn)而給出解決TSP的一種比擬精確的算法——模擬退火算法。然后闡述了模擬退火算法的根本原理，重點(diǎn)說(shuō)明了其根本思想及關(guān)鍵技術(shù)。最后運(yùn)用MATLAB語(yǔ)言實(shí)現(xiàn)了該算法，并將其運(yùn)用到解決旅行商問(wèn)題的優(yōu)化之中。數(shù)值仿真的結(jié)果說(shuō)明了該方法能夠?qū)?shù)據(jù)進(jìn)行全局尋優(yōu)，有效克服了基于導(dǎo)數(shù)的優(yōu)化算法容易陷入局部最優(yōu)的問(wèn)題。關(guān)鍵詞:模擬退火旅行商N(yùn)P組合優(yōu)化SolutionofTravellingSalesmanProblemBacedonSimulatedAnnealingAlgorithmOpticalInformationScienceandTechnologyDongZhuxiangTutorZhangMingqiangAbstract:TravellingSalesmanProblemisoneofthetypicalNP-hardproblemsincombinatorialoptimization,whichiseasytobedescribedbuthardtobesolved.Itspossibleamountsofpathincreaseexponentiallywiththeamountsofcity,soitisverydifficulttosolveit.FirstthispaperintroducesTravellingSalesmanProblem,givesTSPmathematicaldescriptionandpracticalapplication.Inturn,aprecisealgorithm——simulatedannealingalgorithmthetotheaddressofTSPisgiven.Andthenthispaperdescribesthebasicprincipleofsimulatedannealing,highlightsthebasicideasandkeytechnology.Finally,weuseMATLABlanguagetoimplementthealgorithm,andappliedittosolvethetravelingsalesmanproblemintotheoptimization.Numericalsimulationresultsshowthatthismethodcangloballyoptimizesdata,effectivelyovercomestheproblemofderivative-basedoptimizationalgorithmwhichiseasyfallintolocaloptimum.Keywords:simulatedannealing;travellingsalesmanproblem;Non-deterministicPolynomial;combinatorialoptimization引言旅行商問(wèn)題(TravelingSalesmanProblem,TSP)，也稱為貨郎擔(dān)問(wèn)題，是由愛爾蘭數(shù)學(xué)家SirWilliamRowanHamilton和英國(guó)數(shù)學(xué)家ThomasPenyngtonKirkman在19世紀(jì)提出的數(shù)學(xué)問(wèn)題，它是指給定n個(gè)城市并給出每?jī)蓚€(gè)城市之間的距離，旅行商必須以最短路徑訪問(wèn)所有的城市一次且僅一次，并回到原出發(fā)地，現(xiàn)已證明它屬于NP(Non-deterministicPolynomial非確定多項(xiàng)式)難題[1]。歷史上的第一個(gè)正式用來(lái)解決TSP問(wèn)題的算法誕生于1954年,它被用來(lái)計(jì)算49個(gè)城市的TSP問(wèn)題。到現(xiàn)在為止,運(yùn)用目前最先進(jìn)的計(jì)算機(jī)技術(shù)可解決找出游歷24978個(gè)城市的TSP問(wèn)題。TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周游問(wèn)題，即對(duì)于國(guó)際象棋棋盤中的64個(gè)方格，走訪64個(gè)方格一次且僅一次，并且最終返回到起始點(diǎn)。旅行商問(wèn)題(TSP)由美國(guó)RAND公司于1948年引入，該公司的聲譽(yù)以及線性規(guī)劃這一新方法的出現(xiàn)使得TSP成為一個(gè)知名且流行的問(wèn)題[2]。旅行商問(wèn)題是一個(gè)經(jīng)典的圖論問(wèn)題：設(shè)有n個(gè)城市，用Ci，j=1，2，…，n表示。城市Ci,j之間的距離為di,j，i，j=1，2，…，n，設(shè)所有城市間兩兩連通，旅行商需要跑遍n個(gè)城市去推銷他的商品，而這些城市之間的距離都不一樣，這推銷員需要從其中一個(gè)城市出發(fā)，而他老板規(guī)定他必須把所有城市跑一遍，那么TSP問(wèn)題就是尋找讓旅行商遍訪每個(gè)城市一次且恰好一次的一條回路，且要求其路徑總長(zhǎng)度為最短。該問(wèn)題也可以歸結(jié)為：有N個(gè)城市由公路相互連通，從任一城市到另外城市都要支付相應(yīng)的費(fèi)用，一個(gè)銷售商從其中一城市出發(fā)，訪問(wèn)其他N－1個(gè)城市且僅一次，如何規(guī)劃一條路徑，使該旅行商的花費(fèi)最少[3]。當(dāng)城市數(shù)量較小時(shí)，通過(guò)枚舉法就可以找出最短的路徑，然而隨著問(wèn)題規(guī)模的增加，很難找到一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的算法來(lái)求解該問(wèn)題。TSP是一個(gè)典型的組合優(yōu)化問(wèn)題，是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式，并且已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比擬標(biāo)準(zhǔn)。因此，快速、有效地解決TSP有著重要的理論價(jià)值和極高的實(shí)際應(yīng)用價(jià)值。旅行商問(wèn)題代表的一類組合優(yōu)化問(wèn)題,在物流配送、計(jì)算機(jī)網(wǎng)絡(luò)、電子地圖、交通誘導(dǎo)、電氣布線、VLSI單元布局等方面都有重要的工程和理論價(jià)值，引起了許多學(xué)者的關(guān)注。TSP是典型的組合優(yōu)化問(wèn)題，并且是一個(gè)NP-hard問(wèn)題。TSP描述起來(lái)很簡(jiǎn)單，早期的研究者使用精確算法求解該問(wèn)題，TSP問(wèn)題最簡(jiǎn)單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨于無(wú)窮大的復(fù)雜解的空間，搜索空間是n個(gè)點(diǎn)的所有排列的集合，大小為〔n-1〕！。可以形象地把解空間看成是一個(gè)無(wú)窮大的丘陵地帶，各山峰或山谷的高度即是問(wèn)題的極值。求解TSP，那么是在此不能窮盡的丘陵地帶中攀登以到達(dá)山頂或谷底的過(guò)程[2]。常用的方法包括：分枝定界法、線性規(guī)劃法和動(dòng)態(tài)規(guī)劃法等，但可能的路徑總數(shù)隨城市數(shù)目n是成指數(shù)型增長(zhǎng)的，所以當(dāng)城市數(shù)目在100個(gè)以上一般很難精確的求出其全局最優(yōu)解。隨著人工智能的開展，出現(xiàn)了許多獨(dú)立于問(wèn)題的智能優(yōu)化算法，如蟻群算法、遺傳算法、模擬退火、禁忌搜索、神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等，通過(guò)模擬或解釋某些自然現(xiàn)象或過(guò)程而得以開展，為解決復(fù)雜組合優(yōu)化問(wèn)題提供了新的思路和方法[4]。模擬退火算法在迭代搜索過(guò)程以Boltzmann分布概率接受目標(biāo)函數(shù)的“劣化解〞，具有突出的具有脫離局域最優(yōu)陷阱的能力，同時(shí)具有較強(qiáng)的局部搜索能力，從而可以獲取目標(biāo)函數(shù)的全局最優(yōu)解。因?yàn)槟M退火算法具有高效、通用、靈活的優(yōu)點(diǎn)，將模擬退火算法引入TSP求解，可以防止在求解過(guò)程中陷入TSP的局部最優(yōu)解[5]。本文首先介紹傳統(tǒng)的TSP問(wèn)題，先對(duì)其進(jìn)行數(shù)學(xué)描述，又列舉TSP問(wèn)題的應(yīng)用。之后介紹模擬退火算法，主要介紹其根本思想和關(guān)鍵技術(shù)，在此根底上將模擬退火的思想引入TSP的求解，設(shè)計(jì)出TSP的一種模擬退火算法并用MATLAB語(yǔ)言編程予以實(shí)現(xiàn)。1旅行商問(wèn)題和模擬退火算法1.1旅行商問(wèn)題旅行商問(wèn)題的描述旅行商問(wèn)題〔TravelingSalesmanProblem，簡(jiǎn)稱TSP〕又名貨郎擔(dān)問(wèn)題，是威廉·哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼(T.P.Kirkman)于19世紀(jì)初提出的一個(gè)數(shù)學(xué)問(wèn)題，也是著名的組合優(yōu)化問(wèn)題。問(wèn)題是這樣描述的：一名商人要到假設(shè)干城市去推銷商品，城市個(gè)數(shù)和各城市間的路程〔或旅費(fèi)〕，要求找到一條從城市1出發(fā)，經(jīng)過(guò)所有城市且每個(gè)城市只能訪問(wèn)一次，最后回到城市1的路線，使總的路程〔或旅費(fèi)〕最小。TSP剛提出時(shí)，不少人認(rèn)為這個(gè)問(wèn)題很簡(jiǎn)單。后來(lái)人們才逐步意識(shí)到這個(gè)問(wèn)題只是表述簡(jiǎn)單，易于為人們所理解，而其計(jì)算復(fù)雜性卻是問(wèn)題的輸入規(guī)模的指數(shù)函數(shù)，屬于相當(dāng)難解的問(wèn)題。這個(gè)問(wèn)題數(shù)學(xué)描述為：假設(shè)有n個(gè)城市，并分別編號(hào)，給定一個(gè)完全無(wú)向圖G=〔V，E〕，V={1，2，…，n}，n>1。其每一邊(i,j)E有一非負(fù)整數(shù)消耗Ci,j(即上的權(quán)記為Ci,j，i，jV)。并設(shè)G的一條巡回路線是經(jīng)過(guò)V中的每個(gè)頂點(diǎn)恰好一次的回路。一條巡回路線的消耗是這條路線上所有邊的權(quán)值之和。TSP問(wèn)題就是要找出G的最小消耗回路。人們?cè)诳紤]解決這個(gè)問(wèn)題時(shí)，一般首先想到的最原始的一種方法就是:列出每一條可供選擇的路線(即對(duì)給定的城市進(jìn)行排列組合)，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的4個(gè)城市分別為A、B、C和D，各城市之間的消耗為己知數(shù)，如圖1所示。我們可以通過(guò)一個(gè)組合的狀態(tài)空間圖來(lái)表示所有的組合，如圖圖1-1頂點(diǎn)帶權(quán)圖圖1-2TSP問(wèn)題的解空間樹從圖中不難看出，可供選擇的路線共有6條，從中很快可以選出一條總消耗最短的路線：頂點(diǎn)序列為〔A,C,B,D,A〕。由此推算，假設(shè)設(shè)城市數(shù)目為n時(shí)，那么組合路徑數(shù)那么為(n-1)!。很顯然，當(dāng)城市數(shù)目不多時(shí)要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級(jí)數(shù)規(guī)律急劇增長(zhǎng)，以至到達(dá)無(wú)法計(jì)算的地步，這就是所謂的“組合爆炸問(wèn)題〞。假設(shè)現(xiàn)在城市的數(shù)目增為20個(gè)，組合路徑數(shù)那么為(20-1)!≈1.216×1017，如此龐大的組合數(shù)目，假設(shè)計(jì)算機(jī)以每秒檢索1000萬(wàn)條路線的速度計(jì)算，也需要花上386年的時(shí)間[6]。旅行商問(wèn)題的應(yīng)用TSP是最有代表性的優(yōu)化組合問(wèn)題之一，其應(yīng)用已逐步滲透到各個(gè)技術(shù)領(lǐng)域和我們的日常生活中。它一開始是為交通運(yùn)輸而提出的，比方飛機(jī)航線安排、送郵件、快遞效勞、設(shè)計(jì)校車行進(jìn)路線等等。實(shí)際上其應(yīng)用范圍擴(kuò)展到了許多其他領(lǐng)域，如在VLSI芯片設(shè)計(jì)、電路板布局、機(jī)器人控制、車輛選路、物流配送等方面，下面舉幾個(gè)實(shí)例。1．電路板鉆孔進(jìn)度的安排。機(jī)器在電路板上鉆孔的調(diào)度問(wèn)題是TSP應(yīng)用的經(jīng)典例子，在一電路板上打成百上千個(gè)孔，轉(zhuǎn)頭在這些孔之間移動(dòng)，相當(dāng)于對(duì)所有的孔進(jìn)行一次巡游。把這個(gè)問(wèn)題轉(zhuǎn)化為TSP，孔相當(dāng)于城市，轉(zhuǎn)頭從一個(gè)孔移到另一個(gè)孔所耗的時(shí)間相當(dāng)于TSP中的旅費(fèi)。2．車輛選路。一個(gè)經(jīng)典的路由問(wèn)題是在一個(gè)網(wǎng)絡(luò)上發(fā)現(xiàn)從源節(jié)點(diǎn)到一個(gè)目的節(jié)點(diǎn)的最正確交通線路，使與距離成比例的流動(dòng)費(fèi)用降低到最小。這個(gè)問(wèn)題的關(guān)鍵是在交通網(wǎng)絡(luò)上計(jì)算從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的最短路徑。對(duì)這個(gè)最小費(fèi)用流動(dòng)問(wèn)題進(jìn)行擴(kuò)展，就構(gòu)成TSP問(wèn)題，在這個(gè)問(wèn)題中，車輛從源點(diǎn)出發(fā)訪問(wèn)多個(gè)目的地并且最后回到源點(diǎn)。3.基因測(cè)序。Cnoocdre是一種求解旅行商問(wèn)題的程序。美國(guó)國(guó)家衛(wèi)生機(jī)構(gòu)的研究人員利用這一程序來(lái)進(jìn)行基因測(cè)序。在這一應(yīng)用中，DNA片斷作為城市，它們之間的相似程度作為城市與城市的距離。研究人員試圖尋找一種可能性最高的連接方式把這些DNA片斷合成為整張DNA。更重要的是，TSP提供了一個(gè)研究組合優(yōu)化問(wèn)題的理想平臺(tái)。很多組合優(yōu)化問(wèn)題，比方背包問(wèn)題、分配問(wèn)題、車間調(diào)度問(wèn)題，和TSP同屬NP-Hard類，它們難度同等，如果其中一個(gè)能用多項(xiàng)式確定性算法解決，那么其他所有的NP-Hard類問(wèn)題也能用多項(xiàng)式確定性算法解決。很多方法都是從TSP開展起來(lái)的，后來(lái)推廣到其他NP-Hard類問(wèn)題上去。1.2模擬退火算法模擬退火算法由KirkPatrick于1982提出[7]，他將退火思想引入到組合優(yōu)化領(lǐng)域,提出一種求解大規(guī)模組合優(yōu)化問(wèn)題的方法，對(duì)于NP-完全組合優(yōu)化問(wèn)題尤其有效。模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之到達(dá)能量最低點(diǎn)。反之，如果急速降溫(即淬火)那么不能到達(dá)最低點(diǎn)。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而緩慢降溫時(shí)粒子漸趨有序，在每個(gè)溫度上都到達(dá)平衡態(tài)，最后在常溫時(shí)到達(dá)基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)那么，粒子在溫度T時(shí)趨于平衡的概率為exp(-E/(kT))，其中E為溫度T時(shí)的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)產(chǎn)生“新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄〞的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子a、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件C。根本思想模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解3局部。其根本思想是：(1)初始化：初始溫度T(充分大)，初始解狀態(tài)s(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L；(2)對(duì)k=1，……，L做第(3)至第6步；(3)產(chǎn)生新解s′；(4)計(jì)算增量cost=cost(s′)-cost(s)，其中cost(s)為評(píng)價(jià)函數(shù)；(5)假設(shè)t′0那么接受s′作為新的當(dāng)前解，否那么以概率exp(-t′/T)接受s′作為新的當(dāng)前解；(6)如果滿足終止條件那么輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)假設(shè)干個(gè)新解都沒有被接受時(shí)終止算法；(7)T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運(yùn)算。關(guān)鍵技術(shù)〔1〕新解的產(chǎn)生和接受模擬退火算法新解的產(chǎn)生和接受可分為如下4個(gè)步驟：①由一個(gè)函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解。為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，常選擇由當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或局部元素進(jìn)行置換、互換等。產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。②計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換局部產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)說(shuō)明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。③判斷新解是否被接受。判斷的依據(jù)是一個(gè)接受準(zhǔn)那么，最常用的接受準(zhǔn)那么是Metropo1is準(zhǔn)那么：假設(shè)t′0那么接受S′作為新的當(dāng)前解S，否那么以概率exp(-t′/T)接受S′作為新的當(dāng)前解S。④當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解。這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換局部予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代，可在此根底上開始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，那么在原當(dāng)前解的根底上繼續(xù)下一輪試驗(yàn)。模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性?！?〕參數(shù)控制問(wèn)題模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下3點(diǎn)[7]：①溫度T的初始值設(shè)置。溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，那么搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，那么可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行假設(shè)干次調(diào)整。②溫度衰減函數(shù)的選取。衰減函數(shù)用于控制溫度的退火速度，一個(gè)常用的函數(shù)為：式中是一個(gè)非常接近于1的常數(shù)，t為降溫的次數(shù)。③馬爾可夫鏈長(zhǎng)度L的選取。通常的原那么是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L的選取應(yīng)遵循在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡的原那么。小結(jié)本章而要的介紹了旅行商問(wèn)題與模擬退火算法，首先對(duì)旅行商問(wèn)題做了描述并舉例其應(yīng)用，然后介紹了模擬退火算法的來(lái)源，重點(diǎn)介紹了模擬退火算法的根本思想和關(guān)鍵技術(shù)。通過(guò)本章的分析，使我們理解了模擬退火算法的根本原理并且知道了TSP問(wèn)題的數(shù)學(xué)描述，為下面將該算法其應(yīng)用于旅行商問(wèn)題做了準(zhǔn)備。2TSP模擬退火算法的實(shí)現(xiàn)TSP是典型的組合優(yōu)化問(wèn)題，模擬退火算法是一種隨機(jī)性解決組合優(yōu)化方法。將TSP與模擬退火算法相結(jié)合，以實(shí)現(xiàn)對(duì)其求解。2.1TSP算法實(shí)現(xiàn)TSP算法描述〔1〕TSP問(wèn)題的解空間和初始解TSP的解空間S是遍訪每個(gè)城市恰好一次的所有回路，是所有城市排列的集合。TSP問(wèn)題的解空間S可表示為{1,2,…,n}的所有排列的集合，即S={(c1,c2,…,cn)|((c1,c2,…,cn)為{1,2,…,n}的排列〕}，其中每一個(gè)排列Si表示遍訪n個(gè)城市的一個(gè)路徑，ci=j表示在第i次訪問(wèn)城市j。模擬退火算法的最優(yōu)解與初始狀態(tài)無(wú)關(guān)，故初始解為隨機(jī)函數(shù)生成一個(gè){1,2,…,n}的隨機(jī)排列作為S0。〔2〕目標(biāo)函數(shù)TSP問(wèn)題的目標(biāo)函數(shù)即為訪問(wèn)所有城市的路徑總長(zhǎng)度，也可稱為代價(jià)函數(shù)：現(xiàn)在TSP問(wèn)題的求解就是通過(guò)模擬退火算法求出目標(biāo)函數(shù)C(c1,c2,…,cn)的最小值，相應(yīng)地，s*=(c*1,c*2,…,c*n)即為TSP問(wèn)題的最優(yōu)解?！?〕新解產(chǎn)生新解的產(chǎn)生對(duì)問(wèn)題的求解非常重要。新解可通過(guò)分別或者交替用以下2種方法產(chǎn)生：①二變換法：任選序號(hào)u,v(設(shè)uvn)，交換u和v之間的訪問(wèn)順序，假設(shè)交換前的解為si=(c1,c2,…,cu,…,cv,…,cn),交換后的路徑為新路徑，即：si′=(c1,…,cu-1,cv,cv-1,…,cu+1,cu,cv+1,…,cn)②三變換法：任選序號(hào)u,v和ω(u≤vω)，將u和v之間的路徑插到ω之后訪問(wèn)，假設(shè)交換前的解為si=(c1,c2,…,cu,…,cv,…,cω,…,cn)，交換后的路徑為的新路徑為：si′=(c1,…,cu-1,cv+1,…,cω,cu,…,cv,cω+1,…,cn)〔4〕目標(biāo)函數(shù)差計(jì)算變換前的解和變換后目標(biāo)函數(shù)的差值：Δc′=c(si′)-c(si)〔5〕Metropolis接受準(zhǔn)那么根據(jù)目標(biāo)函數(shù)的差值和概率exp(-ΔC′/T)接受si′作為新的當(dāng)前解si，接受準(zhǔn)那么：2.1.2TSP算法流程根據(jù)以上對(duì)TSP的算法描述，可以寫出用模擬退火算法解TSP問(wèn)題的流程圖2-1所示：圖2-1TSP的模擬退火流程2.2TSP的MATLAB實(shí)現(xiàn)2.2.1加載數(shù)據(jù)文件下面是加載數(shù)據(jù)文件的一個(gè)例子：functiond=datafile()cities=[0.6606,0.9695,0.5906,0.2124,0.0398,0.1367,0.9536,0.6091,0.8767,...0.8148,0.3876,0.7041,0.0213,0.3429,0.7471,0.5449,0.9464,0.1247,0.1636,...0.8668,;0.9500,0.6740,0.5029,0.8274,0.9697,0.5979,0.2184,0.7148,0.2395,...0.2867,0.8200,0.3296,0.1649,0.3025,0.8192,0.9392,0.8191,0.4351,0.8646,...0.6768];savecities.matcities-V6;當(dāng)調(diào)用數(shù)據(jù)文件函數(shù)時(shí)，包含城市坐標(biāo)信息的矩陣載入到cities.mat的文件中。該數(shù)據(jù)文件的第一列通常是城市數(shù)量，之后兩列為城市的坐標(biāo)。初始化函數(shù)，根據(jù)直角坐標(biāo)生成城市距離矩陣。計(jì)算總距離的函數(shù)這是一個(gè)城市間計(jì)算距離的函數(shù)，根據(jù)給定路徑計(jì)算該路徑對(duì)應(yīng)總路程。functiond=distance(inputcities)%DISTANCE%d=DISTANCE(inputcities)按照要求計(jì)算TSP問(wèn)題中n個(gè)城市的距離。%輸入?yún)?shù)有兩行和n列，其中n為城市的數(shù)目，列為對(duì)應(yīng)城市的坐標(biāo)。d=0;forn=1:length(inputcities)ifn==length(inputcities)d=d+norm(inputcities(:,n)-inputcities(:,1));elsed=d+norm(inputcities(:,n)-inputcities(:,n+1));endendTSP問(wèn)題的本錢函數(shù)是城市之間的距離。調(diào)用此函數(shù)將計(jì)算n個(gè)城市之間的距離。繪制路線的函數(shù)這是一個(gè)繪制路線的函數(shù)，根據(jù)給定的城市坐標(biāo)生成的城市矩陣?yán)L制城市的坐標(biāo)，根據(jù)給定的路線繪制線路。functionf=plotcities(inputcities)%PLOTCITIES%PLOTCITIES(inputcities)從inputcities參數(shù)中繪制城市的位置。%inputcities參數(shù)有兩行和n列，其中n為城市的數(shù)量。位置和對(duì)稱路徑都被繪制。temp_1=plot(inputcities(1,:),inputcities(2,:),’b*’);set(temp_1,’erasemode’,’none’);temp_2=line(inputcities(1,:),inputcities(2,:),’Marker’,’*’);set(temp_2,’color’,’r’);x=[inputcities(1,1)inputcities(1,length(inputcities))];y=[inputcities(2,1)inputcities(2,length(inputcities))];x1=10*round(max(inputcities(1,:))/10);y1=10*round(max(inputcities(2,:))/10);ifx1==0x1=1;endify1==0y1=1;endaxis([0x10y1]);temp_3=line(x,y);set(temp_3,’color’,’r’);dist=distance(inputcities);distance_print=sprintf(...’Theroundtriplengthfor%dcitiesis%4.6funits’...,length(inputcities),dist);text(x1/15,1.05*y1,distance_print,’fontweight’,’bold’);drawnow;交換城市的函數(shù)這是一個(gè)用于城市交換的函數(shù)，它從某路徑的鄰域中隨機(jī)的選擇一個(gè)新的路徑。functions=swapcities(inputcities,n)%SWAPCITIES%s=SWAPCITIES(inputcities,n)n個(gè)城市隨機(jī)的交換返回一組m個(gè)城市s=inputcities;fori=1:ncity_1=round(length(inputcities)*rand(1));ifcity_1<1city_1=1;endcity_2=round(length(inputcities)*rand(1));ifcity_2<1city_2=1;endtemp=s(:,city_1);s(:,city_1)=s(:,city_2);s(:,city_2)=temp;end執(zhí)行模擬退火的函數(shù)functions=simulatedannealing(inputcities,initial_temperature,...cooling_rate,threshold,numberofcitiestoswap)%SIMULATEDANNEALING%S=SIMULATEDANNEALING(inputcities,initial_temperature,cooling_rate)通過(guò)%n個(gè)城市的TSP問(wèn)題的最優(yōu)解返回一個(gè)新的城市構(gòu)型。globaliterations;temperature=initial_temperature;initial_cities_to_swap=numberofcitiestoswap;iterations=1;complete_temperature_iterations=0;whileiterations<thresholdprevious_distance=distance(inputcities);temp_cities=swapcities(inputcities,numberofcitiestoswap);current_distance=distance(temp_cities);diff=abs(current_distance-previous_distance);ifcurrent_distance<previous_distanceinputcities=temp_cities;plotcities(inputcities);ifcomplete_temperature_iterations>=10temperature=cooling_rate*temperature;complete_temperature_iterations=0;endnumberofcitiestoswap=round(numberofcitiestoswap...*exp(-diff/(iterations*temperature)));ifnumberofcitiestoswap==0numberofcitiestoswap=1;enditerations=iterations+1;complete_temperature_iterations=complete_temperature_iterations+1;elseifrand(1)<exp(-diff/(temperature))inputcities=temp_cities;plotcities(inputcities);numberofcitiestoswap=round(numberofcitiestoswap...*exp(-diff/(iterations*temperature)));ifnumberofcitiestoswap==0numberofcitiestoswap=1;endcomplete_temperature_iterations=complete_temperature_iterations+1;iterations=iterations+1;endendclcfprintf(’\t\t\tIterations=%d\n’,iterations);fprintf(’\t\t\tTemperature=%3.8f\n’,temperature);fprintf(’\t\t\tIncurrenttemperaturefor%dtimes\n’,...complete_temperature_iterations);endprevious_distance輸入?yún)?shù)：inputcities的作用是將n個(gè)城市的坐標(biāo)表示兩行和n列，并且傳遞給simulatedannealing作為新的參數(shù)。initial_temperature那么是開始模擬退火過(guò)程的起始溫度。cooling_rate是模擬退火過(guò)程的冷卻速率，冷卻速率應(yīng)該始終低于1。threshold是模擬退火的停止條件，并且它是n個(gè)城市的可接受的距離。numberofcitiestoswap指定用于交換城市對(duì)數(shù)量的最大值。隨著溫度的降低，用于交換的城市對(duì)也減少，最終到達(dá)一對(duì)城市。小結(jié)本章對(duì)旅行商問(wèn)題的模擬退火求解做了分析說(shuō)明，首先用模擬退火的根本原理對(duì)旅行商問(wèn)題做了理論描述，重點(diǎn)介紹了其解空間、目標(biāo)函數(shù)、新解、以及接收準(zhǔn)那么，并且給出了TSP的實(shí)現(xiàn)流程圖。之后用MATLAB實(shí)現(xiàn)，分析了各個(gè)函數(shù)的用途并附有局部源代碼。通過(guò)本章，我們用MATLAB實(shí)現(xiàn)了基于模擬退火算法的旅行商問(wèn)題的求解。3仿真實(shí)例仿真分析與評(píng)價(jià)為了驗(yàn)證用MATLAB實(shí)現(xiàn)的模擬退火算法的有效性，選擇29個(gè)點(diǎn)作為仿真研究對(duì)象，它們?cè)谧鴺?biāo)平面的坐標(biāo)(Location)如表3-1所示。表3-129個(gè)城市的坐標(biāo)城市序號(hào)12345678910X坐標(biāo)Y坐標(biāo)城市序號(hào)11121314151617181920X坐標(biāo)840.0Y坐標(biāo)城市序號(hào)212223242526272829X坐標(biāo)Y坐標(biāo)運(yùn)行結(jié)果如圖3-1：初始溫度為2000，交換城市數(shù)為2，冷卻速率為0.97，29個(gè)城市的TSP運(yùn)行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9122。初始溫度為2000，交換城市數(shù)為2，冷卻速率為0.97，29個(gè)城市的TSP運(yùn)行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9703。初始溫度為2000，交換城市數(shù)為2，冷卻速率為0.97，29個(gè)城市的TSP運(yùn)行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9077。圖3-1TSP的模擬退火運(yùn)行界面上圖為用模擬退火算法解決TSP的GUI〔GraphicsUserInterface,圖形用戶界面〕。這是由29個(gè)城市構(gòu)成的一個(gè)對(duì)稱TSP實(shí)例，利用上述算法對(duì)該實(shí)例進(jìn)行模擬退火求解，設(shè)定初始溫度T0=2000，冷卻速率為0.97，互換城市數(shù)為2。經(jīng)過(guò)20次仿真，得到的最優(yōu)解與最優(yōu)解非常接近，所需時(shí)間也令人滿意。結(jié)論本節(jié)使用MATIAB對(duì)求解TSP問(wèn)題的模擬退火算法程序進(jìn)行了仿真。平均結(jié)果結(jié)果說(shuō)明，首先該算法能夠找到TSP問(wèn)題的最優(yōu)解，說(shuō)明算法的正確性。其次算法對(duì)TSP問(wèn)題的求解時(shí)間并不呈指數(shù)增長(zhǎng)，說(shuō)明了算法的有效性?？偨Y(jié)與展望模擬退火算法是依據(jù)Metropolis準(zhǔn)那么接受新解，該準(zhǔn)那么除了接受優(yōu)化解外，還在一定的限定范圍內(nèi)接受劣解，這正是模擬退火算法與局部搜索法的本質(zhì)區(qū)別，在防止陷入局部極小值、提高解空間的搜索能力和擴(kuò)大搜索范圍方面