基于統(tǒng)計(jì)分析和停滯速度的ＧＥＰ自動(dòng)建模

摘 要：介紹了基因表達(dá)式程序設(shè)計(jì)的基本原理，并針對經(jīng)典GEP算法存在的不足提出了一種基于統(tǒng)計(jì)分析和停滯速度的改進(jìn)GEP算法——SACVGEP。其特點(diǎn)在于：用重復(fù)體統(tǒng)計(jì)的方法改進(jìn)了初始種群的生成；提出停滯速度概念；引入了動(dòng)態(tài)變異算子。最后，將該算法用于求解復(fù)雜函數(shù)自動(dòng)建模并與傳統(tǒng)方法、神經(jīng)網(wǎng)絡(luò)方法、經(jīng)典GEP方法等進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，用此方法建立的模型比傳統(tǒng)方法、神經(jīng)網(wǎng)絡(luò)方法、經(jīng)典GEP等方法具有更好的性能。

關(guān)鍵詞：基因表達(dá)式程序設(shè)計(jì)； 自動(dòng)建模； 統(tǒng)計(jì)分析； 停滯速度

中圖分類號：TP391.9 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695(2008)08-2312-04

Automatic modeling of novel gene expression programming

based on statistical analysis and critical velocity

LI Kang-shun1，2， PAN Wei-feng1， ZHANG Wen-sheng2 ， WANG Feng3

(1.School of Information Engineering， Jiangxi University of Science Technology， Ganzhou Jiangxi 341000， China; 2.Institute of Automation， Chinese Academy of Sciences， Beijing 100080， China; 3.School of Computer， Wuhan University， Wuhan 430072， China)

Abstract:This paper briefly introduced the basic principle of GEP. And as to the shortcomings of classic GEP， proposed a novel GEP based on statistical analysis and stagnancy velocity (SACVGEP). It mainly had the following characteristics. First， improved the initial population by statistic analysis of repeat bodies. Second， introduced the concept of stagnancy velocity. Third， introduced dynamic mutation operator. Compared with other methods like traditional methods， neural network methods， classic GEP and its like in automatic modeling of complex function， the simulation results show that the SACVGEP is the best.

Key words：gene expression programming(GEP); automatic modeling; statistical analysis; critical velocity

基因表達(dá)式程序設(shè)計(jì)^[1]是演化計(jì)算家族中的新成員，是由葡萄牙科學(xué)家Candida于2001年草創(chuàng)的，是一種基于基因組和表現(xiàn)型組的新的自適應(yīng)演化算法。它綜合了遺傳算法（GA）和遺傳程序設(shè)計(jì)（GP）的優(yōu)點(diǎn)，具有染色體簡單、線性和緊湊、易于遺傳操作等優(yōu)點(diǎn)，比普通的遺傳編程在效率上高2~4個(gè)數(shù)量級^[2]。國內(nèi)在GEP研究方面以四川大學(xué)起步較早，已經(jīng)將其應(yīng)用于函數(shù)發(fā)現(xiàn)、時(shí)間序列預(yù)測、分類問題等領(lǐng)域^[3~6]；中國地質(zhì)大學(xué)也將GEP應(yīng)用于經(jīng)濟(jì)預(yù)測和瓦斯涌出量預(yù)測中^[7，8]。

函數(shù)自動(dòng)化建模(自動(dòng)化程序設(shè)計(jì))是預(yù)測領(lǐng)域的重要問題之一^[9]，最常用的方法是采用最小二乘法進(jìn)行曲線擬合來近似函數(shù)，但這種方法對問題的約束過多，而且只能求解簡單問題^[10]。目前，也有人用神經(jīng)網(wǎng)絡(luò)、遺傳程序設(shè)計(jì)等實(shí)現(xiàn)了復(fù)雜函數(shù)自動(dòng)建模^[10]，取得了較好的效果。鑒于GEP繼承自GP，具有與GP類似的基因結(jié)構(gòu)，這就為函數(shù)自動(dòng)建模提供了依據(jù)，也涌現(xiàn)了很多相關(guān)方面的文章^[11~14]。本文提出了一種基于統(tǒng)計(jì)分析和停滯速度的改進(jìn)GEP算法（SACVGEP），它對經(jīng)典GEP算法存在的多樣性表現(xiàn)不足、容易出現(xiàn)早熟、缺乏學(xué)習(xí)、搜索盲目等缺點(diǎn)進(jìn)行了改進(jìn)。

