[Term-Project]基因演算法

"基因演算法(Genetic Algorithm) 一、前言: 基因演算法是一種模仿大自然界中,物競天擇和基因交配的演算方式。它進來頗引人注意,因為一些傳統人工智慧方法無法有效解決的計算問題,它都可以很快速地找出答案來。基本上來說,基因演算法是一種特殊的搜尋技巧,適合處理多變數非線性的問題。 基因演算法採用三種基本的運作機制以模仿自然遺傳的過程,包括複製(Reproduction)、交配(Crossover)、突變(Mutation),能在合理的時間範圍內求得近似最佳解。 

   二、基因演算法簡述:基因演算法(Genetic Algorithm)其實是取法大自然的一種演算法,藉著對於演化現象的觀察,John H. Holland 認為可以透過把問題轉為基因型(Genotype),利用競爭-生存以及基因交換-突變,尋求出問題的正確解答。透過競爭-生存,擁有好基因的品種會有較高的機會生存到下一代,而與生存較無關的基因則會隨著時間逐漸被淘汰,。在理想的狀態下,競爭-生存會迫使不具優勢的品種逐漸消失。然而單單擁有一種好基因是不夠的;透過基因的交配,不同的個體可以把它們的好基因組合起來,變成更具優勢的下一代;而若是組合出來的後代不理想,也只會加速被淘汰。但交換基因也不能改變現有的基因狀態,還要再配合突變,才能夠產生革命性的改變,進而對族群進步有突破性的發展。因此,"生存-競爭""交配""突變"就是整個基因演算法,也可以說是演化的中心思想。 三、基因演算法的基本元素:第一個是基因;沒有基因來當作媒介,我們沒有辦法進行基因演算法,但是要怎麼表現基因呢?以電腦世界而言,最常見的就是 0 1 的組合形成的"Bit String",例如:0010 就是一個四個位元的 bit string。用四個位元就可以表現出十六種基因組合,而不同的基因組合又可以對照到不同的"表現型"上,例如第一個 bit 表示顏色、第二個 bit 表示長度,第三個 bit 表示色調等等。除了固定長度的基因之外,也可以採用不定長度的基因;例如,假如要用英文字測試是否能夠演化出一本莎士比亞全集,就可以採用不定長度的基因,讓莎士比亞全集由最早的英文單字逐漸長到厚厚數本書這麼大。利用適合的基因表達方式,才能夠讓問題更容易利用演化的方式找到解答。如果問題本身不適合用固定長度來表達,就可以考慮用不定長度的基因;相對的,如果問題本身不需要不定長度就可以解決,用不定長度基因型反而會造成程式更慢找到解答。第二個是適應函式(fitness function);適應函式是用來測試個體在現在的環境中的適應程度,一般而言,適應得越好得分越高,也就會給它更高的機會傳遞它的基因給下一代。舉例來說,如果要程式要找出基因中全都是 1 沒有 0 的個體,那麼適應函式就可以計算現在個體的基因中有幾個 1適應函式其實就是所謂的"環境";適應函式不但要考慮個體相對於整體的表現,還要考慮在不同時期給予個體不同的壓力。例如,程式不太可能在一開始就亂數產生出英文中合文法的句子,這時候就要比較寬容一點給分給鬆一點;等到後期程式已經抓到語法的訣竅,那麼有一個拼字錯誤,或許就會被扣不少分數。第三個是選擇函式(selection function);一般來說,選擇函式都會依照適應函式的分數來作為判斷依據,但選擇有很多方式,最簡單的就是前面一半就晉級,另外也有依照得分多寡加權計算機率的,甚至於保送到下一代的方式。選擇函式做的就是"天擇"的動作。不同的選擇函式各有優缺點,也有其道理所在,請容以後再詳述。第四個是交配方式(crossover);由選擇函式中選出的兩個個體的基因要如何重組?在固定的點切開一人一份,還是可以在任意點切開來組合?對不定長度的基因,是用模組/區塊的方式重組交配還是同樣在固定點切開?這都要依照目標的不同而調整。最後是突變方式(mutation);個體在什麼樣的狀況下會突變?突變的地方又是在哪裡?突變之後會變成什麼值?這些都是可以考慮的。 四、程式架構: 現今電腦中當然沒有所謂的生物基因物質,倒是有一大堆01所組成的記憶體。所以基因演算法就用一串01所組成的字串,來代表基因物質。通常此字串用來表示問題目前搜尋的結果,你必須依問題特性設計編碼的方法。基因演算法就在一堆字串中間進行人工的演化,用類似基因複製時所進行的程序(交叉配對、基因複製和基因突變),產生新的子代字串。然後從中挑選「優秀」的字串們,重複以上動作,直到產生符合成功條件的結果為止。 如底下步驟:1.   產生一堆字串,形成一個大族群。2.   評估每個字串的分數。檢查結束條件是否成立?3.   選擇優秀的字串。4.   進行字串間的交配演化動作(交叉配對、基因複製和基因突變),產生新的子代字串。跳回步驟2              五、結語:「基因演算法」的應用層面相當廣泛,例如:排程、資源配置、生產計劃……等等,皆須應用到基因演算法。先前曾在批踢踢上與人討論一個Case,希望能在大學四年內以打工的方式,來賺取實際寫作的經驗,但對方要求使用「基因演算法」,此演算法當時沒聽過也沒學過,因此只好選擇放棄。現在,我以這個當作我期末的Project,希望能將之前吃鱉的演算法,利用這個機會好好的研究,才不會下次機會來了,但仍沒有這個實力撰寫程式。 參考資料:1.    http://pesty.yichi.org/blog/2.    http://www.weikeg.com.tw/download/clisp2_files/p15.html3.    http://nmlab.mis.nchu.edu.tw/elearn/archives/ga-for-%20itemselect.ppt#269,5,基因演算法[@more@]"