啓發式算法

計算機科學的兩大基礎目標，就是發現可證明其執行效率良好且可得最佳解或次佳解的算法。而啓發式算法則試圖一次提供一或全部目標。 例如它常能發現很不錯的解，但也沒辦法證明它不會得到較壞的解；它通常可在合理時間解出答案，但也沒辦法知道它是否每次都可以這樣的速度求解。

有時候人們會發現在某些特殊情況下，啓發式算法會得到很壞的答案或效率極差，然而造成那些特殊情況的數據組合，也許永遠不會在現實世界出現。因此現實世界中啓發式算法常用來解決問題。啓發式算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。

有一類的通用啓發式策略稱為元啓發式算法（metaheuristic），通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上，但不能保證效率。

近年來隨着智能計算領域的發展，出現了一類被稱為超啓發式算法（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年分別安排了專刊，着重介紹與超啓發式算法有關的研究進展。

元啓發式算法主要指一類通用型的啓發式算法，這類算法的優化機理不過分依賴於算法的組織結構信息，可以廣泛的應用到函數的組合優化和函數計算中。 ^[2] 

現代啓發式算法的各種具體實現方法是相對獨立提出的,相互之間有一定的區別。從歷史上看，現代啓發式算法主要有：模擬退火算法(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逐漸引起其他研究者的注意，並用該算法解決一些實際問題。 ^[3] 

現代啓發式算法在優化機制方面存在一定的差異，但在優化流程上卻具有較大的相似性，均是一種“鄰域搜索”結構。算法都是從一個(一組)初始解出發，在算法的關鍵參數的控制下通過鄰域函數產生若干鄰域解，按接受準則(確定性、概率性或混沌方式)更新當前狀態，而後按關鍵參數修改準則調整關鍵參數。如此重複上述搜索步驟直到滿足算法的收斂準則，最終得到問題的優化結果。

超啓發式算法是由一系列的啓發式算法組合而成的，超啓發式算法是智能化程度更高的算法，每一種超啓發式算法有其自己的機制。超啓發式算法分為兩個層面：在問題域層面上應用領域專家需根據本人的背景知識，提供問題的定義、評估函數等信息和一系列低層啓發式算法(Low-Level Heuristics)；而在高層策略層面上，智能計算專家則通過設計高效的操縱管理機制，利用問題域所提供的問題特徵信息和低層啓發式算法算法庫，構造新的啓發式算法。 ^[7] 

由於超啓發式算法的研究尚處於起步階段，對於已有的各種超啓發式算法，國際上尚未形成一致的分類方法。按照高層策略的機制不同，現有超啓發式算法可以大致分為4類：基於隨機選擇、基於貪心算法、基於元啓發式算法和基於學習的超啓發式算法。 ^[4] 

該類超啓發式算法是從給定的集合中隨機選擇LLH，組合形成新的啓發式算法。這類超啓發式算法的特點是結構簡單、容易實現。同時，這類超啓發式算法也經常被用作基準（bench mark），以評價其他類型的超啓發式算法性能。該類超啓發式算法可以進一步細分為純隨機（pure random）、帶延遲接受條件的隨機（random with late acceptance）等。

該類超啓發式算法在構造新啓發式算法時，每次都挑選那些能夠最大化改進當前（問題實例）解的LLH。由於每次挑選LLH時需要評估所有LLH，故此該類方法的執行效率低於基於隨機選擇的超啓發式算法。

該類超啓發式算法採用現有的元啓發式算法（作為高層策略）來選擇LLH。由於元啓發式算法研究相對充分，因此這類超啓發式算法的研究成果相對較多。根據所採用的元啓發式算法，該類超啓發式算法可以細分為基於禁忌搜索、基於遺傳算法、基於遺傳編程、基於蟻羣算法和基於GRASP with path-relinking等。 ^[5] 

該類超啓發式算法在構造新啓發式算法時，採用一定學習機制，根據現有各種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產生的啓發式算法優於任何先前存在的。而且它也發現了第一個有用的解魔術方塊的啓發式程式。

為了進一步提高優化質量和搜索效率，近年來發展了一些新的搜索機制和並行、混合搜索算法。由於現代啓發式算法結構的開放性、與問題無關性，使得各算法之間容易進行相互綜合。研究表明,新型的算法結構或混合算法對算法性能和效率有較大幅度的改善。此外,結合實際應用或理論問題對算法進行對比研究也是算法研究中值得關注的內容。它有助於分析算法的性能和適用域，且由比較可發現各算法獨特的優點和不足，以便改進算法結構、參數及操作算子，發展各種可能的高效混合算法。

現代啓發式算法的研究,在理論方面還處於不斷髮展中，新思想和新方法仍不斷出現。分析目前的現狀和發展方向,其發展方向有如下幾個方面： ^[6] 

(1)整理歸納分散的研究成果,建立統一的算法體系結構。

(2)在現有的數學方法(模式定理、編碼策略、馬爾可夫鏈理論、維數分析理論、複製遺傳算法理論、二次動力系統理論、傅立葉分析理論、分離函數理論、Walsh函數分析理論)的基礎上尋求新的數學工具。

(3)開發新的混合式算法及開展現有算法改進方面的研究。

(4)研究高效並行或分佈式優化算法。