1 基因表達(dá)式程序設(shè)計(jì)原理

GEP是借鑒生物遺傳的基因表達(dá)規(guī)律提出的一種自適應(yīng)演化算法，它與GP一樣，都是在遺傳算法的基礎(chǔ)上發(fā)展起來的。GEP作為一種通用的自適應(yīng)隨機(jī)搜索算法，能夠在缺乏先驗(yàn)知識的情況下發(fā)現(xiàn)揭示問題本質(zhì)的規(guī)則、公式以及描述問題過程的程序等。本文對GEP作簡要介紹，詳細(xì)請參看文獻(xiàn)[2，15] 。

1.1 GEP的基因結(jié)構(gòu)與編碼

GEP的基因由頭部和尾部構(gòu)成，頭部既可以含有函數(shù)符號，也可以包含終結(jié)點(diǎn)，而尾部只能包含終結(jié)點(diǎn)。對具體的問題頭部長度h是根據(jù)問題需要選定的，而尾部長度t則是由h和n（參數(shù)最多的函數(shù)包含的參數(shù)個(gè)數(shù)）計(jì)算得到的。一般h、t和n要滿足式（1）的函數(shù)關(guān)系。

t=h*(n-1)+1（1）

考慮由{+，-，*，/，Q，a，b}構(gòu)成的基因（其中：Q代表開方），可得n=2。若假設(shè)h=8，那么t=9，則基因總長為8+9=17。也正是由于尾部與頭部滿足上述函數(shù)關(guān)系，才使得基因在任何遺傳算子作用下都不會(huì)產(chǎn)生句法上不正確的個(gè)體^[15]。

由于在GEP中個(gè)體被編碼成固定長度的線性串，然后表達(dá)成不同長度和形狀的非線性實(shí)體（表達(dá)式樹）。若有如下基因：＋－/Qaab*ab abaabba（2）

其中，黑體部分表示填充部分^[1]，在原來表達(dá)式中并不存在；非黑體部分是有效的符號序列，可以轉(zhuǎn)換成表達(dá)式樹（expression tree， ET），如圖1所示。

在將基因轉(zhuǎn)換成表達(dá)式樹的過程中，需要按照從左到右的順序閱讀基因中的字符，并按照層次順序構(gòu)成表達(dá)式樹。GEP的染色體如果由一個(gè)過分長的基因編碼，GEP的搜索效率將很低^[15]；如果基因太短則表達(dá)式的復(fù)雜程度很低。所以通常的GEP染色體由多個(gè)等長的基因構(gòu)成，而每個(gè)基因又可以表示成一棵子表達(dá)式樹，各個(gè)子表達(dá)式樹再通過連接函數(shù)構(gòu)成一棵完整的表達(dá)式樹，以此簡單編碼實(shí)現(xiàn)復(fù)雜問題求解的目的。目前，也有人在頭部和尾部的基礎(chǔ)上提出了頭、身、尾的算法^[16]，對經(jīng)典GEP算法中的基因結(jié)構(gòu)進(jìn)行改進(jìn)，提高了編碼的有效性。

1.2 GEP遺傳算子、適應(yīng)度函數(shù)、停機(jī)條件與算法流程

1.2.1 GEP遺傳算子

GEP遺傳操作包括以下五類遺傳算子：選擇算子、變異算子、插串操作、基因倒置、重組算子。由于GEP只要在進(jìn)行遺傳操作的過程中滿足保持基因的長度和尾部只能出現(xiàn)終結(jié)符，那么得到的子代染色體就仍然是合法的基因^[15，17]，所以這些算子都比較容易實(shí)現(xiàn)。

1）選擇算子 根據(jù)適應(yīng)度函數(shù)和賭盤原理，將染色體（基因組）復(fù)制到下一代中。個(gè)體的適應(yīng)度越好，它被復(fù)制到下一代的可能性越大。

2）變異算子 變異可以發(fā)生在染色體內(nèi)的任何位置，但染色體的結(jié)構(gòu)組織必須保持完整。在基因頭部，任何符號都可以變異成函數(shù)符號或終結(jié)點(diǎn)；在基因的尾部，終結(jié)點(diǎn)只能變異成終結(jié)點(diǎn)。

