1、改變世界的算法模擬退火算法求解TSP問題進修生：曹廣升旅行商問題，即TSP問題(TravellingSalesmanProblem)是數學領域中著名問題之一。假設有一個旅彳T商人要拜訪n個城市，他必須選擇所要走的路徑，路經的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。左邊的路程要小于右邊的圖1TSP問題的示意圖二、遍歷算法一個最容易想到的方法是利用排列組合的方法把所有的路徑都計算出來，并逐一比較，選出最小的路徑。雖然該方法在理論上是可行的，但路徑的個數與城市的個數成指數增長，當城市個數較大時，該方法的求解時間是難以忍受的，甚

2、至是不可能完成的。以每秒1億次的計算速度來估算，如果TSP問題包含20個城市時，求解時間長達350年；如果要處理30個城市，則求解時間更長達1+10e16年。如此長的時間，在實際中完成是難以想象的。三、模擬退火算法模擬退火算法是解決TSP問題的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地將其應用在組合最優化問題中。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。根據Metropol

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

4、退火算法可以分解為解空間、目標函數和初始解三部分。模擬退火的基本思想：(1)初始化：初始溫度T(充分大)，初始解狀態S(是算法迭代的起點)，每個T值的迭彳t次數L(2)對k=1一，L做第至第6步：(3)產生新解S'(4)計算增量At'=C(S')-C(S),其中C(S)為評價函數(5)若At'<0則接受S'作為新的當前解，否則以概率exp(-At'/T)接受S'作為新白當前解.(6)如果滿足終止條件則輸出當前解作為最優解，結束程序。終止條件通常取為連續若干個新解都沒有被接受時終止算法。(7)T逐漸減少，且T->0,然后轉第2步

5、。模擬退火算法新解的產生和接受可分為如下四個步驟：第一步是由一個產生函數從當前解產生一個位于解空間的新解；為便于后續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。第三步是判斷新解是否被接受，判斷的依據是一個接受準則，最常用的接受準則是Metropo1is準則：若At&#

6、39;<0則接受S'作為新白當前解S,否則以概率exp(-At'/T)接受S'作為新白當前解So第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代?？稍诖嘶A上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。模擬退火算法與初始值無關，算法求得的解與初始解狀態S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優解的全局優化算法；模擬退火算法具有并行性。求解TSP的模擬退火算法模型可描述如下：解空間

7、：解空間S是遍訪每個城市恰好一次的所有路經，解可以表示為w1,w2,wn,w1,wn是1,2,n的一個排列，表明w1城市出發，依次經過w2,wn城市，再返回w1城市。初始解可選為(1,n);目標函數：目標函數為訪問所有城市的路徑總長度；我們要求的最優路徑為目標函數為最小值時對應的路徑。新路徑的產生：隨機產生1和n之間的兩相異數k和m,不妨假設k<m,則將原路徑(w1,w2,wk,wk+1,wm,wm+1,wn)變為新路徑：(w1,w2,wm,wk+1,wk,wm+1,wn)上述變換方法就是將k和m對應的兩個城市在路徑序列中交換位置，稱為2-opt映射。2模擬退火算法求解TSP問題的流程框

8、圖如下結束一圖2模擬退火算法的流程框圖3模擬退火算法的參數控制問題模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點：(1)溫度T的初始值設置問題。溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。(2)退火速度問題。模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的

9、性質和特征設置合理的退火平衡條件。(3)溫度管理問題。溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式：T(t+1)=kXT(t)式中k為正的略小于1.00的常數，t為降溫的次數其實,模擬退火就是在一定的解空間內用模擬退火的方式來尋求一個"最優解",其計算復雜度，最壞情況應該就是2的N次方，但是考慮到最壞的情況又不能體現模擬退火的優越性，因為其中尋優的過程中，新解的產生機制和接受機制以及終止條件和降溫方式都影響著這個復雜度的問題.四、主要代碼對應于流程框圖，實現流程的主體函數是SAComputio

10、n(),代碼如下：UINTSACompution(LPVOIDpParam)while(1)doubledeltatotaldis=0.0;while(1)SYRouterSelRouter(ResultRouter.m_CityRouter,NowTemperature,NowExternalIterNumber,NowInnerIterNumber);/從某路徑的鄰域中隨機選擇一個新的路徑，鄰域映射為2-optdeltatotaldis=SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance;/計算新路徑與當前路徑的路程長度差值if

11、(deltatotaldis<=0.0)如果新路徑的路程短，則用它替換當前路徑ResultRouter=SelRouter;/else(doublechgprobability=exp(-(deltatotaldis/NowTemperature);intrandomnum=rand();doublerandom=(double)(randomnum%10000)/10000.0;if(chgprobability>random)ResultRouter=SelRouter;/如果新路徑長于當前路徑，但exp(-Af/t)>random(0,1),則仍然替換當前路徑if(JudgeOverInnerLoop(0)break;/判斷內循環是否結束，結束則跳出當前溫度的內循環elseNowInnerIterNumber+;/判斷內循環是否結束，不結束則繼續內循環if(JudgeOverExternalLoop(0)break;/判斷外循環是否結束，結束則結束模擬退火計算else(NowTemperature=CountDownTemperature(NowTemperature,0);NowExternalIterNumber+;NowInnerIterNumber=0;/判斷外循環是否結束，不結束則計算出下降后的溫度，并繼續循環五