1.1.4 遺傳編程

實際上，把GA和計算機程序結合起來的思想早已出現，Holland把產生式語言和GA結合起來實現分類系統，還有一些GA應用領域的研究者將類似于GA的遺傳操作應用于樹型結構的程序上。1985年，N. L. Cramer首先提出將GA應用于樹型程序，一些重要的概念如程序的樹型結構、終止要求、子樹交叉等被提出[19]。1989年，Stanford大學的J. R. Koza創造性地提出了基于自然選擇原則用層次化的計算機程序來表達問題的遺傳程序設計方法。1992年，Koza出版了專著《遺傳編程：論采用自然選擇方法的計算機編程》[20]；1994年，Koza又出版了《遺傳程序設計（第二冊）：可重用程序的自動發現》[21]，深化了遺傳程序設計的研究，程序設計自動化展開了新局面。自20世紀90年代以來，Koza利用1000臺350MHz的PC自動進化出30多項模擬電子電路專利。這些能自動設計出具有專利水平的設計成果的基于GP的“自動發明機器”成為了新一代計算智能的代表。2000年，Koza進化出了超越傳統控制器的新型控制器。2004年國際遺傳與進化計算國際會議頒發了首屆全球挑戰人類設計錦標賽，獲獎成果包括利用遺傳編程（GP）實現的量子電路設計，美國國家航空航天局進化出的性能優異、外形奇特的天線，康奈爾大學Lipson進化出的機構設計史上的一個難題——實現直線運動的連桿機構，美國著名的噴氣推進實驗室進化出的特殊的電子電路。

GP又稱基因編程，是借鑒生物界的自然選擇和遺傳機制，利用GA的進化原理來自動進化出計算機程序的全局優化搜索算法。GP常采用樹型結構來表示計算機程序，從而解決問題。對于許多問題，包括人工智能和機器學習上的問題都可看作需要發現一個計算機程序，即對特定輸入產生特定輸出的程序，形式化為程序歸納，那么GP提供了實現程序歸納的方法。

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

GP在程序運行過程中會產生適用于給定問題的初始群體，然后不斷地進化，進化過程類似于自然界的生物進化，最終尋找到用戶問題的最優解。在GP運行時，要提前確定解決用戶問題時所有可能需要的集合，如函數集和終止符集。函數集可以是算術運算符（+、?、×、/等）、數學函數（sin、cos、exp、tan等）、布爾運算符（AND、OR、NOT等）、條件表達式（if-then-else）等，還可以是程序中的子程序及其他可定義的函數。終止符集含有與問題相適應的變量、隨機常數等，如終止符集T={p，x}，其中p為隨機數，x為輸入變量。最終程序可通過集合來隨機生成初始群體，然后確定適應度標準，以此來評價程序解決問題的能力，類似于自然界中的適者生存。在進化過程中，個體可進行復制及交叉等遺傳操作，與自然界的進化相似，也有可能產生變異的個體。適應度值較低的個體消亡，適應度值較高的個體經過許多代進化，就會有用戶所需的解產生。但GP并不能保證每次運行都能求得問題的解，須對參數的設置進行多次實驗，可以說GP算法所得結果與實驗過程有著緊密的聯系。同時，其自組織性保證它能根據所給數據產生結構復雜、高精度的函數模型。

函數集中的元素代表解決問題的基本方法，而終止符集中的元素代表問題的基本要素，一個合適的函數集和終止符集將會對尋找最優個體的過程起到積極的作用，因此我們在選取函數集和終止符集的時候，通常遵循以下原則：首先，函數集和終止符集的選擇要滿足充分性和有效性，即函數集和終止符集要能充分表達問題，并且只能產生語法正確的個體；其次，函數要具有在終止符集上的封閉化，即函數集中的任何函數的返回值仍應屬于終止符集，這樣能夠保證最終得到的是可取的解；最后，函數集中的函數個數不能過多，以免在尋優過程中因搜索空間太大而降低尋優效率。

GP簡單通用、穩健性強，并且對非線性復雜問題顯示出很強的求解能力，因而被成功地應用于許多不同的領域。理論上，凡是根據多個輸入值而得到一個值的函數，如：對于f(x1，x2，…，xn)這樣的函數都可以使用GP來生成。當對于邏輯上比較簡單的程序，直接可以手工編寫，而沒有必要用GP來產生，但對于一些邏輯上比較復雜的程序則可以用它來自動進化生成一個程序[22]。

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

GP在具體實現上，有如下特點：

（1）GP求解的是一個描述問題的程序（或者說是一個算法）。

（2）GP通常用樹型結構來表示，描述相對復雜。

（3）GP的每一代的個體的長度（深度）一般是不同的，即使在同一代中，個體的長度（深度）也是不同的。

（4）GP所消耗的資源是不可控的，需要消耗大量的內存空間，因而每一代的進化都比較慢。