基于模擬退火算法的旅行商問題求解

1、目 錄摘要II關(guān)鍵詞IIAbstractIIKeywordsII引言11 旅行商問題和模擬退火算法21.1 旅行商問題21.1.1 旅行商問題的描述21.1.2 旅行商問題的應用31.2 模擬退火算法31.2.1 基本思想31.2.2 關(guān)鍵技術(shù)41.3 小結(jié)42 TSP模擬退火算法的實現(xiàn)52.1 TSP算法實現(xiàn)52.1.1 TSP算法描述52.1.2 TSP算法流程52.2 TSP的MATLAB實現(xiàn)62.2.1 加載數(shù)據(jù)文件62.2.2 計算總距離的函數(shù)72.2.3 繪制路線的函數(shù)72.2.4 交換城市的函數(shù)82.2.5 執(zhí)行模擬退火的函數(shù)82.3 小結(jié)93 仿真實例103.1 仿真分析與評價

2、103.2 結(jié)論12總結(jié)與展望12致謝13參考文獻13基于模擬退火算法的旅行商問題求解 光信息科學與技術(shù) 董鑄祥 指導教師 張明強摘要: 旅行商問題是組合優(yōu)化領域里的一個典型的、易于描述卻難以處理的NP難題，其可能的路徑數(shù)目與城市數(shù)目是呈指數(shù)型增長的，求解非常困難。首先介紹了旅行商問題，給出了其數(shù)學描述以及實際應用，進而給出解決TSP的一種比較精確的算法模擬退火算法。然后闡述了模擬退火算法的基本原理，重點說明了其基本思想及關(guān)鍵技術(shù)。最后運用MATLAB語言實現(xiàn)了該算法，并將其運用到解決旅行商問題的優(yōu)化之中。數(shù)值仿真的結(jié)果表明了該方法能夠?qū)?shù)據(jù)進行全局尋優(yōu)，有效克服了基于導數(shù)的優(yōu)化算法容易陷入局

3、部最優(yōu)的問題。關(guān)鍵詞: 模擬退火 旅行商 NP 組合優(yōu)化Solution of Travelling Salesman ProblemBaced on Simulated Annealing AlgorithmOptical Information Science and Technology Dong ZhuxiangTutor Zhang MingqiangAbstract: Travelling Salesman Problem is one of the typical NP-hard problems in combinatorial optimization, which is e

4、asy to be described but hard to be solved. Its possible amounts of path increase exponentially with the amounts of city, so it is very difficult to solve it. First this paper introduces Travelling Salesman Problem, gives TSP mathematical description and practical application.In turn, a precise algor

5、ithmsimulated annealing algorithmthe to the address of TSP is given. And then this paper describes the basic principle of simulated annealing, highlights the basic ideas and key technology. Finally, we use MATLAB language to implement the algorithm, and applied it to solve the traveling salesman pro

6、blem into the optimization. Numerical simulation results show that this method can globally optimizes data, effectively overcomes the problem of derivative-based optimization algorithm which is easy fall into local optimum. Keywords: simulated annealing; travelling salesman problem;Non-deterministic

7、Polynomial; combinatorial optimization12引言旅行商問題(Traveling Salesman Problem,TSP)，也稱為貨郎擔問題，是由愛爾蘭數(shù)學家Sir William Rowan Hamilton和英國數(shù)學家Thomas Penyngton Kirkman在19世紀提出的數(shù)學問題，它是指給定n個城市并給出每兩個城市之間的距離，旅行商必須以最短路徑訪問所有的城市一次且僅一次，并回到原出發(fā)地，現(xiàn)已證明它屬于NP(Non-deterministic Polynomial-非確定多項式)難題1。歷史上的第一個正式用來解決TSP問題的算法誕生于1954年

8、,它被用來計算49個城市的TSP問題。到現(xiàn)在為止,運用目前最先進的計算機技術(shù)可解決找出游歷24978個城市的TSP問題。TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周游問題，即對于國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，并且最終返回到起始點。旅行商問題(TSP)由美國RAND公司于1948年引入，該公司的聲譽以及線性規(guī)劃這一新方法的出現(xiàn)使得TSP成為一個知名且流行的問題2。旅行商問題是一個經(jīng)典的圖論問題：設有n個城市，用Ci，j=1，2，n表示。城市Ci,j之間的距離為di,j，i，j=1，2，n，設所有城市間兩兩連通，旅行商需要跑遍n個城市去推銷他的商品，而這些城市

