郭 勇，張國鋒，劉麗萍

1.黔南民族師范學(xué)院 計算機與信息學(xué)院，貴州 都勻 558000

2.黔南民族師范學(xué)院 生命科學(xué)與農(nóng)學(xué)院，貴州 都勻 558000

1 引言

受生物界進化、學(xué)習(xí)、覓食等現(xiàn)象和行為的啟發(fā)，衍生了眾多的智能搜索算法，如遺傳算法（Genetic Algorithm，GA）[1]、蟻群算法（Ant Colony Optimization，ACO）[2]、人工魚群（Artificial Fish-Swarm Algorithm，AFSA）[3]、狼群算法（Wolf Pack Algorithm，WPA）[4]等，基因表達式編程（Gene Expression Programming，GEP）[5]是繼GA之后受基因遺傳理論啟發(fā)的另一種智能搜索算法。公開GEP文獻中大量使用形如的多項式函數(shù)進行實驗佐證，實驗表明多基因染色體GEP對多項式函數(shù)的挖掘具有較好的計算效果。在使用文獻[6]中包含了正弦函數(shù)sin x、自然對數(shù)函數(shù)ln x、平方根函數(shù)Sqrt(x)等1目運算符的非多項式函數(shù)作為測試函數(shù)時，傳統(tǒng)多基因染色體GEP的計算效果并不理想。為提升GEP對非多項式函數(shù)的挖掘能力，借鑒轉(zhuǎn)基因工程中的基因沉默現(xiàn)象，定義新的多基因染色體結(jié)構(gòu)，增加表達因子域，遵循“深度優(yōu)先”原則對染色體中的基因進行連接解碼，利用表達因子運算符的不同目數(shù)實現(xiàn)對染色體基因表達的抑制機制，通過遺傳算子中基因轉(zhuǎn)座算子和新的表達因子域突變算子，產(chǎn)生基因表達的位置效應(yīng)，拓展出一種基因表達式編程算法——SFGEP（Gene Expression Programming of Symbol Field，SFGEP），SFGEP對包多種運算目數(shù)的非多項式函數(shù)的挖掘能力得到顯著提升。

2 GEP與基因沉默簡介

2.1 GEP簡介

GEP以種群（Population）來模擬生命物種的遺傳進化，種群由若干個體（individual）組成，個體抽象為染色體（Chromosome），染色體由1個或多個基因（gene）組成，基因編碼字符集分操作符集F和終結(jié)符集T，基因的線性編碼稱為基因型，分為頭部（head）和尾部（tail），頭部編碼取自F?T，尾部編碼取自T，頭部長度h和尾部長度t需滿足關(guān)系式（1）。

式（1）中的M為運算操作符集F中的最大操作符目數(shù)。

基因編碼按照“廣度優(yōu)先”原則構(gòu)建的表達式樹，稱為表現(xiàn)型，對表現(xiàn)型表達式樹后序遍歷所得數(shù)學(xué)表達式稱為基因解釋。如F={+,-,*,/}和T={a,b}，頭部長度為6的基因型編碼“?+b*/aabbbabb”，其表現(xiàn)型表達式樹如圖1。

圖1 表達式樹

GEP通過選擇、突變、轉(zhuǎn)座、重組等遺傳算子實現(xiàn)種群的進化，通過適應(yīng)度及選擇算子來控制種群演化方向。適應(yīng)度函數(shù)可根據(jù)具體GEP問題進行設(shè)計，符號回歸問題常用絕對誤差、相對誤差等統(tǒng)計函數(shù)作為適應(yīng)度函數(shù)[7]：

2.2 基因沉默

基因沉默（gene silencing）[8]指生物中特定基因由于種種原因不表達或者表達減少的現(xiàn)象，是基因表達調(diào)節(jié)的一種重要手段?；虺聊F(xiàn)象最早在植物轉(zhuǎn)基因工程中受到關(guān)注，也稱轉(zhuǎn)基因失活。轉(zhuǎn)基因沉默分為轉(zhuǎn)錄水平與轉(zhuǎn)錄后水平兩種[9]，其中轉(zhuǎn)錄水平的轉(zhuǎn)基因失活有兩種情況，一種情況是導(dǎo)入的外源基因植入宿主基因組時，由于位置效應(yīng)，外源DNA位于轉(zhuǎn)錄的不活躍區(qū)，產(chǎn)生轉(zhuǎn)基因的異染色質(zhì)化，從而出現(xiàn)不轉(zhuǎn)錄或者低水平轉(zhuǎn)錄。另一種情況是轉(zhuǎn)基因反向重復(fù)區(qū)形成莖環(huán)結(jié)構(gòu)，重復(fù)同源拷貝數(shù)增加，出現(xiàn)甲基轉(zhuǎn)移酶異識別、甲基化，導(dǎo)致基因轉(zhuǎn)錄無法進行。

