預(yù)計(jì)讀完 5 分鐘

今天，小編將帶大家學(xué)習(xí)一個經(jīng)典算法——模擬退火算法。

以下為本文框架：

一、什么是模擬退火算法？

模擬退火算法（simulated annealing，SA）來源于固體退火原理，是一種基于概率的算法。

算法思想為：先從一個較高的初始溫度出發(fā)，逐漸降低溫度，直到溫度降低到滿足熱平衡條件為止。在每個溫度下，進(jìn)行n輪搜索，每輪搜索時對舊解添加隨機(jī)擾動生成新解，并按一定規(guī)則接受新解。

打個比方：

有一只兔子在山上，要去山腳下，但它喝醉了。于是它就胡亂瞎蹦跶，有可能直接蹦跶到山腳下，有可能蹦跶到更高的另一座山，也可能跳到某個山谷里。等它醒酒后，它就慢慢地往低處走。這就是模擬退火。

為更好理解模擬退火算法的具體步驟，我們來舉個栗子。

假設(shè)初始溫度為1000℃，溫度衰減系數(shù)α = 0.98，熱平衡條件為溫度小于T℃。

模擬退火算法本質(zhì)是雙層循環(huán)，外層循環(huán)（上圖左側(cè)彩色模塊）控制溫度由高向低變化，溫度計(jì)算公式  ，  為取值在[0, 1]上的溫度衰減系數(shù)，如0.95；內(nèi)層循環(huán)（上圖右側(cè)黑色模塊）中，溫度固定，對舊解添加隨機(jī)擾動得到新解，并按一定規(guī)則接受新解。內(nèi)層循環(huán)的迭代次數(shù)稱為馬爾科夫鏈長度，如上圖中的馬爾科夫鏈的長度為1000.

二、模擬退火算法有什么優(yōu)點(diǎn)？

模擬退火算法的優(yōu)點(diǎn)在于：不管函數(shù)形式多復(fù)雜，模擬退火算法更有可能找到全局最優(yōu)解。

舉個栗子：尋找目標(biāo)函數(shù)f = x + 10 sin(3x) + cos(x) 在[0, 9]范圍內(nèi)的最小值。

從函數(shù)圖像可以看到，該函數(shù)在[0, 9]范圍內(nèi)有多個“坑”，也就是局部最小值，全局最小值位于[1, 2]范圍上的“坑”內(nèi)。如果用梯度下降法來求解全局最小值，若學(xué)習(xí)率設(shè)置得不合理很容易掉進(jìn)某個坑內(nèi)出不來，比如這樣↓

而模擬退火算法相對來說不會那么容易陷入局部最優(yōu)解。

我們把模擬退火算法求出的解看成是一個紅色的小球，可以看到，隨著溫度的下降，這個小球一直反復(fù)橫跳；直到溫度較低時，這個小球才在最小值附近穩(wěn)定下來。

那模擬退火算法是怎么跳出局部最優(yōu)值的呢？

關(guān)鍵點(diǎn)在于模擬退火算法對較差的舊解的處理上。

在任一溫度時，對初始解添加隨機(jī)擾動產(chǎn)生新解，若新解的目標(biāo)函數(shù)值優(yōu)于舊解，則接受新解；若新解差于舊解，則按一定概率接受舊解，從而有一定概率跳出局部最優(yōu)解，找到全局最優(yōu)解。

而這個“一定概率”也不是瞎取的，這個概率的計(jì)算公式為：  。其中，  ，  為新解的目標(biāo)函數(shù)值，為舊解的目標(biāo)函數(shù)值，T為當(dāng)前的溫度，k為玻爾茲曼常數(shù)。溫度越高，算法接受新解的概率越高。這個根據(jù)一定概率選擇是否接受差解的方法叫做Metropolos準(zhǔn)則。

三、模擬退火算法有什么缺陷？

模擬算法雖好，但也存在一些缺點(diǎn)。

1. 初始溫度和馬爾科夫鏈長度的設(shè)置問題

從理論上來說，初始溫度越高，且馬爾科夫鏈越長，算法搜索越充分，得到全局最優(yōu)解的可能性越大，但這也意味著需要耗費(fèi)更多的計(jì)算時間。接下來我們采取控制變量法做個實(shí)驗(yàn)來驗(yàn)證一下這個結(jié)論。

從圖中可以看到，隨著迭代次數(shù)的增加，溫度逐漸降低，馬爾科夫鏈長度1000的模擬退火算法在迭代100多次之后搜索到了全局最小值，而馬爾科夫鏈長度100的模擬退火算法則無法搜索到全劇最小，困在局部最小的坑里出不去了。這說明，馬爾科夫鏈長度越長，模擬退火算法搜索越充分，更容易搜索到全局最優(yōu)解，但相應(yīng)的搜索時間會更長。

再來看一下初始溫度T0對結(jié)果的影響。

可以看到，初始溫度100和初始溫度1000的兩個模擬退火算法都能搜索到全局最小值，初始溫度1000的搜索到全劇最小的速度稍快一點(diǎn)。

2. 退火速度問題

溫度衰減系數(shù)越小，溫度下降越快，對應(yīng)的迭代次數(shù)也就越少，算法搜索的次數(shù)也就越少，因此導(dǎo)致了上圖中溫度衰減系數(shù)0.9的模擬退火算法沒有搜索到最優(yōu)解。

另外，越到后期，溫度衰減得越慢，但是我們可以將溫度衰減系數(shù)設(shè)置為動態(tài)的，即隨著溫度下降，溫度衰減系數(shù)也隨之變小，如  ，以加快后期溫度下降，加速算法收斂。

總結(jié)一下，關(guān)鍵參數(shù)是馬爾科夫鏈長度和溫度衰減系數(shù)，馬爾科夫鏈越長，且溫度衰減系數(shù)越接近于1，模擬退火算法搜索越充分，越有可能找到全局最優(yōu)解，但相應(yīng)地也會增加算法搜索時間。當(dāng)解空間的維度較高時，模擬退火算法要想搜索到全局最優(yōu)解需要耗費(fèi)大量時間，這是模擬退火算法的一個主要缺點(diǎn)。

四、應(yīng)用推廣

模擬退火算法在優(yōu)化類問題的應(yīng)用非常廣泛，可以對上文的代碼進(jìn)行修改以應(yīng)用到其他問題。但是具體問題具體分析，除了必要的數(shù)據(jù)更改之外，特別要注意以下3點(diǎn)：

例如，將問題升級到2維，尋找目標(biāo)函數(shù)f = sin(x) + cos(y) 在[0, 6]×[0, 6]范圍內(nèi)的最小值。

可以看到，隨著迭代次數(shù)的增加，模擬退火算法慢慢逼近目標(biāo)函數(shù)的全局最小值，并最終找到了目標(biāo)函數(shù)在[0, 6]×[0, 6]范圍內(nèi)的全局最小值-2，最小值點(diǎn)位于（4.7162， 3.1358）。