| | simulate anneal arithmetic (saa,模擬退火算法)
模擬退火算法
模擬退火算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據metropolis準則，粒子在溫度t時趨於平衡的概率為e-Δe/(kt)，其中e為溫度t時的內能，Δe為其改變量，k為boltzmann常數。用固體退火模擬組合優化問題，將內能e模擬為目標函數值f，溫度t演化成控製參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控製參數初值t開始，對當前解重複“産生新解→計算目標函數差→接受或捨棄”的迭代，並逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啓發式隨機搜索過程。退火過程由冷卻進度表(cooling schedule)控製，包括控製參數的初值t及其衰減因子Δt、每個t值時的迭代次數l和停止條件s。
1 . 模擬退火算法的模型
模擬退火算法可以分解為解空間、目標函數和初始解三部分。
模擬退火的基本思想:
(1) 初始化：初始溫度t(充分大)，初始解狀態s(是算法迭代的起點)， 每個t值的迭代次數l
(2) 對k=1，……，l做第(3)至第6步：
(3) 産生新解s′
(4) 計算增量Δt′=c(s′)-c(s)，其中c(s)為評價函數
(5) 若Δt′<0則接受s′作為新的當前解，否則以概率exp(-Δt′/t)接受s′作為新的當前解.
(6) 如果滿足終止條件則輸出當前解作為最優解，結束程序。
終止條件通常取為連續若幹個新解都沒有被接受時終止算法。
(7) t逐漸減少，且t->0，然後轉第2步。
算法對應動態演示圖：
模擬退火算法新解的産生和接受可分為如下四個步驟：
第一步是由一個産生函數從當前解産生一個位於解空間的新解；為便於後續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可産生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，註意到産生新解的變換方法决定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分産生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。
第三步是判斷新解是否被接受,判斷的依據是一個接受準則，最常用的接受準則是metropo1is準則: 若Δt′<0則接受s′作為新的當前解s，否則以概率exp(-Δt′/t)接受s′作為新的當前解s。
第四步是當新解被確定接受時，用新解代替當前解，這衹需將當前解中對應於産生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時，則在原當前解的基礎上繼續下一輪試驗。
模擬退火算法與初始值無關，算法求得的解與初始解狀態s(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂於全局最優解的全局優化算法；模擬退火算法具有並行性。
2 模擬退火算法的簡單應用
作為模擬退火算法應用，討論貨郎擔問題(travelling salesman problem，簡記為tsp)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,…,n．tsp問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.。
求解tsp的模擬退火算法模型可描述如下：
解空間 解空間s是遍訪每個城市恰好一次的所有回路，是{1，……，n}的所有循環排列的集合，s中的成員記為(w1,w2 ,……，wn)，並記wn+1= w1。初始解可選為(1，……，n)
目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：
我們要求此代價函數的最小值。
新解的産生 隨機産生1和n之間的兩相異數k和m，若k(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
變為：
(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).
如果是k>m，則將
(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
變為：
(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).
上述變換方法可簡單說成是“逆轉中間或者逆轉兩端”。
也可以采用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。
代價函數差 設將(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(s′form s); { 從當前回路s産生新回路s′}
Δt:=f(s′))-f(s);{f(s)為路徑總長}
if(Δt<0) or (exp(-Δt/t)>random-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)等等。
3 模擬退火算法的參數控製問題
模擬退火算法的應用很廣泛，可以求解np完全問題，但其參數難以控製，其主要問題有以下三點：
(1) 溫度t的初始值設置問題。
溫度t的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若幹次調整。
(2) 退火速度問題。
模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。
(3) 溫度管理問題。
溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式：
t(t+1)＝k×t(t)
式中k為正的略小於1.00的常數，t為降溫的次數 | | Simulate Anneal Arithmetic (SAA,模擬退火算法)
模擬退火算法
模擬退火算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨於平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控製參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控製參數初值t開始，對當前解重複“産生新解→計算目標函數差→接受或捨棄”的迭代，並逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啓發式隨機搜索過程。退火過程由冷卻進度表(Cooling Schedule)控製，包括控製參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。
模擬退火算法起源於物理退火。
物理退火過程：
（1） 加溫過程
（2） 等溫過程
（3） 冷卻過程
1 . 模擬退火算法的模型
模擬退火算法可以分解為解空間、目標函數和初始解三部分。
模擬退火的基本思想:
(1) 初始化：初始溫度T(充分大)，初始解狀態S(是算法迭代的起點)， 每個T值的迭代次數L
(2) 對k=1，……，L做第(3)至第6步：
(3) 産生新解S′
(4) 計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數
(5) 若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的當前解.
(6) 如果滿足終止條件則輸出當前解作為最優解，結束程序。
終止條件通常取為連續若幹個新解都沒有被接受時終止算法。
(7) T逐漸減少，且T->0，然後轉第2步。
算法對應動態演示圖：
模擬退火算法新解的産生和接受可分為如下四個步驟：
第一步是由一個産生函數從當前解産生一個位於解空間的新解；為便於後續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可産生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，註意到産生新解的變換方法决定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分産生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。
第三步是判斷新解是否被接受,判斷的依據是一個接受準則，最常用的接受準則是Metropo1is準則: 若Δt′<0則接受S′作為新的當前解S，否則以概率exp(-Δt′/T)接受S′作為新的當前解S。
第四步是當新解被確定接受時，用新解代替當前解，這衹需將當前解中對應於産生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時，則在原當前解的基礎上繼續下一輪試驗。
模擬退火算法與初始值無關，算法求得的解與初始解狀態S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂於全局最優解的全局優化算法；模擬退火算法具有並行性。
2 模擬退火算法的簡單應用
作為模擬退火算法應用，討論貨郎擔問題(Travelling Salesman Problem，簡記為TSP)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.。
求解TSP的模擬退火算法模型可描述如下：
解空間 解空間S是遍訪每個城市恰好一次的所有回路，是{1，……，n}的所有循環排列的集合，S中的成員記為(w1,w2 ,……，wn)，並記wn+1= w1。初始解可選為(1，……，n)
目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：
我們要求此代價函數的最小值。
新解的産生 隨機産生1和n之間的兩相異數k和m，若k (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
變為：
(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).
如果是k>m，則將
(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
變為：
(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).
上述變換方法可簡單說成是“逆轉中間或者逆轉兩端”。
也可以采用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。
代價函數差 設將(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(S′form S); { 從當前回路S産生新回路S′}
Δt:=f(S′))-f(S);{f(S)為路徑總長}
IF(Δt<0) OR (EXP(-Δt/T)>Random-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)等等。
3 模擬退火算法的參數控製問題
模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數難以控製，其主要問題有以下三點：
(1) 溫度T的初始值設置問題。
溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若幹次調整。
(2) 退火速度問題。
模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。
(3) 溫度管理問題。
溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式：
T(t+1)＝k×T(t)
式中k為正的略小於1.00的常數，t為降溫的次數
4、模擬退火算法的優缺點
優點：計算過程簡單，通用，魯棒性強，適用於並行處理，可用於求解復雜的非綫性優化問題。
缺點：收斂速度慢，執行時間長，算法性能與初始值有關及參數敏感等缺點。
經典模擬退火算法的缺點：
(1)如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢;
(2)如果降溫過程過快，很可能得不到全局最優解。
模擬退火算法的改進
(1) 設計合適的狀態産生函數，使其根據搜索進程的需要
表現出狀態的全空間分散性或局部區域性。
(2) 設計高效的退火策略。
(3) 避免狀態的迂回搜索。
(4) 采用並行搜索結構。
(5) 為避免陷入局部極小，改進對溫度的控製方式
(6) 選擇合適的初始狀態。
(7) 設計合適的算法終止準則。
也可通過增加某些環節而實現對模擬退火算法的改進。
主要的改進方式包括：
(1) 增加升溫或重升溫過程。在算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免算法在局部極小解處停滯不前。
(2) 增加記憶功能。為避免搜索過程中由於執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。
(3) 增加補充搜索過程。即在退火過程結束後，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。
(4) 對每一當前狀態，采用多次搜索策略，以概率接受區域內的最優狀態，而非標準SA的單次比較方式。
(5) 結合其他搜索機製的算法，如遺傳算法、混沌搜索等。
(6)上述各方法的綜合應用。 | | | | |
|
|