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

Slides:



Advertisements
Similar presentations
Exercise 1 EECS, Peking University Exercise in Query Processing.
Advertisements

2014 年 同济大学研究生数模讲座 数学建模中的常用算法 陈雄达
第七組古文閱讀報告 組長:秀惠 組員:孟筑、雅曼、雅文、盈蓁. 《朱買臣苦學有成》之原文翻譯 朱買臣,字翁子,吳人也。 朱買臣,字翁子,吳國人。 家貧,好讀書,不治產業,常刈(一ˋ)薪 樵,賣以給 (ㄐㄧ ˇ ) 食。 家裡雖然很窮困,但是他還是很喜歡讀書,因 不懂得如何治理產業,只能靠著上山砍材去城.
你不知道的 3M P 班級 : 創意二甲 指導老師 : 袁又華 組長 : 林毓茹 組員 : 林以軒 林欣汝 陳盈羽 陳怡如 劉玉婷.
台灣海域珊瑚礁的分佈概況 地處北半球亞熱帶的台灣,由於四面環海,因此擁 有許多美麗的海岸景觀,除了東海岸壯闊的岩岸、西海 岸平緩的沙岸以外,也擁有美麗、珍貴的珊瑚礁海岸。 根據調查結果顯示,寶島台灣的珊瑚礁,大多分佈在綠 島、蘭嶼、小琉球、澎湖群島這些離島,以及本島的恆 春半島、東北角、東部海岸的三仙台等地。
饭水分离 阴阳饮食法 拿掉饭桌上的汤水 创造生命的奇迹 作者/李祥文 八正文化出版
使用說明 高年級 破解賽恩思 (Science)密碼 編輯群 明湖國小 吳立明 老師 李惠雯 老師 林宜璇 老師.
Introduction to Computer Science
An Introduction to Applied AI
11010: Tic-Tac-Tough ★★★★☆ 題組: Problem Set Archive with Online Judge
動畫與遊戲設計 Data structure and artificial intelligent
我在哈佛、麥肯錫 學到的一流工作術 富坂美織◎著.
教學經驗分享 正修科大 資訊管理系(所) 夏自立.
VS 兒童及少年身心發展 幼保三甲 幼兒期 青少年期 4A1I0014 陳佳瑩 4A1I0023 尤秀惠
第五章 思维与想象 苏州大学教育学院心理系 吴继霞
《高级人工智能》参考书目 马少平,朱小燕。人工智能。清华大学出版社。 蔡自兴,徐光祐。人工智能及其应用。清华大学出版社。
鞘翅目 生科四乙 蘇俊融.
整合·创新·提升 -浙江大学图书馆学科分馆的探索与实践
我的未来不是梦 参赛者——陈艳祥.
Network Optimization: Models & Algorithms
Performance Evaluation
第三章 搜索技术 第一节 引言 一、搜索 对于无成熟方法可用的问题求解,必须一步步地摸索求解,这种问题求解过程就是搜索。
核心价值观记心中 主题班会
班级小插曲.
第Ⅱ部分 问题求解 第4章 超越经典搜索 中国科大 计算机学院.
關愛 親情無價 關愛無價.
Mode Selection and Resource Allocation for Deviceto- Device Communications in 5G Cellular Networks 林柏毅 羅傑文.
Minimum Spanning Trees
Digital Terrain Modeling
The Greedy Method.
第4章 网络互联与广域网 4.1 网络互联概述 4.2 网络互联设备 4.3 广域网 4.4 ISDN 4.5 DDN
Course 9 NP Theory序論 An Introduction to the Theory of NP
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi
SpringerLink 新平台介绍.
ZEEV ZEITIN Delft University of Technology, Netherlands
指導教授:金仲達 老師 成員: 陳俊佐 陳惠雯 李怡緯 鄧雅文 劉哲維 鍾逸帆
国际经济贸易学院 2015暑期 社会实践活动总结 本期亮点.
樹 2 Michael Tsai 2013/3/26.
Network Design in the Supply Chain (Part1)
感謝同學們在加分題建議. 我會好好研讀+反省~
Monte Carlo模拟 引言(introduction) 均匀随机数的产生(Random number generation)
计算机问题求解 – 论题3-2 - 贪心算法 2018年09月18日.
贈與契約.
计算机问题求解—论题4.9 随机算法的概念 陶先平 2017年5月15日.
3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19.
Simulated Annealing Algorithm,SAA
VRP工具or-tools调研 王羚宇
Speaker: Wang,Song-Ferng Advisor: Dr. Ho-Ting Wu 2015/7/6
计算机问题求解 – 论题 算法方法 2016年11月28日.
兒少保護通報處理流程介紹 臺中市家庭暴力及性侵害防治中心 陳秀婷/張美慧 社工督導員 2012/10/19.
Course 10 削減與搜尋 Prune and Search
SpringerLink 新平台介绍.
講師:郭育倫 第2章 效能分析 講師:郭育倫
Disjoint Sets Michael Tsai 2013/05/14.
Course 8 回溯、分枝與限制 Backtracking, Branch-and-Bound
演算法分析 (Analyzing Algorithms)
Efficient Query Relaxation for Complex Relationship Search on Graph Data 李舒馨
最短通路问题.
赵才荣 同济大学,电子与信息工程学院,智信馆410室
SLIQ:一种快速可伸缩分类器 Manish Mehta, Rakesh Agrawal, Jorma Rissanen IBM Almaden Research Center, 1996 报告人:郭新涛
購料平台訂購系統 教育訓練_操作手冊 製作:台塑購物網
國立高雄第一科技大學 我們拿什麼 來抹臉 組長:電子3A 張玫琪 組員:運籌1B 吳若萱
Joy? 喜乐? Yes! It’s Possible. 是!这是可能的。.
Monte Carlo模拟 引言(introduction) 均匀随机数的产生(Random number generation)
Class imbalance in Classification
Data Structure.
生產與作業管理CHAPTER13 預測 指導老師:盧淵源 教授 組員 M 丁建忠 M 陳志峰
物流配銷系統下區位途程整合存貨模式之研究
JAVA 程式設計與資料結構 第二十一章 Graph.
Presentation transcript:

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

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

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

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

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.

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

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. 若找到的點比立足點好,則取之。 否則依照機率決定是否取之。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

Thanks for your listening