古詩詞大全網 - 成語故事 - 超啟發式算法的超啟發式算法介紹

超啟發式算法的超啟發式算法介紹

近年來隨著智能計算領域的發展,出現了壹類被稱為超啟發式算法(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-難解問題。

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