學(xué)號(hào)：17020150083

姓名:許學(xué)同

原文鏈接：https://blog.csdn.net/weixin_40562999/article/details/80853354

【嵌牛導(dǎo)讀】著名的模擬退火算法子姜，它是一種基于蒙特卡洛思想設(shè)計(jì)的近似求解最優(yōu)化問(wèn)題的方法庶骄。

【嵌牛鼻子】模擬退火算法

【嵌牛正文】

一點(diǎn)歷史——如果你不感興趣，可以跳過(guò)

? ? ?美國(guó)物理學(xué)家 N.Metropolis 和同仁在1953年發(fā)表研究復(fù)雜系統(tǒng)疏魏、計(jì)算其中能量分布的文章蛉艾，他們使用蒙特卡羅模擬法計(jì)算多分子系統(tǒng)中分子的能量分布钳踊。這相當(dāng)于是本文所探討之問(wèn)題的開(kāi)始，事實(shí)上勿侯，模擬退火中常常被提到的一個(gè)名詞就是Metropolis準(zhǔn)則拓瞪，后面我們還會(huì)介紹。

美國(guó)IBM公司物理學(xué)家 S.Kirkpatrick助琐、C. D. Gelatt 和 M. P. Vecchi 于1983年在《Science》上發(fā)表了一篇頗具影響力的文章：《以模擬退火法進(jìn)行最優(yōu)化（Optimization by Simulated Annealing）》祭埂。他們借用了Metropolis等人的方法探討一種旋轉(zhuǎn)玻璃態(tài)系統(tǒng)（spin glass system）時(shí)，發(fā)覺(jué)其物理系統(tǒng)的能量和一些組合最優(yōu)（combinatorial optimization）問(wèn)題（著名的旅行推銷員問(wèn)題TSP即是一個(gè)代表例子）的成本函數(shù)相當(dāng)類似：尋求最低成本即似尋求最低能量弓柱。由此，他們發(fā)展出以?Metropolis??方法為本的一套算法侧但，并用其來(lái)解決組合問(wèn)題等的尋求最優(yōu)解矢空。

幾乎同時(shí)，歐洲物理學(xué)家 V.Carny 也發(fā)表了幾乎相同的成果禀横，但兩者是各自獨(dú)立發(fā)現(xiàn)的屁药；只是Carny“運(yùn)氣不佳”，當(dāng)時(shí)沒(méi)什么人注意到他的大作柏锄；或許可以說(shuō)酿箭，《Science》雜志行銷全球，“曝光度”很高趾娃，素負(fù)盛名缭嫡，而Carny卻在另外一本發(fā)行量很小的專門(mén)學(xué)術(shù)期刊《J.Opt.Theory Appl.》發(fā)表其成果因而并未引起應(yīng)有的關(guān)注。

Kirkpatrick等人受到Metropolis等人用蒙特卡羅模擬的啟發(fā)而發(fā)明了“模擬退火”這個(gè)名詞抬闷，因?yàn)樗臀矬w退火過(guò)程相類似妇蛀。尋找問(wèn)題的最優(yōu)解（最值）即類似尋找系統(tǒng)的最低能量。因此系統(tǒng)降溫時(shí)笤成，能量也逐漸下降评架，而同樣意義地，問(wèn)題的解也“下降”到最值炕泳。

一纵诞、什么是退火——物理上的由來(lái)

在熱力學(xué)上，退火（annealing）現(xiàn)象指物體逐漸降溫的物理現(xiàn)象培遵，溫度愈低浙芙，物體的能量狀態(tài)會(huì)低登刺；夠低后，液體開(kāi)始冷凝與結(jié)晶茁裙，在結(jié)晶狀態(tài)時(shí)塘砸，系統(tǒng)的能量狀態(tài)最低。大自然在緩慢降溫（亦即晤锥，退火）時(shí)掉蔬，可“找到”最低能量狀態(tài)：結(jié)晶。但是矾瘾，如果過(guò)程過(guò)急過(guò)快女轿，快速降溫（亦稱「淬煉」，quenching）時(shí)壕翩，會(huì)導(dǎo)致不是最低能態(tài)的非晶形蛉迹。

如下圖所示，首先（左圖）物體處于非晶體狀態(tài)放妈。我們將固體加溫至充分高（中圖）北救，再讓其徐徐冷卻，也就退火（右圖）芜抒。加溫時(shí)珍策，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大宅倒，而徐徐冷卻時(shí)粒子漸趨有序攘宙，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)拐迁，內(nèi)能減為最胁渑（此時(shí)物體以晶體形態(tài)呈現(xiàn)）。

似乎线召，大自然知道慢工出細(xì)活：緩緩降溫铺韧，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安頓位置缓淹，則逐漸地祟蚀，到最后可得到最低能態(tài)，系統(tǒng)最安穩(wěn)割卖。

二前酿、模擬退火（Simulate Anneal）