3）插串操作 GEP的可換位元素是由相鄰基因位組合起來的片段或串，它們可以被激活后插到染色體（基因組）中別的位置。在GEP中有三種插串操作，即IS插串、RIS插串、GT插串。

4）基因倒置 在GEP中，隨機(jī)選中染色體中的某個(gè)基因，再在該基因頭部隨機(jī)選擇某個(gè)序列，將該序列倒轉(zhuǎn)。這種變化稱為倒置，其作用域在基因頭部。

5）重組算子 在GEP中有三種重組算子：單點(diǎn)重組、兩點(diǎn)重組和基因重組。

1.2.2 GEP適應(yīng)度函數(shù)

在GEP中，適應(yīng)度函數(shù)設(shè)計(jì)非常重要，它直接影響到所建立模型的精確度。經(jīng)典GEP算法中有三種適應(yīng)度計(jì)算函數(shù)：

a）基于絕對誤差的適應(yīng)度函數(shù)

fi=∑Cij=1(M-|C（i，j）-T(j)|)(3)

b）基于相對誤差的適應(yīng)度函數(shù)

fi=∑Cij=1(M-|（C（i，j）-T(j)）/T(j)×100|)(4)

c）基于邏輯合成問題

if n≥Ct/2， then ft=n; else ft=1(5)

其中：M為一常量，是控制適應(yīng)度fi的取值范圍；C(i，j)表示第i個(gè)基因?qū)?yīng)的函數(shù)表達(dá)式中利用第j個(gè)樣本變量數(shù)據(jù)求得的函數(shù)值；T(j)表示第j個(gè)樣本中包含的實(shí)際測得的該目標(biāo)函數(shù)的真實(shí)值；Ct是測試樣本數(shù)據(jù)總數(shù)；n是正確適例的個(gè)數(shù)。

本文采用式（4）作為適應(yīng)度值的計(jì)算函數(shù)。

1.2.2 GEP停機(jī)條件

在GEP中算法的停機(jī)條件與GA中類似，即種群中最優(yōu)個(gè)體的適應(yīng)值達(dá)到了問題要求的精度或程序運(yùn)行了指定代數(shù)。

1.2.3 GEP算法結(jié)構(gòu)

GEP作為演化計(jì)算的新成員，繼承自GA和GP，具有與GA和GP類似的算法結(jié)構(gòu)。在GEP中，除了與GA似的單點(diǎn)重組、雙點(diǎn)重組、單點(diǎn)變異外，還包括插串操作、基因倒置等具有特色的算子。這些算子作用于GEP獨(dú)特的基因結(jié)構(gòu)，對GEP具有獨(dú)特的作用。其算法基本結(jié)構(gòu)如下：

創(chuàng)建初始化種群

loop

解碼種群中每個(gè)染色體

執(zhí)行解碼得到的程序

進(jìn)行適應(yīng)度評價(jià)

if 結(jié)束then

break;

end if保留最優(yōu)個(gè)體

選擇個(gè)體

復(fù)制

變異

插串

單點(diǎn)重組→雙點(diǎn)重組→基因重組

end loop2 對基因表達(dá)式程序設(shè)計(jì)的改進(jìn)

經(jīng)典GEP算法存在多樣性表現(xiàn)不足、容易出現(xiàn)早熟、缺乏學(xué)習(xí)、搜索盲目等缺點(diǎn)。本文對其作以下三點(diǎn)改進(jìn)：a）用重復(fù)體統(tǒng)計(jì)的方法改進(jìn)了初始種群的生成，使初始種群分布更均勻，個(gè)體多樣；b）提出停滯速度概念，以調(diào)整搜索范圍、控制進(jìn)化速度和提高預(yù)測的精確性；c）引入動(dòng)態(tài)變異算子以提高種群多樣性及算法收斂速度。本文提出了一種基于統(tǒng)計(jì)分析和停滯速度的改進(jìn)的GEP算法——SACVGEP。

2.1 基于重復(fù)體統(tǒng)計(jì)的種群初始化

