基于小生境的GEP新算法

莫海芳，李康順，彭 川

（1.中南民族大學(xué) 計(jì)算與實(shí)驗(yàn)中心，湖北 武漢430074；2.華南農(nóng)業(yè)大學(xué) 信息學(xué)院，廣東 廣州510642）

0 引 言

基因 表 達(dá) 式 編 程（gene expression programming，GEP）作為一種新的演化算法，在演化建模［1－3］，神經(jīng)網(wǎng)絡(luò)［4］和分類［5］等領(lǐng)域取得了很好的應(yīng)用結(jié)果。但是，作為一種隨機(jī)搜索算法，GEP也存在早熟和陷入局部最優(yōu)的缺陷。很多學(xué)者對(duì)GEP進(jìn)行了跟蹤研究并提出不同的改進(jìn)算法，其中避免算法過(guò)早收斂和提高算法收斂速度是改進(jìn)的主要方向。

眾所周知，群體多樣性的過(guò)早缺失會(huì)導(dǎo)致算法早熟收斂。因此，能否保持合適的群體多樣性水平，對(duì)算法的全局收斂性有直接的影響。文獻(xiàn)［6］引入基因漂移和漂移抑制的概念，通過(guò)漂移抑制算子控制基因的過(guò)度漂移，同時(shí)保持種群的多樣性。文獻(xiàn)［7］提出基因空間均勻分布策略，提高初始種群的基因多樣性，從而提高進(jìn)化效率。文獻(xiàn)［8］使用帶權(quán)的函數(shù)符和終結(jié)符，以保證初始種群具有豐富的多樣性，同時(shí)采用自適應(yīng)的交叉和變異算子，維持進(jìn)化過(guò)程中的種群多樣性。但這種方法需要先驗(yàn)知識(shí)來(lái)設(shè)定染色體中各符號(hào)的概率。文獻(xiàn)［9］采用變種群策略，在進(jìn)化初期，采用較小規(guī)模的種群；進(jìn)化過(guò)程中，引入新個(gè)體，增大種群規(guī)模，增加基因多樣性。但是，增大種群規(guī)模也增加了GEP每代進(jìn)化所耗費(fèi)的時(shí)間。也有文獻(xiàn)在GEP中用小生境技術(shù)保持群體的多樣性［10－11］。

提出一種基于小生境的GEP新算法，該算法能夠避免演化后期出現(xiàn)大量重復(fù)個(gè)體，使群體在整個(gè)演化過(guò)程都能保持個(gè)體的多樣性。使得改進(jìn)后的GEP新算法能有效的避免早熟收斂，提高算法的全局搜索效率。

1 基因表達(dá)式編程

GEP的編碼方式是長(zhǎng)度固定的線性符號(hào)串，稱為GEP染色體。一個(gè)染色體包含一個(gè)或多個(gè)基因。每個(gè)基因由頭部和尾部組成，頭部允許出現(xiàn)終結(jié)符和函數(shù)符號(hào)，尾部只能出現(xiàn)終結(jié)符。

頭部的長(zhǎng)度h是事先設(shè)定的，而尾部的長(zhǎng)度t則由以下公式計(jì)算得到

式中：n——所使用的函數(shù)集中需要參數(shù)最多的函數(shù)的參數(shù)個(gè)數(shù)。假設(shè)符號(hào)集為 ｛＋，－，＊，＼｝，則n＝2。設(shè)h＝3，則尾部長(zhǎng)度t＝4。于是，

GEP基因的基因型是K表達(dá)式（K－expression），表現(xiàn)型為表達(dá)式樹(shù)（expression tree）。兩者之間可以相互轉(zhuǎn)換。

K表達(dá)式解碼為表達(dá)式樹(shù)的方法是：按從左到右的順序逐一讀取基因中的字符，然后根據(jù)語(yǔ)法規(guī)則按照層次順序從上到下，從左到右排放即可。反之，對(duì)表達(dá)式樹(shù)按照從上到下，從左到右的順序遍歷，即可得到對(duì)應(yīng)的K表達(dá)式。

以基因（2）為例，其對(duì)應(yīng)的表達(dá)式樹(shù)如圖1所示，其對(duì)應(yīng)的K表達(dá)式是

