【文章內容簡介】 st(s)，其中cost(s)為評價函數(shù)；(5)若t′0則接受s′作為新的當前解，否則以概率exp(t′/T)接受s′作為新的當前解；(6)如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法；(7)T逐漸減少，且T趨于0，然后轉第2步運算。 關鍵技術（1）新解的產生和接受模擬退火算法新解的產生和接受可分為如下4個步驟：①由一個函數(shù)從當前解產生一個位于解空間的新解。為便于后續(xù)的計算和接受，減少算法耗時，常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等。產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。②計算與新解所對應的目標函數(shù)差。因為目標函數(shù)差僅由變換部分產生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。③判斷新解是否被接受。判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropo1is準則：若t′0則接受S′作為新的當前解S，否則以概率exp(t′/T)接受S′作為新的當前解S。④當新解被確定接受時，用新解代替當前解。這只需將當前解中對應于產生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代，可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續(xù)下一輪試驗。模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。（2）參數(shù)控制問題模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下3點[7]：①溫度T的初始值設置。溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據(jù)實驗結果進行若干次調整。②溫度衰減函數(shù)的選取。衰減函數(shù)用于控制溫度的退火速度，一個常用的函數(shù)為： 式中是一個非常接近于1的常數(shù)，t為降溫的次數(shù)。③馬爾可夫鏈長度L的選取。通常的原則是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L的選取應遵循在控制參數(shù)的每一取值上都能恢復準平衡的原則。 小結 本章而要的介紹了旅行商問題與模擬退火算法，首先對旅行商問題做了描述并舉例其應用，然后介紹了模擬退火算法的來源，重點介紹了模擬退火算法的基本思想和關鍵技術。通過本章的分析，使我們理解了模擬退火算法的基本原理并且知道了TSP問題的數(shù)學描述，為下面將該算法其應用于旅行商問題做了準備。2 TSP模擬退火算法的實現(xiàn) TSP是典型的組合優(yōu)化問題，模擬退火算法是一種隨機性解決組合優(yōu)化方法。將TSP與模擬退火算法相結合，以實現(xiàn)對其求解。 TSP算法實現(xiàn) TSP算法描述 （1）TSP問題的解空間和初始解 TSP的解空間S是遍訪每個城市恰好一次的所有回路，是所有城市排列的集合。TSP問題的解空間S可表示為{1,2,…,n}的所有排列的集合，即S = {(c1,c2,…,) | ((c1,c2,…,)為{1,2,…,n}的排列）}，其中每一個排列Si表示遍訪n個城市的一個路徑，ci= j表示在第i次訪問城市j。模擬退火算法的最優(yōu)解與初始狀態(tài)無關，故初始解為隨機函數(shù)生成一個{1,2,…,n}的隨機排列作為S0。（2）目標函數(shù) TSP問題的目標函數(shù)即為訪問所有城市的路徑總長度，也可稱為代價函數(shù)： 現(xiàn)在TSP問題的求解就是通過模擬退火算法求出目標函數(shù)C(c1,c2,…,)的最小值，相應地，s*= (c*1,c*2,…,c*n)即為TSP問題的最優(yōu)解。 （3）新解產生新解的產生對問題的求解非常重要。新解可通過分別或者交替用以下2種方法產生：①二變換法：任選序號u,v(設uvn)，交換u和v之間的訪問順序，若交換前的解為si= (c1,c2,…,cu,…,cv,…,),交換后的路徑為新路徑，即：si′= (c1,…,cu1,cv,cv1,…,cu+1,cu,cv+1,…,)②三變換法：任選序號u,v和ω(u≤vω)，將u和v之間的路徑插到ω之后訪問，若交換前的解為si= (c1,c2,…,cu,…,cv,…,cω,…,)，交換后的路徑為的新路徑為：si′= (c1,…,cu1,cv+1,…,cω,cu,…,cv,cω+1,…,)（4）目標函數(shù)差計算變換前的解和變換后目標函數(shù)的差值：Δc′= c(si′) c(si)（5）Metropolis接受準則根據(jù)目標函數(shù)的差值和概率exp(ΔC′/T)接受si′作為新的當前解si，接受準則： TSP算法流程 根據(jù)以上對TSP的算法描述，可以寫出用模擬退火算法解TSP問題的流程圖21所示：圖 21 TSP的模擬退火流程 TSP的MATLAB實現(xiàn) 加載數(shù)據(jù)文件下面是加載數(shù)據(jù)文件的一個例子：function d = datafile()cities =[,,,...,,,...,。,,,...,,,...]。save cities V6。當調用數(shù)據(jù)文件函數(shù)時。該數(shù)據(jù)文件的第一列通常是城市數(shù)量，之后兩列為城市的坐標。初始化函數(shù)，根據(jù)直角坐標生成城市距離矩陣。 計算總距離的函數(shù)這是一個城市間計算距離的函數(shù)，根據(jù)給定路徑計算該路徑對應總路程。function d = distance(inputcities) % 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ù)是城市之間的距離。調用此函數(shù)將計算n個城市之間的距離。 繪制路線的函數(shù)這是一個繪制路線的函數(shù)，根據(jù)給定的城市坐標生成的城市矩陣繪制城市的坐標，根據(jù)給定的路線