GEP中的初始化種群是對解空間中個(gè)體的描述，對種群中個(gè)體的操作也就間接地映射為對解空間可能解的操作。因此如何使初始化種群中的個(gè)體分布均勻，將對后續(xù)的遺傳操作和算法最終的解都有很大的影響。初始化種群若在整個(gè)解空間中分布不均勻，都集中于某個(gè)區(qū)域，那該種群中的個(gè)體多樣性就有限，種群中個(gè)體的模式就比較少，對這樣的種群進(jìn)行遺傳操作，很有可能使算法在演化的中途就陷入局部解，很難收斂到目標(biāo)解；相反，初始種群若在解空間中分布均勻，幾乎觸及解空間的任何一個(gè)角落，那么這時(shí)的種群個(gè)體的多樣性就比較豐富，種群中個(gè)體的模式就比較多樣，對這樣的種群進(jìn)行遺傳操作，各種模式之間相互通信，形成更多的模式，種群將保持豐富多樣，有利于跳出局部解，收斂到目標(biāo)解。

筆者在初始化種群時(shí)都是借助一個(gè)偽隨機(jī)函數(shù)發(fā)生器來產(chǎn)生規(guī)定范圍的實(shí)數(shù)或是字符，通常都是通過srand（）和rand（）的組合來獲得所要的個(gè)體。這種方法只有在個(gè)體數(shù)量很豐富時(shí)種群分布才比較均勻；若個(gè)體選擇范圍比較小，如要產(chǎn)生0～20的100個(gè)實(shí)數(shù)，則可能出現(xiàn)這100個(gè)數(shù)中，個(gè)體在各個(gè)段分布不均勻。例如有30個(gè)值為10～11，而只有3個(gè)值為11～13的情況，導(dǎo)致種群分布不均勻。在GEP中，由于供選擇的非終結(jié)符和終結(jié)符有限，若仍然采用上面的方法，將導(dǎo)致可能出現(xiàn)上面所述的情況。為此，本文借鑒文獻(xiàn)[18]的思想，提出了一種基于基因重復(fù)體統(tǒng)計(jì)的種群初始化方法。

定義1 在GEP，若一個(gè)染色體含有numofGene個(gè)基因，在每個(gè)基因的頭部（尾部）含有的符號數(shù)目大于等于2時(shí)，統(tǒng)計(jì)所有基因?qū)?yīng)位置上某符號出現(xiàn)的次數(shù)有

countkij=1 for i to popSize k==gen[i][j]

0 otherwise

表示若popSize個(gè)基因在第j個(gè)位置上其字符等于k，則countkij為1；否則為0。

statistic[k][j]=∑popSizeicountkij;

表示統(tǒng)計(jì)popSize個(gè)基因在第j個(gè)位置上其字符等于k的次數(shù)，即字符k的重復(fù)次數(shù)。

下面將提供該初始化種群的方法，并與一般srand()和rand()組合的初始化種群方法進(jìn)行比較，說明該方法的有效性。基于重復(fù)體統(tǒng)計(jì)的初始化種群方法如下：

初始化函數(shù) initial_population(void)

{//子程序開始

a)用一般的srand()和rand()組合產(chǎn)生GEP初始種群。

b)對上述初始化的每個(gè)個(gè)體的各基因位進(jìn)行判斷，記錄各終結(jié)符和非終結(jié)符在各個(gè)位置出現(xiàn)的次數(shù)，如用statistic[0][j]表示終結(jié)符和非終結(jié)符數(shù)組中第0個(gè)元素在GEP個(gè)體第j個(gè)位置出現(xiàn)的次數(shù)。

c)根據(jù)GEP個(gè)體數(shù)popSize、每個(gè)個(gè)體含有的基因個(gè)數(shù)numberofGene以及終結(jié)符和非終結(jié)符數(shù)組第一維的大小M，這三者共同決定每個(gè)位置某符號的平均出現(xiàn)概率averagePro，即averagePro =(numberofGene * popSize)/M。

d)遍歷種群中每個(gè)個(gè)體和個(gè)體的每一位，統(tǒng)計(jì)某個(gè)終結(jié)符或非終結(jié)符重復(fù)出現(xiàn)的次數(shù)。對于由多個(gè)基因組成的個(gè)體，每個(gè)基因相對位置統(tǒng)計(jì)一次，即對每個(gè)個(gè)體中的各個(gè)位置取模（方法為population[i][j%geneLenght]）來判斷各個(gè)相對位置。

