模擬退火算法詳解

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

1、第二章模擬退火算法現(xiàn)代優(yōu)化計(jì)算3.1模擬退火算法及模型3.1.1物理退火過(guò)程3.1.2組合優(yōu)化與物理退火的相似性3.1.3模擬退火算法的基本思想和步驟3.2模擬退火算法的馬氏鏈描述3.2.1馬爾可夫鏈3.2.2模擬退火算法與馬爾可夫鏈3.3模擬退火算法的關(guān)鍵參數(shù)和操作的設(shè)計(jì)3.3.1狀態(tài)產(chǎn)生函數(shù)3.3.2狀態(tài)接受函數(shù)3.3.3初溫3.3.4溫度更新函數(shù)3.3.5內(nèi)循環(huán)終止準(zhǔn)則3.3.6外循環(huán)終止準(zhǔn)則現(xiàn)代優(yōu)化計(jì)算3.4模擬退火算法的改進(jìn)3.4.1模擬退火算法的優(yōu)缺點(diǎn)3.4.2改進(jìn)內(nèi)容3.4.3一種改進(jìn)的模擬退火算法3.5模擬退火算法實(shí)現(xiàn)與應(yīng)用3.5.130城

2、市TSP問(wèn)題（d*=423.741byDBFogel）3.5.2模擬退火算法在管殼式換熱器優(yōu)化設(shè)計(jì)中的應(yīng)用現(xiàn)代優(yōu)化計(jì)算3.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算算法的提出模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問(wèn)題；克服優(yōu)化過(guò)程陷入局部極??；克服初值依賴性。3.1.1物理退火過(guò)程3.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算物理退火過(guò)程什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。3

3、.1.1物理退火過(guò)程3.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算物理退火過(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é)構(gòu)。3.1.1物理退火過(guò)程熱力學(xué)中的退火現(xiàn)象指物體逐漸降溫時(shí)發(fā)生的物理現(xiàn)象：溫度越低，物體的能量狀態(tài)越低，到達(dá)足夠的低點(diǎn)時(shí)，液體開(kāi)始冷凝與結(jié)晶，在結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。緩慢降溫（退火，annealing）時(shí)，可達(dá)到

4、最低能量狀態(tài)；但如果快速降溫（淬火，quenching），會(huì)導(dǎo)致不是最低能態(tài)的非晶形。大自然知道慢工出細(xì)活：緩緩降溫，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安頓位置，則逐漸地，到最后可得到最低能態(tài)，系統(tǒng)最穩(wěn)定。3.1模擬退火算法及模型3.1.1物理退火過(guò)程現(xiàn)代優(yōu)化計(jì)算模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過(guò)程與一般優(yōu)化問(wèn)題的相似性從某一初始溫度開(kāi)始，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解3.1模擬退火算法及模型3.1.1物理退火過(guò)程現(xiàn)代優(yōu)化計(jì)算3.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算數(shù)學(xué)表述在溫度T，分子停留在狀態(tài)r

5、滿足Boltzmann概率分布3.1.1物理退火過(guò)程3.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E10模擬退火算法基本思想：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，搜索過(guò)程以概率1停留在最優(yōu)解3.1模擬退火算法及模型3.1.1物理退火過(guò)程現(xiàn)代優(yōu)化計(jì)算Boltzman概率分布告訴我們：（1）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停留在能量大狀態(tài)的概率（2）溫度越高，不同能量狀態(tài)對(duì)應(yīng)的概率相差越??；溫度足夠高時(shí)，各狀態(tài)對(duì)應(yīng)概率基本相同。（3）隨著

6、溫度的下降，能量最低狀態(tài)對(duì)應(yīng)概率越來(lái)越大；溫度趨于0時(shí)，其狀態(tài)趨于13.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算數(shù)學(xué)表述若

7、D

8、為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/

9、D

10、；狀態(tài)空間存在超過(guò)兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/

11、D

12、；當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。3.1.1物理退火過(guò)程能量最低狀態(tài)非能量最低狀態(tài)3.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）——以概率接受新?tīng)顟B(tài)固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用MonteCarlo方

13、法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。3.1.1物理退火過(guò)程3.1模擬退火算法及模型現(xiàn)代優(yōu)化計(jì)算Metropolis準(zhǔn)則（1953）——以概率接受新?tīng)顟B(tài)若在溫度T，當(dāng)前狀態(tài)i→新?tīng)顟B(tài)j若Ej

14、BT]在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新?tīng)顟B(tài)；在低溫下，只接