Simulated Annealing 報告者:李怡緯 OPLAB in NTUIM.

Presentation on theme: "Simulated Annealing 報告者:李怡緯 OPLAB in NTUIM."— Presentation transcript:

1 Simulated Annealing 報告者:李怡緯 OPLAB in NTUIM

2 agenda Hill climbing V.S. Simulated Annealing(SA) SA歷史與簡介 SA之流程
SA研討:如何處理TSP SA之目前應用 結論

3 agenda Hill climbing V.S. Simulated Annealing(SA) SA歷史與簡介 SA之流程
SA研討:如何處理TSP SA之目前應用 結論

4 Hill Climbing In tree structure，DFS search。
Which node should be selected to expand? Greedy method。

5 Scheme of hill climbing
Step1:form a 1-element stack consisting of root node. Step2:test to see if the top element in the stack is a goal node. Step3:remove the top element from the stack and expand the element. Add the descendants of the element into the stack ordered by the evaluation function Step4:if the list is empty, then failure. Otherwise, go to Step2.

6 8-puzzle problem evaluation function f(n) = w(n)
where w(n) is # of misplaced tiles in node n 2 3 5 1 4 6 8 7 1 2 3 8 4 7 6 5 Initial arrangement Goal state of the puzzle

7

8 Simulated Annealing vs. Hill Climbing
Hill Climbing select best in its level. local optimal. Simulated Annealing: random search neighbor node. If more appropriate than now, then taken from. According to the possibility to decide whether taken from. 若找到的點比立足點好，則取之。 否則依照機率決定是否取之。

9 agenda Hill climbing V.S. Simulated Annealing(SA) SA歷史與簡介 SA之流程
SA研討:如何處理TSP SA之目前應用 結論

10 SA之歷史 最早的想法是由N.Metropolis 等人於1953 年所提出，使用蒙地卡羅模擬（Monte Carlo Simulated）計算多分子系統中分子的能量分佈，在當時並沒有受到重視。 美國物理學家默察波利斯

11 SA之歷史 直到1983 年由Kirkpatrick et al. 在<Science>上發表（Optimization by Simulated Annealing），提出的隨機搜尋技巧，利用此方法來求解的組合最佳化問題時，才使此演算法受到重視。 幾乎同時，歐洲物理學家V.Carny也發表了幾乎相同的發現，但兩者是各自獨立發現的。 美國IBM公司物理學家科克派特瑞克

12 簡介 在熱力學上，annealing指物體逐漸降溫的物理現象。 大自然在緩慢降溫時，可「找到」最低能量狀態：結晶。
但是，如果過程急就章，快速降溫（亦稱「淬煉」，quenching）時，會導致不是最低能態的非晶形。

13 簡介 將材料加熱後再經特定速率冷卻。 增加晶體體積，減少晶格缺陷。 加熱後粒子隨機移動，有可能會停留在比原內能較低的位置。

14 簡介 將熱力學套用到統計學。 每一粒子帶有能量。 空間中每一點也帶有能量(evaluation function)
選定一鄰居並計算到達他之機率。

15 簡介 它能「忍讓一時」才得以「顧全大局」，最後終於求得最小值。這也是為何使用此方法需要一些「嘗試錯誤」，各方向到處試試升降，若實在試不出，則表示確已抵達真正最小解。以數學證明，它漸近地（asymptotically）可找到最小值（概率為1

16 agenda Hill climbing V.S. Simulated Annealing(SA) SA歷史與簡介 SA之流程
SA研討:如何處理TSP SA之目前應用 結論

17 模擬退火法的流程圖 初使化設定 隨機產生一個初始解 擾動產生一個新解 No 是否接受? Yes 修改目前解 降溫 Yes 縮減溫度 No
是否達到中止條件? Yes 最佳解

18 SA之降溫流程 初始溫度 溫度要夠高才能移動到任何的狀態。 溫度不能太高，否則會導致在一段時間內皆用亂數在湊解答。
如果可以知道檢測函數的最大值就可以找到最好的初始溫度。 18

