基于準反向變異的實數笛卡爾遺傳編程算法

付安兵，魏文紅，張宇輝，郭文靜

（東莞理工學院計算機科學與技術學院，廣東東莞 523808）

（*通信作者電子郵箱weiwh@dgut.edu.cn）

0 引言

笛卡爾遺傳編程（Cartesian Genetic Programming，CGP）［1］是一種基于圖結構的遺傳編程，不同于傳統的基于樹形結構的遺傳編程，基于圖結構的遺傳編程具有處理多個輸入和輸出的能力。1997 年，在進化數字電路的技術中第一次描述了和CGP 相關的方法，但CGP 真正出現是在1999 年，到2000 年時它作為一種新的遺傳編程被正式提出［2］。自那以后，CGP就不斷被全世界各地的學者研究和改進，并被成功用于不同的領域。2009 年，Gajda 等［3］將CGP 用于多態電路的門級優化；2005 年，Harding 等［4］將CGP 用于機器人控制器的進化；2010 年，CGP 被Khan 等［5］用來進化神經網絡，后來又被Gadja等［6］用來進化高效數字電路；2015年，Vasicek［7］用CGP來做組合數字電路的優化，到了2016 年，Vasicek 等［8］又用它來做電路的近似模擬。另外在圖像處理領域，Harding［9］于2008 年將CGP 用來做圖片濾波器的進化；Sekanina 等［10］在2011 年將CGP 用來做圖像處理；2015 年，Paris 等［11］又將CGP 用于自學習的圖像濾波器。在生物信息學領域，CGP 同樣有著重要的應用，如Ahmad等［12］在2012年利用基于CGP進化的人工神經網絡進行乳腺癌的檢測。當然CGP 的應用遠不止于此，近年來越來越多的CGP 改進算法在不同領域發揮著重要的作用［13］。

在CGP 不斷被研究改進的過程中，許多CGP 變種算法也相繼被提出。Walker 等［14］提出了Modular CGP（MCGP），MCGP 允許模塊（Modules）能執行創建、進化、重用、刪除等操作，而且Walker 等的研究也表明，在解決和數字電路相關的問題中，MCGP 的解通常優于CGP。Harding 等［15］提出了自修改函數的概念，同時將自修改操作基因加入到基因庫中，由此產生了自修改笛卡爾遺傳編程（Self-Modifying Cartesian Genetic Programming，SMCGP）算法。在SMCGP 算法中，染色體的長度不是固定的，它可以根據自修改操作基因的表達與否而動態地改變自身結構，對于一些特定問題，SMCGP 相較其他CGP 變種算法有更高的收斂速度以及更優的解。另外，Turner 等［16］于2014 年提出了循環笛卡爾遺傳編程算法（Recurrent Cartesian Genetic Programming，RCGP），打破了CGP 有向圖不能存在循環連接的限制，在RCGP 的圖中，節點之間的連接不再受到限制，可以與任何一個節點連接（包括它自己）。實驗表明，在一些不能完全觀測的任務中，RCGP 具有更好的表現。2007年，Clegg等［17］采用浮點數表示基因的方式，提出了另外一種CGP 的變種——實數笛卡爾遺傳編程（Real-Valued Cartesian Genetic Programming，RVCGP）算法，并在該算法中第一次成功地引入交叉操作算子。

在對CGP的研究過程中發現，CGP的變異手段太過單一，進化算法本身過于簡單，因此本文提出了一種基于準反向變異的實數笛卡爾遺傳編程算法（ADvanced Real-Valued Cartesian Genetic Programming algorithm based on quasi oppositional mutation，AD-RVCGP）。在AD-RVCGP 中，利用準反向變異算子和末端變異算子并結合反向個體的信息進行變異操作，在對符號回歸問題的求解中，對比其他三種常見的CGP 變種算法，本文算法在收斂速度以及解的精度等方面的表現明顯優于其他三種算法。

1 實數笛卡爾遺傳編程

1.1 RCVCGP編碼背景

