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

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

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

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

GAflow

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還能做啥呢?! 發揮你們的想像力吧!

sinergy 發表在 痞客邦 PIXNET 留言(9) 人氣()


留言列表 (9)

發表留言
  • tublin
  • 我完全看不懂ㄋㄟ
  • JOHNAN
  • 哩公瞎
  • chiisacat
  • 好像懂又好像不懂= =
  • iamwen
  • 這是一篇有實驗方法和實驗結果但是沒有introduction的paper=.=<br />
  • ffchopin
  • 應該 可以運用在教育上面吧<br />
    <br />
    類似Ausbel meaningful learing theory<br />
    <br />
    或者說 ㄧ種concept map faramwork地展現<br />
    <br />
    <br />
    這是我想到的體悟啦<br />
    <br />
    不知道您認為呢
  • sneaker77
  • 維大力??
  • annaisfay
  • 哈哈...這說明一件事<br />
    女生比較聰明<br />
    男生比較笨...
  • melodyjay
  • 我早就懷疑入妃是男的了= =
  • pocky23
  • 哈哈 樓上的好好笑 XD
【 X 關閉 】

【PIXNET 痞客邦】國外旅遊調查
您是我們挑選到的讀者!

填完問卷將有機會獲得心動好禮哦(注意:關閉此視窗將不再出現)

立即填寫取消