模擬退火算法.doc

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

1、1、?模擬退火算法（起源）模擬退火算法起源于物理退火。?物理退火過程：（1）??????加溫過程（2）??????等溫過程（3）??????冷卻過程???????????????????????????????????物理退火原理?1953年，Metropolis提出重要性采樣法，即以概率接受新狀態(tài)，稱Metropolis準(zhǔn)則，計算量相對MonteCarlo方法顯著減少。?1983年，Kirkpatrick等提出模擬退火算法，并將其應(yīng)用于組合優(yōu)化問題的求解。2、?模擬退火算法???Metropolis準(zhǔn)則1）?Metropolis準(zhǔn)則提出???固體在恒定溫度下達(dá)到熱平衡的過程

2、可以用MorteCarol算法方法加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，因而計算量很大。鑒于物理系統(tǒng)傾向于能量較低的狀態(tài)，而熱運動又妨礙它準(zhǔn)確落到最低態(tài)。采樣時著重選取那些有重要貢獻的狀態(tài)則可較快達(dá)到較好的結(jié)果。因此，Metropolis等在1953年提出了重要的采樣法，即以概率接受新狀態(tài)。2）?Metropolis準(zhǔn)則????假設(shè)在狀態(tài)xold時，系統(tǒng)受到某種擾動而使其狀態(tài)變?yōu)閤new。與此相對應(yīng)，系統(tǒng)的能量也從E(xold)變成E(xnew)，系統(tǒng)由狀態(tài)xold變?yōu)闋顟B(tài)xnew的接受概率p：?模擬退火算法-------步驟1)隨機產(chǎn)生一個初始解x

3、0，令xbest＝x0，并計算目標(biāo)函數(shù)值E(x0);2)設(shè)置初始溫度T(0)=To，迭代次數(shù)i=1;3)DowhileT(i)>Tmin1)forj=1~k2)對當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù)，產(chǎn)生一新的解xnew。計算新的目標(biāo)函數(shù)值E(xnew)，并計算目標(biāo)函數(shù)值的增量ΔE=E(xnew)-E(xbest)。3)如果ΔE＜0，則xbest=xnew；4)如果ΔE＞0，則p=exp(-ΔE/T(i));1)如果c=random[0,1]

4、圖為模擬退火算法流程圖：????????????????????????????????模擬退火算法------參數(shù)的選擇???冷卻進度表???我們稱調(diào)整模擬退火法的一系列重要參數(shù)為冷卻進度表。它控制參數(shù)T的初值及其衰減函數(shù)，對應(yīng)的MARKOV鏈長度和停止條件，非常重要。一個冷卻進度表應(yīng)當(dāng)規(guī)定下述參數(shù)：???1．控制參數(shù)t的初值t0;2．控制參數(shù)t的衰減函數(shù)；3．馬爾可夫鏈的長度Lk。（即每一次隨機游走過程，要迭代多少次，才能趨于一個準(zhǔn)平衡分布，即一個局部收斂解位置）4．結(jié)束條件的選擇有效的冷卻進度表判據(jù)：一．算法的收斂：主要取決于衰減函數(shù)和馬可夫鏈的長度及停止準(zhǔn)則的選擇二．

5、算法的實驗性能：最終解的質(zhì)量和CPU的時間???參數(shù)的選取：一）控制參數(shù)初值T0的選取一般要求初始值t0的值要充分大，即一開始即處于高溫狀態(tài)，且Metropolis的接收率約為1。(1)均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。(2)隨機產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差

6、Δmax

7、，然后依據(jù)差值，利用一定的函數(shù)確定初溫。比如，t0=－Δmax/pr，其中pr為初始接受概率。二）衰減函數(shù)的選取　衰減函數(shù)用于控制溫度的退火速度，一個常用的函數(shù)為：T(n+1)=K*T(n)，其中K是一個非常接近于1的常數(shù)。三）馬可夫鏈長度L的選取原則是：在衰減參數(shù)T的衰減函數(shù)已選定的

8、前提下，L應(yīng)選得在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡。四）終止條件有很多種終止條件的選擇，各種不同的條件對算法的性能和解的質(zhì)量有很大影響，我們只介紹一個常用的終止條件。即上一個最優(yōu)解與最新的一個最優(yōu)解的之差小于某個容差，即可停止此次馬爾可夫鏈的迭代。???3、模擬退火算法的優(yōu)缺點??優(yōu)點：計算過程簡單，通用，魯棒性強，適用于并行處理，可用于求解復(fù)雜的非線性優(yōu)化問題缺點：收斂速度慢，執(zhí)行時間長，算法性能與初始值有關(guān)及參數(shù)敏感等缺點經(jīng)典模擬退火算法的缺點：1)如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢;(2)如果降溫過程過快，很可能得不到全局最優(yōu)解

9、。?模擬退火算法的改進(1)設(shè)計合適的狀態(tài)產(chǎn)生函數(shù)，使其根據(jù)搜索進程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性。(2)設(shè)計高效的退火策略。(3)避免狀態(tài)的迂回搜索。(4)采用并行搜索結(jié)構(gòu)。(5)為避免陷入局部極小，改進對溫度的控制方式(6)選擇合適的初始狀態(tài)。(7)設(shè)計合適的算法終止準(zhǔn)則。也可通過增加某些環(huán)節(jié)而實現(xiàn)對模擬退火算法的改進。主要的改進方式包括：(1)增加升溫或重升溫過程。在算法進程的適當(dāng)時機，將溫度適當(dāng)提高，從而可激活各狀態(tài)的接受概率，以調(diào)整搜索進程中的當(dāng)前狀態(tài)，避免算法在局部極小解處停滯不