第十一章 基因演算法 (Genetic Algorithms)

Presentation on theme: "第十一章 基因演算法 (Genetic Algorithms)"— Presentation transcript:

1 第十一章 基因演算法 (Genetic Algorithms)

2 基因演算法 基因演算法(Genetic Algorithms)也和記憶基礎理解及類神經網路相同，是建立在類比生物思考過程之上。數百萬年來物競天擇使生物不斷進化，也更適應環境，生存下來的適者會藉由繁衍，將自身的基因傳遞給下一代。增加個體對環境的適應性來解決問題。

3 基因演算法 基因演算法常被應用在三個領域： 訓練類神經網路 生成記憶基礎理解的評分函數 排程的最適化功能等。
其中最普遍的，就是用來訓練類神經網路。目前許多類神經網路都將基因演算法列為訓練的選項之一。

4 基因演算法 密西根大學的約翰．賀藍（John Holland）首創用了『基因演算法』，發展出這項技術有力的理論基礎。他在理論中描述了基因演算法是如何運作，以及基因如何巧妙地創造了適應生存的物種。

5 基因演算法 資料採礦著重是分類，預測，而不是最適化，儘管許多資料採礦的問題可以視作最適化問題。一個典型的資料採礦問題，是根據某項產品前一週的銷售量及其特性等等，預測其存貨量。換成最適化的方式，問題就變：『哪一種函數與存貨曲線是最吻合，可用來預測。』使用統計迴歸是一種方式，類神經網路是另一方式，基因演算法則提供了另一種可能性。

6 基因演算法 遺傳學概述: 在比較高等的動物中，這些傳遞下來的DNA 藉由雜交融合了其它適者的DNA，這種技術
稱之為雜交（Cross over）。 有時候傳遞基因給下一代的過程也會有出 錯，稱之突變（mutation）。 這所有的過程加起來，一代一代傳遞，使得 生物高度適應其環境：這就是演化過程。

7 電腦上的遺傳學 一個簡單的例子來解釋基因演算法如何運作：在一個只有一個參數『p』簡單函數，p值為在0 至31之間，該函數31p – p2 見下圖。這個例子可視為一個基因組(genome)，只含有一個5位元基因參數p。（需要5位元來表達0到31）這個函數的最大值出現在p為15與16時，分別以01111與10000代表。這個例子也顯示即使有數個最適狀態，基因演算法依然適用。

8 電腦上的遺傳學

9 電腦上的遺傳學 我們必須選擇所謂的適配函數（fitness function）來解決這個問題。在這個例子裡，適配函數就是31p – p2，然後進行以下一些步驟： 定義基因組以及適配函數，創造第一代的基 因組。 2.藉由選擇，雜交，以及突變，來修訂起始群 體。 3.重複步驟2，直到這個群體不再進步為止。

10 電腦上的遺傳學 運用基因演算的第一個步驟就是設定問題。該基因組含有一個5位元基因參數p。如下表顯示，第一代有四個隨產生的基因組。平均適配值是117.75，已經相當不錯，不過基因演算法可以使其更為改善。

11 電腦上的遺傳學 基因 p 適配值

