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

1、 . . . 目 錄摘要II關(guān)鍵詞IIAbstractIIKeywordsII引言11 旅行商問(wèn)題和模擬退火算法21.1 旅行商問(wèn)題21.1.1 旅行商問(wèn)題的描述21.1.2 旅行商問(wèn)題的應(yīng)用31.2 模擬退火算法31.2.1 基本思想31.2.2 關(guān)鍵技術(shù)41.3小結(jié)42 TSP模擬退火算法的實(shí)現(xiàn)52.1 TSP算法實(shí)現(xiàn)52.1.1 TSP算法描述52.1.2 TSP算法流程52.2 TSP的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仿真分

2、析與評(píng)價(jià)103.2結(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é)果表明了該方法能夠?qū)?shù)據(jù)進(jìn)行全局尋優(yōu)，有效克服了基于導(dǎo)數(shù)的優(yōu)化算法容易陷入局部

3、最優(yōu)的問(wèn)題。關(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 eas

4、y 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 paperintroduces Travelling Salesman Problem, givesTSP mathematical description and practical application.In turn, a precise algorithm

5、simulated annealingalgorithmthe 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 problem

6、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-deterministicPolyno

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

8、它被用來(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è)城市去推銷他的商品，而這些城市之

9、間的距離都不一樣，這推銷員需要從其中一個(gè)城市出發(fā)，而他老板規(guī)定他必須把所有城市跑一遍，則TSP問(wèn)題就是尋找讓旅行商遍訪每個(gè)城市一次且恰好一次的一條回路，且要求其路徑總長(zhǎng)度為最短。該問(wèn)題也可以歸結(jié)為：有N個(gè)城市由公路相互連通，從任一城市到另外城市都要支付相應(yīng)的費(fèi)用，一個(gè)銷售商從其中一城市出發(fā)，訪問(wèn)其他N1個(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)域出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式，并且已成為各種啟發(fā)式的搜索、優(yōu)化算

10、法的間接比較標(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看成是一個(gè)無(wú)窮大的丘陵地帶，各山峰或山谷的高度即是問(wèn)題的極值。求解TSP，則

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

12、目標(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ù)，在此基礎(chǔ)上將模擬退火的思想引入TSP的求解，設(shè)計(jì)出TSP的一種模擬退火算法并用MATLAB語(yǔ)言編程予以實(shí)現(xiàn)。1 旅行商問(wèn)題和模擬退火算法1.1 旅行商問(wèn)題1.1.1 旅行商問(wèn)題的描述旅行商問(wèn)題（Traveling Salesman Problem，簡(jiǎn)稱TSP）又名貨郎擔(dān)問(wèn)題，是威廉·哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼(T.P

13、.Kirkman)于19世紀(jì)初提出的一個(gè)數(shù)學(xué)問(wèn)題，也是著名的組合優(yōu)化問(wèn)題。問(wèn)題是這樣描述的：一名商人要到若干城市去推銷商品，已知城市個(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ù)耗費(fèi) Ci,j(

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

15、條總耗費(fèi)最短的路線：頂點(diǎn)序列為（A,C,B,D,A）。由此推算，若設(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ù)目，若計(jì)算機(jī)以每秒檢索1000萬(wàn)條路線的速度計(jì)算，也需要花上386年的時(shí)間6。1.1.2 旅行商問(wèn)題的應(yīng)用TSP是最有代表性的優(yōu)化組合問(wèn)題之一，其應(yīng)用已逐步滲透到各個(gè)技術(shù)領(lǐng)域和我們的日常生活中。它一開始是為交通

16、運(yùn)輸而提出的，比如飛機(jī)航線安排、送、快遞服務(wù)、設(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ì)算從源

17、節(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)式確定性算法解決，那么其他

18、所有的NP-Hard類問(wèn)題也能用多項(xiàng)式確定性算法解決。很多方法都是從TSP發(fā)展起來(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í)，固體部粒子隨溫升變?yōu)闊o(wú)序狀，能增大，而緩慢降溫時(shí)粒子漸趨有序，在每個(gè)溫度上都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，能減為最小。根據(jù)Metropo

19、lis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為exp(-E/(kT)，其中E為溫度T時(shí)的能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題，將能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)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t與其衰減因子a、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件C。1.2.1 基本思想模擬退火

20、算法可以分解為解空間、目標(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)若t0則接受s作為新的當(dāng)前解，否則以概率exp(-t/T)接受s作為新的當(dāng)前解；(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法；(7)T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運(yùn)算。1.2.2 關(guān)鍵技術(shù)（1）新解的產(chǎn)生和接受模擬退火算法新解的產(chǎn)

21、生和接受可分為如下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í)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。判斷新解是否被接受。判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則：若t0則接受S作為新的當(dāng)前解S，否則以概率exp(-t/T)接受S作

22、為新的當(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)了一次迭代，可在此基礎(chǔ)上開始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。（2）參數(shù)控制問(wèn)題模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下3點(diǎn)7：溫度T的初始值設(shè)置。溫度T的初始值設(shè)置是影響模擬退火算法

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

24、火算法的基本思想和關(guān)鍵技術(shù)。通過(guò)本章的分析，使我們理解了模擬退火算法的基本原理并且知道了TSP問(wèn)題的數(shù)學(xué)描述，為下面將該算法其應(yīng)用于旅行商問(wèn)題做了準(zhǔn)備。2 TSP模擬退火算法的實(shí)現(xiàn) TSP是典型的組合優(yōu)化問(wèn)題，模擬退火算法是一種隨機(jī)性解決組合優(yōu)化方法。將TSP與模擬退火算法相結(jié)合，以實(shí)現(xiàn)對(duì)其求解。2.1 TSP算法實(shí)現(xiàn)2.1.1 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è)排

25、列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)解。 （3）新解產(chǎn)生新解的產(chǎn)生對(duì)問(wèn)題的求解非常重要。新解可通過(guò)分別或者交替用以下2種方法產(chǎn)生：二變換法：任選序號(hào)u,v(設(shè)uvn)，交換u和v之間的訪問(wèn)順序，若交換前的解為si= (c1,c2,cu,cv,c

26、n),交換后的路徑為新路徑，即：si= (c1,cu-1,cv,cv-1,cu+1,cu,cv+1,cn)三變換法：任選序號(hào)u,v和(uv)，將u和v之間的路徑插到之后訪問(wèn)，若交換前的解為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.2 TSP算法流程 根據(jù)以上對(duì)TSP的算法描述，可以寫出用模擬退火算