如果你對(duì)退火的物理意義還是暈暈的，沒(méi)關(guān)系我們還有更為簡(jiǎn)單的理解方式鹏溯。想象一下如果我們現(xiàn)在有下面這樣一個(gè)函數(shù)罢维，現(xiàn)在想求函數(shù)的（全局）最優(yōu)解。如果采用Greedy策略，那么從A點(diǎn)開(kāi)始試探肺孵，如果函數(shù)值繼續(xù)減少匀借，那么試探過(guò)程就會(huì)繼續(xù)。而當(dāng)?shù)竭_(dá)點(diǎn)B時(shí)平窘，顯然我們的探求過(guò)程就結(jié)束了（因?yàn)闊o(wú)論朝哪個(gè)方向努力吓肋，結(jié)果只會(huì)越來(lái)越大）。最終我們只能找打一個(gè)局部最后解B瑰艘。

模擬退火其實(shí)也是一種Greedy算法是鬼，但是它的搜索過(guò)程引入了隨機(jī)因素。模擬退火算法以一定的概率來(lái)接受一個(gè)比當(dāng)前解要差的解紫新，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解均蜜，達(dá)到全局的最優(yōu)解。以上圖為例芒率，模擬退火算法在搜索到局部最優(yōu)解B后囤耳，會(huì)以一定的概率接受向右繼續(xù)移動(dòng)。也許經(jīng)過(guò)幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)B 和C之間的峰點(diǎn)偶芍，于是就跳出了局部最小值B充择。

根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為exp(-ΔE/(kT))匪蟀，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變數(shù),k為Boltzmann常數(shù)萄窜。Metropolis準(zhǔn)則常表示為

Metropolis準(zhǔn)則表明查刻，在溫度為T(mén)時(shí)凤类，出現(xiàn)能量差為dE的降溫的概率為P(dE)，表示為：P(dE) = exp( dE/(kT) )佃延。其中k是一個(gè)常數(shù)夷磕，exp表示自然指數(shù)，且dE<0坐桩。所以P和T正相關(guān)。這條公式就表示：溫度越高绵跷，出現(xiàn)一次能量差為dE的降溫的概率就越大成福；溫度越低荆残，則出現(xiàn)降溫的概率就越小奴艾。又由于dE總是小于0（因?yàn)橥嘶鸬倪^(guò)程是溫度逐漸下降的過(guò)程）内斯，因此dE/kT < 0 ，所以P(dE)的函數(shù)取值范圍是(0,1) 嘿期。隨著溫度T的降低，P(dE)會(huì)逐漸降低备徐。

我們將一次向較差解的移動(dòng)看做一次溫度跳變過(guò)程，我們以概率P(dE)來(lái)接受這樣的移動(dòng)蜜猾。也就是說(shuō)秀菱，在用固體退火模擬組合優(yōu)化問(wèn)題蹭睡，將內(nèi)能E模擬為目標(biāo)函數(shù)值?f，溫度T演化成控制參數(shù)?t肩豁，即得到解組合優(yōu)化問(wèn)題的模擬退火演算法：由初始解?i?和控制參數(shù)初值?t?開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或丟棄”的迭代清钥，并逐步衰減?t?值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解祟昭，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程缕坎。退火過(guò)程由冷卻進(jìn)度表(Cooling Schedule)控制篡悟，包括控制參數(shù)的初值?t?及其衰減因子Δt?、每個(gè)?t?值時(shí)的迭代次數(shù)L和停止條件S搬葬。

總結(jié)起來(lái)就是：

若f( Y(i+1) ) <=?f( Y(i) )? (即移動(dòng)后得到更優(yōu)解)，則總是接受該移動(dòng)急凰；

若f( Y(i+1) ) >?f( Y(i) )? (即移動(dòng)后的解比當(dāng)前解要差)，則以一定的概率接受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）相當(dāng)于上圖中码倦，從B移向BC之間的小波峰時(shí)，每次右移（即接受一個(gè)更糟糕值）的概率在逐漸降低袁稽。如果這個(gè)坡特別長(zhǎng)，那么很有可能最終我們并不會(huì)翻過(guò)這個(gè)坡推汽。如果它不太長(zhǎng)，這很有可能會(huì)翻過(guò)它歧沪，這取決于衰減?t?值的設(shè)定。

關(guān)于普通Greedy算法與模擬退火诊胞，有一個(gè)有趣的比喻：

普通Greedy算法：兔子朝著比現(xiàn)在低的地方跳去。它找到了不遠(yuǎn)處的最低的山谷迈着。但是這座山谷不一定最低的。這就是普通Greedy算法邪码，它不能保證局部最優(yōu)值就是全局最優(yōu)值。

模擬退火：兔子喝醉了闭专。它隨機(jī)地跳了很長(zhǎng)時(shí)間。這期間影钉，它可能走向低處，也可能踏入平地斧拍。但是杖小，它漸漸清醒了并朝最低的方向跳去。這就是模擬退火予权。