基于準(zhǔn)反向變異的實(shí)數(shù)笛卡爾遺傳編程算法

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

（東莞理工學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，廣東東莞 523808）

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

0 引言

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

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

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

1 實(shí)數(shù)笛卡爾遺傳編程

1.1 RCVCGP編碼背景

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

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

1.2 RVCGP編解碼

由于RVCGP 的基因采用浮點(diǎn)數(shù)表示，所以從RVCGP 基因編碼到非循環(huán)有向圖的構(gòu)建需要進(jìn)行一個(gè)如下的解碼過程。

假設(shè)函數(shù)表中有n個(gè)函數(shù)，節(jié)點(diǎn)的函數(shù)基因?yàn)間，則其在函數(shù)表（事先決定的用于算法的一系列函數(shù)集合，如常用的加減乘除等）中的索引由式（1）給出；同樣假設(shè)一條染色體共有m個(gè)節(jié)點(diǎn)，某個(gè)連接基因?yàn)閏，則其對(duì)應(yīng)的連接節(jié)點(diǎn)索引由式（2）給出。

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

圖2 完整計(jì)算圖結(jié)構(gòu)Fig.2 Structure of complete computation diagram

RVCGP 采用1+λ的進(jìn)化策略，每次迭代都選擇一個(gè)當(dāng)前最優(yōu)個(gè)體作為父代，通過變異的手段生成λ個(gè)子代個(gè)體，然后對(duì)子代個(gè)體進(jìn)行適應(yīng)性評(píng)估，當(dāng)子代存在某個(gè)個(gè)體適應(yīng)值優(yōu)于父代個(gè)體適應(yīng)值時(shí)，將該子代個(gè)體替換為父代用于下一代繁殖。另外，當(dāng)子代存在的最優(yōu)個(gè)體的適應(yīng)值等于父代個(gè)體的適應(yīng)值時(shí)，也將用該最優(yōu)子代個(gè)體替換當(dāng)前父代，因?yàn)樵撟哟鷤€(gè)體已經(jīng)累計(jì)過足夠多的變異，有利于后續(xù)的進(jìn)化。進(jìn)化算法的終止條件可分為達(dá)到最大預(yù)設(shè)繁殖代數(shù)停止或達(dá)到一定的誤差值停止兩種方式，前者是在迭代了一定代數(shù)后結(jié)束進(jìn)化過程，后者是當(dāng)進(jìn)化過程中出現(xiàn)最優(yōu)個(gè)體適應(yīng)值滿足一定誤差條件后停止算法的迭代。

1.3 CGP在工程上的應(yīng)用

CGP 最早是一種用于進(jìn)化數(shù)字電路設(shè)計(jì)的算法，但同時(shí)CGP 也是基于圖結(jié)構(gòu)的算法，因此它和神經(jīng)網(wǎng)絡(luò)有著很好的適應(yīng)關(guān)系。因此，近年來隨著神經(jīng)網(wǎng)絡(luò)的發(fā)展，就有學(xué)者將CGP 和神經(jīng)網(wǎng)絡(luò)結(jié)合起來解決一些工程上的實(shí)際問題，如引言提到的用于乳腺癌檢測(cè)的基于CGP 的人工神經(jīng)網(wǎng)絡(luò)。另外相較于傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法，CGP 的一個(gè)明顯優(yōu)勢(shì)是它不會(huì)陷入局部最優(yōu)解，而且CGP 不僅可以學(xué)習(xí)調(diào)整神經(jīng)元之間的權(quán)重參數(shù)，它還可以學(xué)習(xí)調(diào)整整個(gè)神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，因此笛卡爾遺傳編程算法用來訓(xùn)練神經(jīng)網(wǎng)絡(luò)相較傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)訓(xùn)練方法有更廣泛的適用性。但如文獻(xiàn)［19］提到的利用CGP 進(jìn)行卷積神經(jīng)網(wǎng)絡(luò)的進(jìn)化時(shí)，其需要花費(fèi)比學(xué)習(xí)傳統(tǒng)算法更多的時(shí)間才能達(dá)到較好的效果，而且隨著神經(jīng)網(wǎng)絡(luò)層數(shù)的增多，其花費(fèi)的時(shí)間通常是不可接受的，因此該算法主要應(yīng)用在一些相對(duì)較淺的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中。

2 AD-RVCGP

2.1 準(zhǔn)反向變異背景

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

假設(shè)要尋找到的最優(yōu)解處在區(qū)間（a，b），對(duì)于任意X∈(a，b)，其對(duì)稱點(diǎn)X′=a+b-X，對(duì)于X的對(duì)稱點(diǎn)X′，有如下定理。

定理對(duì)于任意X∈(a，b)，其對(duì)稱點(diǎn)為X′，到最優(yōu)解的距離函數(shù)為d（?），概率函數(shù)為P（?），則有結(jié)論：P(d(X′) ＜d(X))=0.5。

證明 如圖3 所示，最優(yōu)解可能分布在區(qū)間（a，X］，（X，M］，（M，X′］，（X′，b）這四個(gè)區(qū)間。

圖3 準(zhǔn)對(duì)稱點(diǎn)的例子Fig.3 Example of quasi-symmetric points

最優(yōu)解落到區(qū)間(a，X]和(X′，b)的概率相等，因?yàn)閍到X和X′到b的距離相同，這時(shí)最優(yōu)解位于區(qū)間(a，X]時(shí)，顯然離X更近，而落到(X′，b)時(shí)，顯然離X′更近。

