爬山演算法

最佳化方法 簡介 歷史 確定性搜尋 基本搜尋法 逐漸深入法 α-β 修剪 A* 搜尋法 隨機搜尋 單粒子隨機搜尋 貪婪演算法 爬山演算法 模擬退火法 禁忌搜尋法 多粒子隨機搜尋 演化策略 鳥群演算法 蟻群演算法 蜂群演算法 程式實作 基本搜尋法 爬山演算法 基因演算法 鳥群演算法 訊息 相關網站 參考文獻 最新修改 簡體版 English

文章 簡介 爬山演算法 HC (Hill-Climbing Algorithm) 是單粒子型算法中最簡單的一種，實作相當容易，且執行速度很快。因此，經常被用來作為各種最佳化演算法的比較基準。但是，由於爬山演算法只尋找鄰近的點進行比較，而且不允許向較差的方向行走，這使得爬山演算法很容易落入山谷區而無法跳出。因而喪失找到更好解的機會。 爬山演算法 Algorithm Hill-Climbing(pi) p = pi // 設定粒子 p 為起始粒子 pi while not isEnd() pn = move(p) //選擇粒子p的鄰居pn if pn.energy()<=p.energy() //能量更低，就接受 p = pn; End Algorithm 模擬退火 SA (Simulated annealing) 演算法改進了爬山演算法的部分缺點，採用以溫度調控的機率特性，讓爬山演算法有機會跳脫較差的區域，因而找到更好的解。但是，當較好的區域距離目前所在地區較遠時，模擬退火演算法通常難以逆向爬升脫離較大的山谷。 文獻回顧 人工智慧中有為數眾多的隨機式最佳化演算法，像是爬山演算法、模擬退火法、遺傳演算法、蟻群演算法、粒子群演算法等等。如果用粒子數量進行區分，則可以將上述演算法區分為『單粒子型』與『多粒子型』兩類。其中，『爬山演算法』、『模擬退火法』、『禁忌搜尋法』屬於『單粒子型的演算法，而『遺傳演算法』、『蟻群演算法』、『粒子群演算法』、『蜂群演算法』則屬於多粒子型的演算法。 雖然目前的學術研究大多集中在多粒子型的演算法上，但是卻很難分析這些演算法的好壞，這是由於多粒子系統天生的複雜性所造成的。因此，我們選擇回到單粒子系統上，以實驗的方式釐清單粒子演算法的行為，期望能建立清楚的理論架構，以便讓隨機式演算法具有紮實的科學基礎。 目前的學術界對這些試圖跳脫區域最佳解之研究，通常被稱為『後設啟發式解法』（Meta-heuristics）(或譯為巨集啟發式解法) (Glover and Laguna, 1997)，這些方法乃是以傳統區域搜尋法 (Local Search) 為核心架構，結合高階的搜尋策略（Meta-strategies），以指導其跳脫局部最佳解的束縛而找到更好的解（Osman and Kelly,1996）。 我們所知的單粒子演算法包含 爬山演算法 (Hill Climbing)、模擬退火法 (Simulated Annealing)（Kirkpatrick et al., 1983）、禁忌搜尋法 (Tabu Search) （Glover,1989,1990）、門檻值接受法（Threshold Accepting）（Dueck and Scheuer, 1990）、大洪水法（Great Deluge Algorithm）（Dueck, 1993）、記錄更新法（Record-to-Record Travel）（Deuck, 1993）、噪音擾動法（Noising Method）（如可參考Charon and Hurdy, 1993 或韓復華與卓裕仁, 1996）、兩極跳躍法（Flip-Flop Method）（如可參考韓復華等人, 1997) ，搜尋空間平滑法（Search Space Smoothing）（如可參考Gu and Huang , 1994 或韓復華與卓裕仁, 1996）等。 目前，我們的研究重點是單粒子的爬山演算法，並且以二次規畫問題作為實驗標的。 爬山跳躍演算法 HCJ 為了讓爬山演算法具有較大的機會跳出山谷區，我們設計了爬山跳躍演算法 HCJ (Hill Climbing With Jumping Strategy)，此演算法企圖讓爬山演算法的跳躍步伐隨著改良失敗的次數而增大，以便在失敗次數很多時能採用較大的步伐跳出山谷，以便進入更低的山谷區。 我們用三個二次規畫的問題 (G1, G7, G9) 進行測試。令人意外的是，傳統爬山演算法 HC 的表現其實相當好，HCJ 只在 G1 上表現得明顯比爬山演算法好，在 G9 上則只有稍微好一點點，但在 G7 上則反而比較差。 由於 HCJ 演算法實驗結果不盡理想，讓我們開始將焦點放在 G7 問題上，研究為何 HCJ 表現不好的原因。 原先我們以為 HCJ 無法找到最佳解是因為落入區域最佳解，卻又無法跳到更好的區域所造成的，但是由於 HCJ 會進行長程跳躍，但明顯的這些長程跳躍時無法跳入最佳解所在的區域中的低窪處。因此我們猜測 G7 的最佳解之低漥處可能很窄小，以致於讓 HCJ 錯過了這些低漥區。 為了驗證這個想法，我們用內插法列出 HCJ 最優解 (s1) 與 G7 (s2) 最佳解之間的點，並一一計算每個點的能量函數，結果發現有一條路徑可以從 s1 直接通往 s2，其中沒有任何阻礙。 這個結果令人費解，因為既然有路可以通往最佳解，但 HCJ 卻無法走過去，這並不純粹是運氣不好的問題。因為我們設定連續十萬次嘗試失敗才結束程式，只要任何一次進入該通道就可以繼續項目標邁進。但經歷了10 次的實驗都沒有任何一次可以找到 G7 的最佳解。而且，這個現象不是 HCJ 特有的，傳統的爬山演算法 HC 與 模擬退火法 SA 也都無法進入這些通道。 經過我們的理論分析，發現在高維空間中，要進入通道的機會相當小，這是為何上述單粒子演算法無法進入通道的原因。然而，經由文獻閱讀，我們發現像 PSO 這樣的多粒子演算法也無法找到 G7 問題的最佳解。這顯示了機率式的最佳化演算法在解決 G7 問題上具有盲點，這個盲點乃是由於高維空間中的狹小通道所造成的，於是我們再度思考，如何讓改良爬山演算法以便克服此一問題。 慣性速度對爬山演算法之影響 為了探索隨機式的爬山演算法 HC 無法找到 G7 最佳解的可能原因，我們必須更深入的理解為何會被狹長通道卡住這個問題。因此必須進行一些理論模型上的探索。由於在狹窄通道中 HC 必須連續很多次成功的向目標前進，最後才能達到目標的最佳解。但如果在這其中有任何一次失敗，就會導致程式中止於通道中。 假如，我們能讓 HC 的粒子具有某種慣性速度。那麼，只要能成功的進入通道，就能直接透過慣性穿過通道，直達最佳解。於是我們為 HC 加上速度，稱為爬山慣性演算法 HCV (Hill-Climbing With Velocity)。 以下表格修改自王政嵐的碩士論文 [4] ，這個表格簡單扼要的描述了各個方法所採用的策略，相當值得參考。 單粒子最佳化算法 演算法 避免陷入局部最佳解之策略 模擬退火法 SA 機率函數e−Δ做為接受暫劣解之機率，以跳脫局部最佳解。 門檻值接受法 TA 設定起始門檻值(可接受之劣化範圍)，並根據門檻數列收斂型態調整門檻值，故門檻值會逐漸遞減(相對門檻值)。 噪音擾動法 NM 使用隨機產生的噪音量，來擾動原來的目標函數，進而對擾動後的問題重新求解。 搜尋空間平滑法 SSS 透過一個標準化的轉換機制，將原本高低起伏的搜尋空間(亦即解空間)加以平滑，以減少局部最佳解的影響。 禁忌搜尋法 TS 透過短期記憶 (禁忌串列) 之應用，以跳脫局部最佳解。 兩極跳躍法 FF 當演算法進入某一局部最佳解的吸引範圍時，即翻轉目標函數，亦即將極大化的求解目標改為極小化(或反之)以快速脫離。 記錄更新法 RRT 以目前找到的最佳解成本值為其記錄值，若鄰近解之目標值在記錄值與誤差之間即被接受，以避免局部最佳解的吸引。 大洪水法 GDA 具有較包容(絕對門檻值)的接受法則可以在傳統搜尋過程中，接受較劣之可行解，跳脫局部最佳解。 多粒子最佳化算法 演算法 避免陷入局部最佳解之策略 蟻群算法 ACO 透過節線上費洛蒙濃度之差異，以多數螞蟻利用開發機制 （exploitation）往較佳解方向搜尋，並利用探索機制（exploration）增加其他解的搜尋機會，避免局部最佳解的吸引。 遺傳演算法 GA 解集合(包含可行解與不可行解)進行交配，並允許其發生突變產生下一代解集合，進行多點平行式搜尋避免受局部最佳解的吸引 粒子群演算法 PSO 透過追蹤鳥群群首與路徑中的最優解，以協調整體的走向 蜂群演算法 BA 透過散佈、評量、召募、搜尋的方式，協調群體行動 相關研究者 Dr. Abdel-Rahman Hedar 參考文獻 Local Search Methods TABU SEARCH , Fred Glover, Manuel Laguna An introduction to Tabu search Bibliography 1. Glover, F., and Laguna, M., “Tabu search, Kluwer Academic Publishers,” Massachusetts (1997). 2. Glover, F., “Tabu Search, Part I,” ORSA Journal on Computing Vol. 1, No. 3, pp.190-206 (1989). 3. Glover, F., “Tabu Search- Part II,” ORSA Journal on Computing, Vol. 2, No. 1, pp. 4-32 (1990). 4. Cheng-Lan Wang(王政嵐) 類螞蟻族群演算法於求解含凹形節線成本最小成本轉運問題之研究 , 國立中央大學土木工程研究所碩 士論文, 指導教授：顏上堯, 中華民國九十四年六月. 5. 以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究 中央大學 李旺蒼(Wang-Tsang Lee) 碩士論文 Facebook 留言 Facebook Wikidot Post preview: Close preview or Sign in as Wikidot user (will not be published) - + Help: wiki text quick reference 授權 本網頁的作者、授權與引用方式 作者 陳鍾誠，於金門大學資訊工程系，電子郵件：wt.ude.uqn|ccc#wt.ude.uqn|ccc，網站：http://ccckmit.wikidot.com。 授權 本文採用創作共用 (Creative Common) 3.0 版的 姓名標示─非商業性─相同方式分享 授權條款，歡迎轉載或修改使用，但若做為商業使用時必須取得授權，引用本文時請參考下列格式。 中文版 (APA格式) 陳鍾誠 (03 Nov 2009 01:17)，(網頁標題) 爬山演算法，(網站標題) 陳鍾誠的網站，取自 http://ccckmit.wikidot.com/so:hillclimbing ，網頁修改第 69 版。 英文版 (APA格式) Chung-Chen Chen (03 Nov 2009 01:17), Retrieved from http://ccckmit.wikidot.com/so:hillclimbing , Page Revision 69.