智能優(yōu)化算法--模擬退火算法

1、智能優(yōu)化算法與應(yīng)用湖南大學(xué)電氣學(xué)院自動(dòng)化系3模擬退火算法及其應(yīng)用Simulated Annealing，SA5尼古拉梅特羅波利斯尼古拉梅特羅波利斯(NicholasConstantineMetropolis)1915年6月11日生于美國(guó)芝加哥。1936年他在芝加哥大學(xué)取得學(xué)士學(xué)位，1941年取得實(shí)驗(yàn)物理學(xué)博士學(xué)位，之后留校在冶金學(xué)實(shí)驗(yàn)室(MetallurgicalLaboratory)工作，其間他在1942年曾參與哥倫比亞大學(xué)的原子彈計(jì)劃。1943年他進(jìn)入洛斯阿拉莫斯實(shí)驗(yàn)室，參加著名的“曼哈頓計(jì)劃”，與“原子彈之父”費(fèi)米(EnricoFermi)和泰勒(EdwardTeller)一起工作，其任

2、務(wù)是為高溫、高壓、高密度下的物質(zhì)建立狀態(tài)方程，從此他的研究工作從物理學(xué)轉(zhuǎn)入了數(shù)學(xué)領(lǐng)域。在曼哈頓計(jì)劃中他是課題組組長(zhǎng)。67組合優(yōu)化，作為應(yīng)用數(shù)學(xué)中最年輕而又至關(guān)重要的領(lǐng)域之一，整合了組合數(shù)學(xué)、線(xiàn)性規(guī)劃以及算法理論的方法和技巧。由于它在解決從遠(yuǎn)程通訊到超大規(guī)模集成電路、從產(chǎn)品運(yùn)銷(xiāo)到航班機(jī)組排班等領(lǐng)域內(nèi)困難問(wèn)題方面的成功，這一領(lǐng)域在過(guò)去的十年里取得了巨大的、超乎尋常的發(fā)展。8910在FBI，人臉識(shí)別終于要真正發(fā)揮在電影中一樣的作用了。作為國(guó)家的指紋數(shù)據(jù)庫(kù)的更新的一部分，美國(guó)聯(lián)邦調(diào)查局已經(jīng)開(kāi)始推出了面部識(shí)別，識(shí)別罪犯，反恐。而這些高富帥們的手筆也不是一般的大：$1billion。1112爬山算法爬山算

3、法 ( Hill Climbing )介紹模擬退火前，先介紹爬山算法。爬山算法是一種簡(jiǎn)單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。爬山算法實(shí)現(xiàn)很簡(jiǎn)單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1所示：假設(shè)C點(diǎn)為當(dāng)前解，爬山算法搜索到A點(diǎn)這個(gè)局部最優(yōu)解就會(huì)停止搜索，因?yàn)樵贏點(diǎn)無(wú)論向那個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解。1314模擬退火模擬退火(SA, Simulated Annealing)思想思想爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是

