啟髮式演算法

出自 MBA智库百科(https://wiki.mbalib.com/)

啟髮式演算法（heuristic algorithm)

　　啟髮式演算法是相對於最優化演算法提出的。一個問題的最優演算法求得該問題每個實例的最優解。啟髮式演算法可以這樣定義：一個基於直觀或經驗構造的演算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個實例的一個可行解，該可行解與最優解的偏離程度一般不能被預計。

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

　　有時候人們會發現在某些特殊情況下，啟髮式演算法會得到很壞的答案或效率極差，然而造成那些特殊情況的數據組合，也許永遠不會在現實世界出現。因此現實世界中啟髮式演算法常用來解決問題。啟髮式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。 有一類的通用啟髮式策略稱為元啟髮式演算法（metaheuristic），通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上，但不能保證效率。

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

　　任何的搜尋問題中，每個節點都有b個選擇以及到達目標的深度d，一個毫無技巧的演算法通常都要搜尋bd個節點才能找到答案。啟髮式演算法藉由使用某種切割機制降低了分叉率(branching factor)以改進搜尋效率，由b降到較低的b'。分叉率可以用來定義啟髮式演算法的偏序關係，例如：若在一個n節點的搜尋樹上，h1(n)的分叉率較h2(n)低，則 h1(n) < h2(n)。啟髮式為每個要解決特定問題的搜尋樹的每個節點提供了較低的分叉率，因此它們擁有較佳效率的計算能力。

　　如何找到一個分叉率較少又通用的合理啟髮式演算法，已被人工智慧社群深入探究過。 他們使用幾種常見技術：部分問題的解答的代價通常可以評估解決整個問題的代價，通常很合理。例如一個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產生的啟髮式演算法優於任何先前存在的！而且它也發現了第一個有用的解魔術方塊的啟髮式程式。