超啓發式算法

近年來隨着智能計算領域的發展，出現了一類被稱為超啓發式算法（Hyper-Heuristic Algorithm）的新算法類型。最近幾年，智能計算領域的著名國際會議（GECCO 2009, CEC 2010，PPSN 2010）[1]分別舉辦了專門針對超啓發式算法的workshop或session。從GECCO 2011開始，超啓發式算法的相關研究正式成為該會議的一個領域（self* search-new frontier track）。國際智能計算領域的兩大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分別安排了專刊，着重介紹與超啓發式算法有關的研究進展。

定義1. 超啓發式算法提供了某種高層策略（High-Level Strategy，HLS），通過操縱或管理一組低層啓發式算法（Low-Level Heuristics, LLH），以獲得新啓發式算法。這些新啓發式算法則被運用於求解各類NP-難解問題。

圖1給出了超啓發式算法的概念模型示意圖。從圖1中可以看出，超啓發式算法分為兩個層面：在問題域層面上應用領域專家需根據本人的背景知識，提供問題的定義、評估函數等信息和一系列LLH；而在高層策略層面上，智能計算專家則通過設計高效的操縱管理機制，利用問題域所提供的問題特徵信息和LLH算法庫，構造新的啓發式算法。因為這兩個層面之間實現了嚴格的領域屏蔽，僅僅需要修改問題域的問題定義和LLH、評估函數等領域有關信息，一種超啓發式算法就可以被快速地遷移到新的問題上。因此，超啓發式算法特別適合求解跨領域的問題。需要引起注意的是，研究超啓發式算法的目標並不是取代智能計算專家，而是如何將智能計算技術更快地推廣到更多的應用領域，同時有效地降低啓發式算法的設計難度，從而將領域專家和智能計算專家的研究重點有效地劃分開。根據圖1 可知，智能計算專家在超啓發式算法設計中主要關注於高層策略，而領域專家則重點研究問題的目標函數和LLH等。

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

該類超啓發式算法是從給定的集合中隨機選擇LLH，組合形成新的啓發式算法。這類超啓發式算法的特點是結構簡單、容易實現。同時，這類超啓發式算法也經常被用作基準（benchmark），以評價其他類型的超啓發式算法性能。該類超啓發式算法可以進一步細分為純隨機（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的取捨

（1）超啓發式算法與啓發式算法均是為了求解問題實例而提出的。因此，問題實例可以視為超啓發式算法和啓發式算法兩者共同的處理對象。

（2）超啓發式算法與啓發式算法都可能包含有參數。在傳統的啓發式算法中，可能有大量的參數需要調製。比如遺傳算法中的種羣規模、交叉率、變異率、迭代次數等。而超啓發式算法的參數來源有兩個層面，在LLH和高層啓發式方法中均可能有參數需要調製。

（3）超啓發式算法與啓發式算法都是運行在搜索空間上，但是各自的搜索空間構成不同：傳統啓發式算法是工作在由問題實例的解構成的搜索空間上；而超啓發式算法運行在一個由啓發式算法構成的搜索空間上，該搜索空間上的每一個頂點代表一系列LLH的組合。因此，超啓發式算法的抽象程度高於傳統啓發式算法。

（4）超啓發式算法與啓發式算法均可以應用到各種不同的領域，但是它們各自對於問題領域知識的需求是不同的。啓發式算法設計通常需要依賴於問題的特徵；而超啓發式算法的高層啓發式方法部分則幾乎不依賴於問題的領域知識，LLH則是與問題的領域知識緊密相關的。目前啓發式算法的應用已經十分廣泛，而超啓發式算法由於歷史較短，還主要侷限在部分常見的組合優化問題上。

超啓發式算法與啓發式算法多視角對比

^[1]