9、之間的距離都不一樣，這推銷員需要從其中一個城市出發(fā)，而他老板規(guī)定他必須把所有城市跑一遍，則TSP問題就是尋找讓旅行商遍訪每個城市一次且恰好一次的一條回路，且要求其路徑總長度為最短。該問題也可以歸結(jié)為：有N個城市由公路相互連通，從任一城市到另外城市都要支付相應的費用，一個銷售商從其中一城市出發(fā)，訪問其他N1個城市且僅一次，如何規(guī)劃一條路徑，使該旅行商的花費最少3。當城市數(shù)量較小時，通過枚舉法就可以找出最短的路徑，然而隨著問題規(guī)模的增加，很難找到一個多項式時間復雜度的算法來求解該問題。TSP是一個典型的組合優(yōu)化問題，是諸多領域內(nèi)出現(xiàn)的多種復雜問題的集中概括和簡化形式，并且已成為各種啟發(fā)式的搜索、優(yōu)

10、化算法的間接比較標準。因此，快速、有效地解決TSP有著重要的理論價值和極高的實際應用價值。旅行商問題代表的一類組合優(yōu)化問題,在物流配送、計算機網(wǎng)絡、電子地圖、交通誘導、電氣布線、VLSI單元布局等方面都有重要的工程和理論價值，引起了許多學者的關(guān)注。TSP是典型的組合優(yōu)化問題，并且是一個NP-hard問題。TSP描述起來很簡單，早期的研究者使用精確算法求解該問題，TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨于無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）！?？梢孕蜗蟮匕呀饪臻g看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP

11、，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程2。常用的方法包括：分枝定界法、線性規(guī)劃法和動態(tài)規(guī)劃法等，但可能的路徑總數(shù)隨城市數(shù)目n是成指數(shù)型增長的，所以當城市數(shù)目在100個以上一般很難精確的求出其全局最優(yōu)解。隨著人工智能的發(fā)展，出現(xiàn)了許多獨立于問題的智能優(yōu)化算法，如蟻群算法、遺傳算法、模擬退火、禁忌搜索、神經(jīng)網(wǎng)絡、粒子群優(yōu)化算法、免疫算法等，通過模擬或解釋某些自然現(xiàn)象或過程而得以發(fā)展，為解決復雜組合優(yōu)化問題提供了新的思路和方法4。模擬退火算法在迭代搜索過程以Boltzmann分布概率接受目標函數(shù)的“劣化解”，具有突出的具有脫離局域最優(yōu)陷阱的能力，同時具有較強的局部搜索能力，從而可以

12、獲取目標函數(shù)的全局最優(yōu)解。因為模擬退火算法具有高效、通用、靈活的優(yōu)點，將模擬退火算法引入TSP求解，可以避免在求解過程中陷入TSP的局部最優(yōu)解5。本文首先介紹傳統(tǒng)的TSP問題，先對其進行數(shù)學描述，又列舉TSP問題的應用。之后介紹模擬退火算法，主要介紹其基本思想和關(guān)鍵技術(shù)，在此基礎上將模擬退火的思想引入TSP的求解，設計出TSP的一種模擬退火算法并用MATLAB語言編程予以實現(xiàn)。1 旅行商問題和模擬退火算法1.1 旅行商問題1.1.1 旅行商問題的描述旅行商問題（Traveling Salesman Problem，簡稱TSP）又名貨郎擔問題，是威廉·哈密爾頓爵士和英國數(shù)學家克克曼(T

13、.P.Kirkman)于19世紀初提出的一個數(shù)學問題，也是著名的組合優(yōu)化問題。問題是這樣描述的：一名商人要到若干城市去推銷商品，已知城市個數(shù)和各城市間的路程（或旅費），要求找到一條從城市1出發(fā)，經(jīng)過所有城市且每個城市只能訪問一次，最后回到城市1的路線，使總的路程（或旅費）最小。TSP剛提出時，不少人認為這個問題很簡單。后來人們才逐步意識到這個問題只是表述簡單，易于為人們所理解，而其計算復雜性卻是問題的輸入規(guī)模的指數(shù)函數(shù)，屬于相當難解的問題。這個問題數(shù)學描述為：假設有n個城市，并分別編號，給定一個完全無向圖G=（V，E），V=1，2，n，n>1。其每一邊(i,j)E有一非負整數(shù)耗費 Ci,