其對(duì)應(yīng)的數(shù)學(xué)公式是

圖1 基因（2）對(duì)應(yīng)的表達(dá)式樹(shù)

顯然，GEP基因的K表達(dá)式是編碼部分從頭開(kāi)始的有效部分，尾部的符號(hào)不一定全部有用。如基因（2）尾部最后的兩個(gè)符號(hào)“bb”并沒(méi)有出現(xiàn)在K表達(dá)式中。

而對(duì)于如下基因

其對(duì)應(yīng)的表達(dá)式樹(shù)如圖2所示，它表示的數(shù)學(xué)公式是

對(duì)應(yīng)的K表達(dá)式是

在這里，基因編碼的所有符號(hào)都出現(xiàn)在K表達(dá)式中。

圖2 基因（5）對(duì)應(yīng)的表達(dá)式樹(shù)

1.1 基于小生境技術(shù)的GEP

演化算法師法自然，模擬自然界的生物演化過(guò)程。但在實(shí)際的演化算法設(shè)計(jì)過(guò)程中，群體的規(guī)模一般只有幾十或幾百，這個(gè)數(shù)字與生物界的物種規(guī)模相差甚遠(yuǎn)。另外，演化算法的雜交和變異是隨機(jī)的，這種隨機(jī)性在演化初期能夠保持解的多樣性，但在演化后期，如果出現(xiàn)了“超級(jí)個(gè)體”，該個(gè)體可能很快就會(huì)得到大量繁殖，導(dǎo)致算法過(guò)早地收斂到一個(gè)局部最優(yōu)點(diǎn)，這種現(xiàn)象稱為過(guò)早收斂（早熟收斂）。作為演化算法的一種，傳統(tǒng)的GEP同樣具有容易陷入局部最優(yōu)的缺陷。

為了保持群體的多樣性，提高算法的全局尋優(yōu)能力和收斂速度，小生境理論被廣泛應(yīng)用到演化算法中。

小生境的基本思想來(lái)源于自然界中，特征、形狀相似的物種往往聚在一起，并與同類交配繁衍后代。反映到演化算法中就是要讓算法中的個(gè)體在一個(gè)特定的生存環(huán)境中進(jìn)化?；谛∩车难莼惴ǎ逊N群劃分為若干小生境，每個(gè)小生境就是具有相似適應(yīng)值的個(gè)體的集合。然后在小生境內(nèi)部以及小生境之間，通過(guò)雜交、變異產(chǎn)生新一代群體，然后采用預(yù)選擇（preselection）機(jī)制、排擠（crowding）機(jī)制或分享（sharing）機(jī)制完成對(duì)種群的選擇操作。

小生境技術(shù)主要是對(duì)演化算法中常規(guī)的選擇策略進(jìn)行改進(jìn)?；陬A(yù)選擇機(jī)制的選擇策略，其基本做法是：只有當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度超過(guò)其父代個(gè)體的適應(yīng)度時(shí)，該子代才能代替其父代而遺傳到下一代群體中去，否則保留父代個(gè)體。由于子代個(gè)體與父代個(gè)體相似，所以替換掉的是結(jié)構(gòu)相似的個(gè)體，從而能維持種群的多樣性。

清除（Clearing）算法類似于適應(yīng)值共享，它需要的參數(shù)包括小生境半徑σ和小生境的容量χ。算法先對(duì)群體中的個(gè)體按適應(yīng)值降序排列。然后對(duì)種群中的每個(gè)個(gè)體逐一進(jìn)行判斷：如果個(gè)體i的適應(yīng)值大于0并且它和所有小生境中心的距離都大于σ，那么以該個(gè)體為中心形成新的小生境；如果個(gè)體i到某個(gè)小生境中心的距離小于σ，并且該小生境中的個(gè)體數(shù)量小于χ，那么該個(gè)體被添加到該小生境中，該小生境中的個(gè)體數(shù)量加l；不滿足以上條件的個(gè)體，其適應(yīng)值被設(shè)置為0。