e)再次遍歷種群中每個(gè)個(gè)體和個(gè)體的每一位，若該位置某符號重復(fù)體出現(xiàn)次數(shù)大于averagePro，則查閱本位置其他個(gè)體中終結(jié)符和非終結(jié)符的出現(xiàn)情況，將其變異成相對小的那個(gè)終結(jié)符或非終結(jié)符。

}//子程序結(jié)束

通過該方法，即兩次遍歷種群，調(diào)整終結(jié)符和非終結(jié)符的分布，以達(dá)到使初始種群分布均勻的目的。

表1是一般初始化種群的方法和基于重復(fù)體統(tǒng)計(jì)的種群初始化方法在終結(jié)符和非終結(jié)符集合為{+，-，*，/，S，C，L，E，Q，P，a}、種群規(guī)模100、每個(gè)染色體由五個(gè)基因組成的情況下初始化個(gè)體，各個(gè)基因位上分布最多和分布最少的符號個(gè)數(shù)間的個(gè)數(shù)差。不考慮尾部，因?yàn)槲膊烤鸵粋€(gè)終結(jié)符a。

表1 一般初始化種群的方法與基于重復(fù)體統(tǒng)計(jì)的初始化方法的比較方法位置12345678一般方法最大差距1311282110302025改進(jìn)方法最大差距11111111從表1可以看出，經(jīng)過基于統(tǒng)計(jì)的初始化方法處理后的各個(gè)體，其內(nèi)部各基因位上各終結(jié)符和非終結(jié)符號的分布趨于相同。

2.2 引入停滯速度

定義2 當(dāng)初始種群在運(yùn)行了一定代數(shù)后，這時(shí)種群中的個(gè)體已經(jīng)比較相似，再運(yùn)行下去個(gè)體的適應(yīng)值也都不再改變了，將這個(gè)代數(shù)定義為停滯速度。提出停滯速度的概念以調(diào)整搜索范圍、控制進(jìn)化速度和提高預(yù)測的精確性。本文提出的停滯速度將在演化的早期發(fā)生停滯時(shí)和演化的末期發(fā)生停滯時(shí)這兩個(gè)階段發(fā)揮作用。

在演化的早期，筆者設(shè)定的停滯速度相對小一點(diǎn)，以此來加快演化的速度。若在這個(gè)階段算法運(yùn)行達(dá)到了停滯速度，表明這時(shí)種群中可能不能立即獲得更好的個(gè)體或模式。可以引入stopPopNum個(gè)隨機(jī)產(chǎn)生的個(gè)體來豐富種群中的個(gè)體，增加個(gè)體的模式，增加算法向更好的解演化的可能性和速度。考慮到停滯速度的選擇問題，這時(shí)的stopPopNum一般選擇得相對小一點(diǎn)，以降低可能對已經(jīng)獲得的相對好的個(gè)體或模式的破壞作用。

在演化的末期，種群中的個(gè)體適應(yīng)值都相對較高了，種群中的模式也是比較優(yōu)秀的，個(gè)體間模式的差別都已經(jīng)較小，種群多樣性很有限。若這時(shí)不對種群進(jìn)行任何操作，繼續(xù)演化下去，則算法獲得更好的解的可能性是很低的。所以在這個(gè)階段，可以引入大一點(diǎn)的停滯速度來適當(dāng)調(diào)整種群中的個(gè)體，提高種群的多樣性。若算法在演化末期達(dá)到了停滯速度，可以引入stopPopNum1個(gè)隨機(jī)產(chǎn)生的個(gè)體來提高種群的多樣性。考慮到演化末期，種群中個(gè)體間的差距和種群的多樣性問題，可以將stopPopNum1設(shè)置得較大一點(diǎn)，使種群中的個(gè)體更豐富，使種群具有更加豐富的個(gè)體模式，以此來提高獲得更好解的可能性。而且，鑒于算法運(yùn)行在停滯時(shí)期和非停滯時(shí)期這兩個(gè)階段時(shí)演化速度存在差異，筆者對停滯階段的遺傳操作進(jìn)行了控制，讓其在每步遺傳操作后都進(jìn)行測試，判斷其是否比它的父輩好，一旦有所改進(jìn)，就立即進(jìn)行替換。這樣處理可以加快在停滯階段算法的收斂速度。下面列出引入外來個(gè)體的算法。