14、j(即上的權(quán)記為Ci,j，i，jV)。并設 G的一條巡回路線是經(jīng)過V中的每個頂點恰好一次的回路。一條巡回路線的耗費是這條路線上所有邊的權(quán)值之和。TSP問題就是要找出G的最小耗費回路。人們在考慮解決這個問題時，一般首先想到的最原始的一種方法就是:列出每一條可供選擇的路線(即對給定的城市進行排列組合)，計算出每條路線的總里程，最后從中選出一條最短的路線。假設現(xiàn)在給定的4個城市分別為A、B、C和D，各城市之間的耗費為己知數(shù)，如圖1所示。我們可以通過一個組合的狀態(tài)空間圖來表示所有的組合，如圖 圖 1-1 頂點帶權(quán)圖 圖 1-2 TSP問題的解空間樹從圖中不難看出，可供選擇的路線共有6條，從中很快可以選

15、出一條總耗費最短的路線：頂點序列為（A,C,B,D,A）。由此推算，若設城市數(shù)目為n時，那么組合路徑數(shù)則為(n-1)!。很顯然，當城市數(shù)目不多時要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級數(shù)規(guī)律急劇增長，以至達到無法計算的地步，這就是所謂的“組合爆炸問題”。假設現(xiàn)在城市的數(shù)目增為20個，組合路徑數(shù)則為(20-1)!1.216×1017，如此龐大的組合數(shù)目，若計算機以每秒檢索1000萬條路線的速度計算，也需要花上386年的時間6。1.1.2 旅行商問題的應用TSP是最有代表性的優(yōu)化組合問題之一，其應用已逐步滲透到各個技術(shù)領域和我們的日常生活中。它一開始是為

16、交通運輸而提出的，比如飛機航線安排、送郵件、快遞服務、設計校車行進路線等等。實際上其應用范圍擴展到了許多其他領域，如在VLSI芯片設計、電路板布局、機器人控制、車輛選路、物流配送等方面，下面舉幾個實例。1電路板鉆孔進度的安排。機器在電路板上鉆孔的調(diào)度問題是TSP應用的經(jīng)典例子，在一電路板上打成百上千個孔，轉(zhuǎn)頭在這些孔之間移動，相當于對所有的孔進行一次巡游。把這個問題轉(zhuǎn)化為TSP，孔相當于城市，轉(zhuǎn)頭從一個孔移到另一個孔所耗的時間相當于TSP中的旅費。2車輛選路。一個經(jīng)典的路由問題是在一個網(wǎng)絡上發(fā)現(xiàn)從源節(jié)點到一個目的節(jié)點的最佳交通線路，使與距離成比例的流動費用降低到最小。這個問題的關(guān)鍵是在交通網(wǎng)絡

17、上計算從源節(jié)點到目的節(jié)點之間的最短路徑。對這個最小費用流動問題進行擴展，就構(gòu)成TSP問題，在這個問題中，車輛從源點出發(fā)訪問多個目的地并且最后回到源點。3.基因測序。Cnoocdre是一種求解旅行商問題的程序。美國國家衛(wèi)生機構(gòu)的研究人員利用這一程序來進行基因測序。在這一應用中，DNA片斷作為城市，它們之間的相似程度作為城市與城市的距離。研究人員試圖尋找一種可能性最高的連接方式把這些DNA片斷合成為整張DNA。更重要的是，TSP提供了一個研究組合優(yōu)化問題的理想平臺。很多組合優(yōu)化問題，比如背包問題、分配問題、車間調(diào)度問題，和TSP同屬NP-Hard類，它們難度同等，如果其中一個能用多項式確定性算法解

18、決，那么其他所有的NP-Hard類問題也能用多項式確定性算法解決。很多方法都是從TSP發(fā)展起來的，后來推廣到其他NP-Hard類問題上去。1.2 模擬退火算法 模擬退火算法由KirkPatrick于1982提出7，他將退火思想引入到組合優(yōu)化領域,提出一種求解大規(guī)模組合優(yōu)化問題的方法，對于NP-完全組合優(yōu)化問題尤其有效。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之達到能量最低點。反之，如果急速降溫(即淬火)則不能達到最低點。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而緩慢降溫時粒子漸趨有序，在每個溫度上都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。

