中國數學建模-編程交流-模擬退火算法.doc

中國數學建模-編程交流-模擬退火算法 模擬退火算法 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為e-E/(kT)，其中E為溫度T時的內能，E為其改變量，k為Boltzmann常數。用固體退火模擬組合優(yōu)化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重復“產生新解計算目標函數差接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(Cooling Schedule)控制，包括控制參數的初值t及其衰減因子t、每個t值時的迭代次數L和停止條件S。 3.5.1 模擬退火算法的模型 模擬退火算法可以分解為解空間、目標函數和初始解三部分。 模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每個T值的迭代次數L (2) 對k=1，L做第(3)至第6步： (3) 產生新解S (4) 計算增量t=C(S)-C(S)，其中C(S)為評價函數 (5) 若t0，然后轉第2步。 算法對應動態(tài)演示圖： 模擬退火算法新解的產生和接受可分為如下四個步驟： 第一步是由一個產生函數從當前解產生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。 第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。 第三步是判斷新解是否被接受,判斷的依據是一個接受準則，最常用的接受準則是Metropo1is準則: 若t0則接受S作為新的當前解S，否則以概率exp(-t/T)接受S作為新的當前解S。 第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代?？稍诖嘶A上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續(xù)下一輪試驗。 模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。 模擬退火算法的簡單應用 作為模擬退火算法應用，討論貨郎擔問題(Travelling Salesman Problem，簡記為TSP)：設有n個城市，用數碼1,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,nTSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.。 求解TSP的模擬退火算法模型可描述如下： 解空間 解空間S是遍訪每個城市恰好一次的所有回路，是1，n的所有循環(huán)排列的集合，S中的成員記為(w1,w2 ,，wn)，并記wn+1= w1。初始解可選為(1，n) 目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數： 我們要求此代價函數的最小值。 新解的產生 隨機產生1和n之間的兩相異數k和m，若km，則將 (w1, w2 ,，wk , wk+1 ,，wm ,，wn) 變?yōu)椋?(wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk). 上述變換方法可簡單說成是“逆轉中間或者逆轉兩端”。 也可以采用其他的變換方法，有些變換有獨特的優(yōu)越性，有時也將它們交替使用，得到一種更好方法。 代價函數差 設將(w1, w2 ,，wn)變換為(u1, u2 ,，un), 則代價函數差為： 根據上述分析，可寫出用模擬退火算法求解TSP問題的偽程序： Procedure TSPSA: begin init-of-T; T為初始溫度 S=1，n; S為初始值 termination=false; while termination=false begin for i=1 to L do begin generate(Sform S); 從當前回路S產生新回路S t:=f(S)-f(S);f(S)為路徑總長 IF(tRandom-of-0,1) S=S; IF the-halt-condition-is-TRUE THEN termination=true; End; T_lower; End; End 模擬退火算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調度問題(Scheduling Problem)等等。 模擬退火算法的參數控制問題 模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點： (1) 溫度T的初始值設置問題。 溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。 (2) 退火速度問題。 模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特征設置合理的退火平衡條件。 (3) 溫度管理問題。 溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式： T(t+1)kT(t) 式中k為正的略小于1.00的常數，t為降溫的次數。 以下是引用b在2004-5-27 19:07:41的發(fā)言： 模擬退火算法的簡單應用 作為模擬退火算法應用，討論貨郎擔問題(Travelling Salesman Problem，簡記為TSP)：設有n個城市，用數碼1,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,nTSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.。 求解TSP的模擬退火算法模型可描述如下： 解空間 解空間S是遍訪每個城市恰好一次的所有回路，是1，n的所有循環(huán)排列的集合，S中的成員記為(w1,w2 ,，wn)，并記wn+1= w1。初始解可選為(1，n) 目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數： 我們要求此代價函數的最小值。 新解的產生 隨機產生1和n之間的兩相異數k和m，若km，則將 (w1, w2 ,，wk , wk+1 ,，wm ,，wn) 變?yōu)椋?(wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk). 上述變換方法可簡單說成是“逆轉中間或者逆轉兩端”。 也可以采用其他的變換方法，有些變換有獨特的優(yōu)越性，有時也將它們交替使用，得到一種更好方法。 代價函數差 設將(w1, w2 ,，wn)變換為(u1, u2 ,，un), 則代價函數差為： 根據上述分析，可寫出用模擬退火算法求解TSP問題的偽程序： Procedure TSPSA: begin init-of-T; T為初始溫度 S=1，n; S為初始值 termination=false; while termination=false begin for i=1 to L do begin generate(Sform S); 從當前回路S產生新回路S t:=f(S)-f(S);f(S)為路徑總長 IF(tRandom-of-0,1) S=S; IF the-halt-condition-is-TRUE THEN