模擬退火算法

1、1、  模擬退火算法（起源）模擬退火算法起源于物理退火。􀂄物理退火過(guò)程：（1）       加溫過(guò)程（2）       等溫過(guò)程（3）       冷卻過(guò)程                   

2、0;               物理退火原理􀂄1953年，Metropolis提出重要性采樣法，即以概率接受新?tīng)顟B(tài)，稱(chēng)Metropolis準(zhǔn)則，計(jì)算量相對(duì)Monte Carlo方法顯著減少。􀂄 1983年，Kirkpatrick等提出模擬退火算法，并將其應(yīng)用于組合優(yōu)化問(wèn)題的求解。2、  模擬退火算法   􀂄 Metropolis準(zhǔn)則1）  Metrop

3、olis準(zhǔn)則提出    固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用MorteCarol算法方法加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，因而計(jì)算量很大。鑒于物理系統(tǒng)傾向于能量較低的狀態(tài)，而熱運(yùn)動(dòng)又妨礙它準(zhǔn)確落到最低態(tài)。采樣時(shí)著重選取那些有重要貢獻(xiàn)的狀態(tài)則可較快達(dá)到較好的結(jié)果。因此，Metropolis等在1953年提出了重要的采樣法，即以概率接受新?tīng)顟B(tài)。2）  Metropolis準(zhǔn)則     假設(shè)在狀態(tài)xold時(shí)，系統(tǒng)受到某種擾動(dòng)而使其狀態(tài)變?yōu)閤new。與此相對(duì)應(yīng)，系統(tǒng)的能量也從E(xold)變

4、成E(xnew)，系統(tǒng)由狀態(tài)xold變?yōu)闋顟B(tài)xnew的接受概率p：􀂄 模擬退火算法-步驟1) 隨機(jī)產(chǎn)生一個(gè)初始解x0，令xbest x0 ，并計(jì)算目標(biāo)函數(shù)值E(x0);2) 設(shè)置初始溫度T(0)=To，迭代次數(shù)i = 1;3) Do while T(i) > Tmin1) for j = 1k2) 對(duì)當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù)，產(chǎn)生一新的解xnew。計(jì)算新的目標(biāo)函數(shù)值E(xnew) ，并計(jì)算目標(biāo)函數(shù)值的增量E = E(xnew) - E(xbest) 。3) 如果E 0，則xbest = xnew；4) 如果E 0，則p = exp(- E /T(i);1)

5、如果c = random0,1 < p， xbest = xnew; 否則xbest = xbest。5) End for4) i = i 1；5) End Do6) 輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束  下圖為模擬退火算法流程圖：                             &#

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

7、及停止準(zhǔn)則的選擇二算法的實(shí)驗(yàn)性能：最終解的質(zhì)量和CPU的時(shí)間   􀂄參數(shù)的選?。阂唬┛刂茀?shù)初值T0的選取一般要求初始值t0的值要充分大，即一開(kāi)始即處于高溫狀態(tài)，且Metropolis的接收率約為1。(1) 均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。(2) 隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差|max|，然后依據(jù)差值，利用一定的函數(shù)確定初溫。比如，t0=max/pr ，其中pr為初始接受概率。二）衰減函數(shù)的選取衰減函數(shù)用于控制溫度的退火速度，一個(gè)常用的函數(shù)為：T(n + 1) = K*T(n)，其中K是一個(gè)非常接近于1的常數(shù)。三）馬可夫鏈長(zhǎng)度

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

9、較好，但與此相對(duì)的是收斂速度太慢;(2)如果降溫過(guò)程過(guò)快，很可能得不到全局最優(yōu)解。􀂄 模擬退火算法的改進(jìn)(1) 設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)，使其根據(jù)搜索進(jìn)程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性。(2) 設(shè)計(jì)高效的退火策略。(3) 避免狀態(tài)的迂回搜索。(4) 采用并行搜索結(jié)構(gòu)。(5) 為避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式(6) 選擇合適的初始狀態(tài)。(7) 設(shè)計(jì)合適的算法終止準(zhǔn)則。也可通過(guò)增加某些環(huán)節(jié)而實(shí)現(xiàn)對(duì)模擬退火算法的改進(jìn)。主要的改進(jìn)方式包括：(1) 增加升溫或重升溫過(guò)程。在算法進(jìn)程的適當(dāng)時(shí)機(jī)，將溫度適當(dāng)提高，從而可激活各狀態(tài)的接受概率，以調(diào)整搜索進(jìn)程中的當(dāng)前狀態(tài)，避免算法在局部極小解處停滯不前。(2) 增加記憶功能。為避免搜索過(guò)程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前遇到的最優(yōu)解，可通過(guò)增加存儲(chǔ)環(huán)節(jié)，將一些在這之前好的態(tài)記憶下來(lái)。(3) 增加補(bǔ)充搜索過(guò)程。即在退火過(guò)程結(jié)束后，以搜索到的最優(yōu)解為初始狀態(tài)，再次執(zhí)行模擬退火過(guò)程或局部性搜索。(4) 對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)，而非標(biāo)準(zhǔn)SA的單次比較方式。(5) 結(jié)