基因沉默的現(xiàn)象不僅存在轉(zhuǎn)基因工程中，在生物界也存在類似現(xiàn)象。如植物抗病毒侵染的自然機制——病毒誘導(dǎo)的基因沉默（Virus-Induced Gene Silencing，VIGS），又如返祖遺傳中祖先部分原有性狀的基因仍然存在，長期的進化使其不具備活性而沉默，由于多基因調(diào)控等因素而激活。轉(zhuǎn)基因沉默可以應(yīng)用于植物抗病的基因工程和植物功能基因組研究?；虺聊图せ畛聊虻募夹g(shù)具有正反兩方面的現(xiàn)實意義，一方面在保留優(yōu)良性狀的生物基因工程中需要克服基因沉默現(xiàn)象，使優(yōu)良基因得以表達，或者對生物原有優(yōu)勢性狀的沉默基因進行激活。另一方面可利用基因沉默屏蔽原有的病理基因或劣勢基因的表達。

3 基因沉默機制的SFGEP

3.1 GEP的“隨機性”和“冗余性”

“隨機性”是自然界演化普遍存在的現(xiàn)象，GEP作為一種仿生智能搜索算法，GEP遺傳算子的隨機性，使較小規(guī)模的種群可演化出更多可能模式，賦予了種群搜索GEP問題解的能力，保持一定的“隨機性”是智能搜索算法有效的基礎(chǔ)。在GEP基因中存在類似位置效應(yīng)而無法在GEP表現(xiàn)型中得以表達的編碼區(qū)域——中性區(qū)域，視為GEP基因編碼中的“冗余”現(xiàn)象，這種“冗余”因遺傳算子的實施而帶來更多演化結(jié)果的可能性。

傳統(tǒng)多基因染色體GEP中，采用固定連接運算符進行多基因的連接解釋，染色體結(jié)構(gòu)中基因個數(shù)固定，且所有基因在染色體的解釋中都得以表現(xiàn)激活，不具備“冗余”情況，也不具備某個基因不表達的“沉默”現(xiàn)象，演化的“隨機性”較弱。

3.2 SFGEP的染色體編碼結(jié)構(gòu)

SFGEP基因編碼字符集包含操作符集F和終結(jié)符集T。SFGEP染色體結(jié)構(gòu)由表達因子域S和表達基因域G兩部分組成，如圖2所示，表達因子域S的編碼全部或部分取自操作符集F，S的符號集記為F′。

圖2 SFGEP染色體結(jié)構(gòu)

圖3 SFGEP的染色體結(jié)構(gòu)

圖4 SFGEP染色體的堆棧解釋

圖2 中 fi表示1個運算操作符，稱為表達因子，gi表示單個基因，gi的編碼結(jié)構(gòu)與傳統(tǒng)GEP相同。S中表達因子個數(shù)m與G中基因個數(shù)n的數(shù)量關(guān)系滿足式（4）：

式（4）中的 M 為F的最大操作符目數(shù)。式（4）保證SFGEP解碼有足夠基因滿足S中所有表達因子運算的需要，使SFGEP染色體的結(jié)構(gòu)具備完備性。

3.3 SFGEP的遺傳算子

SFGEP的遺傳算子包括針對表達基因域與傳統(tǒng)GEP相同的遺傳算子：突變（單點、兩點）、轉(zhuǎn)座算子（IS、RIS）、基因轉(zhuǎn)座算子、重組算子（單點、兩點）。SFGEP增加了1種遺傳算子：表達因子域S的突變算子，簡稱為S突變，即在表達因子域S中隨機選擇1個突變位，隨機取F′中1個符號進行替換。

3.4 SFGEP染色體解釋

（1）單個基因的解釋

