標籤:概率

模擬退火(Simulated Annealing,簡稱SA)是一種通用概率演算法,用來在一個大的搜尋空間內找尋命題的最優解。

1定義

「模擬退火」演算法是源於對熱力學中退火過程的模擬,在某一給定初溫下,通過緩慢下降溫度參數,使演算法能夠在多項式時間內給出一個近似最優解。退火與冶金學上的『退火』相似,而與冶金學的淬火有很大區別,前者是溫度緩慢下降,後者是溫度迅速下降。

2原理

「模擬退火」的原理也和金屬退火的原理近似:我們將熱力學的理論套用到統計學上,將搜尋空間內每一點想像成空氣內的分子;分子的能量,就是它本身的動能;而搜尋空間內的每一點,也像空氣分子一樣帶有「能量」,以表示該點對命題的合適程度。演算法先以搜尋空間內一個任意點作起始:每一步先選擇一個「鄰居」,然後再計算從現有位置到達「鄰居」的概率。
模擬退火演算法可以分解為解空間、目標函數和初始解三部分。
模擬退火的基本思想:
(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步。

3方法

演算法對應動態演示圖:
模擬退火演算法新解的產生和接受可分為如下四個步驟:
第一步是由一個產生函數從當前解產生一個位於解空間的新解;為便於後續的計算和接受,減少演算法耗時,通常選擇由當前新解經過簡單地變換即可產生新解的方法,如對構成新解的全部或部分元素進行置換、互換等,注意到產生新解的變換方法決定了當前新解的鄰域結構,因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生,所以目標函數差的計算最好按增量計算。事實表明,對大多數應用而言,這是計算目標函數差的最快方法。
第三步是判斷新解是否被接受,判斷的依據是一個接受準則,最常用的接受準則是Metropolis準則: 若Δt′<0則接受S′作為新的當前解S,否則以概率exp(-Δt′/T)接受S′作為新的當前解S。
第四步是當新解被確定接受時,用新解代替當前解,這隻需將當前解中對應於產生新解時的變換部分予以實現,同時修正目標函數值即可。此時,當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時,則在原當前解的基礎上繼續下一輪試驗。
模擬退火演算法與初始值無關,演算法求得的解與初始解狀態S(是演算法迭代的起點)無關;模擬退火演算法具有漸近收斂性,已在理論上被證明是一種以概率l 收斂於全局最優解的全局優化演算法;模擬退火演算法具有并行性。

相關評論

同義詞:暫無同義詞