模擬退火算法

關(guān)于模擬退火算法第1頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三一、模擬退火算法的基本思想啟發(fā)注意到一個(gè)自然規(guī)則：物質(zhì)總是趨于最低的能態(tài)。水總是向低處流。電子總是向最低能級(jí)的軌道排布。最低能態(tài)是最穩(wěn)定的狀態(tài)。物質(zhì)會(huì)”自動(dòng)”地趨向的最低能態(tài)。第2頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的設(shè)計(jì)與原理

猜想物質(zhì)自動(dòng)趨向的最低能態(tài)與函數(shù)最小值之間有相似性?。?！我們能不能設(shè)計(jì)一種算法求函數(shù)最小值，就像物質(zhì)”自動(dòng)”地趨向最低能態(tài)？降溫圖像離散函數(shù)圖像相似性?最小值最低能態(tài)第3頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的設(shè)計(jì)與原理

物理模型——固體退火退火俗稱固體降溫先把固體加熱至足夠高溫，使固體中所有粒子處于無(wú)序的狀態(tài)（最高的熵值），然后將溫度緩慢下降，粒子漸漸有序（熵值下降），這樣只要溫度上升得足夠高，冷卻過程足夠慢，則所有粒子最終會(huì)處于最低能態(tài)（最低的熵值）。最低能態(tài)時(shí)間溫度第4頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的設(shè)計(jì)與原理類比根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于熱平衡的概率為

其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)?？梢栽O(shè)計(jì)算法：將系統(tǒng)熵值類比為函數(shù)值F，來(lái)模擬這個(gè)退火過程。第5頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。第6頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的設(shè)計(jì)與原理提出模擬退火算法(SA)就是這樣一個(gè)將退火過程中系統(tǒng)熵值類比為目標(biāo)函數(shù)值F，來(lái)模擬這個(gè)退火系統(tǒng)的算法。第7頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的設(shè)計(jì)與原理

數(shù)學(xué)模型——馬爾可夫過程模擬退火算法在概率理論上有一個(gè)很好的數(shù)學(xué)模型的來(lái)解釋：馬爾可夫(Markov)過程。第8頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三馬爾可夫過程及馬爾可夫鏈簡(jiǎn)介馬爾可夫過程是一個(gè)隨機(jī)過程，它具備這樣的性質(zhì)，即可知tm時(shí)刻過程處在狀態(tài)的條件下，在時(shí)刻tm以后過程將要到達(dá)的狀態(tài)的情況與該時(shí)刻以前過程所處的狀態(tài)無(wú)關(guān)。這個(gè)性質(zhì)也稱為過程的無(wú)后效性或過程的馬爾可夫性。對(duì)一個(gè)狀態(tài)空間(I)離散、參數(shù)為非負(fù)整數(shù)的隨機(jī)過程，若它滿足條件: 這樣的隨機(jī)過程稱為馬爾可夫鏈。馬爾可夫鏈在t時(shí)刻的一步條件轉(zhuǎn)移概率也稱作t時(shí)刻的狀態(tài)轉(zhuǎn)移(i→j)

概率。顯然有：第9頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三二、模擬退火算法的實(shí)現(xiàn)

SA算法在Markov鏈長(zhǎng)度內(nèi)持續(xù)進(jìn)行“產(chǎn)生新解—判斷—接受/舍棄”的迭代過程，對(duì)應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。第10頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的實(shí)現(xiàn)思想SA算法的計(jì)算過程可視為重復(fù)遞減控制參數(shù)值（溫度）并進(jìn)行Metropolis算法的迭代過程。一次Metropolis算法是指，對(duì)于控制參數(shù)t的每一取值，算法在Markov鏈長(zhǎng)度內(nèi)持續(xù)進(jìn)行“產(chǎn)生新解—判斷—接受/舍棄”的迭代過程，對(duì)應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。第11頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三相似性比較

優(yōu)化問題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過程Metropolis抽樣過程等溫過程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量組合優(yōu)化與物理退火的相似性第12頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的實(shí)現(xiàn)

算法描述SimulatedAnnealing(SA)Algorithm:1初始化：系統(tǒng)初溫T，初始狀態(tài)S0，馬爾可夫鏈長(zhǎng)L，終止條件AIM2while(true) 2.1對(duì)于k=1..L,執(zhí)行2.1.1到2.1.4 2.1.1從當(dāng)前解S,產(chǎn)生新解SN