4、其搜索過(guò)程引入了隨機(jī)因素。模擬退火算法以一定的概以一定的概率率接受一個(gè)比當(dāng)前解要差的解，因此有可能有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會(huì)以一定的概率以一定的概率接受到E的移動(dòng)。也許經(jīng)過(guò)幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)D點(diǎn)，于是就跳出了局部最大值A(chǔ)。15模擬退火算法描述：若J(Y(i+1)=J(Y(i)(即移動(dòng)后得到更優(yōu)解)，則總是接受該移動(dòng)若J(Y(i+1)J(Y(i)(即移動(dòng)后的解比當(dāng)前解要差)，則以一定的概率接受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移以一定的概率接受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）逐漸降低

5、（逐漸降低才能趨向穩(wěn)定）這里的“一定的概率”的計(jì)算參考了金屬冶煉的退火過(guò)程，這也是模擬退火算法名稱(chēng)的由來(lái)。16作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問(wèn)題(TravellingSalesmanProblem，簡(jiǎn)記為T(mén)SP)：設(shè)有n個(gè)城市，用數(shù)碼1,n代表。城市i和城市j之間的距離為d(i，j)i,j=1,nTSP問(wèn)題是要找遍訪(fǎng)每個(gè)域市恰好一次的一條回路，且其路徑總長(zhǎng)度為最短。旅行商旅行商問(wèn)題屬于所謂的NP完全問(wèn)題，精確的解決TSP只能通過(guò)窮舉所有的路徑組合，其時(shí)間復(fù)雜度是O(N!)。使用模擬退火用模擬退火算法可以比較快的求出TSP的一條近似最優(yōu)路徑。17P問(wèn)題：可以在以多項(xiàng)式表達(dá)的時(shí)間內(nèi)求出確切解的問(wèn)

6、題，也就是說(shuō)它的計(jì)算復(fù)雜度是一個(gè)多項(xiàng)式。我們通常用的O(n),O(logn),O(n2)等等類(lèi)似的都是這類(lèi)問(wèn)題。18什么是非確定性問(wèn)題呢？有些計(jì)算問(wèn)題是確定性的，比如加減乘除之類(lèi)，你只要按照公式推導(dǎo)，按部就班一步步來(lái)，就可以得到結(jié)果。但是，有些問(wèn)題是無(wú)法按部就班直接地計(jì)算出來(lái)。比如，找大質(zhì)數(shù)的問(wèn)題。有沒(méi)有一個(gè)公式，你一套公式，就可以一步步推算出來(lái)，下一個(gè)質(zhì)數(shù)應(yīng)該是多少呢？這樣的公式是沒(méi)有的。19NP問(wèn)題：英文是non-deterministicpolynomial,是多項(xiàng)式時(shí)間可以驗(yàn)證的問(wèn)題。最初是在非確定圖靈機(jī)上，如果一個(gè)問(wèn)題存在一個(gè)解，那么就先猜它，一定可以在多項(xiàng)式時(shí)間內(nèi)猜到這個(gè)解。（關(guān)鍵

7、是就是不判定這個(gè)問(wèn)題到底有沒(méi)有解）p？=NP目前還沒(méi)有被證實(shí)。也就是還不知道P和NP的關(guān)系，但是可以確定的是P屬于NP。2021歐洲地中海之濱、法國(guó)的東南方，有一個(gè)世界上版圖最小的國(guó)家摩納哥公國(guó)，世人稱(chēng)之為“賭博之國(guó)”、“袖珍之國(guó)”、“郵票小國(guó)”。22蒙特卡洛模擬為方便的解決困難而復(fù)雜的實(shí)際問(wèn)題開(kāi)啟了一扇大門(mén)。估計(jì)蒙特卡羅模擬最著名的早期使用是諾貝爾獎(jiǎng)物理學(xué)家EnricoFermi（原子彈之父）在1930年的應(yīng)用，那時(shí)他用一種隨機(jī)方法來(lái)計(jì)算剛發(fā)現(xiàn)的中子的性質(zhì)。23專(zhuān)著專(zhuān)著薛定諤方薛定諤方程程統(tǒng)計(jì)物理學(xué)統(tǒng)計(jì)物理學(xué)典論典論24蒙特卡羅模擬是曼哈頓計(jì)劃所用到的模擬的核心部分，在20世紀(jì)50年代蒙特卡

8、羅模擬就用在LosAlamos國(guó)家實(shí)驗(yàn)室發(fā)展氫彈的早期工作中，并流行于物理學(xué)和運(yùn)籌學(xué)研究領(lǐng)域。蘭德公司和美國(guó)空軍是這個(gè)時(shí)期主要的兩個(gè)負(fù)責(zé)資助和傳播蒙特卡羅方法的組織，今天蒙特卡羅模擬也被廣泛應(yīng)用于不同的領(lǐng)域，包括工程，物理學(xué)，研發(fā)，商業(yè)和金融。25中文名稱(chēng)：退火英文名稱(chēng)：annealing將金屬加熱到一定溫度，保持足夠時(shí)間，然后以適宜速度冷卻(通常是緩慢冷卻，有時(shí)是控制冷卻)的一種金屬熱處理工藝。12627(1)降低硬度，改善切削加工性.(2)消除殘余應(yīng)力，穩(wěn)定尺寸，減少變形與裂紋傾向；(3)細(xì)化晶粒，調(diào)整組織，消除組織缺陷。(4)均勻材料組織和成分，改善材料性能或?yàn)橐院鬅崽幚碜鼋M織準(zhǔn)備。在生

9、產(chǎn)中，退火工藝應(yīng)用很廣泛。根據(jù)工件要求退火的目的不同，退火的工藝規(guī)范有多種，常用的有完全退火、球化退火、和去應(yīng)力退火等。28物質(zhì)自動(dòng)趨向的最低能態(tài)與函數(shù)最小值之間物質(zhì)自動(dòng)趨向的最低能態(tài)與函數(shù)最小值之間有相有相似性似性！函數(shù)最小值，就像最低能態(tài)？降溫圖像離散函數(shù)圖像相似性?最小值最低能態(tài)退火俗稱(chēng)退火俗稱(chēng)先把固體加熱至足夠高溫先把固體加熱至足夠高溫，使固體中所有粒子處于，使固體中所有粒子處于無(wú)序的狀態(tài)（最高的熵值無(wú)序的狀態(tài)（最高的熵值），然后將溫度緩慢下降），然后將溫度緩慢下降，粒子漸漸有序（熵值下，粒子漸漸有序（熵值下降），這樣只要溫度上升降），這樣只要溫度上升得足夠高，冷卻過(guò)程足夠得足夠高，冷

10、卻過(guò)程足夠慢，則所有粒子最終會(huì)處慢，則所有粒子最終會(huì)處于最低能態(tài)（最低的熵值于最低能態(tài)（最低的熵值）。）。t07a0.187H5T t ( )Ht0H()eat t0()0102030051015T t ( )t最低能態(tài)時(shí)間溫度EKTe34353637SA 算法的計(jì)算過(guò)程可視為重復(fù)遞減控制參數(shù)值（溫度）并算法的計(jì)算過(guò)程可視為重復(fù)遞減控制參數(shù)值（溫度）并進(jìn)行進(jìn)行Metropolis 算法的迭代過(guò)程。一次算法的迭代過(guò)程。一次Metropolis 算法是算法是指，對(duì)于控制參數(shù)指，對(duì)于控制參數(shù)t的每一取值，算法在的每一取值，算法在Markov 鏈長(zhǎng)度內(nèi)鏈長(zhǎng)度內(nèi)持續(xù)進(jìn)行持續(xù)進(jìn)行“產(chǎn)生新解產(chǎn)生新解判斷判斷

11、接受接受/舍棄舍棄”的迭代過(guò)程，對(duì)的迭代過(guò)程，對(duì)應(yīng)著固體在某一恒定溫度下趨于熱平衡的過(guò)程。算法終止應(yīng)著固體在某一恒定溫度下趨于熱平衡的過(guò)程。算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。一類(lèi)隨機(jī)過(guò)程。它的原始模型馬爾可夫鏈，由俄國(guó)數(shù)學(xué)家A.A.馬爾可夫于1907年提出。該過(guò)程具有如下特性：在已知目前狀態(tài)（現(xiàn)在）的條件下，它未來(lái)的演變（將來(lái)）不依賴(lài)于它以往的演變(過(guò)去)。例如森林中動(dòng)物頭數(shù)的變化構(gòu)成馬爾可夫過(guò)程。在現(xiàn)實(shí)世界中，有很多過(guò)程都是馬爾可夫過(guò)程，如液體中微粒所作的

12、布朗運(yùn)動(dòng)、傳染病受感染的人數(shù)、車(chē)站的候車(chē)人數(shù)等，都可視為馬爾可夫過(guò)程。關(guān)于該過(guò)程的研究，1931年A.H.柯?tīng)柲缏宸蛟诟怕收摰慕馕龇椒ㄒ晃闹惺紫葘⑽⒎址匠痰确治龅姆椒ㄓ糜谶@類(lèi)過(guò)程，奠定了馬爾可夫過(guò)程的理論基礎(chǔ)。394041 sin 102.01,2fxxxx 4243 ?exp, kikiikikkikiCPTPETECTPiTEinS如何確定則有如下關(guān)系：的概率為：這時(shí)處于狀態(tài)平衡，下，經(jīng)一段時(shí)間達(dá)到熱在溫度的能量為，狀態(tài)有限個(gè)，離散的個(gè)狀態(tài)中有設(shè)熱力學(xué)系統(tǒng)44iknikiikkikikkiinikikikiEETTPETETEiTPTTPETETETP ,1expexp11下的平均能量：

13、最小的那一個(gè)代表可見(jiàn)：45kTkiTPkT0kiTEnTPki1kiTP46kiTP0kTkiTEiEjEkjTPiEjE47kT367. 0406. 0367. 0406. 010010010090kkkkkjkiCCueCeCTPTP48200001072.310194.84440kkkjkiCCTPTPkinikiTPTP1kT0kT4950515253221( )afa，- 21( )exp22f，- 1 , ( )0baa bfelse545556575859606162 內(nèi)循環(huán)熱平衡的達(dá)到外循環(huán)算法的特點(diǎn)冷卻控制搜索：隨機(jī)的鄰域移動(dòng)移動(dòng)同要素：狀態(tài)表達(dá)和鄰域代表狀態(tài)是離散有限狀態(tài)空

14、間， , , minSATSiSSiif63Si0TfT0, 0TTkk 的鄰域表示iiNiNj, ifjff0T0kiTE64 kTnjiTfUk, exp, 1 , 0則令若, 0jif令kTkT651 kkfkTT kTkTTTTrrTTkkkk112.99. 095. 0 . 1優(yōu)點(diǎn)：簡(jiǎn)單易行。其中較好的方法660,0TTkkSikTn0n ifjff iNj 1 nn1 kkkT0f1 , 0expUTfkji kTnn fkTT 6715, 5,18, 84321PPPP41miniiF68 43214321321211PPPPFPPPFPPFPF 92181152835412344321PPPPF691000T60fT3020kkkTnTTTT 118if704.是隨機(jī)產(chǎn)生的是隨機(jī)產(chǎn)生的100kT ji