文獻(xiàn)［10］將小生境概念引入到GEP中，實(shí)現(xiàn)用GEP進(jìn)行多模函數(shù)優(yōu)化。文獻(xiàn)［11］在GEP中采用改進(jìn)的k－均值的聚類分析，保持群體多樣性，提高算法跳出局部最優(yōu)的能力。但是算法需要對(duì)種群個(gè)體進(jìn)行排序，增加了算法復(fù)雜度。

1.2 多樣性的測(cè)度

生物學(xué)中的多樣性是指種群中個(gè)體的不同，包括個(gè)體結(jié)構(gòu)和行為的差異。在演化算法中，種群的多樣性往往指基因結(jié)構(gòu)的差異，或者是適應(yīng)值的差異。

本文采用多基因的染色體，多基因之間用加法連接，基因的順序?qū)φ麄€(gè)染色體的適應(yīng)值沒(méi)有影響。因此，不便于用基因結(jié)構(gòu)來(lái)描述其差異，而是直接采用適應(yīng)值的不同來(lái)描述種群多樣性。

定義1 假定種群規(guī)模為N，第t代的種群中不同個(gè)體的數(shù)目記為n（t），種群的多樣度記為

顯然，0＜D（t）≤1，D（t）越大，則群體的多樣性就越豐富。

2 基于改進(jìn)小生境技術(shù)的GEP

文獻(xiàn)［2］以挖掘函數(shù)f（n）＝5n4＋4n3＋3n2＋2n＋1為例，分析了不同遺傳算子對(duì)種群多樣性的影響，并指出：重組算子（包括基因交換、單點(diǎn)雜交和兩點(diǎn)雜交）容易產(chǎn)生大量相同個(gè)體并最終導(dǎo)致種群完全失去多樣性，因此常常容易出現(xiàn)過(guò)早收斂的現(xiàn)象。

基于小生境的GEP新算法niche－GEP，采用類似于清除算法的小生境技術(shù)，其參數(shù)包括小生境半徑σ和小生境容量x。小生境半徑σ設(shè)置為0，即相同適應(yīng)值的個(gè)體組成一個(gè)小生境；小生境容量x限定了適應(yīng)值相同的個(gè)體的數(shù)量上限，避免出現(xiàn)大量重復(fù)個(gè)體。需要說(shuō)明的是，具有相同編碼的個(gè)體，它們的適應(yīng)值一定是相等的；但具有相同適應(yīng)值的個(gè)體，它們的編碼不一定相同。

清除算法需要對(duì)種群按適應(yīng)值大小進(jìn)行降序排序，以保證每個(gè)小生境的中心是該小生境中適應(yīng)值最大的個(gè)體，同時(shí)也保證淘汰掉的是相似個(gè)體中適應(yīng)值較小的個(gè)體。但是排序也增加了算法的計(jì)算量。

niche－GEP算法不需要進(jìn)行排序。因?yàn)樗胁煌m應(yīng)值的個(gè)體都得以保留，即使是適應(yīng)值相似的個(gè)體。當(dāng)相同適應(yīng)值的個(gè)體數(shù)量超過(guò)小生境容量x時(shí)，超過(guò)的個(gè)體被初始化。在演化算法中，初始化部分個(gè)體是增加種群多樣性的有效方法之一。這些被重新初始化的個(gè)體，增加了種群的多樣性，也許其適應(yīng)值很小，但是有可能包含良好的基因片段，在經(jīng)過(guò)雜交、變異后，產(chǎn)生優(yōu)良個(gè)體。

改進(jìn)的小生境算法描述如下：

其中，x為小生境容量，same（i）表示與個(gè)體i適應(yīng)值相同的個(gè)體的數(shù)量，fitness（i）表示個(gè)體i的適應(yīng)值，initialize（i）表示初始化個(gè)體i。

niche－GEP算法框架如下：

步驟1 初始化種群并計(jì)算種群中所有個(gè)體的適應(yīng)值。

步驟2 對(duì)種群中的個(gè)體進(jìn)行變異、重組等遺傳操作，產(chǎn)生后代。當(dāng)后代個(gè)體的適應(yīng)值大于父代個(gè)體的適應(yīng)值時(shí)，取代父代個(gè)體，否則保留父代個(gè)體。

