模擬退火模型

《模擬退火模型》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、模擬退火模型主講人：泰山教育小石老師模型背景什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。泰山教育版權(quán)所有淘寶ID:liuxingma123模型背景物理退火過(guò)程加溫過(guò)程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過(guò)程——對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過(guò)程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)

2、構(gòu)。泰山教育版權(quán)所有淘寶ID:liuxingma123模型背景熱力學(xué)中的退火現(xiàn)象指物體逐漸降溫時(shí)發(fā)生的物理現(xiàn)象：溫度越低，物體的能量狀態(tài)越低，到達(dá)足夠的低點(diǎn)時(shí)，液體開(kāi)始冷凝與結(jié)晶，在結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。緩慢降溫時(shí)，可達(dá)到最低能量狀態(tài)；但如果快速降溫，會(huì)導(dǎo)致不是最低能態(tài)的非晶形。大自然知道慢工出細(xì)活：緩緩降溫，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安頓位置，則逐漸地，到最后可得到最低能態(tài)，系統(tǒng)最穩(wěn)定。泰山教育版權(quán)所有淘寶ID:liuxingma123模擬退火算法思想模仿自然界退火現(xiàn)象而得，利用了物理

3、中固體物質(zhì)的退火過(guò)程與一般優(yōu)化問(wèn)題的相似性從某一初始溫度開(kāi)始，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解組合優(yōu)化問(wèn)題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過(guò)程Metropolis抽樣過(guò)程等溫過(guò)程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量泰山教育版權(quán)所有淘寶ID:liuxingma123算法簡(jiǎn)介設(shè)熱力學(xué)系統(tǒng)Sn中有個(gè)狀態(tài)(有限個(gè),離散的),狀態(tài)iET的能量為,在溫度下，經(jīng)一段時(shí)間達(dá)到熱平衡，ik這時(shí)處于狀態(tài)i的概率為：???EPT()=Cexp??iikkT??k則有如下關(guān)系：EP↓→↑TP↓→

4、↓iiki如何確定C?k泰山教育版權(quán)所有淘寶ID:liuxingma123算法簡(jiǎn)介Bolzman方程???Eexp??iT??kPTik()=n???E∑exp??iTi=1??k可見(jiàn)：Ei↑?PTik()↓?Tkk↓?PTi?()→1,i代表Ei最小的那一個(gè)nTk下的平均能量：ET(k)=∑EPTiik?()i=1Tk↓?→EEi?泰山教育版權(quán)所有淘寶ID:liuxingma123背景溫度TPT對(duì)()的影響kikEi當(dāng)T很大時(shí)，→0kTkPTik()≈1各狀態(tài)的概率幾乎相等n隨著溫度的下降PTik()差別擴(kuò)大Ei

5、當(dāng)T很小趨于0時(shí)，→∞kTk當(dāng)T→01時(shí)，以概率趨于最小能量狀態(tài)k泰山教育版權(quán)所有淘寶ID:liuxingma123算法簡(jiǎn)介模擬退火算法的模擬要求1初始溫度足夠高2降溫過(guò)程足夠慢3終止溫度足夠低泰山教育版權(quán)所有淘寶ID:liuxingma123算法簡(jiǎn)介模擬退火算法的計(jì)算步驟①初始化,任選初始解,,iS∈給定初始溫度T0，終止溫度T,令迭代指標(biāo)kTT=0,=。fk0E注：選擇T時(shí)，要足夠高，使i→00Tk②隨機(jī)產(chǎn)生一個(gè)鄰域解，jNiNi∈(),(()表示i的鄰域)計(jì)算目標(biāo)值增量?=ffjfi()?()泰山教育版權(quán)所有

6、淘寶ID:liuxingma123算法簡(jiǎn)介③若?U(0,1,)若exp??????f,T??k則令ij=(j比i好，有條件轉(zhuǎn)移)。注：T高時(shí)，廣域搜索；T低時(shí)，局域搜索kk④若達(dá)到熱平衡(內(nèi)循環(huán)次數(shù)大于nT(k))轉(zhuǎn)步⑤，否則轉(zhuǎn)步②。泰山教育版權(quán)所有淘寶ID:liuxingma123算法簡(jiǎn)介⑤kk=+1降低Tk，若TTkf<停止，否則轉(zhuǎn)步②。注：降低Tk的方法有以下兩種1.較好的方法TTrkk+1=?其中r∈?(0.950.99)。優(yōu)點(diǎn)：簡(jiǎn)單易行2.TT

7、T=??kk+112泰山教育版權(quán)所有淘寶ID:liuxingma123模擬退火算法對(duì)TSP問(wèn)題的求解旅行商問(wèn)題，即TSP問(wèn)題（TravellingSalesmanProblem）又譯為旅行推銷員問(wèn)題、貨郎擔(dān)問(wèn)題，是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。迄今為止，這類問(wèn)題中沒(méi)有一個(gè)找到有效算法。傾向于接受NP完全問(wèn)題（NP-Complet或NPC）和NP難

8、題（NP-Hard或NPH）不存在有效算法這一猜想，認(rèn)為這類問(wèn)題的大型實(shí)例不能用精確算法求解，必須尋求這類問(wèn)題的有效的近似算法。泰山教育版權(quán)所有淘寶ID:liuxingma123模擬退火算法對(duì)TSP問(wèn)題的求解城市X坐標(biāo)Y坐標(biāo)城市X坐標(biāo)Y坐標(biāo)10.66830.253660.22930.761020.61950.263470.51710.941430.40000