模擬退火算法詳解1

第三章模擬退火算法

現(xiàn)代優(yōu)化計(jì)算3.1模擬退火算法及模型

3.1.1物理退火過程

3.1.2組合優(yōu)化與物理退火的相似性

3.1.3模擬退火算法的基本思想和步驟

3.2模擬退火算法的關(guān)鍵參數(shù)和操作的設(shè)計(jì)

3.2.1狀態(tài)產(chǎn)生函數(shù)

3.2.2狀態(tài)接受函數(shù)

3.2.3初溫

3.2.4溫度更新函數(shù)

3.2.5內(nèi)循環(huán)終止準(zhǔn)則

3.2.6外循環(huán)終止準(zhǔn)則

3.3模擬退火算法的改進(jìn)

3.3.1模擬退火算法的優(yōu)缺點(diǎn)

3.3.2改進(jìn)內(nèi)容現(xiàn)代優(yōu)化計(jì)算3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極??；克服初值依賴性。

3.1.1物理退火過程3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算物理退火過程

什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。

3.1.1物理退火過程3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算物理退火過程

加溫過程——增強(qiáng)粒子的熱運(yùn)動，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程——對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過程——使粒子熱運(yùn)動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。

3.1.1物理退火過程熱力學(xué)中的退火現(xiàn)象指物體逐漸降溫時(shí)發(fā)生的物理現(xiàn)象：溫度越低，物體的能量狀態(tài)越低，到達(dá)足夠的低點(diǎn)時(shí)，液體開始冷凝與結(jié)晶，在結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。緩慢降溫（退火，annealing）時(shí)，可達(dá)到最低能量狀態(tài)；但如果快速降溫（淬火，quenching），會導(dǎo)致不是最低能態(tài)的非晶形。為什么緩慢降溫：緩緩降溫，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安頓位置，則逐漸地，到最后可得到最低能態(tài)，系統(tǒng)最穩(wěn)定。3.1模擬退火算法及模型

3.1.1物理退火過程現(xiàn)代優(yōu)化計(jì)算模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性

從某一初始溫度開始，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解3.1模擬退火算法及模型

3.1.1物理退火過程現(xiàn)代優(yōu)化計(jì)算3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布

3.1.1物理退火過程3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E1<E2，有

3.1.1物理退火過程<1>0模擬退火算法基本思想：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，搜索過程以概率1停留在最優(yōu)解3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算

3.1.1物理退火過程溫度對的影響當(dāng)很大時(shí)， ，各狀態(tài)的概率幾乎相等SA開始做廣域搜索，隨著溫度的下降 差別擴(kuò)大3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算

3.1.1物理退火過程當(dāng) 時(shí)，與的小差別帶來和的巨大差別例如：=90， =100，3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算

3.1.1物理退火過程當(dāng) =100時(shí)3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算

3.1.1物理退火過程當(dāng)=1時(shí)此時(shí)結(jié)論:

時(shí)，以概率1趨于最小能量狀態(tài)3.1模擬退火算法及模型

3.1.1物理退火過程現(xiàn)代優(yōu)化計(jì)算Boltzman概率分布告訴我們：

（1）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停留在能量大狀態(tài)的概率（2）溫度越高，不同能量狀態(tài)對應(yīng)的概率相差越??；溫度足夠高時(shí)，各狀態(tài)對應(yīng)概率基本相同。（3）隨著溫度的下降，能量最低狀態(tài)對應(yīng)概率越來越大；溫度趨于0時(shí)，其狀態(tài)趨于13.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算數(shù)學(xué)表述

若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/|D|；狀態(tài)空間存在超過兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D|；當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。

3.1.1物理退火過程能量最低狀態(tài)非能量最低狀態(tài)3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算相似性比較

3.1.2組合優(yōu)化與物理退火的相似性組合優(yōu)化問題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)目標(biāo)函數(shù)能量3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算SA的計(jì)算步驟初始化,任選初始解,,給定初始溫度，終止溫度，令迭代指標(biāo) 。

注：選擇時(shí)，要足夠高，使隨機(jī)產(chǎn)生一個(gè)鄰域解， 計(jì)算目標(biāo)值增量

3.1.3模擬退火算法的基本思想和步驟3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算

3.1.3模擬退火算法的基本思想和步驟若 轉(zhuǎn)步④(j比i好無條件轉(zhuǎn)移)；否則產(chǎn)生

(j比i好，有條件轉(zhuǎn)移)。

注： 高時(shí)，廣域搜索；低時(shí)，局域搜索若達(dá)到熱平衡轉(zhuǎn)步⑤(每個(gè)特定溫度下的搜索次數(shù)N：根據(jù)計(jì)算耗時(shí)來確定)，否則轉(zhuǎn)步②。

3.1模擬退火算法及模型

現(xiàn)代優(yōu)化計(jì)算

3.1.3模擬退火算法的基本思想和步驟

降低，若停止，否則轉(zhuǎn)步②。

注：降低的方法有以下兩種流程框圖見下頁 T=Th求得初始解BS=初始解n=0求得新的解接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStart是否是否是是否是否新的解比當(dāng)前解好？T:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)ExampleTravelingSalesmanProblem(TSP)Given6citiesandthetravelingcostbetweenanytwocitiesAsalesmanneedtostartfromcity1andtravelallothercitiesthenbacktocity1MinimizethetotaltravelingcostTSP算例Citytocity1234561247910211213836813469556SAparametersettingTh=2000t=10r=0.6N=2生成新的解：隨機(jī)選擇兩個(gè)位置，交換其表示的城市T:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStart是否是否是否是否是否求得初始解BS=初始解

SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解溫度T＝2000n=0SequenceThelengthoftheroute12345630新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStart是否是否是否是否是否T:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)SequenceThelengthoftheroute13245628當(dāng)前解SequenceThelengthoftheroute12345630新的解Exp((新的解－當(dāng)前解)/T)=exp(-2/2000)Random[0,1]=0.7T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStart是否是否是否是否是否T:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628當(dāng)前解溫度T＝2000n=1T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rT