與CGP 一樣，RVCGP 也采用圖結構進行非循環有向圖的表示，圖中的節點由一個函數基因和一組連接基因構成；不同之處在于CGP采用整數表示一個基因，而RVCGP中的每個基因則是由一個大于0 小于1 的浮點數表示。圖1 顯示了一條染色體編碼的例子。RVCGP 被提出的初衷是為了將交叉算子加入到該算法中，研究表明在RVCGP 中引入交叉算子后，其性能表現要優于傳統的笛卡爾遺傳編程算法［18］。另外，采用浮點數表示基因的方式使得基因的變異粒度更小，并能以更緩慢的速度影響個體的表現，因此與CGP 跳躍式的變異過程相比，RVCGP的變異過程顯得更加平滑。

圖1 RVCGP中的染色體示意圖Fig.1 Schematic diagram of a chromosome in RVCGP

1.2 RVCGP編解碼

由于RVCGP 的基因采用浮點數表示，所以從RVCGP 基因編碼到非循環有向圖的構建需要進行一個如下的解碼過程。

假設函數表中有n個函數，節點的函數基因為g，則其在函數表（事先決定的用于算法的一系列函數集合，如常用的加減乘除等）中的索引由式（1）給出；同樣假設一條染色體共有m個節點，某個連接基因為c，則其對應的連接節點索引由式（2）給出。

其中：Ig表示該函數在函數表中的索引，Ic表示該連接節點在染色體節點集合中的索引；floor 表示向下取整函數。一個完整的解碼過程如圖2 所示，假設算法用到的函數集合為FUNC，它包含｛+，-，*，/}這四個函數，算法輸入變量個數為2，分別用x1、x2表示，輸出變量個數為1，用o表示。從圖2 中可以看出，節點的序號從2 開始，那是因為算法含有兩個輸入，即兩個輸入節點分別占有編號0 和1，在圖中并未畫出它們，但這并不影響算法的具體實現，因為當處理到連接節點序號為0 或者1 的時候就知道它表示的是算法的輸入參數。節點2 的函數基因為0.2，連接基因分別為0.02 和0.56，該節點代表的函數在函數表中的索引為floor(4*0.2)=0，那么該節點的函數為加法函數，它的兩個輸入參數分別來自節點0(floor(2*0.02)=0)和節點1(floor(2*0.56)=1)的輸出，即第一個輸入變量x1和第二個輸入變量x2，那么該節點的輸出就是x1+x2。同樣對于節點3 而言，其函數基因為0.31，則該函數在函數表中的索引為floor(4*0.31)=1，減法函數為該節點的函數，它的連接基因分別為0.7 和0.41，表示節點2(floor(4*0.7)=2)和節點1(floor(4*0.41)=1)的輸出為該節點函數的輸入，該節點的輸出是節點2 的輸出x1+x2減去節點1 的輸出x2，即x1。以此類推，最終可得到如圖2 所示的完整的計算圖結構，整個算法的輸出o是：x1*x1。從圖2中還可以看出，節點5 沒有連接到輸出節點，因此它的輸出對整個計算圖的輸出不產生影響，這種對輸出不產生影響的節點稱為非激活節點，其他節點稱為激活節點。激活節點和非激活節點并非一直不變的，隨著算法演進，激活節點可以變成非激活節點，非激活節點同樣也可以變成激活節點。研究表明，在CGP 中大量非激活節點的存在有助于提高算法的性能［18］。

圖2 完整計算圖結構Fig.2 Structure of complete computation diagram

RVCGP 采用1+λ的進化策略，每次迭代都選擇一個當前最優個體作為父代，通過變異的手段生成λ個子代個體，然后對子代個體進行適應性評估，當子代存在某個個體適應值優于父代個體適應值時，將該子代個體替換為父代用于下一代繁殖。另外，當子代存在的最優個體的適應值等于父代個體的適應值時，也將用該最優子代個體替換當前父代，因為該子代個體已經累計過足夠多的變異，有利于后續的進化。進化算法的終止條件可分為達到最大預設繁殖代數停止或達到一定的誤差值停止兩種方式，前者是在迭代了一定代數后結束進化過程，后者是當進化過程中出現最優個體適應值滿足一定誤差條件后停止算法的迭代。

