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

機(jī)器學(xué)習(xí)基礎(chǔ)（四十五）—— 模擬退火（Simulated Annealing）

機(jī)器學(xué)習(xí)（123） 

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

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

退火算法以一個(gè)問(wèn)題的隨機(jī)解開始。它用一個(gè)變量來(lái)表示溫度，這一溫度開始時(shí)非常高，而后逐漸變低：

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

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

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