引入外來個(gè)體算法exoticIndividual()

{//子程序開始

if(是否到達(dá)了停滯速度)

{

if(是演化早期停滯速度)

隨機(jī)生成stopPopNum個(gè)外來個(gè)體，替換種群中適應(yīng)值相對較低的相應(yīng)數(shù)量個(gè)體；

else

隨機(jī)生成stopPopNum1個(gè)外來個(gè)體，替換種群中適應(yīng)值相對較低的相應(yīng)數(shù)量個(gè)體；

}

else不進(jìn)行任何操作；

}//子程序結(jié)束

2.3 引入動(dòng)態(tài)變異算子

變異算子是保持種群多樣性的有利措施，好的變異算子可以使得群體覆蓋面大大增加，而經(jīng)典GEP中變異算子過于簡單，使得種群多樣性有限，極易出現(xiàn)早熟現(xiàn)象。但是變異操作是盲目的，它在算法初期發(fā)揮作用較大。當(dāng)算法快收斂到近似解時(shí)，變異算子所起的作用比較小，所以很有必要?jiǎng)討B(tài)地改變算法變異算子的選擇概率，使得適應(yīng)值低的個(gè)體對應(yīng)更大的變異概率，適應(yīng)值高的個(gè)體對應(yīng)更小的變異概率，以實(shí)現(xiàn)提高算法收斂速度的目的。

pM=pM×(1-(gen×0.01)/maxGen)+

pM×(1-fitness[icon[popSize-1]]/fitness[ti]) (6)

其中：pM代表變異概率；gen代表當(dāng)前演化的代數(shù)；maxGen代表種群的最大演化代數(shù)；fitness[]是存儲個(gè)體適應(yīng)值的數(shù)組；icon[]中是存儲個(gè)體按照適應(yīng)值從大到小排序后的下標(biāo)在原個(gè)體數(shù)組中的位置；popSize是種群規(guī)模；ti是當(dāng)前個(gè)體對應(yīng)的適應(yīng)值在適應(yīng)值數(shù)組中的下標(biāo)。

通過式（6）可以發(fā)現(xiàn)，在演化的初期pM比較大，在演化的后期pM比較小，符合算法對變異算子的要求。引入動(dòng)態(tài)變異算子算法如下：

引入動(dòng)態(tài)變異算子算法mutation()

{//子程序開始

先隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)p；由式（6）產(chǎn)生一個(gè)pM；

if(p＜pM)

{對每個(gè)基因都產(chǎn)生一個(gè)變異位；取出各個(gè)變異位置判斷是頭部還是尾部，分別進(jìn)行變異；}

else 不進(jìn)行任何操作；

if(是演化晚期)

{if(優(yōu)于父體)

替換父體；}

else 不進(jìn)行任何操作；

}//子程序結(jié)束

3 仿真實(shí)驗(yàn)與分析

筆者將SACVGEP算法用于求解復(fù)雜函數(shù)自動(dòng)建模，并與傳統(tǒng)方法、神經(jīng)網(wǎng)絡(luò)方法、經(jīng)典GEP方法和其他一些改進(jìn)GEP算法進(jìn)行對比。為了與相關(guān)文獻(xiàn)形成對比，本章選用的例子都是從要進(jìn)行對比的文獻(xiàn)中選取。

1)算法參數(shù)設(shè)置(表2)

表2 各實(shí)驗(yàn)公共參數(shù)設(shè)置參數(shù)名稱參數(shù)值參數(shù)名稱參數(shù)值演化代數(shù)1 000種群規(guī)模100基因頭部長度8基因尾部長度9單染色體基因數(shù)5基因連接符＋停滯速度（早期）20停滯速度（末期）30stopPopNum20stopPopNum140變異概率0.044IS變換概率0.1RIS變換概率0.1單點(diǎn)重組概率0.3雙點(diǎn)重組概率0.3基因重組概率0.12）實(shí)驗(yàn)一

數(shù)據(jù)來源于文獻(xiàn)[19]。在某化學(xué)反應(yīng)中，測得生成物的濃度y與時(shí)間t的數(shù)據(jù)表，試找出t與y的關(guān)系式（表3）。

