模擬退火算法詳解
一個由金屬退火啟發(fā)的算法!
本文主要內(nèi)容：
金屬退火的原理 模擬退火算法機制 模擬退火的流程 模擬退火的應用 算法小結(jié)
1.金屬退火的原理
金屬退火是將金屬加熱到一定溫度，保持足夠時間，然后以適宜速度冷卻(通常是緩慢冷卻，有時是控制冷卻)的一種金屬熱處理工藝。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。
如上圖，處在低溫狀態(tài)時，固體中分子具有的內(nèi)能很低，在原本的位置上做小范圍的振動。若是將固體加熱到一定溫度，分子內(nèi)能將會增加，熱運動加劇，分子排列的無序度增加。此時再將溫度緩緩降低，在每個溫度都達到平衡態(tài)（即準靜態(tài)過程），分子具有的能量逐漸降低，最終回歸到有序排列的狀態(tài)，分子內(nèi)能也跟著降到最低。
2.模擬退火算法機制
模擬退火算法(Simulated Annealing,SA)最早的思想是由N. Metropolis等人于1953年提出。1983年,S. Kirkpatrick等成功地將退火思想引入到組合優(yōu)化領域。它是基于Monte-Carlo 迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。
介紹模擬退火前，還是有必要先介紹爬山算法。
爬山算法
爬山算法是一種簡單的貪心搜索算法，該算法每次從當前解的臨近解空間中選擇一個最優(yōu)解作為當前解，直到達到一個局部最優(yōu)解。
爬山算法實現(xiàn)很簡單，其主要缺點是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如上圖所示：假設C點為當前解，爬山算法搜索到A點這個局部最優(yōu)解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優(yōu)的解。
模擬退火核心思想
模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合一定的概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。如下圖：
這里的“一定的概率”的計算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。將溫度T當作控制參數(shù)，目標函數(shù)值f視為內(nèi)能E，而固體在某溫度T時的一個狀態(tài)對應一個解，然后算法試圖隨著控制參數(shù)T的降低，使目標函數(shù)f(內(nèi)能E)也逐漸降低，直至趨于全局最小值（退火中低溫時的最低能量狀態(tài)），就像金屬退火過程一樣。
關于爬山算法與模擬退火，有一個有趣的比喻：
爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。 模擬退火：兔子喝醉了。它隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。這就是模擬退火。
模擬退火數(shù)學原理
從上面我們知道，會結(jié)合概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，那么具體的更新解的機制是什么呢？如果新解比當前解更優(yōu)，則接受新解，否則基于Metropolis準則判斷是否接受新解。接受概率為：
如上公式，假設當前時刻搜索的解為，對應的系統(tǒng)能量(目標函數(shù))為，對搜索點施加隨機擾動，產(chǎn)生新解，相應地，系統(tǒng)能量為，那么系統(tǒng)對搜索點從到轉(zhuǎn)變的接受概率就為上公式。具體以下圖為例：
假設開始狀態(tài)在A，隨著迭代次數(shù)更新到B局部最優(yōu)解，這時發(fā)現(xiàn)更新到B時，能量比A要低，則說明接近最優(yōu)解了，因此百分百轉(zhuǎn)移，狀態(tài)到達B后，發(fā)現(xiàn)下一步能量上升了，如果是梯度下降則是不允許繼續(xù)向前的，而這里會以一定的概率跳出這個坑，這個概率和當前的狀態(tài)、能量等都有關系，如果B最終跳出來了到達C，又會繼續(xù)以一定的概率跳出來，直到到達D后，就會穩(wěn)定下來。
3.模擬退火的流程
算法實質(zhì)分兩層循環(huán)，在任一溫度水平下，隨機擾動產(chǎn)生新解，并計算目標函數(shù)值的變化，決定是否被接受。由于算法初始溫度比較高，這樣，使E增大的新解在初始時也可能被接受，因而能跳出局部極小值，然后通過緩慢地降低溫度，算法就最終可能收斂到全局最優(yōu)解，具體流程為：
令,表示開始退火的初始溫度，隨機產(chǎn)生一個初始解,并計算對應的目標函數(shù)值; 令,其中 k取值0到1之間，為溫度下降速率；對當前解施加隨機擾動，在其鄰域內(nèi)產(chǎn)生一個新解，并計算對應的目標函數(shù)值,計算
若,接受新解作為當前解，否則按照概率判斷是否接受新解； 在溫度 T下，重復L次擾動和接受過程，即執(zhí)行步驟3和4；判斷溫度是否達到終止溫度水平，若是則終止算法，否則返回步驟 2.
具體流程圖如下：
其中有幾個需要注意的點：
初始點的選取對算法結(jié)果有一定的影響，最好是多次運行對結(jié)果進行綜合判斷。 在算法運行初期，溫度下降快，避免接受過多的差結(jié)果。當運行時間增加，溫度下降減緩，以便于更快穩(wěn)定結(jié)果。 當?shù)螖?shù)增加到一定次數(shù)時，結(jié)果可能已經(jīng)達到穩(wěn)定，但是距離算法結(jié)束還有一段時間。在設計程序時應該加入適當?shù)妮敵鰲l件，滿足輸出條件即可結(jié)束程序。
4.模擬退火的應用
模擬退火算法作為一種通用的隨機搜索算法，現(xiàn)已廣泛用于VLSI設計、圖像識別和神經(jīng)網(wǎng)計算機的研究。模擬退火算法的應用如下：
模擬退火算法在 VLSI設計中的應用
利用模擬退火算法進行VLSI(Very Large Scale Integration,超大規(guī)模集成電路)的最優(yōu)設計，是目前模擬退火算法最成功的應用實例之一。用模擬退火算法幾乎可以很好地完成所有優(yōu)化的VLSI設計工作。如全局布線、布板、布局和邏輯最小化等等。
模擬退火算法在圖像處理中的應用
模擬退火算法可用來進行圖像恢復等工作，即把一幅被污染的圖像重新恢復成清晰的原圖，濾掉其中被畸變的部分。因此它在圖像處理方面的應用前景是廣闊的。模擬退火算法在神經(jīng)網(wǎng)計算機中的應用
模擬退火算法具有跳出局部最優(yōu)陷阱的能力。在Boltzmann機中，即使系統(tǒng)落入了局部最優(yōu)的陷阱，經(jīng)過一段時間后，它還能再跳出來，系統(tǒng)最終將往全局最優(yōu)值的方向收斂。
模擬退火算法的其他應用
除了上述應用外，模擬退火算法還用于其它各種組合優(yōu)化問題，如TSP和Knapsack問題等。大量的模擬實驗表明，模擬退火算法在求解這些問題時能產(chǎn)生令人滿意的近似最優(yōu)解，而且所用的時間也不很長。
5.小結(jié)
總之，模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法。算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合一定的概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。
至此，本文從金屬退火的原理，爬山算法，模擬退火算法思想以及原理，到模擬退火的流程和應用方面對模擬退火算法進行了簡單的闡述，希望對大家有所幫助。
?點個贊再走唄?