SFGEP表達基因域G中單個基因的解釋與標(biāo)準(zhǔn)GEP相同，遵循“廣度優(yōu)先建樹”、“后序遍歷表達式樹”等原則進行解釋，基于“建樹解釋”算法時空復(fù)雜度高，可使用文獻[10]等“無樹解釋”算法，提升基因解釋效率。

（2）染色體基因的連接解釋

SFGEP對G中基因采用文獻[11]“深度優(yōu)先”的堆棧解釋方式，由于S中的表達因子運算目數(shù)可能不相同，基本原則是“每個表達因子 fi都要從基因棧中彈出至少1個基因”，當(dāng) fi(i＞1)運算目數(shù)為1時，不需要彈出的基因參與解釋運算，則丟棄此基因，從而使此基因在解釋中沒有得到表達，成為“沉默基因”。

例1如圖3所示的SFGEP染色體，表達因子域S部分的編碼為6個運算操作符：+S－Q*/，表達基因域G包含7個基因，即關(guān)系式（4）取等號的情形。

例1中的SFGEP染色體基因連接堆棧解釋過程如圖4。圖4（d）和（f）中由于表達因子Q和S的目數(shù)為1，不需要彈出的基因g4和g6參與運算，即g4和g6沒有參與染色體的解釋，形成基因沉默現(xiàn)象，顯然沉默基因位受到了表達因子域中表達因子目數(shù)和位置的影響。

圖4（g）中表達因子棧為空是染色體基因連接解釋的終止條件。由于本例中表達基因域G基因個數(shù)取3.2節(jié)關(guān)系式（4）的“＝”情況，所以表達基因棧同時為空，若關(guān)系式（4）取“＞”，則基因棧中會存在冗余基因，這些冗余的基因與傳統(tǒng)GEP基因的中性區(qū)域編碼一樣，可因“基因轉(zhuǎn)座”算子等原因在演化中得以表達，形成另一種位置效應(yīng)。例1表達因子域S對表達基因域G中的基因“激活”解釋所得表現(xiàn)型如圖5。

圖5 SFGEP染色體基因的解釋

4 對比實驗與分析

本章以GEP公開文獻及文獻[6]中部分函數(shù)進行SFGEP與傳統(tǒng)多基因染色體GEP函數(shù)挖掘的對比實驗，實驗一的表達因子符號集F′與操作符集F相等，統(tǒng)計標(biāo)識為SFGEP-I，實驗二限制表達因子符號集F′取F中部分符號，統(tǒng)計標(biāo)識為SFGEP-II。

4.1 實驗一

目標(biāo)函數(shù)10個，其中前5個為公開文獻中常用的多項式函數(shù)，后5個為包含了1目和2目運算符的函數(shù)，在對應(yīng)取值范圍內(nèi)隨機生成20組精度為10-16的訓(xùn)練樣本。

表達因子域長度取3，關(guān)系式（4）取“＝”，所以表達基因域由4個基因構(gòu)成。傳統(tǒng)多基因GEP染色體也由4個基因構(gòu)成，采用“+”作為染色體基因連接運算符，函數(shù)F3的基因頭部長度為15，其他函數(shù)的基因頭部長度均為10，表達因子符號集F′=F。適應(yīng)度函數(shù)采用反映訓(xùn)練樣本集整體擬合度的統(tǒng)計函數(shù)R2：

其中m為樣本數(shù)，yi為樣本集第i個樣本函數(shù)，y′i為染色體對i樣本的解析值，yˉ為所有樣本解析的平均值。

實驗適應(yīng)度控制閾值取0.999 9，S突變率為0.1，其他遺傳算子參數(shù)設(shè)置如表1。

表1 遺傳算子參數(shù)設(shè)置

演化種群大小為100個染色體，控制演化最大輩數(shù)為5 000輩，使用C#設(shè)計程序?qū)γ總€目標(biāo)函數(shù)分別使用SFGEP和GEP連續(xù)演化100次。實驗統(tǒng)計項如表2。

（1）對于前5個多項式函數(shù)，傳統(tǒng)GEP整體計算效果優(yōu)于SFGEP，兩者的成功率無顯著差異。其原因主要在于本實驗中GEP采用“+”作為多基因染色體的連接運算符，連接運算結(jié)果：g1+g2+g3+g4，形式上與多項式函數(shù)相近，GEP演化成功輩數(shù)的3項指標(biāo)整體優(yōu)于SFGEP。但由于“+”滿足交換律，盡管傳統(tǒng)GEP多基因的連接運算采用“廣度優(yōu)先”原則如圖6（a），其運算結(jié)果與采用“深度優(yōu)先”原則如圖6（b）的結(jié)果相同，實驗中的操作符集F均含有“+”，顯然SFGEP的表達空間包含了GEP的表達空間，SFGEP隨機演化搜索到最優(yōu)解的概率相對較小，表現(xiàn)在平均成功輩數(shù)上SFGEP劣于傳統(tǒng)GEP。