1.3 CGP在工程上的應用

CGP 最早是一種用于進化數字電路設計的算法，但同時CGP 也是基于圖結構的算法，因此它和神經網絡有著很好的適應關系。因此，近年來隨著神經網絡的發展，就有學者將CGP 和神經網絡結合起來解決一些工程上的實際問題，如引言提到的用于乳腺癌檢測的基于CGP 的人工神經網絡。另外相較于傳統的神經網絡學習算法，CGP 的一個明顯優勢是它不會陷入局部最優解，而且CGP 不僅可以學習調整神經元之間的權重參數，它還可以學習調整整個神經網絡的結構，因此笛卡爾遺傳編程算法用來訓練神經網絡相較傳統的神經網絡訓練方法有更廣泛的適用性。但如文獻［19］提到的利用CGP 進行卷積神經網絡的進化時，其需要花費比學習傳統算法更多的時間才能達到較好的效果，而且隨著神經網絡層數的增多，其花費的時間通常是不可接受的，因此該算法主要應用在一些相對較淺的神經網絡結構中。

2 AD-RVCGP

2.1 準反向變異背景

一般在進化算法的種群初始化，大都選用隨機的方式初始化種群，這樣算法的收斂速度就具有極大的不確定性，如果種群初始化個體中有些個體離最優解個體距離（一般指歐氏距離）近，那么理論上算法應該能較快地尋找到最優解；反之，種群初始化個體都離最優解很遠，那么理論上算法將進行大量的迭代才有可能找到最優解。這樣的情況對采用1+λ進化策略的算法影響很大，因為采用1+λ進化策略的算法在每次迭代都是由一個最優父代個體生成λ個子代個體，相當于每次迭代都在初始化種群。為了彌補這種缺陷，本文提出了一種基于準對稱點的變異算子，即準反向變異。準反向變異的概念與準對稱點有著必然的聯系，下面介紹準對稱點的概念。

假設要尋找到的最優解處在區間（a，b），對于任意X∈(a，b)，其對稱點X′=a+b-X，對于X的對稱點X′，有如下定理。

定理對于任意X∈(a，b)，其對稱點為X′，到最優解的距離函數為d（?），概率函數為P（?），則有結論：P(d(X′) ＜d(X))=0.5。

證明 如圖3 所示，最優解可能分布在區間（a，X］，（X，M］，（M，X′］，（X′，b）這四個區間。

圖3 準對稱點的例子Fig.3 Example of quasi-symmetric points

最優解落到區間(a，X]和(X′，b)的概率相等，因為a到X和X′到b的距離相同，這時最優解位于區間(a，X]時，顯然離X更近，而落到(X′，b)時，顯然離X′更近。

同樣，最優解落到區間(X，M]和(M，X′]的概率相同，而最優解位于區間(X，M]時，顯然離X更近，落到區間(M，X′]時，離X′更近。

綜上，最優解離X更近或者離X′ 更近有著相同的概率，即P(d(X′) ＜d(X))=0.5，得證。

這樣直接對X取其對稱點X′，從概率上來說X′離最優解更近的概率不會比X離最優解近的概率大，準對稱點的提出改變了這種現狀。

準對稱點 對任意X∈（a，b），X的對稱點為X′，關于X的準對稱點Xopp由式（3）給出：

式中：M代表（a，b）的中點，rand(x，y)表示區間［x，y］中的隨機數。

在文獻［20］中，已經證明了對于X的準對稱點Xopp，它離最優解更近的概率比X離最優解更近的概率大。

2.2 準反向變異和末端變異

