第3章 模擬退火算法

第三章模擬退火算法（SimulatedAnnealing）搜索問題描述除高度信息外，對環(huán)境沒有任何感知能力最優(yōu)解位于海拔最高處可以任意方式移動(dòng)搜索問題描述LandscapewithvariousfeaturesObjectivefunctionshoulderglobalmaxlocalmaxflatlocalmaxcurrentstateStatespace搜索算法盲目搜索還是啟發(fā)式搜索？按照預(yù)定的控制策略實(shí)行搜索，在搜索過程中獲取的中間信息不用來改進(jìn)控制策略，稱為盲目搜索，反之，稱為啟發(fā)式搜索。關(guān)于“啟發(fā)式”，可有兩種看法：1)任何有助于找到問題的最優(yōu)解，但不能保證找到最優(yōu)解的方法均是啟發(fā)式方法；2)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)式方法。搜索算法盲目搜索深度優(yōu)先、廣度優(yōu)先、代價(jià)優(yōu)先、向前、向后、雙向。。。啟發(fā)式搜索爬山法、模擬退火算法、遺傳算法、粒子群算法、蟻群算法。。。貪心算法隨機(jī)選定一個(gè)初始解x0；Dowhile（終止條件不滿足）在某個(gè)鄰域函數(shù)所定義的鄰域范圍內(nèi)，按照某個(gè)（隨機(jī)）擾動(dòng)

產(chǎn)生策略，得到一個(gè)新解xi’；對新解進(jìn)行評估，得f(xi’)；如果f(xi’)>f(xi)（或者f(xi’)<f(xi)），即新解比老解好，則令xi＋1＝xi’；否則，xi＋1＝xi。EndDo爬山法隨機(jī)選定一個(gè)初始解x0；Dowhile（中止條件不滿足）在某個(gè)鄰域函數(shù)所定義的鄰域范圍內(nèi)，按照某個(gè)（隨機(jī)）擾動(dòng)

產(chǎn)生策略，得到多個(gè)新解Xnew={xi1,xi2,…,xik}；對這組新解進(jìn)行評估，得{f(xi1),f(xi2),…,f(xik)}；xi＋1＝xi’,

xi’

Xnew,

xij,(i=1,2,…,n;j=1,2,…,k),f(xi’)>f(xi)

且f(xi’)>f(xij)（或者f(xi’)<f(xi)且f(xi’)<f(xij)），即新的當(dāng)前解比老解好，并且是所有新解中最好的一個(gè)；如果，

xij,(i=1,2,…,n;j=1,2,…,k),f(xi)>f(xij)（或者f(xi)<f(xij)），則xi＋1＝xi

。EndDo特點(diǎn)快速收斂于局部最優(yōu)解特點(diǎn)遇到平臺則無以事從算法設(shè)計(jì)要素編碼策略（“個(gè)體表示”與“問題解”的映射關(guān)系）初始解的產(chǎn)生（從什么位置開始搜索）鄰域函數(shù)的設(shè)計(jì)（下一個(gè)解的產(chǎn)生概率與當(dāng)前解之間[包括方向和步長]的關(guān)系）新解產(chǎn)生策略（隨機(jī)，確定）接受策略（貪心）存在問題：對初始解（狀態(tài)）敏感容易陷入局部最優(yōu)模擬退火算法（起源）物理退火原理模擬退火算法（起源）物理退火過程：加溫過程等溫過程冷卻（退火）過程等溫下熱平衡過程可用MonteCarlo方法模擬，計(jì)算量大。1953年，Metropolis提出重要性采樣法，即以概率接受新狀態(tài)，稱Metropolis準(zhǔn)則，計(jì)算量相對MonteCarlo方法顯著減少。1983年，Kirkpatrick等提出模擬退火算法，并將其應(yīng)用于組合優(yōu)化問題的求解。模擬退火算法（Metropolis準(zhǔn)則）Metropolis準(zhǔn)則 假設(shè)在狀態(tài)xold時(shí)，系統(tǒng)受到某種擾動(dò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：模擬退火算法與物理退火過程的相似關(guān)系模擬退火物理退火解粒子狀態(tài)最優(yōu)解能量最低態(tài)設(shè)定初溫熔解過程Metropolis采樣過程等溫過程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量模擬退火算法（流程）隨機(jī)產(chǎn)生一個(gè)初始解x0，令xbest＝x0，并計(jì)算目標(biāo)函數(shù)值E(x0);設(shè)置初始溫度T(0)=To;DowhileT>Tmin

//降溫過程forj=1~k //等溫過程對當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù)，產(chǎn)生一新的解xnew。計(jì)算新的目標(biāo)函數(shù)值E(xnew)，并計(jì)算目標(biāo)函數(shù)值的增量

E=E(xnew)-E(xbest)

。如果

E＜0，則xbest=xnew；如果

E＞0，則p=exp(-

E/T(i));如果c=random[0,1]<p，xbest=xnew;否則xbest=xbest。Endfor按照溫度控制策略更新T；EndDo輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束。模擬退火算法（要素）1、狀態(tài)空間與狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）搜索空間也稱為狀態(tài)空間，它由經(jīng)過編碼的可行解的集合所組成。狀態(tài)產(chǎn)生函數(shù)(鄰域函數(shù))應(yīng)盡可能保證產(chǎn)生的候選解能遍布全部解空間。通常由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。候選解一般按照某一概率分布對解空間進(jìn)行隨機(jī)采樣來獲得。概率分布可以是均勻分布、正態(tài)分布、指數(shù)分布等等。模擬退火算法（要素）2、狀態(tài)轉(zhuǎn)移概率（接受概率）p狀態(tài)轉(zhuǎn)移概率是指從一個(gè)狀態(tài)xold(一個(gè)可行解)向另一個(gè)狀態(tài)xnew(另一個(gè)可行解)的轉(zhuǎn)移概率;通俗的理解是接受一個(gè)新解為當(dāng)前解的概率;它與當(dāng)前的溫度參數(shù)T有關(guān)，隨溫度下降而減小。一般采用Metropolis準(zhǔn)則模擬退火算法（要素）3