跳至內容

遺傳編程

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

遺傳編程或稱基因編程,簡稱GP,是一種從生物演化過程得到靈感的自動化生成和選擇電腦程式來完成用戶定義的任務的技術。從理論上講,人類用遺傳編程只需要告訴電腦「需要完成什麼」,而不用告訴它「如何去完成」,最終可能實現真正意義上的人工智能:自動化的發明機器。

遺傳編程是一種特殊的利用進化演算法機器學習技術,它開始於一群由隨機生成的千百萬個電腦程式組成的「人群」,然後根據一個程式完成給定的任務的能力來確定某個程式的適合度,應用達爾文自然選擇(適者生存)確定勝出的程式,電腦程式間也模擬兩性組合,變異基因複製,基因刪除等代代進化,直到達到預先確定的某個終止條件為止。

遺傳編程的首批試驗由斯蒂芬·史密斯頁面存檔備份,存於互聯網檔案館)(1980年)和Nichael·克拉姆(1985年)發表。約翰·Koza(1992年)也寫了一本著名的書,《遺傳編程:用自然選擇讓電腦編程》(ISBN 9780262111706),來介紹遺傳編程。

使用遺傳編程的電腦程式可以用很多種程式語言來寫成。早期(或者說傳統)的GP實現中,程式的指令和數據的值使用樹狀結構的組織方式,所以那些本來就提供樹狀組織形式的程式語言最適合與GP,例如Koza使用的Lisp語言。其他形式的GP也被提倡和實現,例如相對簡單的適合傳統程式語言(例如FortranBASICC語言)的線性遺傳編程。有商業化的GP軟件把線性遺傳編程和匯編語言結合來獲得更好的效能,也有的實現方法直接生成組譯程式。

遺傳編程所需的計算量非常之大(處理大量候選的電腦程式),以至於在90年代的時候它只能用來解決一些簡單的問題。近年來,隨着遺傳編程技術自身的發展和中央處理器計算能力的指數級提升,GP開始產生了一大批顯著的結果。例如在2004年左右,GP在多個領域取得近40項成果[1]量子計算、電子設計、遊戲比賽、排序搜尋等等。這些電腦自動生成的程式(演算法)中有些與2000年後人工產生的發明十分類似,甚至有兩項結果產生了可以申請專利的新發明。

在90年代,人們普遍認為為遺傳編程發展一個理論十分困難,GP在各種搜尋技術中也處於劣勢。2000年後,GP的理論取得重大發展,建立確切的GP概率模型和馬爾可夫鏈模型已成為可能。遺傳編程比遺傳演算法適用的範圍更廣(實際上包含了遺傳演算法)

除了生成電腦程式,遺傳編程也被用與產生可發展的硬件

Juergen Schmidhuber進一步提出了宏遺傳編程,一種使用遺傳編程來生成一個遺傳編程系統的技術。一些評論認為宏遺傳編程在理論上不可行,但是需要更多的研究來確認。

參考文獻

參照

  1. ^ John R. Koza. 36 Human-Competitive Results Produced by Genetic Programming. 2003-12-30 [2015-12-21]. (原始內容存檔於2016-07-08) (英語). 

來源

  • Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D. (1997), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann
  • Cramer, Nichael Lynn (1985), "A representation for the Adaptive Generation of Simple Sequential Programs" in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), CMU
  • Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314頁面存檔備份,存於互聯網檔案館). A thorough report, possibly used as a draft to his 1992 book.
  • Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press
  • Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press
  • Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann
  • Langdon, W. B., Poli, R. (2001), Foundations of Genetic Programming, Springer-Verlag
  • Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming頁面存檔備份,存於互聯網檔案館), freely available via Lulu.com.
  • Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)

外部連結