除了運用CGP 原始的單點變異算子，本文還提出了兩種變異算子，分別為準反向變異和末端變異。在準反向變異中，對于一個基因g，如果它被選中變異，那么取g的準對稱點作為突變后的基因gmut，gmut的值由式（4）給出。

準反向變異的偽代碼在算法1給出。

算法1 準反向變異。

算法1 中的G表示染色體所包含的基因集合，算法遍歷整個基因集合，按照一定的概率選擇基因進行準反向變異操作，其中，rand(x，y)表示x和y之間的一個隨機數，Gk表示基因集合中第k個基因的值。

在單點變異算子和上述的準反向變異算子中，因為每個基因都有變異的概率，因此需要對每個基因進行遍歷，這樣對于含大量基因的染色體個體而言將花費大量的計算時間，其時間復雜度為O（n），n為染色體基因的長度。因此本文提出了一種只對輸出節點進行變異的變異算子，即末端變異，該變異通過只對輸出節點進行變異，能明顯減少計算的時間，其時間復雜度為O（1）。而且，通過改變輸出節點對應的輸入，也能有效地改變個體的輸出，特別是在輸出節點前已經有了大量節點相互連接的情況下，僅通過輸出節點變異能極大地利用前面節點的累積的變異成果。

2.3 反向個體

在RVCGP 中，每一個個體可以由一條包含多個節點的染色體所標識，每個節點又由多個基因構成。節點的連接基因決定了節點之間的連接結構。對于一個個體的反向個體，有如下定義。

反向個體 對于一個個體M，對應的染色體X，除去X的輸入和輸出節點后，將X中的激活節點變為非激活節點、非激活節點變為激活節點而形成的新染色體X′對應的個體M′被稱為M的反向個體。需要注意：一個個體的反向個體不止一個，因為變化后的激活節點之間的連接方式不止一種。反向個體生成算法由算法2給出。

算法2 反向個體生成算法。

算法2 的主要功能是將一個個體中的激活節點和非激活節點的狀態進行置換，算法先遍歷整個染色體包含的節點集合，將非激活節點加入到集合activeNodes中（它們將被變為激活狀態），隨后遍歷集合activeNodes中的每個激活節點為其設置連接節點。

2.4 AD-RVCGP描述

傳統的CGP 采用1+λ的進化策略，通常取λ=4，每一次迭代都是一個最優父代僅通過變異的手段生成4 個子代個體，然后對這4 個個體進行適應性評估得到其適應值，如果子代個體中存在其適應值不差于父代個體的適應值，則用該子代個體取代父代個體進行下一次的迭代。在這個進化過程中發現，會出現很多代的迭代都不會有優于父代的子代個體出現，這時候可能目前的最優個體已經陷入了局部最優解，因此本文提出了一種基于準反向變異的RVCGP 算法。預設了一個參數t，當t次迭代之后都沒有比父代更優的個體出現時，下一次迭代用當前父代的反向個體進行變異生成子代個體。整個AD-RVCGP由算法3給出。

算法3 準反向變異進化算法。

其中：maxGeneration、maxHit、index、lowerImprovedCount、childrenSize、changeParentThreshold、muteParam分別表示算法最大迭代次數、算法最大命中次數、循環索引、未能找到優于當前最優個體的迭代次數、子代個體數、改變生成父代個體策略控制參數、子代變異方法選擇控制參數。算法的終止條件有兩個：一個是達到最大迭代次數maxGeneration，另外一個是算法運行過程中命中次數達到預設數值maxHit。算法最外層的循環代表迭代次數，每一次循環代表產生新一代種群，這個生成過程通過一定策略選擇父代進行單點變異以及算法2 的準反向變異手段產生子代，然后進行適應性評估，接著選取優于父代個體的最優子代個體作為當前最優個體。值得注意的是，當算法在一定的迭代次數后仍未能有比當前個體更優的個體出現時，算法會選擇用當前最優個體的反向個體作為父代進行下一代種群的生成。

2.5 AD-RVCGP收斂性分析

