【正文】 是遍訪每個城市恰好一次的所有回路，是所有城市排列的集合。2 TSP模擬退火算法的實現(xiàn) TSP是典型的組合優(yōu)化問題，模擬退火算法是一種隨機性解決組合優(yōu)化方法。 小結(jié) 本章而要的介紹了旅行商問題與模擬退火算法，首先對旅行商問題做了描述并舉例其應(yīng)用，然后介紹了模擬退火算法的來源，重點介紹了模擬退火算法的基本思想和關(guān)鍵技術(shù)。③馬爾可夫鏈長度L的選取。②溫度衰減函數(shù)的選取。初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。（2）參數(shù)控制問題模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下3點[7]：①溫度T的初始值設(shè)置。而當(dāng)新解被判定為舍棄時，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗。這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標(biāo)函數(shù)值即可。判斷的依據(jù)是一個接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則：若t′0則接受S′作為新的當(dāng)前解S，否則以概率exp(t′/T)接受S′作為新的當(dāng)前解S。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的最快方法。②計算與新解所對應(yīng)的目標(biāo)函數(shù)差。為便于后續(xù)的計算和接受，減少算法耗時，常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法；(7)T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運算。 基本思想 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解3部分。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)產(chǎn)生“新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而緩慢降溫時粒子漸趨有序，在每個溫度上都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之達到能量最低點。很多方法都是從TSP發(fā)展起來的，后來推廣到其他NPHard類問題上去。更重要的是，TSP提供了一個研究組合優(yōu)化問題的理想平臺。在這一應(yīng)用中，DNA片斷作為城市，它們之間的相似程度作為城市與城市的距離。Cnoocdre是一種求解旅行商問題的程序。對這個最小費用流動問題進行擴展，就構(gòu)成TSP問題，在這個問題中，車輛從源點出發(fā)訪問多個目的地并且最后回到源點。一個經(jīng)典的路由問題是在一個網(wǎng)絡(luò)上發(fā)現(xiàn)從源節(jié)點到一個目的節(jié)點的最佳交通線路，使與距離成比例的流動費用降低到最小。把這個問題轉(zhuǎn)化為TSP，孔相當(dāng)于城市，轉(zhuǎn)頭從一個孔移到另一個孔所耗的時間相當(dāng)于TSP中的旅費。1．電路板鉆孔進度的安排。它一開始是為交通運輸而提出的，比如飛機航線安排、送郵件、快遞服務(wù)、設(shè)計校車行進路線等等。假設(shè)現(xiàn)在城市的數(shù)目增為20個，組合路徑數(shù)則為(201)!≈1017，如此龐大的組合數(shù)目，若計算機以每秒檢索1000萬條路線的速度計算，也需要花上386年的時間[6]。由此推算，若設(shè)城市數(shù)目為n時，那么組合路徑數(shù)則為(n1)!。假設(shè)現(xiàn)在給定的4個城市分別為A、B、C和D，各城市之間的耗費為己知數(shù)，如圖1所示。TSP問題就是要找出G的最小耗費回路。并設(shè) G的一條巡回路線是經(jīng)過V中的每個頂點恰好一次的回路。這個問題數(shù)學(xué)描述為：假設(shè)有n個城市，并分別編號，給定一個完全無向圖G=（V，E），V={1，2，…，n}，n1。TSP剛提出時，不少人認為這個問題很簡單。哈密爾頓爵士和英國數(shù)學(xué)家克克曼()于19世紀初提出的一個數(shù)學(xué)問題，也是著名的組合優(yōu)化問題。之后介紹模擬退火算法，主要介紹其基本思想和關(guān)鍵技術(shù)，在此基礎(chǔ)上將模擬退火的思想引入TSP的求解，設(shè)計出TSP的一種模擬退火算法并用MATLAB語言編程予以實現(xiàn)。因為模擬退火算法具有高效、通用、靈活的優(yōu)點，將模擬退火算法引入TSP求解，可以避免在求解過程中陷入TSP的局部最優(yōu)解[5]。隨著人工智能的發(fā)展，出現(xiàn)了許多獨立于問題的智能優(yōu)化算法，如蟻群算法、遺傳算法、模擬退火、禁忌搜索、神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等，通過模擬或解釋某些自然現(xiàn)象或過程而得以發(fā)展，為解決復(fù)雜組合優(yōu)化問題提供了新的思路和方法[4]。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程[2]。它的解是多維的、多局部極值的、趨于無窮大的復(fù)雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n1）！。TSP是典型的組合優(yōu)化問題，并且是一個NPhard問題。因此，快速、有效地解決TSP有著重要的理論價值和極高的實際應(yīng)用價值。當(dāng)城市數(shù)量較小時，通過枚舉法就可以找出最短的路徑，然而隨著問題規(guī)模的增加，很難找到一個多項式時間復(fù)雜度的算法來求解該問題。城市Ci,j之間的距離為di,j，i，j=1，2，…，n，設(shè)所有城市間兩兩連通，旅行商需要跑遍n個城市去推銷他的商品，而這些城市之間的距離都不一樣，這推銷員需要從其中一個城市出發(fā)，而他老板規(guī)定他必須把所有城市跑一遍，則TSP問題就是尋找讓旅行商遍訪每個城市一次且恰好一次的一條回路，且要求其路徑總長度為最短。旅行商問題(TSP)由美國RAND公司于1948年引入，該公司的聲譽以及線性規(guī)劃這一新方法的出現(xiàn)使得TSP成為一個知名且流行的問題[2]。到現(xiàn)在為止,運用目前最先進的計算機技術(shù)可解決找出游歷24978個城市的TSP問題。 binatorial optimization13引言旅行商問題(Traveling Salesman Problem,TSP)，也稱為貨郎擔(dān)問題，是由愛爾蘭數(shù)學(xué)家Sir William Rowan Hamilton和英國數(shù)學(xué)家Thomas Penyngton Kirkman在19世紀提出的數(shù)學(xué)問題，它是指給定n個城市并給出每兩個城市之間的距離，旅行商必須以最短路徑訪問所有的城市一次且僅一次，并回到原出發(fā)地，現(xiàn)已證明它屬于NP(Nondeterministic Polynomial非確定多項式)難題[1]。 travelling salesman problem。數(shù)值仿真的結(jié)果表明了該方法能夠?qū)?shù)據(jù)進行全局尋優(yōu)，有效克服了基于導(dǎo)數(shù)的優(yōu)化算法容易陷入局部最優(yōu)的問題。然后闡述了模擬退火算法的基本原理，重點說明了其基本思想及關(guān)鍵技術(shù)。目 錄摘要 II關(guān)鍵詞 IIAbstract IIKeywords II引言 11 旅行商問題和模擬退火算法 2 旅行商問題 2 旅行商問題的描述 2 旅行商問題的應(yīng)用 3 模擬退火算法 3 基本思想 3 關(guān)鍵技術(shù) 4 小結(jié) 42 TSP模擬退火算法的實現(xiàn) 5 TSP算法實現(xiàn) 5 TSP算法描述 5 TSP算法流程 5 TSP的MATLAB實現(xiàn) 6 加載數(shù)據(jù)文件 6 計算總距離的函數(shù) 7 繪制路線的函數(shù)