圖6 多基因染色體連接解釋

（2）對于后面5個包含有1目和2目操作符的非多項式函數(shù)，除了相對簡單的函數(shù)F10外，其他略復(fù)雜的非多項式函數(shù)，SFGEP的整體計算效果明顯優(yōu)于傳統(tǒng)GEP，主要體現(xiàn)在成功率方面。特別是在F7、F8、F9這三個函數(shù)的成功率上，SFGEP大幅領(lǐng)先于傳統(tǒng)GEP。對于類似F10這樣形式較簡單的函數(shù)，SFGEP則不具備優(yōu)勢。

4.2 實驗二

針對實驗一中F10等函數(shù)的平均成功輩數(shù)較弱于傳統(tǒng)GEP的結(jié)果，采取表達因子符號集F′取操作符集F的部分符號的措施再進行對比實驗，即限制表達因子符號集F′的方法，并增加了以下五個目標(biāo)函數(shù)：

表2 實驗一數(shù)據(jù)統(tǒng)計

限制表達因子符號集F′的基本原則：（1）基于“+”與“－”、“*”與“/”的逆運算關(guān)系，二者取其一；（2）基于基本三角函數(shù)間的可換算關(guān)系，正弦函數(shù)、余弦函數(shù)、正切函數(shù)、余切函數(shù)四者取其一；（3）其他函數(shù)適當(dāng)取舍，保持表達因子符號集F′至少包含2個符號。各目標(biāo)函數(shù)的表達因子符號集F′如表3。

表3 實驗二表達因子符號集F′設(shè)置

演化的其他設(shè)置與實驗一相同，實驗主要統(tǒng)計了SFGEP-II與傳統(tǒng)GEP的成功率和平均成功輩數(shù)（四舍五入保留2位小數(shù)），成功率統(tǒng)計結(jié)果如表4。

表4 實驗二成功率統(tǒng)計%

表4數(shù)據(jù)表明，前5個多項式函數(shù)，SFGEP-II與GEP的成功率無顯著差異。后10個非多項式函數(shù)SFGEP-II成功率整體比GEP高，7個帶下劃線的數(shù)據(jù)具有非常明顯優(yōu)勢。平均成功輩數(shù)統(tǒng)計結(jié)果如圖7。

圖7（a）為多項式函數(shù) F1～F5對比。SFGEP-II在平均成功輩數(shù)上與傳統(tǒng)多基因染色體GEP仍有一定差距，但相較SFGEP-I來說差距大幅縮小，F(xiàn)1和F2基本無差異，F(xiàn)4反而是SFGEP-II的平均成功輩數(shù)更小。

圖7（b）為非多項式函數(shù)F6～F15的對比。由于GEP對F7的成功率為0，因而沒有列出。統(tǒng)計結(jié)果顯示，SFGEP-II在平均成功輩數(shù)上都優(yōu)于傳統(tǒng)多基因染色體GEP，體現(xiàn)了SFGEP對非多項式函數(shù)的總體收斂速度更快。

圖7（c）為非多項式函數(shù)的SFGEP-I與SFGEP-II的對比。除F7外，其余函數(shù)的SFGEP-II SFGEP-I的平均成功輩數(shù)小，這主要得益于適當(dāng)?shù)谋磉_因子限制使SFGEP-II的表達空間有所縮減。

5 SFGEP效能分析

5.1 SFGEP的計算復(fù)雜度分析

圖7 實驗二平均成功輩數(shù)統(tǒng)計

由于SFGEP染色體結(jié)構(gòu)中包含了表達因子域S，在SFGEP染色體的基因個數(shù)取式（4）中的大于符號時，SFGEP的空間復(fù)雜度略高于傳統(tǒng)多基因GEP，對巨大種群應(yīng)用情景有一定影響，在沒有突破硬件內(nèi)存極限的應(yīng)用環(huán)境中影響較小。