27、法解TSP問(wèn)題的流程圖2-1所示：圖 2-1 TSP的模擬退火流程2.2 TSP的MATLAB實(shí)現(xiàn)2.2.1 加載數(shù)據(jù)文件下面是加載數(shù)據(jù)文件的一個(gè)例子：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,0.5979,0.2184,0

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

29、d = DISTANCE(inputcities)按照要求計(jì)算TSP問(wèn)題中n個(gè)城市的距離。% 輸入?yún)?shù)有兩行和n列，其中n為城市的數(shù)目，列為對(duì)應(yīng)城市的坐標(biāo)。 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問(wèn)題的成本函數(shù)是城市之間的距離。調(diào)用此函數(shù)將計(jì)算n個(gè)城市之間的距離。2.2

30、.3繪制路線的函數(shù)這是一個(gè)繪制路線的函數(shù)，根據(jù)給定的城市坐標(biāo)生成的城市矩陣?yán)L制城市的坐標(biāo)，根據(jù)給定的路線繪制線路。function f = 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

31、(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;endaxis(0 x1 0 y1);te

32、mp_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ù) 這是一個(gè)用于城市交換的函數(shù)，它從某路徑的鄰域中隨機(jī)的選擇一個(gè)新的路徑。function s = swapcitie

33、s(inputcities,n)% SWAPCITIES% s = SWAPCITIES(inputcities,n)n個(gè)城市隨機(jī)的交換返回一組m個(gè)城市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); s(:,city_1) = s(:,c

34、ity_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)通過(guò)% n個(gè)城市的TSP問(wèn)題的最優(yōu)解返回一個(gè)新的城市構(gòu)型。global iterations;temperatu

35、re = 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 = distance(temp_cities); d

36、iff = 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 numberofcitiestoswap = round(nu

37、mberofcitiestoswap. *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_cities; plotcities(in

38、putcities); 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(tttIterations = %dn,it

39、erations); fprintf(tttTemperature = %3.8fn,temperature); fprintf(tttIn current temperature for %d timesn,. 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。th

40、reshold是模擬退火的停止條件，并且它是n個(gè)城市的可接受的距離。numberofcitiestoswap指定用于交換城市對(duì)數(shù)量的最大值。隨著溫度的降低，用于交換的城市對(duì)也減少，最終達(dá)到一對(duì)城市。2.3 小結(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í)例3.1 仿真分析與評(píng)價(jià)為了驗(yàn)證用MATLAB實(shí)現(xiàn)的模擬退火算法的有效性，

41、選擇29個(gè)點(diǎn)作為仿真研究對(duì)象，它們?cè)谧鴺?biāo)平面的坐標(biāo)(Location)如表3-1所示。表 3-1 29個(gè)城市的坐標(biāo)城市序號(hào)12345678910X坐標(biāo)1150.0630.040.0750.0750.01030.01650.01490.0790.0710.0Y坐標(biāo)1760.01660.02090.01100.02030.02070.0650.01630.02260.01310.0城市序號(hào)11121314151617181920X坐標(biāo)840.0 1170.0970.0510.0750.01280.0230.0460.01040.0590.0Y坐標(biāo)550.02300.01340.0700.0900.

42、01200.0590.0860.0950.01390.0城市序號(hào)212223242526272829X坐標(biāo) 830.0 490.01840.01260.01280.0490.01460.01260.0360.0Y坐標(biāo)1770.0500.01240.01500.0790.02130.01420.01910.01980.0運(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。 初始溫

43、度為2000，交換城市數(shù)為2，冷卻速率為0.97，29個(gè)城市的TSP運(yùn)行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9077。圖 3-1 TSP的模擬退火運(yùn)行界面上圖為用模擬退火算法解決TSP的GUI（Graphics User Interface,圖形用戶界面）。這是由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í)間也令人滿意。3.2 結(jié)論本節(jié)使用MATIAB對(duì)求解TSP問(wèn)題的模擬退火算法程序進(jìn)行了仿真。平均結(jié)果結(jié)果表明，首先該算法能夠找到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)化解外，還在一定的限定圍接受劣解，這正是模擬退火算法與局部搜索法的本質(zhì)區(qū)別，在避免陷入局部極小值、提高解空間的搜索能力