兔窩

啟發式演算法 – 爬山演算法　Hill-Climbing Algorithm

閒言：

　　這次拖了一個月才更新，最近開始嘗試 C++ 跟一些一般演算法，感到博大精深一不小心就栽下去忘記寫部落格了。這篇文章是啟發式演算法系列的第二篇，我們選擇啟發式中最簡單的爬山演算法做開頭，因為流程上比較簡短所以這篇文章會同時帶入一些通用知識讓之後其他演算法比較好介紹。

簡介：

　　我一開始認識爬山算法時是被稱作 Iterative Improvement（II），不過似乎是 Hill-Climbing 這個名稱比較常被使用，大概是爬山比較符合啟發式那種學習自然的感覺吧，看了一下內容基本上兩個也是一樣的，所以就當作一樣的演算法介紹了。Iterative Improvement 顧名思義會有個啟發式必備的疊代（Iterative）用來產生出新解，然後每一次疊代都會選出品質更好的新解（Improvement），通常無法產生出比現在的解更高品質時就是 II 的結束條件。

說明：

　　基本上II的核心精神已經在簡介被講完了，接下來我們要再深入提到的是II的上層分類，II屬於軌跡式啟發式演算法的一種。當這個啟發式演算法同一時間只會存在一個解，由這一個解產生出新解之後也只會留下一個解，其他都被淘汰時，我們就稱他是軌跡式（Trajectory-based）或是我個人喜歡更直白的稱作單點式。現在我們結合簡介中的 II 核心以及單點式特性就可以繪製出II的流程圖。

再來就直接根據流程圖的各步驟做說明。

編碼（encoding）

　　前我們要先談談 encoding，不只啟發式，許多一般演算法的第一步也都是 encoding，所謂的 encoding 就是將你要解決的問題轉換成程式語言支援的資料結構，之後產生的解也都會依照這個 encoding。encoding 非常吃重你對於問題的瞭解程度，他重要的原因在於會關連到搜尋區域，搜尋區域代表你的 encoding 所有可能性的大小，而搜尋區域越大時，事情也就理所當然的更複雜。

初始解

　　最一開始我們會需要初始的解，基本上初始族群很多都是用隨機產生，當然也有一些啟發式算法著重在初始化，不過那不在我們今天討論的範圍內。

鄰域函數（neighborhood function）

　　由現有的解生出新的解，負責這項功能的函數就稱作 neighborhood function，neighborhood function 會關聯到整個 II 的運作，所以等到全部名詞解釋完的最後會再提及它，這邊只要知道它會產生出新解就好。

適應函數（fitness function）

　　啟發式中必須有能評判好的個體的標準或方法，來篩選出族群較強的個體，這個判斷的方法就是 fitness function，藉由 fitness function 得知解的好壞程度，fitness function 不一定是一個單一函數，也可以由多個組成，甚至在一個程式中擁有兩個 fitness function，比較需要注意的點是即使 fitness function 就算無法給出確切的分數，至少也要可以明確的排列出一群解的優劣，如果只是回傳"好"或"不好"這種極端答案是沒有辦法運作的，很有可能遇到現有解跟所有新解都是"不好"的情況，或是只要一個解變成"好"，整個 II 立即停止，解的品質不可能再上升。當我們說一個解的 fitness 值，就代表這個解經過 fitness function 後所得出的適應值。

選出新的解

　　II 的框架說明選出新解時，這個新解必須比現有解優秀，這樣聽起來在選出新的解這方面我們不能做太多的變動。其實不然，II 中還是有幾中方式可以更動選擇的機制。當鄰域函數生出的解中，存在超過一個新解優於現有解時，有幾個常見的擇優機制：

• Best-improving：採用從新解中最優秀的那一個。這種做法就永遠只有最優秀解可以被接受，如果用演算法的詞彙來說就是比較貪婪（greedy）。
• First-improving：從新解中隨機拉出一個解，只要他比現有解更優秀就直接採用，不在乎後面有沒有其他新解更優秀。這樣的做法讓每個較優秀的新解都有機會被選中，比較隨機。

