[Wave 09]

先來給各位介紹一下Genetic Algorithm吧!
畢竟大家大部分都生物背景的，應該比較能夠了解
有興趣的同學就看看囉 也只是做個介紹囉!

Genetic Algorithm (以下簡稱GA) 是由John Henry Holland所創造的
有興趣的同學可以google一下這位人物 或是到Wiki小妞那查查
他是個不折不扣的資訊人。

Genetic?! 很熟悉吧?!
嗯 沒錯 這個演算法就是模仿人類gene的仿製過程
主要有兩個特性：
1.遺傳(保有親代的特徵)
2.競爭(適者生存，不適者淘汰)
看到這邊就會覺得 哇~~~好像很簡單的概念
沒錯 的確是很簡單的概念 讓我們繼續往下看吧

首先 讓我們先來看一下GA的流程是怎麼樣
以下是簡單的流程圖：



1st:
GA是將一整個population作為一個單位下去計算
在一個population當中，想必會有許多不同的基因組成的基因庫
也就是說 在這個population當中具有帶有不同gene的差異個體

2nd:
在產生新的子代的時候，親代會將自己的基因遺傳給子代
也就是說子代將保有親代的部份特性
為什麼不是完全保留呢?!
因為在遺傳或是後天的發育過程中 突變發生的可能性是相當的高的
並且會有基因重組的現象 (crossover or recombination)
所以說子代皆會有和親代些許不同的表徵
我們可以把recombination看成是保留大片段的優質的親代基因
而將mutaion看成是給予子代另一種的選擇 (萬一遇到環境大改變時也許能生存)

3rd:
新的子代產生之後，我們知道自然是現實的
並不是所有的子代都可以生存下來
所以說必須對子代進行篩選，通常能夠適應環境的子代是現階段來說好的子代
我們把這些個體加到整個population中，然後再對population做整體的評估
如果說整個population都相當的能夠適應環境
那麼這樣一來可以說是達到一個穩定的狀態
如果不是呢?
那麼我們將淘汰一些個體 e.g.老弱殘疾..etc. (人權團體可別幹譙我XD)
然後讓新的population在進行下一次的generation
一直到整個population都是最佳的狀態。


整個GA的架構大致上是這個樣子，說穿了不過就是取之於自然
不過在電腦上面運作可是還是得考慮一些因素
例如說不可能將像人類這麼大的population全部放進去作運算
computation的方法還是有他的限制等等 在這邊就不多作介紹
GA目前已經被廣泛的運用在各行各業 e.g.財經、商業等等
他可以解決項是如何找到最佳路徑、最佳組合等等的趨近解
只要是能夠將問題模擬成和chromosome一樣的機制
都能把GA運用在其中。

所以GA可以做啥咧?? 好像很多事都可以作
的確是蠻powerful的一個演算法!
我們所上的作業就是用GA寫一個pairwise alignment的程式
GA還能做啥呢?! 發揮你們的想像力吧!