19 模擬退火法的流程圖 初使化設定 隨機產生一個初始解 擾動產生一個新解 No 是否接受? Yes 修改目前解 降溫 Yes 縮減溫度 No
是否達到中止條件? Yes 最佳解

20 SA之判別標準 須先設定參數 X 及其函數值 擾動後之解 X’及其函數值

21 模擬退火法的流程圖 初使化設定 隨機產生一個初始解 擾動產生一個新解 No 是否接受? Yes 修改目前解 降溫 Yes 縮減溫度 No
是否達到中止條件? Yes 最佳解

22 SA之判別標準 根據熱力學公式，在溫度為t時 能量差為: P(ΔE)=exp(-ΔE / kt) (k:玻茲曼常數)
轉換到模擬退火法，則變成: P=exp(-c / t)>r c: 評估函數的差 r: 0~1之間的亂數 玻耳茲曼常數

23 SA之判別標準 參照 若能量差<=0，則將擾動解取代原解。 若能量差>0，則依機率判別是否取代之。
並非像HILLCLIMBING否決 而是以一定機率取代之

24 模擬退火法的流程圖 初使化設定 隨機產生一個初始解 擾動產生一個新解 No 是否接受? Yes 修改目前解 降溫 Yes 縮減溫度 No
是否達到中止條件? Yes 最佳解

25 SA之降溫時機 最直接的方式是設定一個固定長度，但此長度與問題規模有關，如在1992 年Kouvelis 與Chiang 將其設定為鄰近解個數之比率。 此外亦可設定降溫時機為移轉接受次數已達一定值，如Heragu 以及 Alfa（1992）所使用的方式便是。

26 SA之降溫幅度 每次降低溫度的差距以及在同一溫度反覆尋找最適解會導致指數般成長的搜尋空間。 1.Linear: Temp=Temp-x
2.Geometry: Temp=Temp*y (y約0.8~0.99為佳)

27 模擬退火法的流程圖 初使化設定 隨機產生一個初始解 擾動產生一個新解 No 是否接受? Yes 修改目前解 降溫 Yes 縮減溫度 No
是否達到中止條件? Yes 最佳解

28 SA之降溫流程 終止條件 通常是零，但會耗掉許多模擬時間。 另一種終結法為限定退火次數不超過預設值。
若退火超過一定次數仍未改善解或轉移比率低於一定值，也宣告終止退火。

29 agenda Hill climbing V.S. Simulated Annealing(SA) SA歷史與簡介 SA之流程
SA研討:如何處理TSP SA之目前應用 結論

30 Case研討: Traveling Salesman Problem
Problem Definition: TSP is the problem of a salesman who wants to find, starting from his home town, a shortest possible trip through a given set of customer cities and to return to its home town; visiting exactly once each city.

31 random select 2 edges in a tour
該如何使用SA處理之? random select 2 edges in a tour West Side East Side

32 以SA計算是否由62、 73取代67、31

33

34 agenda Hill climbing V.S. Simulated Annealing(SA) SA歷史與簡介 SA之流程
SA研討:如何處理TSP SA之目前應用 結論

35 應用 VLSI computer-aided design。 影像處理。 Neural Network。 平衡運算。
也有生物學上的應用例子。 模擬退火方法有很多實際應用的例子

36 Meta-heuristics 禁制搜尋法(Tabu Search, TS) 基因演算法(Genetic Algorithm, GA)
門檻接受法(Threshold Accepting, TA) 類神經網路(Neural Network, NN) 蟻群演算法(Ant Colony Optimization, ACO)

37 agenda Hill climbing V.S. Simulated Annealing(SA) SA歷史與簡介 SA之流程
SA研討:如何處理TSP SA之目前應用 結論

38 結論 模擬退火法已經證明可能收斂出最好解。 要花較多的時間去搜尋各種解。 各參數的設定可自由控制。 在時間與解之品質做trade off
自從模擬退火方法發表以來，已有不少「改進」的新方法出籠。

39 Thanks for your listening