登錄

模擬退火算法

百科 > 信息管理工具 > 模擬退火算法

1.什么是模擬退火算法

模擬退火算法（Simulate Anneal Arithmetic，SAA）是一種通用概率演算法，用來在一個大的搜尋空間內(nèi)找尋命題的最優(yōu)解。模擬退火是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所發(fā)明。而V.?erny在1985年也獨立發(fā)明此演算法。模擬退火算法是解決TSP問題的有效方法之一。

模擬退火來自冶金學(xué)的專有名詞退火。退火是將材料加熱后再經(jīng)特定速率冷卻，目的是增大晶粒的體積，并且減少晶格中的缺陷。材料中的原子原來會停留在使內(nèi)能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動。退火冷卻時速度較慢，使得原子有較多可能可以找到內(nèi)能比原先更低的位置。

模擬退火的原理也和金屬退火的原理近似：將熱力學(xué)的理論套用到統(tǒng)計學(xué)上，將搜尋空間內(nèi)每一點想像成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度。演算法先以搜尋空間內(nèi)一個任意點作起始：每一步先選擇一個“鄰居”，然后再計算從現(xiàn)有位置到達“鄰居”的概率。

2.模擬退火算法的模型[1]

模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。

  • 模擬退火的基本思想:
    • (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每個T值的迭代次數(shù)L
    • (2) 對k=1，……，L做第(3)至第6步：
    • (3) 產(chǎn)生新解S′
    • (4) 計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數(shù)
    • (5) 若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的當前解.
    • (6) 如果滿足終止條件則輸出當前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。
    • (7) T逐漸減少，且T->0，然后轉(zhuǎn)第2步。

算法對應(yīng)動態(tài)演示圖：

Image:模擬退火算法.jpg

  • 模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟：
    • 第一步是由一個產(chǎn)生函數(shù)從當前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。
    • 第二步是計算與新解所對應(yīng)的目標函數(shù)差。因為目標函數(shù)差僅由變換部分產(chǎn)生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標函數(shù)差的最快方法。
    • 第三步是判斷新解是否被接受，判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropolis準則: 若Δt′<0則接受S′作為新的當前解S，否則以概率exp(-Δt′/T)接受S′作為新的當前解S。
    • 第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代。可在此基礎(chǔ)上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎(chǔ)上繼續(xù)下一輪試驗。

模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。

3.模擬退火算法求解TSP問題的偽程序[1]

根據(jù)上述分析，可寫出用模擬退火算法求解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產(chǎn)生新回路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

模擬退火算法的應(yīng)用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調(diào)度問題(Scheduling Problem)等等。

評論  |   0條評論