超啟發式算法與元啟發式算法有些類似,也提供了一種高層框架,通過調用底層啟發式運算元來實現對於問題的求解。與元啟發式算法相比,超啟發式算法更加側重如何將套用領域知識禁止在高層框架以外。通俗地說,超啟發式算法是“尋找啟發式算法的啟發式算法”。更加嚴格地定義如下:
定義1. 超啟發式算法提供了某種高層策略(High-Level Strategy,HLS),通過操縱或管理一組低層啟發式算法(Low-Level Heuristics, LLH),以獲得新啟發式算法。這些新啟發式算法則被運用於求解各類NP-難解問題。
上圖給出了超啟發式算法的概念模型示意圖。從圖中可以看出,超啟發式算法分為兩個層面:在問題域層面上套用領域專家需根據本人的背景知識,提供問題的定義、評估函式等信息和一系列LLH;而在高層策略層面上,智慧型計算專家則通過設計高效的操縱管理機制,利用問題域所提供的問題特徵信息和LLH算法庫,構造新的啟發式算法。因為這兩個層面之間實現了嚴格的領域禁止,僅僅需要修改問題域的問題定義和LLH、評估函式等領域有關信息,一種超啟發式算法就可以被快速地遷移到新的問題上。因此,超啟發式算法特別適合求解跨領域的問題。需要引起注意的是,研究超啟發式算法的目標並不是取代智慧型計算專家,而是如何將智慧型計算技術更快地推廣到更多的套用領域,同時有效第降低啟發式算法的設計難度,從而將領域專家和智慧型計算專家的研究重點有效地劃分開。根據圖1 可知,智慧型計算專家在超啟發式算法設計中主要關注於高層策略,而領域專家則重點研究問題的目標函式和LLH等。
超啟發式算法的分類
由於超啟發式算法的研究尚處於起步階段,對於已有的各種超啟發式算法,國際上尚未形成一致的分類方法。按照高層策略的機制不同,現有超啟發式算法可以大致分為4類:基於隨機選擇、基於貪心策略、基於元啟發式算法和基於學習的超啟發式算法。
基於隨機選擇的超啟發式算法該類超啟發式算法是從給定的集合中隨機選擇LLH,組合形成新的啟發式算法。這類超啟發式算法的特點是結構簡單、容易實現。同時,這類超啟發式算法也經常被用作基準(benchmark),以評價其他類型的超啟發式算法性能。該類超啟發式算法可以進一步細分為純隨機(pure random)、帶延遲接受條件的隨機(random with late acceptance)等。
基於貪心(greedy)策略的超啟發式算法該類超啟發式算法在構造新啟發式算法時,每次都挑選那些能夠最大化改進當前(問題實例)解的LLH。由於每次挑選LLH時需要評估所有LLH,故此該類方法的執行效率低於基於隨機選擇的超啟發式算法。
基於元啟發式算法的超啟發式算法該類超啟發式算法採用現有的元啟發式算法(作為高層策略)來選擇LLH。由於元啟發式算法研究相對充分,因此這類超啟發式算法的研究成果相對較多。根據所採用的元啟發式算法,該類超啟發式算法可以細分為基於禁忌搜尋、基於遺傳算法、基於遺傳編程、基於蟻群算法和基於GRASP with path-relinking等。
基於學習的超啟發式算法該類超啟發式算法在構造新啟發式算法時,採用一定學習機制,根據現有各種LLH的歷史信息來決定採納哪一個LLH。根據LLH歷史信息來源的不同,該類超啟發式算法可以進一步分為線上學習(on-line learning)和離線學習(off-line learning)兩種:前者是指LLH的歷史信息是在求解當前實例過程中積累下來的;後者通常將實例集合分為訓練實例和待求解實例兩部分,訓練實例主要用於積累LLH的歷史信息,而待求解實例則可以根據這些歷史信息來決定LLH的取捨
超啟發式算法vs.啟發式算法
超啟發式算法與已有的啟發式算法既有一定的相似性,又有顯著的不同。通過分析超啟發式算法與啟發式算法的異同點,可以更加深入地理解超啟發式算法。表2從多個視角,對超啟發式算法與啟發式算法進行了對比,從中我們可以發現以下現象:
(1)超啟發式算法與啟發式算法均是為了求解問題實例而提出的。因此,問題實例可以視為超啟發式算法和啟發式算法兩者共同的處理對象。
(2)超啟發式算法與啟發式算法都可能包含有參數。在傳統的啟發式算法中,可能有大量的參數需要調製。比如遺傳算法中的種群規模、交叉率、變異率、疊代次數等。而超啟發式算法的參數來源有兩個層面,在LLH和高層啟發式方法中均可能有參數需要調製。
(3)超啟發式算法與啟發式算法都是運行在搜尋空間上,但是各自的搜尋空間構成不同:傳統啟發式算法是工作在由問題實例的解構成的搜尋空間上;而超啟發式算法運行在一個由啟發式算法構成的搜尋空間上,該搜尋空間上的每一個頂點代表一系列LLH的組合。因此,超啟發式算法的抽象程度高於傳統啟發式算法。
(4)超啟發式算法與啟發式算法均可以套用到各種不同的領域,但是它們各自對於問題領域知識的需求是不同的。啟發式算法設計通常需要依賴於問題的特徵;而超啟發式算法的高層啟發式方法部分則幾乎不依賴於問題的領域知識,LLH則是與問題的領域知識緊密相關的。目前啟發式算法的套用已經十分廣泛,而超啟發式算法由於歷史較短,還主要局限在部分常見的組合最佳化問題上。
超啟發式算法與啟發式算法多視角對比
啟發式算法 | 超啟發式算法 | |
處理對象 | 問題實例 | 問題實例 |
參數 | 可能有 | 可能有 |
搜尋空間 | 由實例的解構成 | 由LLH串(啟發式算法)構成 |
套用領域 | 廣泛 | 有待拓展 |