采用保留最優個體的進化算法在理論上是能保證算法的收斂性的，遺傳編程雖不同于傳統的進化算法，但算法還是有保留當前最優個體的操作（最優父代變異產生子代，而且子代中優于當前父代的個體將被選為最新父代）。因此，ADRVCGP在理論上是收斂的，下面給出簡要證明。

定義搜索空間為S＝｛Li|節點數為N的節點列表集合，Li節點中的基因g∈(0，1)｝，其中N為事先給定的染色體節點數。在S上定義適應值函數f：S→R。則AD-RVCGP 的任務是在S中尋找至少一個適應值最優的個體L*，使得f(L*)=max{f(L)：L∈S}?？紤]S中的任意兩個個體L1和L2，顯然當采用變異手段時，從L1通過變異的手段得到L2的概率p是一個大于0的數。因為L1和L2都是一個等長的包含實數元組的列表，因此它們之間是可以僅通過變異操作來改變實數元組的值實現互相轉換的。

設S*={L∈S|f(L)=f*}表示取得全局最優的個體集合，考慮算法執行到第k代，每個個體的變異概率為pm，每一代產生的個體數為n，這樣到第k代時一共有k*n個個體被選擇變異，而且對于這些個體中的每一個，發生變異后屬于S*的概率為pc=pm*p，p的含義和上面任意兩個個體轉換的概率相同。由于采用了最優個體保留的策略，因此在這k*m個個體中只要有一個屬于S*，就有Ek=0，Ek代表第k代當前最優解和真實最優解之間的誤差，從而得到P(Ek=0) ≥1-(1-pc)k*n，另外對?ε＞0，有1 ≥P(Ek≤ε) ≥P(Ek=0) ≥1-(1-pc)k*n。對上式取極限有，即得limk→∞P(Ek≤ε)=1，因此算法以概率1 收斂到全局最優。

3 實驗與結果分析

為了將本文算法和傳統的CGP 進行性能比較，主要用到5 個符號回歸問題（表1）進行測試。符號回歸問題主要是從一些給定的輸入-輸出對樣本中找到一個將自變量和因變量相關聯的數學表達式。在解決以上問題時，將分別用笛卡爾遺傳編程（CGP）、實數笛卡爾遺傳編程（RVCGP）、自修改笛卡爾遺傳編程（SMCGP）以及本文所提的AD-RVCGP 進行實驗測試。其中，在文獻［21］中，研究表明第三個函數用傳統的CGP 很難對該問題進行求解，得出了傳統CGP 在平均進行大約55 萬次迭代才能找到該表達式。為了進行實驗測試，一些參數需要被確定，如節點個數、最大迭代次數、函數集合、輸入集合等。在本次實驗中，傳統CGP的參數由表2給出，RVCGP參數由表3 給出，SMCGP 參數由表4 給出，AD-RVCGP 參數由表5 給出。其中，在CGP 中有一個Level-back 的參數，該參數限制了每個節點能和它相連接的最前面的節點位置，如Level-back取5，則每個節點只能和其前面5個節點進行連接。由式（2）可以看出，從RVCGP 到CGP 的轉換后，RVCGP 的每個節點都可以連接到它前面的任意節點，因此在實驗中對CGP 的參數取19，另外為了保證測試公平，由于本文提出的進化算法不完全和傳統CGP 的進化算法一致，所以本文算法的子代個體數設置為10，而其他3 種算法的則設置為20。對于個體適應值，本文選擇算法對每個樣本自變量的輸出和樣本真實輸出之差的絕對值的累計誤差，即：

其中：Otrain代表每個樣本的輸入對應的算法輸出；Osample代表樣本的真實輸出；n代表樣本數。因此個體的適應值越小，則代表其適應性越好，本文的目標是使得最優個體的適應值變得越來越小，直至趨于0。除此之外，還新增了一個評估參數“hit”［22］，它表示當算法對于單獨的一個樣本的輸出與其真實值之間的誤差的絕對值小于0.01 時，則代表一次命中。因為這時對于當前樣本的預測值和真實值之間的差異已經很小了，在函數圖像上表現為這兩個點幾乎是重合的，另外實驗主機CPU 為Intel i5-8400，內存大小為16 GB，磁盤大小為500 GB，操作系統為Windows 10專業版。

