2012年6月1日 星期五

基因演算法 (一) 複製 (Genetic Algorithm Part I : Reproduction)


基因演算法(Genetic Algorithm)是將多個十進制數字各自轉換為一串 0、1 所組成的碼(視為基因碼),並以亂數模擬生物演進的複製(Reproduction)、交配(Crossover)、突變(Mutation)等過程,淘汰不佳者,逐代演繹,找出問題較佳解的一種方法。本文則先針對基因演算法的第一個步驟 "複製" 進行解說。


名詞介紹
  • 適應函數 (Fitness Value):它是判斷基因碼優劣的依據,將基因碼所對應的十進制數字代入此函數,所得值愈大,表示基因碼愈優秀。
  • 輪盤式選擇 (Roulette Wheel Selection):一種依適應函數大小來判斷該基因複製數量的方法。


實例說明

以適應函數 f(X) = X^2 + 2X + 1 為例,當 X 被限制在 [0, 10] 範圍時,求該函數的最大值;其中每代有四個項目 (即四組基因碼),且每個基因碼由四個 0、1 數字所組成。

1) 產生初始代:隨機產生四組 0, 1 字串,並分別組合為初始代基因碼 (二進制)、算出各二進制數值所對應的十進位數值,再依所得到的十進位數值,導出各成員的適應函數值。


2) 採用輪盤式選擇,將各項目的 (適應函數值 / 總適應函數值) X 總項目數,以作為該項目被複製次數的參考。


3) 複製出第一代成員


接著進入該世代的第二階段:交配