http://blog.csdn.net/lanchunhui/article/details/51112227

機器學習基礎（四十五）—— 模擬退火（Simulated Annealing）

機器學習（123） 

版權聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

模擬退火算法是受物理學領域啟發(fā)而提出的一種優(yōu)化算法。所謂的退火是指將合金加熱后再慢慢冷卻的過程。大量的原子因為受到激發(fā)而向周圍跳躍，然后又逐漸穩(wěn)定到一個低能階的狀態(tài)，所以這些原子能夠找到一個低能階的配置（configuration）。

退火算法以一個問題的隨機解開始。它用一個變量來表示溫度，這一溫度開始時非常高，而后逐漸變低：

退火算法的每一次迭代期間，算法會首先隨機地選擇某個數(shù)字，然后朝某個方向變化。算法最為關鍵的部分在于，如果新的變化帶來的新的成本更低，則新的題解就會成為當前題解，這個爬山算法類似。不過如果成本值更高的話，則新的題解仍將可能成為當前題解（這是不同于爬山算法的地方）。這也是避免出現(xiàn)局部最小值的一種改進。

某些情況下，我們能夠得到一個更優(yōu)的解之前轉(zhuǎn)向一個更差的解是很有必要的。模擬算法之所以管用，不僅在于它總是會接受一個更優(yōu)的解，而且在退貨的開始階段會（以一定概率）接受表現(xiàn)較差的解。隨著退火過程（溫度減少）的不斷進行，算法越來越不可能接受較差的解。知道最后節(jié)點，它將只會接受更優(yōu)的解。更高成本的題解，其被接受的概率如下： 

T 溫度（表示接受較差解的意愿）開始非常高，指數(shù)部分接近于0，所以概率幾乎為1.隨著溫度的遞減，高成本和低成本值之間的差異越來越重要——差異越大，概率越低。因此此算法只傾向于稍差的解而不會是非常差的解。