遺傳演算法

遺傳演算法（粵拼：wai4 cyun4 jin2 syun3 faat3；英文：genetic algorithm，簡稱「GA」）係一種建基於進化論當中嘅物競天擇概念嘅機械學習演算法：喺進化論上，一個族群內部嘅生物個體（例如一群人類）彼此之間或多或少噉喺遺傳上有所差異，而呢啲差異會引致佢哋喺表現型（包括外表、行為、同體質等）上有個體差異，當中佢哋有啲生存同繁殖會比較叻，所以就更加有機會將自己啲遺傳基因傳俾下一代。假設環境唔變，個族群就會一代一代噉喺遺傳上有變異，變到愈發適合喺嗰個環境生存同繁衍。

遺傳演算法就係受呢個理論啟發嘅一種演算法。做法如下：

1. 整一大柞同類嘅數學模型（「個體」）出嚟，當中每個啲參數（「基因」）都有唔同；
2. 叫每個數學模型做若干次嘅預測，每個按佢做預測陣時嘅準確度得返個分數 $s$，分數愈高表示佢表現愈好（適合度函數；fitness function）；
3. 揀選分數 $s$ 最高嗰柞模型，將其餘嘅模型淘汰（選擇）；
4. 做「繁殖」嘅過程－用最高分嗰柞模型做「父母」，生產下一代嘅模型。啲「仔女」喺參數上會似佢哋嘅父母（「每個仔女嘅每粒參數」都係「佢父母嘅同位參數」嘅函數），途中啲參數可能會有隨機性嘅變化（「突變」）；
5. 再做過上述過程，重複若干代；
6. 如果一切順利，若干代之後手上嘅模型會係一啲預估估得啱嘅模型。

相關

布穀鳥搜尋演算法

布穀鳥搜尋演算法（cuckoo search algorithm）係一種機械學習上會用嘅最佳化演算法：喺自然界，布穀鳥出咗名會喺第啲品種嘅雀鳥嘅巢嗰度生蛋，而啲布穀鳥仔生咗出嚟之後，仲會本能噉將同一個巢嘅蛋推出去巢外，等佢養父母集中精神淨係餵佢－布穀鳥仔會寄生喺第啲雀鳥嗰度；布穀鳥演算法就係建基於布穀鳥嘅繁殖過程嘅做法。最基本嘅虛擬碼如下：

 Objective function: $f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,$
 產生 $n$ 個寄主巢；
 While 終止條件未達到
   隨機攞隻布穀鳥，設定佢個解答（解答喺機械學習上就係柞模型參數）
   評估佢嘅表現 $F_{i}$
     [For maximization, $F_{i}\propto f(\mathbf {x} _{i})$ ];
   隨機攞個寄主巢，佢嘅表現係 $F_{j}$
   if $F_{i}>F_{j}$
      將 $j$ 放棄，以布穀鳥個解答取代；
   end if
   
   將表現最差嗰啲巢刪除；
   得淨低嗰啲巢有得繁殖。
 end while

概念

• 變化結構神經進化（neuroevolution of augmenting topologies，NEAT）：指喺用遺傳演算法令神經網絡進化嗰陣，唔淨只改變啲權重，仲改變網絡嘅結構（加新嘅隱藏層以至加新嘅連繫等等）。
• 複合模式產生網絡（compositional pattern-producing network，CPPN）：指個網絡入面嘅細胞可以有唔同樣嘅啟動函數－喺一個普通嘅廿一世紀初前饋網絡裏面，好多時啲細胞冚唪唥都係用 sigmoid 函數做啟動函數嘅，而一個 CPPN 入面就容許唔同細胞有唔同嘅啟動函數（例：一啲用 sigmoid 函數、一啲用放射狀基底函數... 等等），配合遺傳演算法用嘅話，CPPN 仲會容許生產下一代嘅模型嘅過程當中喺啟動函數嘅款上出現突變；CPPN 可以有極之複雜嘅輸入輸出關係，所以喺圖像相關應用上可以攞嚟由簡單嘅輸入嗰度產生好多變嘅圖像。
• 歷史記號（historical marking）：CPPN 進化演算法會用嘅數字；每當一個噉嘅演算法加一個新嘅結構（新細胞或者新連繫等）嗰陣，會順手掕個歷史記號數值落嗰個結構度，表示嗰個結構係喺邊一代加入嘅，方便設計者做記錄。
• 物種形成（speciation）：同進化論上嘅物種形成概念相似，指一柞 CPPN 進化嘅過程當中有咗多個唔同款嘅個體網絡，就好似出咗幾個唔同嘅物種噉；喺呢個時候，設計者好多時會選擇俾呢幾個唔同嘅 CPPN「物種」分開進化（唔俾佢哋彼此競爭），用意在於想防止其中一啲「物種」打低初頭表現唔夠好（但可能將來表現會變好）嘅新「物種」。

睇埋

• 機械學習
• 進化論

參考文獻

• Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetic Programming – An Introduction. San Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107.
• Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Sale, Mark E. (2006). "A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection". Journal of Pharmacokinetics and Pharmacodynamics. 33 (2): 196–221. doi:10.1007/s10928-006-9004-6. PMID 16565924.
• Cha, Sung-Hyuk; Tappert, Charles C. (2009). "A Genetic Algorithm for Constructing Compact Binary Decision Trees". Journal of Pattern Recognition Research. 4 (1): 1–13. CiteSeerX 10.1.1.154.8314. doi:10.13176/11.44.
• Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction". Australian Journal of Biological Sciences. 10 (4): 484–491. doi:10.1071/BI9570484.

拎

• Genetic Algorithms - Computer programs that "evolve" in ways that resemble natural selection can solve complex problems even their creators do not fully understand An excellent introduction to GA by John Holland and with an application to the Prisoner's Dilemma
• An online interactive Genetic Algorithm tutorial for a reader to practise or learn how a GA works: Learn step by step or watch global convergence in batch, change the population size, crossover rates/bounds, mutation rates/bounds and selection mechanisms, and add constraints.
• A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University An excellent tutorial with lots of theory
• "Essentials of Metaheuristics", 2009 (225 p). Free open text by Sean Luke.
• Global Optimization Algorithms – Theory and Application
• Genetic Algorithms in Python Tutorial with the intuition behind GAs and Python implementation.
• Genetic Algorithms evolves to solve the prisoner's dilemma. Written by Robert Axelrod.