表3 生成物濃縮與時(shí)間關(guān)系t/miny/%t/miny/%t/miny/%t/miny/%14.0059.22910.01310.5026.4069.501010.21410.5538.0079.701110.321510.5848.8089.861210.421610.60在本實(shí)驗(yàn)中，設(shè)定終結(jié)符和非終結(jié)符集為F={+，-，*，/，S，C，L，E，Q，P，t}。其中：S表示sin()函數(shù)；C表示cos()函數(shù)；L代表log()函數(shù)；E代表指數(shù)函數(shù)ex；Q代表sqrt()開方函數(shù)；P代表pow()冪函數(shù)；t表示時(shí)間。運(yùn)行算法五次得到最好函數(shù)模型為

y=esin(sin(log a))+a+sin(log(elog a-log a/a2))+

log(sin(sin a-a)+3a)+sin(esin(sin(sin(esina))))

與文獻(xiàn)[11，12，19]中最好結(jié)果進(jìn)行比較，如表4所示。

表4 與各文獻(xiàn)進(jìn)行比較雙曲

線型指數(shù)

類型神經(jīng)

網(wǎng)絡(luò)GP2GEPIGEPSASV

GEP均

方

差37.77637.7760.242 40.227 10.115 20.233 20.106 45550699390777383圖2為用SACVGEP求解實(shí)驗(yàn)一的最好的擬合曲線。從圖2可以看出，用SACVGEP方法求解實(shí)驗(yàn)一的效果較其他的方法好，由它擬合的曲線幾乎與真實(shí)值曲線重合。

3）實(shí)驗(yàn)二

數(shù)據(jù)來源于文獻(xiàn)[19]。某物理實(shí)驗(yàn)中電流I(xiàn)通過2 Ω的電阻，用伏特表測得電阻兩端的電壓為V，多次實(shí)驗(yàn)測得的數(shù)據(jù)如表5所示，要求找出I(xiàn)與V的關(guān)系式φ(I)，使得其滿足V=φ(I)。

表5 電流I(xiàn)與V的數(shù)據(jù)關(guān)系I(xiàn)/A1246810V/V1.83.78.212.015.820.2在本實(shí)驗(yàn)中，設(shè)定終結(jié)符和非終結(jié)符集為F={+，-，*，/，S，C，L，E，Q，P，I}。其中：S表示sin()函數(shù)；C表示cos()函數(shù)；L代表log()函數(shù)；E代表指數(shù)函數(shù)ex；Q代表sqrt()開方函數(shù)；P代表pow()冪函數(shù)；I(xiàn)表示電流。運(yùn)行算法五次得到最好的函數(shù)模型為

V=Icos(log(cos(log(cos(sin(I(xiàn)))))))+elog I(xiàn)+

((cos(I(xiàn)2))I(xiàn))log(eI2)+sin((cos(1)-sin I(xiàn))/eI(xiàn))+

sin((1+sin I(xiàn))/(-eI))

與文獻(xiàn)[19，20]中最好結(jié)果進(jìn)行比較如表6所示。

表6 與各文獻(xiàn)進(jìn)行比較文獻(xiàn)[20]GP1GP2SASVGEP最小二乘誤差0.172 50.1580 840.087 2340.005 157 25圖3為用SACVGEP求解實(shí)驗(yàn)二的最好擬合曲線。

從圖3可以看出，用SACVGEP方法求解實(shí)驗(yàn)二的效果較其他方法好，由它擬合的曲線幾乎與真實(shí)值曲線重合。

4 結(jié)束語

本文從介紹GEP的基本原理入手，并針對經(jīng)典GEP存在的問題對它進(jìn)行了改進(jìn)，引入了重復(fù)體統(tǒng)計(jì)方法改進(jìn)了初始種群的生成，使初始種群分布更均勻，個(gè)體多樣；提出了停滯速度概念，適當(dāng)調(diào)整搜索范圍，控制種群進(jìn)化速度、多樣性和預(yù)測的精確性；引入動(dòng)態(tài)變異算子提高種群多樣性、算法收斂速度。最后的仿真實(shí)驗(yàn)也說明，在求解復(fù)雜函數(shù)自動(dòng)化建模方面，SACVGEP比傳統(tǒng)方法、神經(jīng)網(wǎng)絡(luò)方法、經(jīng)典GEP方法以及其他一些改進(jìn)的GEP算法具有更好的性能。

參考文獻(xiàn)：