GEP的每代演化都要在樣本集上對種群所有個體進行解碼計算，其中染色體的每個基因的解碼總耗時最多。對于符號回歸問題，由于傳統(tǒng)GEP一般采用運算目數(shù)為2的加號對染色體中多個基因進行連接解釋，傳統(tǒng)GEP多基因染色體中的所有基因都需要進行基因解碼計算。SFGEP在進行染色體解釋的過程中，可能因為表達因子S中存在運算目數(shù)為1的運算符，形成部分沉默基因，染色體解釋不需要對這些沉默基因進行解碼計算。盡管SFGEP演化中多了1個S突變算子，由于一般其突變率較小，每代演化僅進行1次S突變，而每代演化基因解碼的計算量要大得多，加上多數(shù)符號回歸問題只包含1目或2目運算符，染色體結(jié)構(gòu)相近的SFGEP由于存在基因沉默現(xiàn)象，不需解碼沉默基因，需要解碼的基因總量相對傳統(tǒng)GEP更少。所以，從整體演化計算過程來看，在種群規(guī)模相同，染色體結(jié)構(gòu)基因數(shù)相近的情況下，SFGEP的計算時間復(fù)雜度不高于傳統(tǒng)多基因染色體GEP。

傳統(tǒng)多基因染色體GEP采用廣度優(yōu)先原則連接解釋多基因染色體的方式，當(dāng)不采用“+”（或“OR”）等具備交換律特性的連接符時，算法設(shè)計的時空復(fù)雜度較高，SFGEP采用深度優(yōu)先原則連接解釋多基因染色體，算法可使用時空復(fù)雜度更低的簡單循環(huán)結(jié)構(gòu)實現(xiàn)。

5.2 算法有效性分析

由于傳統(tǒng)多基因染色體GEP采用固定連接符號“+”（或“OR”）進行基因連接運算，使得從染色體結(jié)構(gòu)“模式”更接近于“多項式函數(shù)”，在多項式函數(shù)發(fā)現(xiàn)方面具有先天優(yōu)勢。SFGEP利用表達因子域中的多種符號進行基因的連接運算，染色體結(jié)構(gòu)“模式”較接近于非多項式函數(shù)，雖在多項式函數(shù)發(fā)現(xiàn)上有一定弱勢，但對第4章實驗中的非多項式函數(shù)的發(fā)現(xiàn)有明顯的優(yōu)勢。SFGEP既保持了對多項式函數(shù)的挖掘能力，同時具有良好的多種目數(shù)運算符、非多項式函數(shù)挖掘的效能。表達因子域的多操作符連接運算與“冗余”的基因域，使SFGEP可能包含更多形式的數(shù)學(xué)模型，從而帶來更多的選擇與可能，采用SFGEP有可能找到符合生產(chǎn)實際的數(shù)學(xué)模型，所以SFGEP具有一定的工程實踐意義。

SFGEP對非多項式函數(shù)符號回歸問題的有效性不僅因為“模式”上的優(yōu)勢，還來源于SFGEP采用深度優(yōu)先原則連接多基因，相對于傳統(tǒng)GEP的廣度連接，SFGEP染色體的表現(xiàn)型表達式樹更高，按照文獻[12]基于表現(xiàn)型的GEP解空間模型理論，在更高的表現(xiàn)型子空間中等價的最優(yōu)解接近于幾何級數(shù)的增長趨勢，相同基因數(shù)的染色體，SFGEP比傳統(tǒng)GEP探索更高子空間的能力更強，根據(jù)文獻[13-14]理論，隨著演化代數(shù)的增加，種群中適應(yīng)度更高的個體更多，SFGEP搜索到等價最優(yōu)解的概率更大。

6 結(jié)束語

GEP給出了一種非二進制編碼遺傳進化算法的基本思想與計算框架，在此基礎(chǔ)上許多GEP研究者針對解決不同類型問題和GEP效能的改進進行了GEP算法的拓展[15-20]，SFGEP給出了一種包含表達因子域的多基因染色體結(jié)構(gòu)和“深度優(yōu)先”、“多表達連接運算符”解釋染色體的GEP拓展計算框架，為解決生產(chǎn)實踐中的GEP問題提供了一種新計算方案的選擇。今后將進一步對SFGEP的生產(chǎn)實踐應(yīng)用、染色體基因數(shù)對演化效果的影響及調(diào)控、表達空間模式及其多解特性等方面深入研究。