運用遺傳規劃解決異或問題的新方法

摘要：介紹了一種用遺傳規劃這種新的搜索優化技術解決經典異或問題的新途徑。遺傳規劃實質是使用廣義的計算機程序來描述問題，并且可以根據環境狀況動態改變計算機程序的結構。根據遺傳規劃特征，引入兩種思路、三種方法對異或問題進行求解，取得了很好的效果。與神經網絡相比，遺傳規劃可以動態進化學習并取得顯式的數學表達式。

關鍵詞： 遺傳規劃； 異或；神經網絡

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2007)11-0040-03

0引言

異或問題就是如何實現異或邏輯關系，即對于兩個相同的布爾輸入0或1，其輸出為0；而對于兩個不同的輸入，其輸出為1。對于這個問題，最初的感知基因只作線形分類而無法解決XOR邏輯運算，導致神經網絡的研究出現低潮[1]。但是對于神經網絡的研究并沒有停止，20世紀80年代后期，Rumelhart等人提出了多層前向網絡的誤差反向傳播（BP）算法，使得網絡可以逼近任意一個連續系統，實現了非線性分類問題[2]。然而BP算法在具體實現中出現了一些問題，如收斂速度慢、神經網絡結構的確定比較復雜、參數之間存在較強的耦合關系、不能顯性表示相關關系、局部極小等[3]。

遺傳規劃，又稱遺傳程序設計[4]，是近年來出現的一種全新的方法。80年代末90年代初，美國斯坦福大學Koza 教授將計算機自動程序設計思想引入遺傳算法 GAs(genetics algorithms)中[5，6]，創立了遺傳規劃。遺傳規劃可以自動地在可能的解空間中尋找最優或最滿意的計算機程序。經過近幾年的研究，遺傳規劃已經在自動設計、模式識別、機器人控制、神經網絡結構的合成等領域中得到廣泛應用[7，8]。

遺傳規劃能動態產生預測分析的最優非線性結構，也能在描述模式分類問題的不同特征之間發現聯系。它

不需要數據統計分布的預處理知識，可自動地發現某一類判別式的特征。

1遺傳規劃的基本原理

遺傳規劃的基本思想是隨機產生一個適合于給定環境的初始群體，即問題的搜索空間，構成群體的個體均有一個適應度值；依據達爾文適者生存原則，對群體中的個體進行遺傳操作，產生新一代群體。如此進化下去，直到給定問題的解或近似解在某一代上出現為止。在遺傳規劃技術中，組成群體的個體，即遺傳程序（genetic programs）是一種動態的樹狀結構，樹的節點由葉節點（終端集）和非葉節點（根節點和運算符）組成。這種樹結構的層與節點都是可以變化的。

采用遺傳規劃解決特定問題需確定以下五個要素：

a）終端集（terminal set）。由輸入變量和常量構成。輸入變量，又叫特征終端，與具體的領域問題有關，它是從問題領域中抽取的特征值，如表示輸入、傳感器或某個系統的狀態變量；常量是一些數字或者布爾常數，由系統生成初始群體或變異操作隨機產生，并且在進化過程中保持不變。

b）函數集（function set）。可以由算術運算符（+、-、*、/）、標準數學函數（sin、cos、tan、exp、log）、布爾運算、條件運算、迭代運算、遞歸函數、自定義函數等構成。

c）適應度（fitness）。適應度函數是評價個體的函數（該性能代表個體解決問題的能力）。種群中每個個體均會依照適應度評價函數算出一個適應度值。

d）算法控制參數。包括種群的大小、遺傳操作（交叉、復制、變異）的概率等。

e）終止條件。它通常是預先給定的，可以是最大優化迭代數或是要求的最小適應度值。

遺傳規劃通過以下三個步驟解決問題[9，10]：

生成一個初始群體，其個體是由終端集和函數集的隨機組合產生的；

重復計算群體中每個個體的適合值，并進行遺傳操作，直到滿足終止準則為止；

終止遺傳規劃的運行，確定運行結構。

2用神經網絡方法解決XOR問題 

XOR問題的樣本集如表1前三列所示。

4結束語

本文采用兩種思路、三種方法提供了一種用遺傳規劃解決XOR問題的新途徑。這三種方法均能快速準確地找出多個合適的樹型遺傳程序（表現為顯式數學模型）來解決XOR問題。對于該問題，盡管用分類思想比用符號回歸來解決稍顯復雜，但它為遺傳規劃程序延伸解決其他分類問題提供了一種新的思路。

較之神經網絡方法，遺傳規劃方法無須確定具體的函數形態；不需要對輸入預處理或對輸出進行后處理；生成的計算機程序會按照接近問題解的方式動態改變；進化學習的時間短，可以直接給出變量之間顯性的函數關系。

遺傳規劃是一種不依賴問題域的方法，它提供了一個找到解決問題的計算機程序的有效途徑。

參考文獻：

［1］蔣宗禮.人工神經網絡導論[M].北京：高等教育出版社，2001:109－114.

［2］楊行峻，鄭君里.人工神經網絡[M].北京：高等教育出版社，1992：100－110.

［3］胡守仁，余少波，戴葵.神經網絡導論[M].長沙：國防科技大學出版社，1993:158－164.

［4］BANZHAF W， NORDIN P， KELLER R E， et al. Genetic programming: an introduction on the automatic evolution of computer programs and its applications[M].[S.l.]: Morgan Kaufmann Publishers， 1998.

［5］KOZA J R. Genetic programming: on the programming of computers by means of natural selection[M]. Cambridge: MIT Press， 1992.

［6］KOZA J R. Genetic programming II: automatic discovery of reusable programs[M]. Massachusetts:MIT Press， 1994.

［7］云慶夏，黃光球，王占權.遺傳算法與遺傳規劃[M].北京:冶金工業出版社，1997.

［8］KOZA J R， KEANE M A， STREETER M J， et al. Genetic programming IV: routine human－competitive machine intelligence[M]. [S.l.]:Kluwer Academic Publishers， 2003.

［9］王占權，云慶夏，楊東援.改進的遺傳規劃研究[J].系統工程與理論實踐，2000(5):66-67.

［10］王占權，云慶夏.工作面設備選型的遺傳規劃[J].中國鉬業，1999，23(5).

［11］ZHANG Meng－jie， CIESIELKI V. Genetic programming for multiple class object detection[C]//FOO N. Proc of the 12th Australian Joint Conference on Artificial Intelligence. Berlin: Springer－Verlag，1999.

［12］查志琴，高波，鄭成僧.遺傳編程實現的研究[J].計算機應用，2003，23(7):137－139.

［13］何登旭.遺傳規劃設計與應用[J].廣西民族學院學報:自然科學版，1999，5(3):31-33.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”