很經(jīng)典的模擬退火算法PPT.ppt

1、Simulated Annealing,1,Simulated Annealing（模擬退火法）,報告人:陳世明,Simulated Annealing,2,大綱,簡介 攀登算法 模擬退火法v.s. Hill Climbing 仿真退火法的檢測標(biāo)準(zhǔn)與流程 模擬退火法的考慮因素 其他的問題 提高效能與算法的修正 結(jié)論,Simulated Annealing,3,簡介,仿真退火法是仿真冷卻晶體的過程。 最早是由Metropolis、Rosenbluth等人在1953年提出。 1983年，Kirkpatrick等人將其運(yùn)用在求優(yōu)化的問題、定位及圖分割等問題上，它是蒙地卡羅算法的推廣。,Simulat

2、ed Annealing,4,攀登算法(Hill Climbing),攀登算法（Hill-climbingAlgorithm）是一種迭代增進(jìn)的算法，它用單一解在解空間作搜尋，并在每一次迭代中，在目前解的鄰近解空間選擇出一個鄰近解。 當(dāng)鄰近解的目標(biāo)函值比目前解的目標(biāo)函值的佳時，就以鄰近解取代目前解；否則，就重新在目前解的鄰近解空間選擇一個鄰近解。,Simulated Annealing,5,模擬退火法v.s. Hill Climbing,HillClimbing是挑選鄰近點(diǎn)中最好的點(diǎn)，但這樣會有局部最大值的問題。 仿真算法是隨機(jī)數(shù)找尋鄰近的點(diǎn)。 若找到的點(diǎn)比立足點(diǎn)好，則取之。 否則依照機(jī)率決定是

3、否取之。,Simulated Annealing,6,模擬退火法的程(1/2),需先設(shè)定一些，。接著隨機(jī)產(chǎn)生一個初始的目前解 ，并計算他的目標(biāo)函值 。 以目前解為中心對解空間做隨機(jī)擾動，產(chǎn)生一個擾動解 ，其目標(biāo)函值為。 接受，則以該擾動解取代目前解作為該次迭代的解。,Simulated Annealing,7,模擬退火法的檢測標(biāo)準(zhǔn),根據(jù)熱力學(xué)定律，在溫度為t的情況下，能量差所表現(xiàn)的機(jī)率如下： P(E)=exp(-E / kt) k是Boltzmanns Constant 轉(zhuǎn)換到模擬退火法，則變成 P=exp(-c / t)r c是評估函數(shù)的差 r是01之間的隨機(jī)數(shù),Simulated Annealing,8,模擬退火法的程(2/2),假設(shè)所求解的問題是目標(biāo)函最小化問題 ， ，則透過機(jī)函接受 為新解。 接著判斷是否滿足溫條件，是，則透過卻機(jī)制溫， ， 。 反之，維持目前溫。之后判斷是否達(dá)到終止條件，如達(dá)到設(shè)定的迭代次或是續(xù)幾次迭代目前解再改變時。,Simulated Annealing,9,模擬退火法的程圖,初使化設(shè)定,隨機(jī)產(chǎn)生一個初始解,擾動產(chǎn)生一個新