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