，他們之間的差值為D. 2.1.2若(D<0或滿足概率exp(-D/T)),則S:=SN. 2.1.3若(當(dāng)前解S<當(dāng)前最優(yōu)解SB),則SB:=S. 2.1.4if(T趨于0或連續(xù)AIM次迭代物最優(yōu)值),則可近似認(rèn)為SB為最優(yōu)，轉(zhuǎn)3. 2.2降溫 2.3S=SB3輸出SB第13頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的實(shí)現(xiàn)

實(shí)現(xiàn)技術(shù)冷卻進(jìn)度表、鄰域結(jié)構(gòu)和新解產(chǎn)生器、接受準(zhǔn)則和隨機(jī)數(shù)產(chǎn)生器一起構(gòu)成算法的三大支柱。從算法結(jié)構(gòu)可知，新狀態(tài)產(chǎn)生函數(shù)、新狀態(tài)接受函數(shù)、退溫函數(shù)、退火結(jié)束準(zhǔn)則以及初始溫度是直接影響算法優(yōu)化結(jié)果的主要環(huán)節(jié)。第14頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的實(shí)現(xiàn)

冷卻進(jìn)度表冷卻進(jìn)度表包含：初始溫度，退溫速率，退火結(jié)束準(zhǔn)則，Markov鏈長(zhǎng)。它直接決定了算法的效率，需要大量試驗(yàn)才能得出其最佳的組合。第15頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的優(yōu)化

回火技術(shù)如圖所示，若粒子開始處于D狀態(tài)，若讓能量逐漸減小，則粒子最終到達(dá)的是A點(diǎn)(局部最低點(diǎn))而不是B(全局最低點(diǎn))點(diǎn)，這是我們所不希望的。解決的辦法是對(duì)系統(tǒng)經(jīng)常地”搖動(dòng)”一下，就很可能把粒子從D點(diǎn)越過C點(diǎn)搖到B點(diǎn)，而把它搖到A點(diǎn)的可能性減小。這就是回火技術(shù)：降溫后以一定概率升溫，引入產(chǎn)生函數(shù)擾動(dòng)因子，來(lái)控制搜尋全局最優(yōu)值的范圍。ABCD第16頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的應(yīng)用前景

NP問題與計(jì)算復(fù)雜性理論計(jì)算復(fù)雜性理論通俗的解釋：多項(xiàng)式時(shí)間:運(yùn)行時(shí)間最多是輸入量的多項(xiàng)式函數(shù)。P類問題是可被“在多項(xiàng)式時(shí)間運(yùn)行”一個(gè)算法解決的問題，換句話說(shuō)這種解決是好的，快的。NP完全類問題即是目前沒有一個(gè)“可用多項(xiàng)式時(shí)間解決”的問題，這種問題是稱為”難的”。如TSP問題，若有144個(gè)城市，求最優(yōu)解，則要運(yùn)行144!次，這是要幾萬(wàn)年的時(shí)間。該類問題排位“新千年急待解決的7大數(shù)學(xué)問題”之首！NP完全問題都是相互多項(xiàng)式等價(jià)的，就是說(shuō)，解決了其中一個(gè)問題，所有的NP完全問題都被“好的”解決。第17頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三模擬退火算法的應(yīng)用前景

算法特性優(yōu)點(diǎn)可并行性擴(kuò)展性和通用性

它可以高效的解決幾乎所有的組合優(yōu)化問題。高效率，高性價(jià)比逼近速度快，可極快的求得很好的近似值SA算法比傳統(tǒng)算法速度快的多了，解也以1的概率趨于最優(yōu)解。在解的質(zhì)量與時(shí)間的比上效果良好。

傳統(tǒng)算法要運(yùn)行幾年的情況，SA只需幾秒。具有全局優(yōu)化特性

第18頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

TSPBenchmark問題

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450第19頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三算法流程

第20頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三初始溫度的計(jì)算

fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);

三、模擬退火算法的實(shí)現(xiàn)與應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

第21頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì)（1）互換操作，隨機(jī)交換兩個(gè)城市的順序；（2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序；（3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。283591467283591467283591467281593467283419567235981467

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

第22頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三參數(shù)設(shè)定

截止溫度tf=0.01;

退溫系數(shù)alpha=0.90;

內(nèi)循環(huán)次數(shù)L=200*CityNum;

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

第23頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三運(yùn)行過程

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

第24頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三運(yùn)行過程

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

第25頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三運(yùn)行過程

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

第26頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三運(yùn)行過程

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=423.741byDBFogel）

第27頁(yè)，講稿共31頁(yè)，2023年5月2日，星期三運(yùn)行過程

三、模擬退火算法的應(yīng)用

3.130城市TSP問題（d*=