遺傳編程

遺傳編程

遺傳編程,或稱基因編程/GP ,是一種從生物進化過程得到靈感的自動化生成和選擇計算機程序來完成用戶定義的任務的技術。從理論上講,人類用遺傳編程只需要告訴計算機"需要完成什麼",而不用告訴它"如何去完成",最終可能實現真正意義上的人工智慧:自動化的發明機器。遺傳編程是一種特殊的利用進化演演算法的機器學習技術, 它開始於一群由隨機生成的千百萬個計算機程序組成的"人群",然後根據一個程序完成給定的任務的能力來確定某個程序的適合度,應用達爾文的自然選擇(適者生存)確定勝出的程序,計算機程序間也模擬兩性組合,變異,基因複製,基因刪除等代代進化,直到達到預先確定的某個中止條件為止。

進展


遺傳編程的首批試驗由斯蒂芬。史密斯 (1980)和Nichael .克拉姆 (1985)發表。約翰.Koza(1992)也寫了一本著名的書,《遺傳編程:用自然選擇讓計算機編程》,來介紹遺傳編程。
使用遺傳編程的計算機程序可以用很多種編程語言來寫成。早期(或者說傳統)的GP實現中,程序的指令和數據的值使用樹狀結構的組織方式,所以那些本來就提供樹狀組織形式的編程語言最適合與GP,例如Koza使用的Lisp語言。其他形式的GP也被提倡和實現,例如相對簡單的適合傳統編程語言(例如Fortran, BASIC, and C)的線性遺傳編程。有商業化的GP軟體把線性遺傳編程和彙編語言結合來獲得更好的性能,也有的實現方法直接生成彙編程序。
遺傳編程所需的計算量非常之大(處理大量候選的計算機程序),以至於在90年代的時候它只能用來解決一些簡單的問題。近年來,隨著遺傳編程技術自身的發展和中央處理器計算能力的指數級提升,GP開始產生了一大批顯著的結果。例如在2004年左右,GP在多個領域取得近40項成果:量子計算,電子設計,遊戲比賽,排序,搜索等等。這些計算機自動生成的程序(演演算法)中有些與2000年後人工產生的發明十分類似,甚至有兩項結果產生了可以申請專利的新發明。

發展


在90年代,人們普遍認為為遺傳編程發展一個理論十分困難,GP在各種搜索技術中也處於劣勢。2000年後,GP的理論取得重大發展,建立確切的GP概率模型和 馬爾可夫鏈模型已成為可能。遺傳編程比遺傳演演算法適用的範圍更廣(實際上包含了遺傳演演算法)
除了生成計算機程序,遺傳編程也被用與產生可發展的硬體。
Juergen Schmidhuber進一步提出了宏遺傳編程,一種使用遺傳編程來生成一個遺傳編程系統的技術。一些評論認為宏遺傳編程在理論上不可行,但是需要更多的研究再確認。