基本介紹
算法簡介,原理,套用,
算法簡介
模擬退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人於1953年提出。1983 年,S. Kirkpatrick 等成功地將退火思想引入到組合最佳化領域。它是基於Monte-Carlo疊代求解策略的一種隨機尋優算法，其出發點是基於物理中固體物質的退火過程與一般組合最佳化問題之間的相似性。模擬退火算法從某一較高初溫出發，伴隨溫度參數的不斷下降,結合機率突跳特性在解空間中隨機尋找目標函式的全局最優解，即在局部最優解能機率性地跳出並最終趨於全局最優。模擬退火算法是一種通用的最佳化算法，理論上算法具有機率的全局最佳化性能,目前已在工程中得到了廣泛套用，諸如VLSI、生產調度、控制工程、機器學習、神經網路、信號處理等領域。
模擬退火算法是通過賦予搜尋過程一種時變且最終趨於零的機率突跳性，從而可有效避免陷入局部極小並最終趨於全局最優的串列結構的最佳化算法。
原理
模擬退火算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨於平衡的機率為e(-ΔE/(kT))，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合最佳化問題，將內能E模擬為目標函式值f，溫度T演化成控制參數t，即得到解組合最佳化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重複“產生新解→計算目標函式差→接受或捨棄”的疊代，並逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅疊代求解法的一種啟發式隨機搜尋過程。退火過程由冷卻進度表(Cooling Schedule)控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的疊代次數L和停止條件S。
模擬退火算法的模型
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步。
模擬退火算法的步驟
模擬退火算法新解的產生和接受可分為如下四個步驟：
第一步是由一個產生函式從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函式差。因為目標函式差僅由變換部分產生，所以目標函式差的計算最好按增量計算。事實表明，對大多數套用而言，這是計算目標函式差的最快方法。
第三步是判斷新解是否被接受,判斷的依據是一個接受準則，最常用的接受準則是Metropolis準則: 若ΔT<0則接受S′作為新的當前解S，否則以機率exp(-ΔT/T)接受S′作為新的當前解S。
第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函式值即可。此時，當前解實現了一次疊代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時，則在原當前解的基礎上繼續下一輪試驗。
模擬退火算法與初始值無關，算法求得的解與初始解狀態S(是算法疊代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以機率l 收斂於全局最優解的全局最佳化算法；模擬退火算法具有並行性。
套用
模擬退火算法作為一種通用的隨機搜尋算法，現已廣泛用於VLSI設計、圖像識別和神經網計算機的研究。模擬退火算法的套用如下：
1、模擬退火算法在VLSI設計中的套用
利用模擬退火算法進行VLSI的最優設計，是目前模擬退火算法最成功的套用實例之一。用模擬退火算法幾乎可以很好地完成所有最佳化的VLSI設計工作。如全局布線、布板、布局和邏輯最小化等等。
2、模擬退火算法在神經網計算機中的套用
模擬退火算法具有跳出局部最優陷阱的能力。在Boltzmann機中，即使系統落入了局部最優的陷阱，經過一段時間後，它還能再跳出來，再系統最終將往全局最優值的方向收斂。
3、模擬退火算法在圖像處理中的套用
模擬退火算法可用來進行圖像恢復等工作，即把一幅被污染的圖像重新恢復成清晰的原圖，濾掉其中被畸變的部分。因此它在圖像處理方面的套用前景是廣闊的。
4、模擬退火算法的其他套用
除了上述套用外，模擬退火算法還用於其它各種組合最佳化問題，如TSP和Knapsack問題等。大量的模擬實驗表明，模擬退火算法在求解這些問題時能產生令人滿意的近似最優解，而且所用的時間也不很長。
模擬退火算法 偽代碼
s:=s0;e:=E(s)//設定目前狀態為s0，其能量E(s0)k:=0//評估次數kwhilek<kmaxande>emax//若還有時間（評估次數k還不到kmax）且結果還不夠好（能量e不夠低）則：sn:=neighbour(s)//隨機選取一臨近狀態snen:=Esn)//sn的能量為E(sn)ifrandom()<P(e,en,temp(k/kmax))then//決定是否移至臨近狀態sns:=sn;e:=en//移至臨近狀態snk:=k+1//評估完成，次數k加一returns//迴轉狀態s
