兔窩

啟發式演算法 – 系列簡介

閒言：

　　去年因為大學畢業專題接觸到基因遺傳演算法（Genetic Algorithm，GA）時有寫一篇文章稍作介紹，裡面也有提及我個人很喜歡GA模仿自然跟核心機制不固定的特性，所以最近開始研究這類的演算法，也順手開一個新的系列紀錄所學，之後主要會都是演算法跟技術書讀書心得這兩大類在更新。

簡介：

先來看看維基百科所寫的啟發式演算法特性

These are properties that characterize most metaheuristics:

➤ Metaheuristics are strategies that guide the search process.

➤ The goal is to efficiently explore the search space in order to find near–optimal solutions.

➤ Techniques which constitute metaheuristic algorithms range from simple local search procedures to complex learning processes.

➤ Metaheuristic algorithms are approximate and usually non-deterministic.

➤ Metaheuristics are not problem-specific.

　　從一二點我們可以看出啟發式的目標在於搜尋近似最佳解，屬於最佳化演算法的一種，而在最佳化算法中有一族是基於模仿大自然不斷的傳遞、重複後會收斂到一個平衡的機制所設計的，並且把自然界中的平衡當作問題的解。這類受到自然啟發、重複疊代的演算法就被稱作啟發式演算法（Metaheuristics Algorithm），其特點在於求解問題時比起一般明確的演算法提出完整公式來說，啟發式演算法只提出一個流程框架（strategies that guide the search process），內部核心因為與問題本身相關，由實作者自行設計，所以也高度依賴實作者對問題的瞭解程度（not problem-specific）。同時啟發式演算法通常包含隨機要素導致每一次輸出的結果都不一定會相同，當然也就不保證可以找出最優解（approximate and usually non-deterministic）。

說明：

　　這樣聽起來啟發式演算法好像很弱，既找不出最優解又依賴對問題的了解性，那到底什麼樣的地方會用到啟發式算法？在這裡先說說使用條件，使用啟發式的條件只有兩個：

• 此問題可以被編碼成程式語言支援的資料結構。
• 擁有判斷（或比較）此問題解的優良度的方法。

　　這兩個條件在演算法中都不少見、多數問題也不是很難達成，也就是說大部分的問題都可以使用啟發式演算法，話說如此卻因為前面提及的特性（non-deterministic等）導致啟發式的成效大多比一般演算法差勁，所以啟發式一般被用在搜尋空間過大或是沒有專用演算法的問題。

　　舉個例子來說，面對尋找最短路徑這種常見問題必定存在專用的演算法可以求得最佳（最短）解，但是由於他的計算過程與花費時間是相當明確的，當這個兩個路徑上的點很多時速度也會無法避免的上升。更簡單的說法我們也可以使用迴圈直接暴力的看每一種路線組合，最終一定可以拿到最佳解，但是當這個組合過多時速度就會無法避免的上升。在真實世界裡可能沒有這麼多時間資源可以投資在上面，也不一定真的需要最佳解。

　　例如今天我們的最短路徑應用在送貨員身上，假設送貨員的路線最長花費時間是1小時，使用一般的演算法要等1小時才能算出最佳解（騎5分鐘就到），這時候得出的最佳解反而比不用演算法直接亂騎花費更多時間（1小時5分鐘），而啟發式則可以在10分鐘左右給出一個還可以看（10分鐘左右到）得解，讓他更快的去送貨（20分鐘左右 ）。這時候就是搜尋空間過大導致我們沒有足夠的時間投資一般的演算法。

　　那要是這個問題剛好就存在一種相當完善的演算法，速度超快（比啟發式快）、得出的解也超優呢（比啟發式優）？我的大學專題就是這樣的問題，當然這時候啟發式就沒有發揮的空間了，此問題就是有完善專用演算法。

　　到這邊就介紹完啟發式的應用領域，接下來介紹大部分啟發式的流程

　　第三點就會利用到條件中必備的判斷（或比較）此問題解的優良度的方法，並被稱為適應函數（Fitness Function），而第二點到第四點就是所謂的重複疊代（Iteration），啟發式藉由這樣的疊代讓每一次解的品質上升來達到最佳化。至於怎麼產生初始解跟其他的解，又要用那些機制留下比較優的解則會根據不同的啟發式、不同的問題有不同的做法，同時也是啟發式最讓人著迷的地方。

總結：

　　從上述的介紹可能對啟發式演算法還是有些模糊，畢竟沒有真實的演算法範例，所以接下來這個系列會一一介紹我所知道的啟發式演算法，如果有機會實作出一些不錯的成果也會分享我嘗試了哪些啟發式演算法、踩了哪些坑、達到了哪些結果。本次的啟發式演算法系列就到此為止，謝謝正在觀看的你。