遺傳演算法

遺傳演算法（粵音：wai4 cyun4 jin2 syun3 faat3；英文：genetic algorithm，GA）係一類做機械學習用嘅演算法，建基於進化論裏面嘅物競天擇概念。响 GA 當中，解決問題用嘅數學模型「會好似生物噉經過物競天擇嚟進化」，具體啲講（以下係簡化版）可以噉想像^[1]^[2]

隨機整一拃模型出嚟，啲模型每個都識由 input 計 output；
不過啲模型因為內部參數唔同，「計出正確 output」嘅能力唔同；
按某啲基準（簡單嘅可以想像「邊個模型比較計到正確 output」^{[註 1]}），決定邊啲模型要淘汰邊啲有得留低；
有得留低嗰啲模型要「繁衍後代」－整啲新嘅模型出嚟，而啲模型响內部參數上會似「父母」；
攞住班後代，去重複步驟 2 至 4，做到某啲終結條件達到咗就停；

－彷彿好似啲模型係生物噉，「汰弱留強，勁嘅個體先至有得繁殖同埋將自己基因傳去下一代」。實證研究表明，GA 的確能夠有效噉解決好多數學最佳化上嘅問題，仲能夠配合人工神經網絡（ANN）嚟用，响廿一世紀初嘅 AI 工作當中得到廣泛嘅採用^[1]。

理論背景

喺進化論上，一個族群內部嘅生物個體（例如一群人類）彼此之間或多或少噉喺遺傳上有所差異，而呢啲差異會引致佢哋喺表現型（包括外表、行為、同體質等）上有個體差異，當中佢哋有啲生存同繁殖能力比較勁，所以就更加有機會將自己啲遺傳基因傳俾下一代。假設環境唔變，個族群就會一代一代噉喺遺傳上有變異，變到愈發適合喺嗰個環境生存同繁衍。

基本步驟

遺傳演算法就係受呢個理論啟發嘅一種演算法。做法如下^[3]^[4]^[5]：

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

適合度分數

註釋

↑ 假想設計者已經定義好「咩先算係正確 output」

睇埋

文獻

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.

引咗

↑ ^1.0 ^1.1 Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press. p. 2.
↑ Gerges, F.; Zouein, G.; Azar, D. (2018). "Genetic Algorithms with Local Optima Handling to Solve Sudoku Puzzles". Proceedings of the 2018 International Conference on Computing and Artificial Intelligence. ICCAI 2018. New York, NY, USA: Association for Computing Machinery: 19-22.
↑ Goldberg, David E.; Holland, John H. (1988). "Genetic algorithms and machine learning". Machine Learning. 3 (2): 95–99.
↑ Michie, D.; Spiegelhalter, D. J.; Taylor, C. C. (1994). "Machine Learning, Neural and Statistical Classification". Ellis Horwood Series in Artificial Intelligence.
↑ Weber, M., & Notargiacomo, P. (2020, November). Dynamic Difficulty Adjustment in Digital Games Using Genetic Algorithms (PDF). In 2020 19th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames) (pp. 62-70). IEEE.
↑ Zhang, Jun; Zhan, Zhi-hui; Lin, Ying; Chen, Ni; Gong, Yue-jiao; Zhong, Jing-hui; Chung, Henry S.H.; Li, Yun; Shi, Yu-hui (2011). "Evolutionary Computation Meets Machine Learning: A Survey" (PDF). Computational Intelligence Magazine. 6 (4): 68–75.
↑ Kenneth O. Stanley & Risto Miikkulainen (2002). "Evolving Neural Networks Through Augmenting Topologies" (PDF). Evolutionary Computation. 10 (2): 99–127.
↑ ^8.0 ^8.1 ^8.2 Understanding Compositional Pattern Producing Networks (Part One). Towards Data Science.

拎

Genetic Algorithms. GeeksForGeeks.
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.

[3] 假想設計者已經定義好「咩先算係正確 output」

[mitch96-1] 1.0 ^1.1 Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press. p. 2.

[2] Gerges, F.; Zouein, G.; Azar, D. (2018). "Genetic Algorithms with Local Optima Handling to Solve Sudoku Puzzles". Proceedings of the 2018 International Conference on Computing and Artificial Intelligence. ICCAI 2018. New York, NY, USA: Association for Computing Machinery: 19-22.

[4] Goldberg, David E.; Holland, John H. (1988). "Genetic algorithms and machine learning". Machine Learning. 3 (2): 95–99.

[5] Michie, D.; Spiegelhalter, D. J.; Taylor, C. C. (1994). "Machine Learning, Neural and Statistical Classification". Ellis Horwood Series in Artificial Intelligence.

[6] Weber, M., & Notargiacomo, P. (2020, November). Dynamic Difficulty Adjustment in Digital Games Using Genetic Algorithms (PDF). In 2020 19th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames) (pp. 62-70). IEEE.

[7] Zhang, Jun; Zhan, Zhi-hui; Lin, Ying; Chen, Ni; Gong, Yue-jiao; Zhong, Jing-hui; Chung, Henry S.H.; Li, Yun; Shi, Yu-hui (2011). "Evolutionary Computation Meets Machine Learning: A Survey" (PDF). Computational Intelligence Magazine. 6 (4): 68–75.

[8] Kenneth O. Stanley & Risto Miikkulainen (2002). "Evolving Neural Networks Through Augmenting Topologies" (PDF). Evolutionary Computation. 10 (2): 99–127.

[CPPNtowardsdatascience-9] 8.0 ^8.1 ^8.2 Understanding Compositional Pattern Producing Networks (Part One). Towards Data Science.

[1]

[2]

[註 1]

[3]

[4]

[5]

[6]

[7]

[8]

遺傳演算法

目錄

理論背景

基本步驟

適合度分數

相關概念

註釋

睇埋

文獻

引咗

拎