上帝的靈藥─基因演算法(二)

距離上次介紹基因演算法的第一篇已經好久了,重新回顧才發現並沒有在技巧上面說明得很清楚,所以打算再繼續這個主題,把基因演算法做一個完整的介紹…

如果您不知道基因演算法是什麼,建議您可以先參考上一篇

先前提到基因演算法的基本概念,但是要怎麼寫程式呢?首先我們先來探討基因演算法的幾個基本元素。

第一個是基因;沒有基因來當作媒介,我們沒有辦法進行基因演算法,但是要怎麼表現基因呢?以電腦世界而言,最常見的就是 0 和 1 的組合形成的"Bit String",例如:0010 就是一個四個位元的 bit string。用四個位元就可以表現出十六種基因組合,而不同的基因組合又可以對照到不同的"表現型"上,例如第一個 bit 表示顏色、第二個 bit 表示長度,第三個 bit 表示色調等等。

除了固定長度的基因之外,也可以採用不定長度的基因;例如,假如要用英文字測試是否能夠演化出一本莎士比亞全集,就可以採用不定長度的基因,讓莎士比亞全集由最早的英文單字逐漸長到厚厚數本書這麼大。

利用適合的基因表達方式,才能夠讓問題更容易利用演化的方式找到解答。如果問題本身不適合用固定長度來表達,就可以考慮用不定長度的基因;相對的,如果問題本身不需要不定長度就可以解決,用不定長度基因型反而會造成程式更慢找到解答。

第二個是適應函式(fitness function);適應函式是用來測試個體在現在的環境中的適應程度,一般而言,適應得越好得分越高,也就會給它更高的機會傳遞它的基因給下一代。舉例來說,如果要程式要找出基因中全都是 1 沒有 0 的個體,那麼適應函式就可以計算現在個體的基因中有幾個 1。

適應函式其實就是所謂的"環境";適應函式不但要考慮個體相對於整體的表現,還要考慮在不同時期給予個體不同的壓力。例如,程式不太可能在一開始就亂數產生出英文中合文法的句子,這時候就要比較寬容一點給分給鬆一點;等到後期程式已經抓到語法的訣竅,那麼有一個拼字錯誤,或許就會被扣不少分數。

第三個是選擇函式(selection function);一般來說,選擇函式都會依照適應函式的分數來作為判斷依據,但選擇有很多方式,最簡單的就是前面一半就晉級,另外也有依照得分多寡加權計算機率的,甚至於保送到下一代的方式。選擇函式做的就是"天擇"的動作。不同的選擇函式各有優缺點,也有其道理所在,請容以後再詳述。

第四個是交配方式(crossover);由選擇函式中選出的兩個個體的基因要如何重組?在固定的點切開一人一份,還是可以在任意點切開來組合?對不定長度的基因,是用模組/區塊的方式重組交配還是同樣在固定點切開?這都要依照目標的不同而調整。

最後是突變方式(mutation);個體在什麼樣的狀況下會突變?突變的地方又是在哪裡?突變之後會變成什麼值?這些都是可以考慮的。

以上五個是基因演算法程式設計中,最重要的幾個架構,至於每個架構有什麼樣的考量,之後再專文說明。

Advertisements

3 thoughts on “上帝的靈藥─基因演算法(二)

  1. Pingback: fcamel / chlo’s Blog » Blog Archive » 大學留下的Computer Science Notes

  2. –羊–

     
    好可惜…雖然是許多年前的文章…
    不過現在才看到…有種相見恨晚的感覺…
    呵呵…還蠻期待有技術專文出現的…
     

  3. ironsnow

    找資料看到 MISM 的介紹,點進來發現你有寫 Genetic algorithm 的文章,下面的資料給你做參考。

    天下出版社出過「複雜」,就是介紹基因演算法的發源地 — 聖塔菲研究院

    http://www.bookzone.com.tw/Publish/book.asp?bookno=CS018

    另外,我不知道這本書有沒有中譯本:Hidden Order: How Adaptation Builds Complexity

    http://www.amazon.com/Hidden-Order-Adaptation-Builds-Complexity/dp/0201442302/ref=pd_sim_b_img_2

Comments are closed.