[1]CANDIDA F. Gene expression programming: a new adaptive algorithm for solving problems [J]. Complex Systems， 2001， 13(2):87-129.

[2]CANDIDA F. Gene expression programming [M]. Portugal: Angra do Heroismo， 2002.

[3]ZUO Jie， TANG Chang-jie， LI Chuan， et al. Time series prediction based on gene expression programming[C]//Lecture Notes in Compu-ter Science， vol 3129. Berling: Springer-Verlag， 2004:55-66.

[4]黃曉冬，唐常杰，李智，等. 基于基因表達(dá)式編程挖掘函數(shù)關(guān)系[J]. 軟件學(xué)報(bào)， 2004， 15（增刊）:96-105.

[5]賈曉斌，唐常杰，鐘義嘯，等. 頻繁函數(shù)集的可配置挖掘算法[J].計(jì)算機(jī)研究與發(fā)展， 2004， 41（增刊）:240-245.

[6]段磊，唐常杰，左劼，等. 基于基因表達(dá)式編程的抗噪聲數(shù)據(jù)的函數(shù)挖掘方法[J]. 計(jì)算機(jī)研究與發(fā)展， 2004， 41(10):1684-1689.

[7]李曲， 蔡之華， 朱莉， 等. 基因表達(dá)式程序設(shè)計(jì)方法在采煤工作面瓦斯涌出量預(yù)測中的應(yīng)用[J]. 應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報(bào)， 2004，12(1): 49-54.

[8]李曲， 蔡之華， 蔣思偉，等. 基因表達(dá)式程序設(shè)計(jì)在預(yù)測中的應(yīng)用研究[C]// 第五屆全球智能控制與自動(dòng)化大會(huì).2004：2171-2175.

[9]潘正君，康立山，陳毓屏. 演化計(jì)算[M].北京: 清華大學(xué)出版社，1998.

[10]張群飛， 黃建國， 保錚. 用子空間旋轉(zhuǎn)不變法同時(shí)估計(jì)水下多目標(biāo)的距離和方位[J]. 聲學(xué)學(xué)報(bào)， 1999， 24(4): 400-406.

[11]龔文引，蔡之華，劉亞東. 基因表達(dá)式程序設(shè)計(jì)在復(fù)雜函數(shù)自動(dòng)建模中的應(yīng)用[J]. 系統(tǒng)仿真學(xué)報(bào)， 2006， 18(6): 1450-1457.

[12]方旺盛，張克俊，召利平. 基于改進(jìn)的基因表達(dá)式編程的復(fù)雜函數(shù)建模[J]. 計(jì)算機(jī)工程， 2006， 32(21): 188-190.

[13]陸昕為，蔡之華. 一種改進(jìn)的GEP方法及其在演化建模預(yù)測中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用， 2005， 25(12): 2783-2786.

[14]杜欣，劉坤起，陳玉軍，等. 改進(jìn)的基因表達(dá)式程序設(shè)計(jì)實(shí)現(xiàn)復(fù)雜函數(shù)的自動(dòng)建模[J]. 微計(jì)算機(jī)信息， 2006， 22(6): 295-297.

[15]左劼．基于表達(dá)式編程核心技術(shù)研究[D]．成都：四川大學(xué)，2004．

[16]LI Zhen-hua， KANG Li-shan. Effect of learning selection and head-body expression on GEP function finding in the one-dimensional parameter space progress in intelligence computation and applications[C]// Proc of ISICA’ 2005.2005: 819-822.

[17]MUTATIION C. Mutation， transposition， and recombination: an ana-lysis of the evolutionary dynamics [C]// Proc of the 4th International Workshop on Frontiers in Evolutionary Algorithms . North Carolina: [s.n.]， 2002:614- 617.

[18]胡建軍，唐常杰，段磊，等. 基因表達(dá)式編程初始種群多樣化策略[J]. 計(jì)算機(jī)學(xué)報(bào)， 2007， 30(2): 305-310.

[19]周愛民，曹宏慶，康立山，等. 用遺傳程序設(shè)計(jì)實(shí)現(xiàn)復(fù)雜函數(shù)的自動(dòng)建模[J]. 系統(tǒng)仿真學(xué)報(bào)， 2003， 15(6): 797-799.

[20]李有法. 數(shù)值計(jì)算方法[M].北京: 高等教育出版社，1996.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文