遺傳編程

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

基本介紹

• 中文名：遺傳編程
• 外文名：Genetic Programming
• 別名：基因編程/GP
• 發表人：史蒂芬.史密斯和Nichael .克拉姆
• 成果：量子計算，電子設計，遊戲比賽等
• 發展目標：自動化的發明機器

簡介

遺傳編程是一種特殊的利用進化算法的機器學習技術， 它開始於一群由隨機生成的千百萬個電腦程式組成的"人群"，然後根據一個程式完成給定的任務的能力來確定某個程式的適合度，套用達爾文的自然選擇（適者生存）確定勝出的程式，電腦程式間也模擬兩性組合，變異，基因複製，基因刪除等代代進化，直到達到預先確定的某箇中止條件為止。遺傳編程的基本思想也是借鑑了自然界生物進化理論和遺傳的原理，是一種自動隨機產生搜尋程式的方法。由於該算法作為一種新的全局最佳化搜尋算法，以其簡單通用、魯棒性強，並且對非線性複雜問題顯示出很強的求解能力，因而被成功地套用於許多不同的領域，並且在近幾年中得到了更深入的研究。

使用範圍及特點

GP的適用範圍是非常廣泛的，理論上凡是根據多個輸入值而得到一個值的函式，如:對於f(x1，x2，… ，xn)這樣的函式都可以使用GP來生成。當對於邏輯上比較簡單的程式，直接可以用手工編寫，而沒有必要用GP來產生，但對於一些邏輯上比較複雜的程式則可以用它來自動進化生成一個程式。

例如:對於有較多控制回響的Agent，產生其控制程式是非常困難的，它們往往是根據多個外界刺激而產生相應的決策(動作)，這類程式就可以用GP來生成。

在具體實現上，它有如下一些特點:

(1)GP求解的是一個描述問題的程式(或者說是一個算法)。

(2)GP通常用樹型結構來表示，描述相對複雜。

(3)GP的每一代的個體的長度(深度)一般是不同的，即使在同一代中的個體之間的長度(深度)也是不同的。

(4)GP所消耗的資源是不可控的(這裡所指的不可控是指不能精確的描述)，需要消耗大量的記憶體空間，因而每一代的進化都比較慢。

實現過程

語言的選擇

遺傳編程在不同的語言上有不同的實現方法。對於遺傳編程所生成的程式既可以看成是程式又可以看成是數據。在遺傳編程的過程中它是數據，需要對它進行隨機生成、交叉操作、變異、評估等操作;在遺傳編程結束後，它又是程式，需要執行它。Lisp語言非常適合於遺傳編程，因為Lisp語言可以對程式本身進行操作，然後再執行。

程式表示方法

程式可以有兩種表示方法:樹型結構表示法和字元串表示方法。樹型結構表示方法結構清晰，在進行交叉和變異操作時比較簡單，但需要占用較大的存貯空間，由於遺傳編程每一代需要用到大量的樹結構，所以存貯開銷是非常大的，空間複雜度是遺傳編程中需要研究的一個課題；對字元串來表示程式可以節省大量的存貯空間，但進行遺傳操作時比較困難，如在選擇“雙親”的隨機交叉點或變異點時比較複雜，需要進行轉換。

對於Lisp語言來說，其本身就是字元串，所以比較適合用字元串來表示遺傳程式；對於C語言來說，這兩種方法就都可以選擇了。所以共有4種結合方式:C語言+樹型結構、C語言+字元串表示、Lisp+樹型結構、Lisp+字元串表示，其中第三種方式不常用(這裡所指的C語言是代表除了Lisp以外的大部分其它通用語言)。

用Lisp語言來表示樹型結構則比較少用，因為沒有必要。若用C語言來表示字元串結構，則與Lisp語言相似，比較簡單，可以把遺傳程式當作數據來處理，把程式表示成偽Lisp語言，等到遺傳結束以後，再把它當作程式來使用，當然，在進行性能評估時也要當作程式來進行執行，這一點下面會作具體的描述。

程式執行方法

對於Lisp語言來說程式的執行是比較簡單的，因為遺傳生成的數據就是程式，可以立即執行。而對於C語言來說就是非常複雜的了，因為C語言生成的程式僅僅是數據而已，不可以拿來執行。為此，必須設計一個解釋器，來解釋所生成的程式，對於樹型結構和字元串型結構需要生成不同的解釋器。但對於不同的套用需有不同的解釋方法，所以解釋後的執行方法也是不同的，為了做到通用，設計了一個執行接口，對於所有的套用，可以使用相同的解釋器，稱之為虛擬機，只有執行部分可以是變化的，對於不同的套用，調用不同的執行函式。

評估函式選擇

對於不同的套用，需要選擇不同的評估函式，所以在程式設計上就不能作出一個通用的評估函式。評估函式的取法，當前也是一個需要研究的課題，目前還沒有一個通用的有效的設定方法。對於這種情況，可以設定一個通用接口(利用類的多態性)，對於不同的套用設定不同的評估函式(用一個子類來實現這個接口)。

發展過程

遺傳編程的首批試驗由史蒂芬.史密斯 (1980)和克拉姆 (1985)發表。約翰.Koza(1992)也寫了一本著名的書，來介紹遺傳編程。

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

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

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

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