很經典的模擬退火算法PPT.ppt

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

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

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

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

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

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

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

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

9、。 隨機值r與 比較，若，則接收擾動解；反之，則接受。,Simulated Annealing,20,機函(3/3),當 越高或 越小時，則 越大，相對的擾動解被接受成新解的機越高。 因此會隨著迭代次的增加而逐漸下，所以較差的擾動解被接受成新解的機會也隨著 的下而越越小。 所以當迭代到最后因為溫 已到達低點，這時系統(tǒng)只會接受較佳的擾動解為新解。 而擾動解 小于目前解 則一定接受為新解，但是 則接受為新解的機隨著 的變大而越小。,Simulated Annealing,21,模擬退火法的程圖,初使化設定,隨機產生一個初始解,擾動產生一個新解,是否接受?,修改目前解,降溫,縮減溫度,是否達到中止條

10、件?,最佳解,No,Yes,Yes,Yes,No,No,Simulated Annealing,22,其他的問題(1/4),價值函數（Cost Function） 用來評估解的質量。 Delta Evaluation 求某解與其鄰近點的價值。 Partial Evaluation 不需額外產生的計算結果就可以判斷出來解的價值。,Simulated Annealing,23,其他的問題（2/4）,價值函數（Cost Function） Hard Constraints 在不違背合適解的條件下，所提出的強制規(guī)定。 Soft Constraints 無論這種解是否違背條件，都算是合適解。 HardC

11、onstraints會給一個很大的weight SoftConstraints則是情況給予不同的weight,Simulated Annealing,24,其他的問題（3/4）,鄰近點的結構（Neighborhood Structure） 有些結構是對稱性的，即可以從A狀態(tài)到B狀態(tài)，也可以從B狀態(tài)到A狀態(tài)。 條件較弱（結構較松散）的有穩(wěn)定的收斂。 條件定的好，就可以使得在各種狀態(tài)之下都可以到達另一種狀態(tài)。,Simulated Annealing,25,其他的問題（4/4）,所有解的空間（The Solution Space） 空間小，可以展開搜尋。 若允許不合適的解也存在的話就會加大搜尋空間。

12、 我們想辦法取一個適當值，期望能快速搜尋，又可避免在不利的情況下沒有好的進展。,Simulated Annealing,26,提高效能,初始化（Initialization） 將原本用隨機數取初始值的方式改為盡可能找出一有用的起始點。 結合（Combine） 可將仿真退火法配合其他算法應用于問題上。,Simulated Annealing,27,算法修正(1/2),可接受的機率（Acceptance Probability） 少計算exponential會加快速度 建立一個可查詢各種值的table 冷卻（Cooling） 花一些時間找尋最佳溫度（包括最終溫度、溫差）,Simulated Annealing,28,算法修正（2/2）,鄰近點（Neighborhood） 對于不好的鄰近點給予一個懲罰值。 價值函數（Cost Functio