很經(jīng)典的模擬退火算法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ōu)化的問題、定位及圖分割等問題上，它是蒙地卡羅算法的推廣,Simulated

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

3、Simulated Annealing,6,模擬退火法的程(1/2,需先設(shè)定一些，。接著隨機產(chǎn)生一個初始的目前解 ，并計算他的目標(biāo)函值 。 以目前解為中心對解空間做隨機擾動，產(chǎn)生一個擾動解 ，其目標(biāo)函值為。 接受，則以該擾動解取代目前解作為該次迭代的解,Simulated Annealing,7,模擬退火法的檢測標(biāo)準(zhǔn),根據(jù)熱力學(xué)定律，在溫度為t的情況下，能量差所表現(xiàn)的機率如下： P(E)=exp(-E / kt) k是Boltzmanns Constant 轉(zhuǎn)換到模擬退火法，則變成 P=exp(-c / t)r c是評估函數(shù)的差 r是01之間的隨機數(shù),Simulated Annealing,8

4、,模擬退火法的程(2/2,假設(shè)所求解的問題是目標(biāo)函最小化問題 ， ，則透過機函接受 為新解。 接著判斷是否滿足溫條件，是，則透過卻機制溫， ， 。 反之，維持目前溫。之后判斷是否達到終止條件，如達到設(shè)定的迭代次或是續(xù)幾次迭代目前解再改變時,Simulated Annealing,9,模擬退火法的程圖,初使化設(shè)定,隨機產(chǎn)生一個初始解,擾動產(chǎn)生一個新解,是否接受,修改目前解,降溫,縮減溫度,是否達到中止條件,最佳解,No,Yes,Yes,Yes,No,No,Simulated Annealing,10,冷卻排程(1/4,初始溫度（Starting Temperature） 溫度要夠高才能移動到任何

5、的狀態(tài)。 溫度不能太高，否則會導(dǎo)致在一段時間內(nèi)皆用隨機數(shù)在湊解答。 如果可以知道檢測函數(shù)的最大值就可以找到最好的初始溫度。 快速提高溫度，然后又快速降溫，直到有60%的最差解被接受。 快速提高溫度，但慢慢降溫，并定出適當(dāng)比例最差解的接受度,Simulated Annealing,11,冷卻排程(2/4,最終溫度（Final Temperature） 通常是零，但會耗掉許多模擬時間。 溫度趨近于零，其周遭狀態(tài)幾乎是一樣的。 所以尋找一個低到可接受的溫度,Simulated Annealing,12,冷卻排程(3/4,溫度減少（Temperature Decrement） 每次降低溫度的差距以及在

6、同一溫度反復(fù)尋找最適解會導(dǎo)致指數(shù)般成長的搜尋空間。 1.以線性降溫來說 Temp=Temp-x 2.以幾何觀念來看 Temp=Temp*y (y約0.80.99為佳,Simulated Annealing,13,冷卻排程（4/4,反復(fù)次數(shù)（Iterations at each Temperature） 一般會定一個常數(shù)。 Lundy認為只要反復(fù)一次，但每次降低的溫度差距必須非常小。 Temp=Temp / (1+a*Temp) a是非常小的值 低溫需要較多反復(fù)次數(shù)以避免找到局部最大值，但高溫則可減少次數(shù),Simulated Annealing,14,模擬退火法的程圖,初使化設(shè)定,隨機產(chǎn)生一個初

7、始解,擾動產(chǎn)生一個新解,是否接受,修改目前解,降溫,縮減溫度,是否達到中止條件,最佳解,No,Yes,Yes,Yes,No,No,Simulated Annealing,15,擾動方式(1/2,模擬退火法以擾動的機制產(chǎn)生一個解，我們稱此解為擾動解，在以機函判斷是否接受此擾動解為此次迭代的新解。 被接受，就再以擾動重新產(chǎn)生一個擾動解，并以機函重新判斷。每代重復(fù)以上的步驟，直到接受為此次迭代的新解為止,Simulated Annealing,16,擾動方式(2/2,擾動的作法就是以目前解為中心，對部分或整個解空間隨機取樣一個解,Simulated Annealing,17,模擬退火法的程圖,初使化

8、設(shè)定,隨機產(chǎn)生一個初始解,擾動產(chǎn)生一個新解,是否接受,修改目前解,降溫,縮減溫度,是否達到中止條件,最佳解,No,Yes,Yes,Yes,No,No,Simulated Annealing,18,機函(1/3,模擬退火法用機函有機的接受較差的擾動解為新解，使其避免傳統(tǒng)梯搜尋法（GradientSearch）往往陷入?yún)^(qū)域解的缺點，而使模擬退火法有機會跳脫區(qū)域解，往全局最佳解收斂,Simulated Annealing,19,機函(2/3,一般的機函方程式如下: 為目前溫。當(dāng) ， ；當(dāng)會是之后隨機產(chǎn)生一個介于0到1間的一個小于1大於0的值。 隨機值r與 比較，若，則接收擾動解；反之，則接受,Sim

9、ulated Annealing,20,機函(3/3,當(dāng) 越高或 越小時，則 越大，相對的擾動解被接受成新解的機越高。 因此會隨著迭代次的增加而逐漸下，所以較差的擾動解被接受成新解的機會也隨著 的下而越越小。 所以當(dāng)?shù)阶詈笠驗闇?已到達低點，這時系統(tǒng)只會接受較佳的擾動解為新解。 而擾動解 小于目前解 則一定接受為新解，但是 則接受為新解的機隨著 的變大而越小,Simulated Annealing,21,模擬退火法的程圖,初使化設(shè)定,隨機產(chǎn)生一個初始解,擾動產(chǎn)生一個新解,是否接受,修改目前解,降溫,縮減溫度,是否達到中止條件,最佳解,No,Yes,Yes,Yes,No,No,Simulat

10、ed Annealing,22,其他的問題(1/4,價值函數(shù)（Cost Function） 用來評估解的質(zhì)量。 Delta Evaluation 求某解與其鄰近點的價值。 Partial Evaluation 不需額外產(chǎn)生的計算結(jié)果就可以判斷出來解的價值,Simulated Annealing,23,其他的問題（2/4,價值函數(shù)（Cost Function） Hard Constraints 在不違背合適解的條件下，所提出的強制規(guī)定。 Soft Constraints 無論這種解是否違背條件，都算是合適解。 HardConstraints會給一個很大的weight SoftConstraint

11、s則是情況給予不同的weight,Simulated Annealing,24,其他的問題（3/4,鄰近點的結(jié)構(gòu)（Neighborhood Structure） 有些結(jié)構(gòu)是對稱性的，即可以從A狀態(tài)到B狀態(tài)，也可以從B狀態(tài)到A狀態(tài)。 條件較弱（結(jié)構(gòu)較松散）的有穩(wěn)定的收斂。 條件定的好，就可以使得在各種狀態(tài)之下都可以到達另一種狀態(tài),Simulated Annealing,25,其他的問題（4/4,所有解的空間（The Solution Space） 空間小，可以展開搜尋。 若允許不合適的解也存在的話就會加大搜尋空間。 我們想辦法取一個適當(dāng)值，期望能快速搜尋，又可避免在不利的情況下沒有好的進展,Si

12、mulated Annealing,26,提高效能,初始化（Initialization） 將原本用隨機數(shù)取初始值的方式改為盡可能找出一有用的起始點。 結(jié)合（Combine） 可將仿真退火法配合其他算法應(yīng)用于問題上,Simulated Annealing,27,算法修正(1/2,可接受的機率（Acceptance Probability） 少計算exponential會加快速度 建立一個可查詢各種值的table 冷卻（Cooling） 花一些時間找尋最佳溫度（包括最終溫度、溫差,Simulated Annealing,28,算法修正（2/2,鄰近點（Neighborhood） 對于不好的鄰近點給予一個懲罰值。 價值函數(shù)（Cost Functio