基本介紹
概括內容,元啟發式算法,分類,起源與歷史,算法機制特點,超啟發式算法,改進新算法,發展方向,
概括內容
計算機科學的兩大基礎目標，就是發現可證明其執行效率良好且可得最佳解或次佳解的算法。而啟發式算法則試圖一次提供一或全部目標。 例如它常能發現很不錯的解，但也沒辦法證明它不會得到較壞的解；它通常可在合理時間解出答案，但也沒辦法知道它是否每次都可以這樣的速度求解。
有時候人們會發現在某些特殊情況下，啟發式算法會得到很壞的答案或效率極差，然而造成那些特殊情況的數據組合，也許永遠不會在現實世界出現。因此現實世界中啟發式算法常用來解決問題。啟發式算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。
近年來隨著智慧型計算領域的發展，出現了一類被稱為超啟發式算法（Hyper-Heuristic Algorithm）的新算法類型。最近幾年，智慧型計算領域的著名國際會議（GECCO 2009, CEC 2010，PPSN 2010）分別舉辦了專門針對超啟發式算法的workshop或session。從GECCO 2011開始，超啟發式算法的相關研究正式成為該會議的一個領域（self* search-new frontier track）。國際智慧型計算領域的兩大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分別安排了專刊，著重介紹與超啟發式算法有關的研究進展。
元啟發式算法
元啟發式算法主要指一類通用型的啟發式算法，這類算法的最佳化機理不過分依賴於算法的組織結構信息，可以廣泛的套用到函式的組合最佳化和函式計算中。
分類
現代啟發式算法的各種具體實現方法是相對獨立提出的,相互之間有一定的區別。從歷史上看,現代啟發式算法主要有:模擬退火算法(SA)、遺傳算法(GA)、列表搜尋算法(ST)、進化規劃(EP)、進化策略(ES)、蟻群算法(ACA)、人工神經網路(ANN)。如果從決策變數編碼方案的不同來考慮,可以有固定長度的編碼(靜態編碼)和可變長度的編碼(動態編碼)兩種方案。SA是基於Monte Carlo算法疊代求解的一種全局機率型搜尋算法,具有區別於常規算法的搜尋機制和特點,它是借鑑了熱力學的退火原理建立起來的。GA是借鑑“優勝劣汰”生物進化與遺傳思想而提出的一種全局性並行搜尋算法。EP和ES不像GA注重父代與子代遺傳細節而側重父代與子代表現行為上的聯繫(強調物種層的行為變化)。TS是一種具有記憶功能的全局逐步最佳化算法。ACA是受到人們對自然界中真實的蟻群集體行為研究成果的啟發而提出的一種基於種群的模擬進化算法,屬於隨機搜尋算法。
起源與歷史
上世紀50年代中期創立了仿生學,許多科學家從生物中尋求新的用於人造系統的靈感。一些科學家分別獨立地從生物進化的機理中發展出適合於現實世界複雜問題最佳化的模擬進化算法。SA是由Kirkprtricrk等人首先用於組合最佳化問題,它克服了爬山法(HC)極易陷人局部解的缺點。近年來SA的主要發展方向是與其他算法結合構成新的混合算法來充分發揮其突跳性和可避免局部解的特點。ACA是最近幾年才提出的一種新型的模擬進化算法,由義大利學者Dirgo等人首先提出來,他們稱之為蟻群算法，並用該方法求解旅行商問題(TSp)、指派問題、job一shop調度問題，取得了一系列較好的實驗結果。受其影響，ACA逐漸引起其他研究者的注意，並用該算法解決一些實際問題。
算法機制特點
現代啟發式算法在最佳化機制方面存在一定的差異,但在最佳化流程上卻具有較大的相似性,均是一種“鄰域搜尋”結構。算法都是從一個(一組)初始解出發,在算法的關鍵參數的控制下通過鄰域函式產生若干鄰域解,按接受準則(確定性、機率性或混沌方式)更新當前狀態,而後按關鍵參數修改準則調整關鍵參數。如此重複上述搜尋步驟直到滿足算法的收斂準則,最終得到問題的最佳化結果。
算法類型 | 首次使用者 | 機制 | 最佳化流程 | 關鍵參數 | 收斂準則 |
SA | Kirkpatrick | 基於蒙特卡洛進行串列搜尋最佳化 | 鄰域搜尋 | 初始溫度、退溫函式 | 疊代次數、搜尋序列均值與極值的最小偏差 |
GA | Holland | 基於生物進化和遺傳進行全局最最佳化 | 鄰域搜尋 | 種群數目、複製、交叉、變異機率 | 同上 |
TS | Glove | 記憶功能的全局逐步最佳化算法 | 鄰域搜尋 | 列表大小、鄰域函式結構與數量 | 同上 |
ACA | Dorigo | 強化學習功能的全局性並行最佳化算法 | 鄰域搜尋 | 殘留信息量、信息增量、積累量、啟發或消失因子 | 同上 |
超啟發式算法
由於超啟發式算法的研究尚處於起步階段，對於已有的各種超啟發式算法，國際上尚未形成一致的分類方法。按照高層策略的機制不同，現有超啟發式算法可以大致分為4類：基於隨機選擇、基於貪心算法、基於元啟發式算法和基於學習的超啟發式算法。
基於隨機選擇的超啟發式算法
該類超啟發式算法是從給定的集合中隨機選擇LLH，組合形成新的啟發式算法。這類超啟發式算法的特點是結構簡單、容易實現。同時，這類超啟發式算法也經常被用作基準（bench mark），以評價其他類型的超啟發式算法性能。該類超啟發式算法可以進一步細分為純隨機（pure random）、帶延遲接受條件的隨機（random with late acceptance）等。
基於貪心策略的超啟發式算法
該類超啟發式算法在構造新啟發式算法時，每次都挑選那些能夠最大化改進當前（問題實例）解的LLH。由於每次挑選LLH時需要評估所有LLH，故此該類方法的執行效率低於基於隨機選擇的超啟發式算法。
基於元啟發式算法的超啟發式算法
該類超啟發式算法採用現有的元啟發式算法（作為高層策略）來選擇LLH。由於元啟發式算法研究相對充分，因此這類超啟發式算法的研究成果相對較多。根據所採用的元啟發式算法，該類超啟發式算法可以細分為基於禁忌搜尋、基於遺傳算法、基於遺傳編程、基於蟻群算法和基於GRASP with path-relinking等。
基於學習的超啟發式算法
該類超啟發式算法在構造新啟發式算法時，採用一定學習機制，根據現有各種LLH的歷史信息來決定採納哪一個LLH。根據LLH歷史信息來源的不同，該類超啟發式算法可以進一步分為線上學習（on-line learning）和離線學習（off-line learning）兩種：前者是指LLH的歷史信息是在求解當前實例過程中積累下來的；後者通常將實例集合分為訓練實例和待求解實例兩部分，訓練實例主要用於積累LLH的歷史信息，而待求解實例則可以根據這些歷史信息來決定LLH的取捨
改進新算法
如何找到一個分叉率較少又通用的合理啟發式算法，已被人工智慧社群深入探究過，部分問題的解答的代價通常可以評估解決整個問題的代價，通常很合理。例如一個10-puzzle拼盤，解題的代價應該與將1到5的方塊移回正確位置的代價差不多。通常解題者會先建立一個儲存部份問題所需代價的模式資料庫(pattern database)以評估問題，解決較易的近似問題通常可以拿來合理評估原先問題。例如曼哈頓距離是一個簡單版本的n-puzzle問題，因為我們假設可以獨立移動一個方塊到我們想要的位置，而暫不考慮會移到其他方塊的問題。 給我們一群合理的啟發式函式h1(n),h2(n),...,hi(n)，而函式h(n) = max{h1(n),h2(n),...,hi(n)}則是個可預測這些函式的啟發式函式。 一個在1993年由A.E. Prieditis寫出的程式ABSOLVER就運用了這些技術，這個程式可以自動為問題產生啟發式算法。ABSOLVER為8-puzzle產生的啟發式算法優於任何先前存在的！而且它也發現了第一個有用的解魔術方塊的啟發式程式。
為了進一步提高最佳化質量和搜尋效率,近年來發展了一些新的搜尋機制和並行、混合搜尋算法。由於現代啟發式算法結構的開放性、與問題無關性,使得各算法之間容易進行相互綜合。研究表明,新型的算法結構或混合算法對算法性能和效率有較大幅度的改善。此外,結合實際套用或理論問題對算法進行對比研究也是算法研究中值得關注的內容。它有助於分析算法的性能和適用域,且由比較可發現各算法獨特的優點和不足,以便改進算法結構、參數及操作運算元,發展各種可能的高效混合算法。
發展方向
現代啟發式算法的研究,在理論方面還處於不斷發展中,新思想和新方法仍不斷出現。分析目前的現狀和發展方向,其發展方向有如下幾個方面:
(1)整理歸納分散的研究成果,建立統一的算法體系結構。
(3)開發新的混合式算法及開展現有算法改進方面的研究。
