兔窩

基因遺傳演算法 - 原理篇

閒言

　　就個人來說我很喜歡基因遺傳演算法，它是我第一個實際上寫出、利用、並且解決問題的最佳化演算法，實例中首次體驗演算法的威力也使得我對他印象很深，同時它的概念不但沒有艱澀的數學公式也沒有複雜的程式流程，可以從一個很抽象的角度來探討它求出最佳解的機制，對於沒有堅強程式底子的人也很好推廣。

簡介

　　基因遺傳演算法(Genetic Algorithm)，以下簡稱GA，基因演算法屬於最佳化演算法中模仿自然生態的類型之一，其他常見的還有粒子、蜂群、蟻群等演算法，這類的演算法都是基於自然界中的生物行為在不斷的傳遞、重複後會收斂到一個平衡的機制，GA就如其名，是一個模仿生物在演化的過程，生存力較弱的個體交配機率就會低下，甚至沒有交配的機會，這樣下一代產出的新族群整體上生存力就會高於其父母，反覆的繁衍之下，達到進化出最佳解或是趨近最佳解(最佳解可能不存在)的效果。

　　GA提供的不是一段虛擬碼，而是一個流程設計上的概念，也就是說今天兩個不同領域的問題都使用GA解決，但是除了大方向的流程圖相似之外，他們內部的程式碼可能會完全不同。下圖為GA的流程

以下針對GA流程中的主要運算機制簡要介紹

初始族群

　　最一開始我們會需要初始的族群，基本上初始族群很多都是用隨機產生，當作第一代的族群。

適應函數

　　GA中必須有能評判好的個體的標準或方法，來篩選出族群較強的個體，這個判斷的方法就是適應函數，藉由比較適應函數得知好壞，適應函數不一定是一個函數，也可以由多個數值組成，甚至在一個GA程式中擁有兩個適應函數。

交配選擇

　　世代交提前，我們需要決定族群中哪些個體用有交配的權力，然而這個權力不一定是固定的，可能是全隨機、機率與適應函數成正比(飛鏢法)、或是直接選出最強個體強制參與交配(菁英法)。

交配機制

　　交配機制中要設計交配的方式，交配基本上就是在做訊息交換，可能是交換單一變數、隨機交換多個變數、也有固定交換某些特定部分的方式。

突變機制

　　突變是基因演算法非常重要的一個關鍵，由於純交配機制的結果取決於初始族群的好壞，所以需要適度的引入新訊息，以改變現有族群某些個體部份的資訊，新資訊的引入就稱為突變，當此新訊息是良好的，他就會獲得更高的適應函數與交配機會，來把良好的新訊息傳遞到子代；若是突變的結果不良，該資訊會在幾個世代之後淘汰。

世代交替

　　世代交替，不一定要產生一樣多的子代，更多情況下會選擇留下小量母代的菁英，加上交配出的子代當作新族群。

演化需求

　　GA並沒有甚麼很明顯的停止，一般需要自己設定一個停下條件，像是一開始迴圈就限制在1000次之類的，或是適應函數高到一個點時停止。前者較常使用，因為GA有時候求解的是無解問題，很難預先判斷它最高可以趨近到甚麼地步。

總結

　　我們可以在非常多的領域中看見GA的蹤影，原因就在於它的使用條件並不嚴苛，只有兩個，第一個是可以將輸入離散化來進行交配或突變的動作，第二個就是可以判斷輸出優良度的適應函數，只要滿足這兩個條件時就可以使用。

　　同時從介紹中我們可以看出GA的核心機制沒有一個固定統一的方法，我們可以根據自身遇到的問題，對適應函數、交配機制、突變機制、世代交替機製來隨意變動，反覆實驗後找出最適合此問題的GA，這樣的特性使得它可以很輕易的被各方領域採用。

範例

　　結束前我們使用一個圖例來說明剛剛提及的核心機制隨意變動是怎麼一回事，以上圖來說我們的初始族群是六隻，排序之後我們取適應力最強的兩隻(紅色)存活到下一代，而排行前四的個體(紅色)同時獲得全部的交配權力後兩兩產生三個子代(綠色)，最後再隨機生成一隻全新的突變體(紫色)，用這六隻(兩紅三綠一紫)當成新的族群做世代交替，反覆之下尋找出最佳解。這時候雖然看似完成了設計，這個架構應該也會找出最佳解，但是還是有些許疑問在。

例如

如果交配權力不是全數被適應力高的個體搶走？

適應力強的菁英客個體沒有存活到下一代的能力？

突變體不是全新的，是由菁英隨機改變些許自身訊息產生的？

如果照上面的疑問去設計流程

程式找出最佳解的速度會不會變快？

會不會比較容易找到最佳解？

　　答案是不知道，對，這就是所謂的核心機制隨意變動，在目標不確定的狀況下這個問題是不知道的，我們必須在針對不同領域下利用此領域的知識與反覆實驗，最終找出最合適的組合，這個特性正是GA這種自然生態模仿類演算法的優勢所在，也是他們應用廣泛的原因，原理篇就到這裡結束，下一回將會舉幾個實例，實際設計出GA的流程並解決問題。

2018/06/13更新：由於後來自己對於GA這一類的演算法相當感興趣，所以決定開始從頭研究起，如果對這類演算法感興趣的朋友們也可以去看看啟發式演算法系列文章。