步驟3 通過(guò)小生境技術(shù)初始化部分重復(fù)個(gè)體。

步驟4 如果達(dá)到設(shè)定的最大演化代數(shù)，則結(jié)束運(yùn)行，否則轉(zhuǎn)到步驟2。

3 仿真試驗(yàn)及分析

分別對(duì)一元函數(shù)和二元函數(shù)進(jìn)行試驗(yàn)，小生境容量x＝3，GEP相關(guān)參數(shù)的設(shè)置見(jiàn)表1。

表1 參數(shù)設(shè)置

3.1 實(shí)驗(yàn)1

實(shí)驗(yàn)1模擬以下一元函數(shù)的挖掘過(guò)程

根據(jù)這個(gè)公式，產(chǎn)生10組訓(xùn)練數(shù)據(jù)，見(jiàn)表2。

表2 挖掘函數(shù)F1所用的訓(xùn)練數(shù)據(jù)

基因頭部長(zhǎng)度為6，一個(gè)染色中包含的基因個(gè)數(shù)為4，其它參數(shù)的設(shè)置如表1所示。算法連續(xù)運(yùn)行100次，取平均值為統(tǒng)計(jì)結(jié)果。從種群多樣性、成功率和收斂速度三方面，對(duì)GEP和niche－GEP進(jìn)行比較。演化過(guò)程中種群多樣性的變化如圖3所示；算法成功率的比較如圖4所示；算法收斂時(shí)的平均代數(shù)如圖5所示。

實(shí)驗(yàn)數(shù)據(jù)表明，在挖掘F1函數(shù)時(shí)，niche－GEP在種群多樣性、算法成功率和收斂速度3方面都優(yōu)于傳統(tǒng)GEP。

3.2 實(shí)驗(yàn)2

實(shí)驗(yàn)2模擬挖掘二元函數(shù)

根據(jù)這個(gè)公式，隨機(jī)產(chǎn)生10組范圍在［－10，10］的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)?；蝾^部長(zhǎng)度為4，一個(gè)染色中包含的基因個(gè)數(shù)為3，其它參數(shù)的設(shè)置如表1所示。算法連續(xù)運(yùn)行100次，種群多樣性的變化如圖6所示；算法成功率的比較如圖7所示；算法收斂時(shí)的平均代數(shù)的比較如圖8所示。

在挖掘函數(shù)F2時(shí)，niche－GEP的成功率優(yōu)于GEP，在收斂速度方面也有一定提高。從圖3和圖6看出，在演化進(jìn)行到200代以前，GEP和niche－GEP的多樣性都比較豐富，niche－GEP并沒(méi)有優(yōu)勢(shì)。但在200代以后，GEP的多樣性明顯下降，容易陷入局部最優(yōu)。niche－GEP由于始終保持較豐富的多樣性，能從總體上提高算法的成功率。

4 結(jié)束語(yǔ)

由于GEP中的重組算子容易產(chǎn)生大量重復(fù)個(gè)體，使種群中的個(gè)體趨向于一致，群體的多樣性缺失，導(dǎo)致算法容易陷入局部最優(yōu)而出現(xiàn)早熟現(xiàn)象。鑒此，提出了一種基于小生境的GEP新算法，該算法將相同適應(yīng)值的個(gè)體組成一個(gè)小生境，如果相同適應(yīng)值的個(gè)體數(shù)量超過(guò)小生境容量x，則將超出的個(gè)體放入演化池中進(jìn)行重新初始化。并分別對(duì)一元函數(shù)和二元函數(shù)進(jìn)行模擬挖掘。實(shí)驗(yàn)表明，新算法能在整個(gè)演化過(guò)程中保持豐富的群體多樣性，能夠有效地避免算法的早熟現(xiàn)象，在算法成功率和收斂速度方面都優(yōu)于傳統(tǒng)的GEP算法。

［1］XIANG Yong，TANG Chang－jie，ZHU Ming－fang，et al.Embedded gene expression programming and its application in function mining［J］.Journal of University of Electronic Science and Technology of China，2011，40（1）：116－121（in Chinese）.［向勇，唐常杰，朱明放，等.內(nèi)嵌基因表達(dá)式編程及其在函數(shù)發(fā)現(xiàn)中的應(yīng)用［J］.電子科技大學(xué)學(xué)報(bào)，2011，40（1）：116－121.］

