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

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

機器學習（123） 

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

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

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

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

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

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