遺傳演算法
(一)文章
什麼是Genetic
Algorithm？中文翻譯做基因演算法，或是遺傳演法。
大家都知道「物競天擇、適者生存」的進化論，在電腦科學的領域上，有個領域在做求取最佳解的 問題，最佳解就是對於某個函數而言，什麼參數會讓這個函數得到最大或是最小的結果。
最簡單的方法就是，將變數從小到大一個一個代入，也就是代入所以變數可能的值之後，從得出的 值來做比較，自得可以得到那個值是我們要的。
但是這雖然是最有效的方法，但也是最浪費時間的辦法，雖然電腦跑很快，但是如果資料龐大時， 我們必須試著用最好的演算法，來提高求得答案的效率。
所以有人把進化的理論拿來應用了。我們先要了解一些名詞：
Generation：世代，阿公的下一代就是你爸爸叔叔伯伯，再下一代就是你啦
Population：族群，想像成一個社區
Gene：基因
Individual：個體，想像成一個人
Crossover：交配
Reproduction：複製
Mutation：突變
Population：族群，想像成一個社區
Gene：基因
Individual：個體，想像成一個人
Crossover：交配
Reproduction：複製
Mutation：突變
當然啦，在基因演算法的領域內，以上的名詞只是基本中的基本。簡單地說，就是「基因」組成 「個體」，許多個「個體」所組成的「族群」經由「交配」、「複製」與「突變」的演化過程後，產 生出新的世代。而「交配」、「複製」與「突變」我們稱為三項「基因操作」。
有沒有一點靈感了？沒錯，我們把某些變數當做族群，讓這些變變去做交配、複製與突變之後， 產生出的新世代就是我們的新變數，再把新變數代入函數內，看看會不會產生比較好的結果。這就是 基因演算法的基本想法。
第二節、基因操作
變數做交配？變數也分公的母的嗎？當然不是。要將變數做交配的動作，必須對變數先做編碼， 最常用的編碼方式就是用二進位來表示這個變數值，我們用例子讓你更明白：
例一：
F(X)=X3-10X2-5X
我們要求的是：在9<x<51時，那一個x可以讓我們得到最接近零的值？
我們先定義族群數為5，分別是10、20、30、40與50，用二進位表示為
F(X)=X3-10X2-5X
我們要求的是：在9<x<51時，那一個x可以讓我們得到最接近零的值？
我們先定義族群數為5，分別是10、20、30、40與50，用二進位表示為
原來的數值
|
二進位
|
代入函數所得到的結果
|
10
|
001010
|
1000-1000-50=-50
|
20
|
010100
|
8000-4000-100=3900
|
30
|
011110
|
27000-9000-150=17850
|
40
|
101000
|
64000-16000-200=47800
|
50
|
110010
|
125000-25000-250=99750
|
這時我們有五個編碼後的字串了，這就是我們要用來做交配、複製與突變的東西啦！而10、20、30、40與 50經過編碼後的0與1字串即為一個個體，0與1則是基因，這五個東西是一個族群。</x<51時，那一個x可以讓我們得到最接近零的值？
那麼，怎麼做複製、交配與突變呢？
第三節、交配
我們一個一個來看，先來說「交配」。以例一所表示的10（001010）與20（010100）來看， 10與20經由二進位表示後，變成了六個位元的字串，我們現在要將它們做「交配」。先隨機選擇 一個介於１到６之間的數字，假設是３，那麼我們可以先得到：
10=001010
20=010100
有底線的部份就是第３個位元以後的部份，我們現在將這兩個有劃底線的地方交換！變成： 000100
011010
於是我們變出兩個新的變數！分別是4（000100）與26（011010），這兩個新的字串就是交 配後的結果。於是我們代入4與26得到F(4)=-116與F(26)=10686。
10=001010
20=010100
有底線的部份就是第３個位元以後的部份，我們現在將這兩個有劃底線的地方交換！變成： 000100
011010
於是我們變出兩個新的變數！分別是4（000100）與26（011010），這兩個新的字串就是交 配後的結果。於是我們代入4與26得到F(4)=-116與F(26)=10686。
經由這種過程，我們可以任意挑選變數來做交配的動作，進而得出新的變數與新的值，如此 將一步步得出最接近我們要的結果！
第四節、複製
那麼什麼是複製呢？複製就是很單純的保留住這些個體啦，不過呢，別忘了在最前面提到的， 基因演算法是基於「物競天擇」的「適者生存、不適者淘汰」演算法，所以我們在做保留的動作時 ，當然必須要先捨棄掉一些表現不好的個體！而保留的數目為你當初所設定好的族群大小，以例一 來說，就是５個。
怎麼捨棄呢？方法很多，最最簡單的方法為輪盤法，你先畫一個輪盤，然後用以下的方法計算： （假設我們剛才只做了一次交配的動作）
例二：
代入函數的結果
|
與我們所要求的結果
（零）的差距 |
表現好壞的百分比
|
F(4)=-116
|
116
|
(116/180152)*100%=0.064%
|
F(10)=-50
|
50
|
(50/180152)*100%=0.027%
|
F(20)=3900
|
3900
|
(3900/180152)*100%=2.168%
|
F(26)=10686
|
10686
|
(10686/180152)*100%=5.931%
|
F(30)=17850
|
17850
|
(17850/180152)*100%=9.908%
|
F(40)=47800
|
47800
|
(47800/180152)*100%=26.533%
|
F(50)=99750
|
99750
|
(99750/180152)*100%=55.369%
|
總合
|
180152
|
100%
|
這裡要注意一下，在例二中的「表現好壞的百分比」是愈小愈好，因為愈小代表愈接近我們要的結 果，也就是F(X)=0，所以我們在畫輪盤時是這樣畫的，輪盤中有55.369%的區域是屬於F(10)，有26.533% 的區域是屬於F(4)的，也就是依百分比大小由大而小排下來之後，愈大的區域是給愈小的百分比值。
當然也有別的方法來計算區域所佔的大小，這裡是一個比較簡單的計算方式，重點在於，表現愈好 的個體，有比較大的區域。再來呢，就是轉動輪盤，然後射飛鏢，因為表現比較好的個體所佔的區域大 ，所以很容易就被飛鏢打到，所以就被留了下來。射五發飛標後，看是那五個被打到，就留那五個下來 ；或是射四發飛鏢，然後留下四個，再將表現最好的那一個直接留下來，湊成五個。然後做複製的動作 就可以了！
也許有人會有疑問，為什麼不要直接保留最好的那一個，或是最好的那二個下來做複製就好了呢？ 答案是：「歹竹出好筍」，也許它在這裡的表現很差，但是誰知道它會不會在保留後，做了交配之後反 而得出更好的結果，甚至就是我們要的結果呢？而且可以增加基因組合的變化。
第五節、突變
那麼我們再來談談什麼是突變。突變就如同字義所示，是指「突然的變化」，在使用二進位的編碼 時，簡單的做法就是把某個0變成1，或是某個1變成0，讓他變成一個新的個體，這就是突變。突變的用 意在於增加我們個體的變化，當交配不足以形成新的個體時，突變是解決的辦法。當全世界的氧氣都用 完時，如果有個原本靠氧氣生活生物能突然改變成靠二氧化碳生活，那麼它將是唯一存活下來的。
10=001010
我們隨機選擇一個數字，假設是３，那麼有底線的部份就是第３個位元，我們現在有劃底線的地方做突變 ！變成：
02=000010
也就是變成2啦！
我們隨機選擇一個數字，假設是３，那麼有底線的部份就是第３個位元，我們現在有劃底線的地方做突變 ！變成：
02=000010
也就是變成2啦！
第六節、總結基因演算法
好啦，我己經告訴你基因演算法的最基礎知識了，你也許根本沒聽過這種東西，不過它已經行之有年 了，只是在一般的場合中根本不需要知道罷了，它是屬於人工智慧的一種工具。好用嗎？我不知道，因為 我沒有用來做什麼用途，也許在學術上或是某個程式中就有應用這種技巧也說不定。我們在下一篇談談什 麼是基因程式設計。