同樣，最優(yōu)解落到區(qū)間(X，M]和(M，X′]的概率相同，而最優(yōu)解位于區(qū)間(X，M]時(shí)，顯然離X更近，落到區(qū)間(M，X′]時(shí)，離X′更近。

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

這樣直接對(duì)X取其對(duì)稱點(diǎn)X′，從概率上來說X′離最優(yōu)解更近的概率不會(huì)比X離最優(yōu)解近的概率大，準(zhǔn)對(duì)稱點(diǎn)的提出改變了這種現(xiàn)狀。

準(zhǔn)對(duì)稱點(diǎn) 對(duì)任意X∈（a，b），X的對(duì)稱點(diǎn)為X′，關(guān)于X的準(zhǔn)對(duì)稱點(diǎn)Xopp由式（3）給出：

式中：M代表（a，b）的中點(diǎn)，rand(x，y)表示區(qū)間［x，y］中的隨機(jī)數(shù)。

在文獻(xiàn)［20］中，已經(jīng)證明了對(duì)于X的準(zhǔn)對(duì)稱點(diǎn)Xopp，它離最優(yōu)解更近的概率比X離最優(yōu)解更近的概率大。

2.2 準(zhǔn)反向變異和末端變異

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

準(zhǔn)反向變異的偽代碼在算法1給出。

算法1 準(zhǔn)反向變異。

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

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

2.3 反向個(gè)體

在RVCGP 中，每一個(gè)個(gè)體可以由一條包含多個(gè)節(jié)點(diǎn)的染色體所標(biāo)識(shí)，每個(gè)節(jié)點(diǎn)又由多個(gè)基因構(gòu)成。節(jié)點(diǎn)的連接基因決定了節(jié)點(diǎn)之間的連接結(jié)構(gòu)。對(duì)于一個(gè)個(gè)體的反向個(gè)體，有如下定義。

反向個(gè)體 對(duì)于一個(gè)個(gè)體M，對(duì)應(yīng)的染色體X，除去X的輸入和輸出節(jié)點(diǎn)后，將X中的激活節(jié)點(diǎn)變?yōu)榉羌せ罟?jié)點(diǎn)、非激活節(jié)點(diǎn)變?yōu)榧せ罟?jié)點(diǎn)而形成的新染色體X′對(duì)應(yīng)的個(gè)體M′被稱為M的反向個(gè)體。需要注意：一個(gè)個(gè)體的反向個(gè)體不止一個(gè)，因?yàn)樽兓蟮募せ罟?jié)點(diǎn)之間的連接方式不止一種。反向個(gè)體生成算法由算法2給出。

算法2 反向個(gè)體生成算法。

算法2 的主要功能是將一個(gè)個(gè)體中的激活節(jié)點(diǎn)和非激活節(jié)點(diǎn)的狀態(tài)進(jìn)行置換，算法先遍歷整個(gè)染色體包含的節(jié)點(diǎn)集合，將非激活節(jié)點(diǎn)加入到集合activeNodes中（它們將被變?yōu)榧せ顮顟B(tài)），隨后遍歷集合activeNodes中的每個(gè)激活節(jié)點(diǎn)為其設(shè)置連接節(jié)點(diǎn)。

2.4 AD-RVCGP描述

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

算法3 準(zhǔn)反向變異進(jìn)化算法。

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

2.5 AD-RVCGP收斂性分析

采用保留最優(yōu)個(gè)體的進(jìn)化算法在理論上是能保證算法的收斂性的，遺傳編程雖不同于傳統(tǒng)的進(jìn)化算法，但算法還是有保留當(dāng)前最優(yōu)個(gè)體的操作（最優(yōu)父代變異產(chǎn)生子代，而且子代中優(yōu)于當(dāng)前父代的個(gè)體將被選為最新父代）。因此，ADRVCGP在理論上是收斂的，下面給出簡(jiǎn)要證明。

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

表1 符號(hào)回歸函數(shù)Tab.1 Functions of symbolic regression

基于表2～5 對(duì)應(yīng)的算法參數(shù)分別利用CGP、RVCGP、SMCGP 和AD-RVCGP 對(duì)表1 的五個(gè)符號(hào)回歸函數(shù)進(jìn)行測(cè)試，每個(gè)符號(hào)回歸問題都測(cè)試100 次，四個(gè)算法分別都最多迭代10 000 次，然后統(tǒng)計(jì)成功找到表達(dá)式的次數(shù)、失敗的次數(shù)、成功的次數(shù)中平均迭代的次數(shù)、成功找到表達(dá)式所花費(fèi)的平均時(shí)間（單位：s）、最差命中次數(shù)，實(shí)驗(yàn)結(jié)果如表6所示。

表2 傳統(tǒng)CGP參數(shù)Tab.2 Parameters of traditional CGP

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

表3 RVCGP的參數(shù)Tab.3 Parameters of RVCGP

表4 SMCGP的參數(shù)Tab.4 Parameters of SMCGP

表5 AD-RVCGP的參數(shù)Tab.5 Parameters of AD-RVCGP

表6 不同算法的符號(hào)回歸測(cè)試性能對(duì)比Tab.6 Performance comparison of different algorithms in symbolic regression test

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

圖4 函數(shù)x6 -2x4 + x2收斂效果對(duì)比Fig.4 Comparison of convergence effect of function x6 -2x4 + x2

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

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

圖7 函數(shù)x5 -2x3 + x收斂效果對(duì)比Fig.7 Comparison of convergence effect of function x5 -2x3 + x

圖8 函數(shù)x4 + x3 + x2 + x收斂效果對(duì)比Fig.8 Comparison of convergence effect of function x4 + x3 + x2 + x

4 結(jié)語

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