遺傳編程

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

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

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

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

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

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

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

(4)GP所消耗的資源是不可控的(這裏所指的不可控是指不能精確的描述)，需要消耗大量的內存空間，因而每一代的進化都比較慢。 ^[2] 

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

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

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

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

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

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

遺傳編程的首批試驗由斯蒂芬.史密斯 (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進一步提出了宏遺傳編程，一種使用遺傳編程來生成一個遺傳編程系統的技術。一些評論認為宏遺傳編程在理論上不可行，但是需要更多的研究再確認。 ^[1]