12 電腦上的遺傳學 如下圖所示，基本演算過程利用三個運算元來修訂起始群體 - 選擇(selection），雜交(crossover)，及突變（mutation）。

13 電腦上的遺傳學

14 電腦上的遺傳學 在我們的計算過程中，母群體的數量是保持恆定的，也就是說該群體不致滅種。基因組存活並繁衍的機率，與其適配值（fitness value）成正比：值越高者，在下一代基因組中所佔比例就越高。按比例計算後，遺傳給下一代的數量通常是個分數，但是群體中基因組的數量卻絕對是整數。生存是建立在依照比例再任意選擇基因組的基準上。

15 電腦上的遺傳學 基因 適配值 適配值百分比 期望子代數 10110 176 37.4% 1.50 00011 87 18.5% 0.74
基因 適配值 適配值百分比 期望子代數 % % % %

16 電腦上的遺傳學 這種選擇的過程，如下表所示，使得4 個基因組出現生存的勝利者。值得注意的是，傳遞下來的基因組，適者較多，不適者較少。例如00011就沒有在這一次的選擇過程中生存下來，而10110這個最適者則佔了2個名額。母群體的平均適配值從 提高140。

17 電腦上的遺傳學 基因 適配值

18 電腦上的遺傳學 下一個運算元的因素則是雜交。雜交也發生在自然界中，將２組基因組原有的某一部分與另一組雜交，產生了新的２組基因組。如前圖所示，雜交發生在２組基因組之間，且發生的節點位置乃隨機決定。舉例來說：10110與00010這2組基因組在2與3之間的位置做雜交。過程如下： １０∣１１０ ００∣０１０ ─────

19 電腦上的遺傳學 經過雜交後（加底線者為原本第２個基因組） １０ ∣ ０１０ ００ ∣ ０１０
１０　∣ ０１０ ００　∣ ０１０ 新產生的基因組，稱為子嗣 (children)，皆繼承了來自雙親的某部份。雜交進行的過程就是選擇某一對基因後，再如擲銅板般隨機決定是否雜交基因。這個機率稱之為雜交機率 (crossover probability)，通常以pc表示。0 . 5的雜交機率（與擲銅板擲到人頭那一面的機率相同）通常會帶來好結果。

20 電腦上的遺傳學 在這個例子中，10110與00010這2個基因組被選擇在2與3位元之間的位進行雜交，如下表。經過選擇與雜交，母群體的平均適配值由 提高到 。這對僅僅經過一代是相當了不起的進步。

21 電腦上的遺傳學 基因 p 適配值

22 電腦上的遺傳學 最後一種運算元的因素是突變。突變在自然界中極少發生，是因為親代在繁衍後代時，基因編碼產生了錯誤所致。在提高適應性上，選擇和雜交相當有助益，但與其原先的狀況有密切相關，隨機的特性也可能阻礙一些基因產生更好的組合。突變提供了另一種可能。自然界中，突變極少發生，在基因演算法裡其比例也很低，每一代的發生機率小於1為合理。

23 電腦上的遺傳學 假設接下來這一代第2個基因組第3個位元的位置發生了突變。下表顯示了經過突變後的基因組。如同多數突變一般，這個突變造成毀滅性的結果：該突變基因組也不可能存活至下一代。

24 電腦上的遺傳學 基因 p 適配值

25 電腦上的遺傳學 基因演算法就是基因在一代一代傳遞的過程中，藉由選擇，雜交，以及突變來不斷改善自身的適應力。它不一定會導向最適境界（optimal solution），但卻可以很快地接這個最適境界。

26 應用在類神經網路上 下圖顯示一個有3個輸入節點 ( input nodes)的簡單類神經網路，一個有2個輸入節點的隱藏層，以及一個輸出節點 (output nodes) 。使得這個網路運作順利的關鍵在於調整其中的加權值，如此最適的輸入才能得到正確的答案。第一個面對的問題是這個基因組的組成。基因組包含了許多組合在一起的加權數。每個加權值都介於0與1之間。

27 應用在類神經網路上

28 應用在類神經網路上 適配函數是什麼？將訓練系統內預測的輸出值與實際的輸出值相比較，是適配函數的基礎，也就是評估網路所犯的錯誤大小，這可以藉著取網路實際的輸出值與正確的輸出值的絕對值總和來衡量。 基因演算法就是求函數的最小值。

29 應用在類神經網路上 現在類神經網路內這個64位元的基因組包含了許多加權值。適配函數必須決定這些加權值的在訓練系統內的比重。要用基因演算法進行訓練需要起始母群體，然後進行選擇，雜交，以及突變。 關鍵是要將問題正確編碼成為基因組，然後尋找其正確的適配函數。

30 基因演算法的優點 基因演算法的優點有： ●產生可解釋的結果 ●結果易於應用 ●可以處理的資料型範圍極大
●可以用在最適化（optimization）問題上 ●和類神經網路結合容易

31 基因演算法的缺點 基因演算法的缺點有： ●許多問題有編碼（encoding）上的困難 ●不保証最適化 ●運算成本極高
●可以運用的商業套裝軟體不多