19、根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為exp(-E/(kT)，其中E為溫度T時的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復產(chǎn)生“新解計算目標函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子a、每個t值時的迭代次數(shù)L和停止條件C。1.2

20、.1 基本思想 模擬退火算法可以分解為解空間、目標函數(shù)和初始解3部分。其基本思想是：(1)初始化：初始溫度T(充分大)，初始解狀態(tài)s(是算法迭代的起點)，每個T值的迭代次數(shù)L；(2)對k=1，L做第(3)至第6步；(3)產(chǎn)生新解s；(4)計算增量cost=cost(s)-cost(s)，其中cost(s)為評價函數(shù)；(5)若t0則接受s作為新的當前解，否則以概率exp(-t/T)接受s作為新的當前解；(6)如果滿足終止條件則輸出當前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法；(7)T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運算。 1.2.2 關(guān)鍵技術(shù)（1）新解的產(chǎn)生

21、和接受模擬退火算法新解的產(chǎn)生和接受可分為如下4個步驟：由一個函數(shù)從當前解產(chǎn)生一個位于解空間的新解。為便于后續(xù)的計算和接受，減少算法耗時，常選擇由當前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等。產(chǎn)生新解的變換方法決定了當前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。計算與新解所對應的目標函數(shù)差。因為目標函數(shù)差僅由變換部分產(chǎn)生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。判斷新解是否被接受。判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropo1is準則：若t0則接受S作為新的當前解S，否則以概率

22、exp(-t/T)接受S作為新的當前解S。當新解被確定接受時，用新解代替當前解。這只需將當前解中對應于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代，可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續(xù)下一輪試驗。模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。（2）參數(shù)控制問題模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下3點7：溫度T的初始值設置。溫度T的初

23、始值設置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據(jù)實驗結(jié)果進行若干次調(diào)整。溫度衰減函數(shù)的選取。衰減函數(shù)用于控制溫度的退火速度，一個常用的函數(shù)為： 式中是一個非常接近于1的常數(shù)，t為降溫的次數(shù)。馬爾可夫鏈長度L的選取。通常的原則是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L的選取應遵循在控制參數(shù)的每一取值上都能恢復準平衡的原則。1.3 小結(jié) 本章而要的介紹了旅行商問題與模擬退火算法，首先對旅行商問題做了描述并舉例其應用，然后介紹了模擬退火

24、算法的來源，重點介紹了模擬退火算法的基本思想和關(guān)鍵技術(shù)。通過本章的分析，使我們理解了模擬退火算法的基本原理并且知道了TSP問題的數(shù)學描述，為下面將該算法其應用于旅行商問題做了準備。2 TSP模擬退火算法的實現(xiàn) TSP是典型的組合優(yōu)化問題，模擬退火算法是一種隨機性解決組合優(yōu)化方法。將TSP與模擬退火算法相結(jié)合，以實現(xiàn)對其求解。2.1 TSP算法實現(xiàn)2.1.1 TSP算法描述 （1）TSP問題的解空間和初始解 TSP的解空間S是遍訪每個城市恰好一次的所有回路，是所有城市排列的集合。TSP問題的解空間S可表示為1,2,n的所有排列的集合，即S = (c1,c2,cn) | (c1,c2,cn)為1,

25、2,n的排列），其中每一個排列Si表示遍訪n個城市的一個路徑，ci= j表示在第i次訪問城市j。模擬退火算法的最優(yōu)解與初始狀態(tài)無關(guān)，故初始解為隨機函數(shù)生成一個1,2,n的隨機排列作為S0。（2）目標函數(shù) TSP問題的目標函數(shù)即為訪問所有城市的路徑總長度，也可稱為代價函數(shù)： 現(xiàn)在TSP問題的求解就是通過模擬退火算法求出目標函數(shù)C(c1,c2,cn)的最小值，相應地，s*= (c*1,c*2,c*n)即為TSP問題的最優(yōu)解。 （3）新解產(chǎn)生新解的產(chǎn)生對問題的求解非常重要。新解可通過分別或者交替用以下2種方法產(chǎn)生：二變換法：任選序號u,v(設uvn)，交換u和v之間的訪問順序，若交換前的解為si=

26、(c1,c2,cu,cv,cn),交換后的路徑為新路徑，即：si= (c1,cu-1,cv,cv-1,cu+1,cu,cv+1,cn)三變換法：任選序號u,v和(uv)，將u和v之間的路徑插到之后訪問，若交換前的解為si= (c1,c2,cu,cv,c,cn)，交換后的路徑為的新路徑為：si= (c1,cu-1,cv+1,c,cu,cv,c+1,cn)（4）目標函數(shù)差計算變換前的解和變換后目標函數(shù)的差值：c= c(si)- c(si)（5）Metropolis接受準則根據(jù)目標函數(shù)的差值和概率exp(-C/T)接受si作為新的當前解si，接受準則： 2.1.2 TSP算法流程 根據(jù)以上對TSP的

27、算法描述，可以寫出用模擬退火算法解TSP問題的流程圖2-1所示：圖 2-1 TSP的模擬退火流程2.2 TSP的MATLAB實現(xiàn)2.2.1 加載數(shù)據(jù)文件下面是加載數(shù)據(jù)文件的一個例子：function d = 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,

28、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;save cities.mat cities -V6;當調(diào)用數(shù)據(jù)文件函數(shù)時，包含城市坐標信息的矩陣載入到cities.mat的文件中。該數(shù)據(jù)文件的第一列通常是城市數(shù)量，之后兩列為城市的坐標。初始化函數(shù)，根據(jù)直角坐標生成城市距離矩陣。2.2.2 計算總距離的函數(shù)這是一個城市間計算距離的函數(shù)，根據(jù)給定路徑計算該路徑對應總路程。function d = distance(inputciti

29、es) % DISTANCE% d = DISTANCE(inputcities)按照要求計算TSP問題中n個城市的距離。% 輸入?yún)?shù)有兩行和n列，其中n為城市的數(shù)目，列為對應城市的坐標。 d = 0; for n = 1 : length(inputcities) if n = length(inputcities) d = d + norm(inputcities(:,n) - inputcities(:,1); else d = d + norm(inputcities(:,n) - inputcities(:,n+1); end end TSP問題的成本函數(shù)是城市之間的距離。調(diào)用此函數(shù)

30、將計算n個城市之間的距離。2.2.3 繪制路線的函數(shù)這是一個繪制路線的函數(shù)，根據(jù)給定的城市坐標生成的城市矩陣繪制城市的坐標，根據(jù)給定的路線繪制線路。function f = plotcities(inputcities)% PLOTCITIES% PLOTCITIES(inputcities)從inputcities參數(shù)中繪制城市的位置。%inputcities參數(shù)有兩行和n列，其中n為城市的數(shù)量。位置和對稱路徑都被繪制。temp_1 = plot(inputcities(1,:),inputcities(2,:),b*);set(temp_1,erasemode,none);temp_2 =

31、 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);if x1 = 0 x1 = 1;end if y1 = 0 y1 = 1;enda

32、xis(0 x1 0 y1);temp_3 = line(x,y);set(temp_3,color,r);dist = distance(inputcities);distance_print = sprintf(.The roundtrip length for %d cities is % 4.6f units. ,length(inputcities),dist);text(x1/15,1.05*y1,distance_print,fontweight,bold);drawnow;2.2.4 交換城市的函數(shù) 這是一個用于城市交換的函數(shù)，它從某路徑的鄰域中隨機的選擇一個新的路徑。 fun

33、ction s = swapcities(inputcities,n)% SWAPCITIES% s = SWAPCITIES(inputcities,n)n個城市隨機的交換返回一組m個城市s = inputcities; for i = 1 : n city_1 = round(length(inputcities)*rand(1); if city_1 < 1 city_1 = 1; end city_2 = round(length(inputcities)*rand(1); if city_2 < 1 city_2 = 1; end temp = s(:,city_1);

34、s(:,city_1) = s(:,city_2); s(:,city_2) = temp; end2.2.5 執(zhí)行模擬退火的函數(shù)function s = simulatedannealing(inputcities,initial_temperature,.cooling_rate,threshold,numberofcitiestoswap)% SIMULATEDANNEALING% S = SIMULATEDANNEALING(inputcities,initial_temperature,cooling_rate)通過% n 個城市的TSP問題的最優(yōu)解返回一個新的城市構(gòu)型。 globa

35、l iterations;temperature = initial_temperature;initial_cities_to_swap = numberofcitiestoswap;iterations = 1;complete_temperature_iterations = 0;while iterations < threshold previous_distance = distance(inputcities); temp_cities = swapcities(inputcities,numberofcitiestoswap); current_distance = di

36、stance(temp_cities); diff = abs(current_distance - previous_distance); if current_distance < previous_distance inputcities = temp_cities; plotcities(inputcities); if complete_temperature_iterations >= 10 temperature = cooling_rate*temperature; complete_temperature_iterations = 0; end numberofc

37、itiestoswap = round(numberofcitiestoswap. *exp(-diff/(iterations*temperature); if numberofcitiestoswap = 0 numberofcitiestoswap = 1; end iterations = iterations + 1; complete_temperature_iterations = complete_temperature_iterations + 1; else if rand(1) < exp(-diff/(temperature) inputcities = temp

38、_cities; plotcities(inputcities); numberofcitiestoswap = round(numberofcitiestoswap. *exp(-diff/(iterations*temperature); if numberofcitiestoswap = 0 numberofcitiestoswap = 1; end complete_temperature_iterations = complete_temperature_iterations + 1; iterations = iterations + 1; end end clc fprintf(

39、tttIterations = %dn,iterations); fprintf(tttTemperature = %3.8fn,temperature); fprintf(tttIn current temperature for %d timesn,. complete_temperature_iterations);endprevious_distance輸入?yún)?shù)：inputcities的作用是將n個城市的坐標表示兩行和n列，并且傳遞給simulatedannealing作為新的參數(shù)。initial_temperature則是開始模擬退火過程的起始溫度。cooling_rate是模擬退火

40、過程的冷卻速率，冷卻速率應該始終低于1。threshold是模擬退火的停止條件，并且它是n個城市的可接受的距離。numberofcitiestoswap指定用于交換城市對數(shù)量的最大值。隨著溫度的降低，用于交換的城市對也減少，最終達到一對城市。2.3 小結(jié)本章對旅行商問題的模擬退火求解做了分析說明，首先用模擬退火的基本原理對旅行商問題做了理論描述，重點介紹了其解空間、目標函數(shù)、新解、以及接收準則，并且給出了TSP的實現(xiàn)流程圖。之后用MATLAB實現(xiàn)，分析了各個函數(shù)的用途并附有部分源代碼。通過本章，我們用MATLAB實現(xiàn)了基于模擬退火算法的旅行商問題的求解。3 仿真實例3.1 仿真分析與評價為了驗

41、證用MATLAB實現(xiàn)的模擬退火算法的有效性，選擇29個點作為仿真研究對象，它們在坐標平面的坐標(Location)如表3-1所示。表 3-1 29個城市的坐標城市序號12345678910X坐標1150.0630.040.0750.0750.01030.01650.01490.0790.0710.0Y坐標1760.01660.02090.01100.02030.02070.0650.01630.02260.01310.0城市序號11121314151617181920X坐標840.0 1170.0970.0510.0750.01280.0230.0460.01040.0590.0Y坐標550.

42、02300.01340.0700.0900.01200.0590.0860.0950.01390.0城市序號212223242526272829X坐標 830.0 490.01840.01260.01280.0490.01460.01260.0360.0Y坐標1770.0500.01240.01500.0790.02130.01420.01910.01980.0 運行結(jié)果如圖3-1： 初始溫度為2000，交換城市數(shù)為2，冷卻速率為0.97，29個城市的TSP運行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9122。 初始溫度為2000，交換城市數(shù)為2，冷卻速率為0.97，29個城市的TSP運行結(jié)果 如

43、上圖，該優(yōu)化路徑的總路程近似為9703。 初始溫度為2000，交換城市數(shù)為2，冷卻速率為0.97，29個城市的TSP運行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9077。圖 3-1 TSP的模擬退火運行界面 上圖為用模擬退火算法解決TSP的GUI（Graphics User Interface,圖形用戶界面）。這是由29個城市構(gòu)成的一個對稱TSP實例，利用上述算法對該實例進行模擬退火求解，設定初始溫度T0=2000，冷卻速率為0.97，互換城市數(shù)為2。經(jīng)過20次仿真，得到的最優(yōu)解與已知最優(yōu)解非常接近，所需時間也令人滿意。3.2 結(jié)論 本節(jié)使用MATIAB對求解TSP問題的模擬退火算法程序進行了仿真。平均結(jié)果結(jié)果表明，首先該算法能夠找到TSP問題的最優(yōu)解，說明算法的正確性。其次算法對TSP問題的求解時間并不呈指數(shù)增長，說明了算法的有效性?？偨Y(jié)與展望 模擬退火算法是依據(jù)Metropolis準則接受新解，該準則除了接受優(yōu)化解外，還在一定的限定范圍內(nèi)接受劣解，這正是模擬退火算法與局部搜索法的本質(zhì)區(qū)別，在避免陷入局部極小值、提高解空間的搜索能力和擴大搜索范圍方面具有明顯的優(yōu)越性8。本文給