維基百科

遺傳演算法

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

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

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

理論背景

編輯
内文：物競天擇
睇埋：進化論

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

基本步驟

編輯
睇埋：機械學習

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

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

適合度分數

編輯
睇埋：進化適應度

相關概念

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

註釋

編輯
  1. ↑ 假想設計者已經定義好「咩先算係正確 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. ↑ 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.
  3. ↑ Goldberg, David E.; Holland, John H. (1988). "Genetic algorithms and machine learning". Machine Learning. 3 (2): 95–99.
  4. ↑ Michie, D.; Spiegelhalter, D. J.; Taylor, C. C. (1994). "Machine Learning, Neural and Statistical Classification". Ellis Horwood Series in Artificial Intelligence.
  5. ↑ 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.
  6. ↑ 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.
  7. ↑ Kenneth O. Stanley & Risto Miikkulainen (2002). "Evolving Neural Networks Through Augmenting Topologies" (PDF). Evolutionary Computation. 10 (2): 99–127.
  8. ↑ 8.0 8.1 8.2 Understanding Compositional Pattern Producing Networks (Part One). Towards Data Science.

拎

編輯
由「https://zh-yue.wikipedia.org/w/index.php?title=遺傳演算法&oldid=2151979」收