還有沒有其他的？當然有，只要不偏離框架的設定，啟發式任何一個部分都可以自訂，比如說我可以根據新解的更優秀的程度給予不同的機率，最優秀解有極高的機率被選中，但是其他的解也還是有低機率會被選中，達到介於 Best-improving 跟 First-improving 的效果。

結束條件

　　通常無法產生出比現在的解更高品質時就是 II 的結束條件，不過也是會有特例，比如說我們今天的需求必須限制程式執行的時間，時間到就停止。又或是我們只讓 II 看過 1000 個解的 fitness 值就停下來等，這些都是常見的結束條件。值得一提的是看過固定幾個解的 fitness 值這點在啟發式中很常被用來當作結束條件，然後互相比較演算法的效能，英文為 MaxFES（Maximum number of function evaluations）。

　　現在我們再回來說說 neighborhood function，在 II 的教學中你會常常看到下面這種示意圖來說明 II 的機制。

　　我個人認為這種示意圖對於理解 II 機制來說真的很直觀，我們的編碼是一個實數，並隨機產生一個紅點（初始解），從圖中的箭頭看來，我們的鄰域函數一次會產生出現有解的前後兩個解，可能是加一跟減一。同時他也點出了 II 的最大缺點，當這個紅點現有解移動到下圖中的藍色點時，會因為無法再提升品質而停下來，這些藍色點我們稱為所謂的區域最佳解（local optimum），從這張圖我們可以看出 II 能否得到真正全域最佳解（綠色點，稱為  global optimum）取決於隨機初始化的紅點位置，這也是第一篇《系列簡介》中說到的，啟發式演算法通常包含隨機要素導致每一次輸出的結果都不一定會相同，當然也就不保證可以找出最優解（4. approximate and usually non-deterministic），但是他可以在較低計算資源，不窮舉所有可能性的情況下給予一個還不錯的 local optimum（2. the goal is to efficiently explore the search space in order to find near–optimal solutions）。

　　那有沒有可能提升找到 global optimum 的機率呢？我們可以嘗試讓 neighborhood function 產生出更多的解，讓紅點可以往前後看得更遠，也許它就有機會看見遠方的 global optimum，不過這樣會導致 II 每一次疊代花費更多的速度在產生新解、用 fitness function 評估新解、選擇新解，甚至當我們把 neighborhood function 開到最大一次看整張地圖時這個 II 就只會疊代一次，同時看光所有的解，但是這樣就沒有啟發式的意義在了，這就是一個單純的窮舉法把所有可能性都嘗試一次，通常我們會利用啟發式的問題都是窮舉起來很花時間的大問題。所以 neighborhood function 的大小是一把雙面刃，一次看愈多越有機會找到 global optimum，但同時也會犧牲速度跟啟發式的特性。

　　到這裡我們已經完全了解 II 的最佳化原理，由一個現有解產生出其他新解，選擇新解中優秀者替換現有解，到結束條件時終止。同時我們也了解到 II 最大的缺點就是當今天處於一個 local optimum 時他就會停下，但是又不能把 neighborhood function 無限上綱的開大，也因為這樣的缺點導致了之後其他單點式啟發式的誕生，他們各自用擴大 neighborhood function 以外的方法去嘗試提升找到 global optimum 的機會，至於如何避開，就有待下一回的說明了。

總結：

　　希望讀到現在的你有感受到啟發式跟一般演算法的差異，流程上最簡單的 II 在面對不同問題不同實作者時產生的是完全不同的內容，從encoding、neighborhood、結束條件、最後還有擇優的機制都是他可以變動的地方，也就是我在第一篇時說到的啟發式只提供框架的概念，如何在這個框架中組合出適合你問題的最佳 II 就是最吸引人的地方了。這次教學中順便帶出單點式啟發式演算法的通用特性是因為接下來兩篇文章也都會是單點式啟發式。 本次的啟發式演算法系列就到此為止，謝謝正在觀看的你。