表1 符號回歸函數Tab.1 Functions of symbolic regression

基于表2～5 對應的算法參數分別利用CGP、RVCGP、SMCGP 和AD-RVCGP 對表1 的五個符號回歸函數進行測試，每個符號回歸問題都測試100 次，四個算法分別都最多迭代10 000 次，然后統計成功找到表達式的次數、失敗的次數、成功的次數中平均迭代的次數、成功找到表達式所花費的平均時間（單位：s）、最差命中次數，實驗結果如表6所示。

表2 傳統CGP參數Tab.2 Parameters of traditional CGP

AD-RVCGP、CGP、RVCGP、SMCGP 算法在表1 中的函數的符號回歸實驗中迭代2 000次時，算法的收斂效果分別如圖4～8所示（總共進行了100次實驗）。

表3 RVCGP的參數Tab.3 Parameters of RVCGP

表4 SMCGP的參數Tab.4 Parameters of SMCGP

表5 AD-RVCGP的參數Tab.5 Parameters of AD-RVCGP

表6 不同算法的符號回歸測試性能對比Tab.6 Performance comparison of different algorithms in symbolic regression test

從圖4～8的收斂效果來看，AD-RVCGP在所有表1中的函數的符號回歸測試的表現均優于CGP、RVCGP 以及SMCGP算法。另外從表6 的實驗數值結果來看，AD-RVCGP 的成功次數比其他三個算法都要多，而且其平均迭代次數、平均花費時間也是四個算法中最少的，在失敗的案例上，AD-RVCGP最差命中次數是四個算法中最多的，因此可以看出，即使在未能成功找到表達式的情況下，AD-RVCGP 找到的表達式也是更接近真實表達式的。另外SMCGP 算法在解決本次實驗所提問題時，它是四個算法中表現最差的，不僅需要花費比其他算法多得多的迭代次數，而且還存在很多次失敗的結果，這可能跟SMCGP 的染色體節點數是動態的因素有關，每次進化過程中，SMCGP 算法的變異操作不僅包括常用的單節點變異，還包括修改染色體節點的操作，如增加、刪除、替換染色體的節點等，因此該算法需要花費的時間較多，另外染色體節點最大數參數也會對算法的性能造成影響。

圖4 函數x6 -2x4 + x2收斂效果對比Fig.4 Comparison of convergence effect of function x6 -2x4 + x2

圖5 函數(x3 + x)/2收斂效果對比Fig.5 Comparison of convergence effect of function(x3 + x)/2

圖6 函數(x2 + x+2)/2收斂效果對比Fig.6 Comparison of convergence effect of function(x2 + x+2)/2

圖7 函數x5 -2x3 + x收斂效果對比Fig.7 Comparison of convergence effect of function x5 -2x3 + x

圖8 函數x4 + x3 + x2 + x收斂效果對比Fig.8 Comparison of convergence effect of function x4 + x3 + x2 + x

4 結語

針對CGP 算法變異手段單一、進化方法過于簡單等問題，本文提出了一種基于準反向變異的RVCGP 算法ADRVCGP。AD-RVCGP 利用準反向變異手段并結合反向個體的信息，將其用于算法的演進過程中。實驗結果表明，ADRVCGP 相較CGP、RVCGP、SMCGP 有著更強的尋找最優解的能力，也具有更高的收斂速度和更優的求解精度。算法參數的選擇對算法產生的影響需要進一步驗證，如節點個數參數、變異選擇參數、改變父代個體控制參數等參數的選擇會對該算法的性能產生怎樣的影響還不得而知，這也是接下來要進行的研究。另外，本文提出的反向個體的概念，目前也只是簡單利用激活節點和非激活節點進行取反得出，更有創意的反個體概念也值得進行深入的研究。