［2］MO Hai－fang，KANG Li－shan.Automatic modeling of complex functions based on gene expression programming［J］.Journal of System Simulation，2008，20（11）：2828－2831（in Chinese）.［莫海芳，康立山.用GEP實(shí)現(xiàn)復(fù)雜函數(shù)的自動(dòng)建模［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20（11）：2828－2831.］

［3］MO Hai－fang，LI Kang－shun.New genetic operator of gene expression programming［J］.Computer Engineering and Applications，2011，47（7）：23－25（in Chinese）.［莫海芳，李康順.基因表達(dá)式編程的一種新遺傳算子［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（7）：23－25.］

［4］QI Xing，QIN xu－jia，LI Qu.An improved method for evolving GEP neural network［J］.Computer Systems＆ Applications，2009，19（4）：49－52（in Chinese）.［齊星，秦緒佳，李曲.一種改進(jìn)的GEP神經(jīng)網(wǎng)絡(luò)演化方法及其應(yīng)用［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2009，19（4）：49－52.］

［5］WANG Wei－h(huán)ong，RUAN Wei，LI Qu.Decision tree algorithm by gene expression programming based on differential evolution［J］.Computer Engineering，2011，37（1）：181－183（in Chinese）.［王衛(wèi)紅，阮薇，李曲.基于差分演化的GEP決策樹(shù)算法［J］.計(jì)算機(jī)工程，2011，37（1）：181－183.］

［6］WU Zhi－jian，JIANG Da－zhi，TANG Ming－duan.New algorithm based on gene expression programming［J］.Journal of System Simulation，2008，20（8）：1986－1989（in Chinese）.［吳志健，姜大志，湯銘端.一種基于基因表達(dá)式程序設(shè)計(jì)的新算法［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20（8）：1986－1989.］

［7］ HU Jian－jun，TANG Chang－jie，DUAN Lei，et al.The strategy for diversifying initial population of gene expression programming［J］.Chinese Journal of Computers，2007，30（2）：305－309（in Chinese）.［胡建軍，唐常杰，段磊，等.基因表達(dá)式編程初始種群的多樣化策略［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（2）：305－309.］

［8］LI Tai－yong，TANG Chang－jie，WU Jiang，et al.Adaptive population diversity tuning algorithm for gene expression programming［J］.Journal of University of Electronic Science and Technology of China，2010，39（2）：279－283（in Chinese）.［李太勇，唐常杰，吳江，等.基因表達(dá)式編程種群多樣性自適應(yīng)調(diào)控算法［J］.電子科技大學(xué)學(xué)報(bào)，2010，39（2）：279－283.］

［9］ HU Jian－jun，TANG Chang－jie，PENG Jing.VPS－GEP：Skipping from local optimization fast algorithm［J］.Journal of Sichuan University（Engineering Science Edition），2007，39（1）：128－133（in Chinese）.［胡建軍，唐常杰，彭京，等.快速跳出局部最優(yōu)的VPS－GEP算法［J］.四川大學(xué)學(xué)報(bào)（工程科學(xué)版）.2007，39（1）：128－133.］

［10］LI Tai－yong，TANG Chang－jie，WU Jiang.Multimodal function optimization based on niche gene expression programming［J］.Journal of Sichuan University（Engineering Science Edition），2009，41（2）：162－166（in Chinese）.［李太勇，唐常杰，吳江.等.基于小生境基因表達(dá)式編程的多模函數(shù)優(yōu)化［J］.四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2009，41（2）：162－166.］

［11］LIN Yi－shen，PENG Hong，WEI Jia.Function finding in niching gene expression programming［J］.Journal of Chinese Computer Systems，2008，29（11）：2111－2114（in Chinese）.［林毅申，彭宏，韋佳.小生境基因表達(dá)式編程在函數(shù)發(fā)現(xiàn)的研究［J］.小型微型計(jì)算機(jī)系統(tǒng).2008，29（11）：2111－2114.］