模擬退火

模擬退火算法（Simulate Anneal，SA）是一種通用機率演算法，用來在一個大的搜尋空間內找尋命題的最優解。模擬退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所發明的。V.Černý在1985年也獨立發明此演算法。模擬退火算法是解決TSP問題的有效方法之一。

模擬退火的出發點是基於物理中固體物質的退火過程與一般組合最佳化問題之間的相似性。模擬退火算法是一種通用的最佳化算法，其物理退火過程由加溫過程、等溫過程、冷卻過程這三部分組成。

基本介紹

• 中文名：模擬退火
• 外文名：Simulated Annealing
• 時間：1983年
• 學科：計算機科學
• 簡稱：SA

原理

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

基本要素

狀態空間與狀態產生函式

1）搜尋空間也稱為狀態空間，它由經過編碼的可行解的集合組成。
2）狀態產生函式（鄰域函式）應儘可能保證產生的候選解遍布全部解空間。通常由兩部分組成，即產生候選解的方式和候選解產生的機率分布。
3）候選解一般採用按照某一機率密度函式對解空間進行隨機採樣來獲得。
4）機率分布可以是均勻分布、常態分配、指數分布等。

狀態轉移機率

1）狀態轉移機率是指從一個狀態向另一個狀態的轉移機率。
2）通俗的理解是接受一個新解為當前解的機率。
3）它與當前的溫度參數T有關，隨溫度下降而減小。
4）一般採用Metropolis準則。

內循環終止準則

也稱Metropolis抽樣穩定準則，用於決定在各溫度下產生候選解的數目。常用的抽樣穩定準則包括：
1）檢驗目標函式的均值是否穩定。
2）連續若干步的目標值變化較小。
3）按一定的步數抽樣。

外循環終止準則

即算法終止準則，常用的包括：
1）設定終止溫度的閾值。
2）設定外循環疊代次數。
3）算法搜尋到的最優值連續若干步保持不變。
4）檢驗系統熵是否穩定。

模擬退火模型

模擬退火算法新解的產生和接受可分為如下四個步驟：

第一步是由一個產生函式從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。

第二步是計算與新解所對應的目標函式差。因為目標函式差僅由變換部分產生，所以目標函式差的計算最好按增量計算。事實表明，對大多數套用而言，這是計算目標函式差的最快方法。

第三步是判斷新解是否被接受，判斷的依據是一個接受準則，最常用的接受準則是Metropolis準則: 若Δt′<0則接受S′作為新的當前解S，否則以機率exp(-Δt′/T)接受S′作為新的當前解S。

第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函式值即可。此時，當前解實現了一次疊代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時，則在原當前解的基礎上繼續下一輪試驗。

模擬退火算法與初始值無關，算法求得的解與初始解狀態S(是算法疊代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以機率收斂於全局最優解的全局最佳化算法；模擬退火算法具有並行性。

參數控制

模擬退火算法的套用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點：

(1) 溫度T的初始值設定問題。

溫度T的初始值設定是影響模擬退火算法全局搜尋性能的重要因素之一、初始溫度高，則搜尋到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜尋性能可能受到影響。實際套用過程中，初始溫度一般需要依據實驗結果進行若干次調整。

(2) 退火速度問題。

模擬退火算法的全局搜尋性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜尋(退火)是相當必要的，但這需要計算時間。實際套用中，要針對具體問題的性質和特徵設定合理的退火平衡條件。

(3) 溫度管理問題。

溫度管理問題也是模擬退火算法難以處理的問題之一。實際套用中，由於必須考慮計算複雜度的切實可行性等問題，常採用如下所示的降溫方式：

式中k為正的略小於1.00的常數，t為降溫的次數。

算法改進

（1）設計合適的狀態產生函式，使其根據搜尋進程的需要表現出狀態的全空間分散性或局部區域性；
（2）設計高效的退火策略；
（3）避免狀態的迂迴搜尋；
（4）採用並行搜尋結構；
（5）為避免陷入局部極小，改進對溫度的控制方式；
（6）選擇合適的初始狀態；
（7）設計合適的算法終止準則。