李煜林

摘? 要：提出一種改進(jìn)的基因表達(dá)式編程方法，針對(duì)傳統(tǒng)基因表達(dá)式編程容易出現(xiàn)過(guò)早收斂或者陷入局部收斂，進(jìn)化后期種群多樣性軟弱及遺傳操作隨機(jī)性大等問(wèn)題，加入小生境技術(shù)對(duì)算法進(jìn)行改進(jìn)。實(shí)驗(yàn)表明，改進(jìn)的GEP算法能夠克服傳統(tǒng)GEP算法的不足。

關(guān)鍵詞：基因表達(dá)式;小生境算法;劃分半徑;動(dòng)態(tài)變異策略

中圖分類號(hào)：TP18? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號(hào)：2095-2945（2019）07-0028-03

Abstract： An improved gene expression programming method is proposed to solve the problems of premature convergence or local convergence， weak population diversity and high randomness of genetic operation in traditional gene expression programming. Niche technology is added to improve the algorithm. Experiments show that the improved GEP algorithm can overcome the shortcomings of the traditional GEP algorithm.

Keywords： gene expression; niche algorithm; partition radius; dynamic mutation strategy

引言

基因表達(dá)式編程（gene expression programming，簡(jiǎn)稱GEP）是由葡萄牙進(jìn)化生物學(xué)家兼計(jì)算機(jī)學(xué)家Ferreira于2000年提出的遺傳計(jì)算家族中的新算法，這種新算法融合遺傳算法（Genetic Algorithms，簡(jiǎn)稱GA）中定長(zhǎng)線性編碼的簡(jiǎn)單方便的優(yōu)勢(shì)與遺傳編程（Genetic Programming，簡(jiǎn)稱GP）樹形結(jié)構(gòu)靈活多變的優(yōu)點(diǎn)[3]。研究表明，基因表達(dá)式編程算法及針對(duì)它的各種改進(jìn)算法，其最大的優(yōu)勢(shì)是可以利用簡(jiǎn)單的編碼來(lái)解決相對(duì)繁瑣的問(wèn)題，在數(shù)據(jù)挖掘和函數(shù)發(fā)現(xiàn)等方面有著突出的效果。當(dāng)前GEP廣泛應(yīng)用到化學(xué)、醫(yī)學(xué)、股票預(yù)測(cè)、災(zāi)害預(yù)測(cè)、產(chǎn)量預(yù)測(cè)、經(jīng)濟(jì)、管理、測(cè)繪等多個(gè)領(lǐng)域。一些研究學(xué)者發(fā)現(xiàn)GEP也存在一些不足之處，如收斂過(guò)早、進(jìn)化后期種群多樣性弱、陷入局部收斂、隨機(jī)操作性強(qiáng)等等。

1 小生境技術(shù)

小生境技術(shù)借鑒了生物進(jìn)化過(guò)程中，往往喜歡和特征相同的物種相聚在一起，共同繁衍后代的方式，將每一代遺傳的個(gè)體進(jìn)行了分類，然后在每個(gè)類中選取適應(yīng)度較高的個(gè)體構(gòu)成一個(gè)優(yōu)秀群體，個(gè)體在種群中，以及不同種群之間進(jìn)行雜交、變異產(chǎn)生新一代個(gè)體群，并對(duì)新產(chǎn)生的個(gè)體群進(jìn)行適應(yīng)度評(píng)估，通過(guò)利用預(yù)選機(jī)制或排擠機(jī)制或分享機(jī)制根據(jù)實(shí)際來(lái)解決不同的問(wèn)題。研究表明，這種小生境技術(shù)的遺傳算法在解決所需問(wèn)題時(shí)，能夠很好的保持種群個(gè)體的多樣性，也有相對(duì)較高的尋優(yōu)能力和更快的收斂速度。

2 算法的改進(jìn)

2.1 引入小生境雙重劃分半徑

假設(shè)在一個(gè)種群當(dāng)中，通過(guò)計(jì)算所有個(gè)體適應(yīng)度，選擇出N個(gè)最優(yōu)個(gè)體，在種群中劃分出N個(gè)小生境，為了將種群中的個(gè)體進(jìn)行劃分，引入小生境的雙重劃分半徑r1和r2，計(jì)算任意兩個(gè)最優(yōu)個(gè)體的共享度Dij，根據(jù)任意兩個(gè)最優(yōu)個(gè)體之間的共享度距離來(lái)確認(rèn)劃分半徑。

利用雙重劃分半徑將種群中的所有個(gè)體劃分為最優(yōu)個(gè)體，次優(yōu)個(gè)體，一般個(gè)體和排擠個(gè)體。次優(yōu)個(gè)體一般處于半徑為r1的范圍中，一般個(gè)體處于半徑r1和r2之間，排擠個(gè)體處于半徑r2之外。通過(guò)這樣形式的個(gè)體劃分，目的就是使種群中個(gè)體在遺傳操作過(guò)程不像傳統(tǒng)GEP的遺傳操作那樣隨機(jī)選擇，使遺傳操作變的有針對(duì)性，可以有效的提高算法的收斂速度。

2.2 個(gè)體進(jìn)行分類遺傳操作及動(dòng)態(tài)變異策略

傳統(tǒng)GEP中遺傳操作的變異、插串、重組等操作是針對(duì)種群的所有個(gè)體進(jìn)行的，遺傳操作的過(guò)程是通過(guò)設(shè)置固定的概率隨機(jī)進(jìn)行，使得算法遺傳操作的隨機(jī)性比較大，這將一定程度上影響算法在尋找全局最優(yōu)解的速度，在傳統(tǒng)GEP的三種遺傳操作中，變異算子的遺傳操作性是最強(qiáng)的，為了保持種群的豐富性，從而預(yù)防過(guò)早收斂的現(xiàn)象，傳統(tǒng)GEP采用較小的變異概率，這很大程度上是以犧牲收斂速度為代價(jià)的。因此，本文通過(guò)小生境雙重劃分半徑將種群中的個(gè)體進(jìn)行劃分之后進(jìn)行分類遺傳操作，并設(shè)計(jì)一種動(dòng)態(tài)變異策略，能夠有效的降低遺傳操作的隨機(jī)性，在維持種群多樣性的同時(shí)也在一定程度上提高了算法的收斂速度，具體方法如下：

首先利用小生境雙重劃分半徑對(duì)種群中的個(gè)體進(jìn)行分類，劃分的類別包括最優(yōu)個(gè)體、次優(yōu)個(gè)體、一般個(gè)體和排擠個(gè)體。

其中最優(yōu)個(gè)體采用克隆操作，具體操作步驟如下：

（1）創(chuàng)建初始種群;

（2）計(jì)算個(gè)體適應(yīng)度;

（3）選擇最優(yōu)個(gè)體種群C;

（4）將最優(yōu)個(gè)體種群C克隆，并以較小的概率P1發(fā)生變異，形成臨時(shí)種群C1加入初始種群。

種群中的次優(yōu)個(gè)體由于小生境分享機(jī)制強(qiáng)制降低了其個(gè)體適應(yīng)度，但是其個(gè)體基因表現(xiàn)型還是優(yōu)良的，僅次于最優(yōu)個(gè)體，為了保持種群多樣性，我們將次優(yōu)個(gè)體按較大的概率P2發(fā)生變異，避免出現(xiàn)適應(yīng)度相對(duì)較高的個(gè)體扎堆現(xiàn)象;對(duì)于種群重的排擠個(gè)體，同樣被小生境分享機(jī)制提高了其個(gè)體的適應(yīng)度，也就意味著其被選擇的機(jī)率被提高，然后將排擠個(gè)體按一定的概率P3發(fā)生變異，以便得到更好基因個(gè)體。

經(jīng)過(guò)這種分類遺傳操作之后，種群中的最優(yōu)個(gè)體克隆變異，次優(yōu)個(gè)體和排擠個(gè)體通過(guò)動(dòng)態(tài)變異策略調(diào)整變異概率之后，弱勢(shì)群體適應(yīng)度被提高，被選擇繁衍的概率被加大，種群中的個(gè)體多樣性明顯變得豐富，同時(shí)由于次優(yōu)個(gè)體被大概率的突變使得與最優(yōu)個(gè)體基因表現(xiàn)性相似的個(gè)體明顯被減少，避免次優(yōu)個(gè)體扎堆最優(yōu)個(gè)體的現(xiàn)象，有助于預(yù)防算法進(jìn)化過(guò)程出現(xiàn)過(guò)早收斂和陷入局部收斂，引領(lǐng)進(jìn)化走向全局最優(yōu)。

結(jié)合小生境算法和傳統(tǒng)GEP算法，通過(guò)上述兩點(diǎn)改進(jìn)之后得到改進(jìn)GEP算法，具體算法框架如下：

（1）創(chuàng)建初始種群;

（2）設(shè)置基因表達(dá)式控制參數(shù);

（3）計(jì)算種群中個(gè)體適應(yīng)度;

（4）判斷每一代是否達(dá)到最優(yōu)解，如果達(dá)到，輸出結(jié)果，算法結(jié)束;否則繼續(xù)下一步;

（5）按照輪盤賭法選擇輸出個(gè)體進(jìn)行下一步;

（6）選擇最優(yōu)個(gè)體群體，設(shè)置克隆參數(shù)，進(jìn)行克隆操作;

（7）確定小生境個(gè)數(shù)，計(jì)算最優(yōu)個(gè)體之間的共享度距離sD;

（8）設(shè)置劃分參數(shù)，利用小生境雙重劃分半徑劃分出次優(yōu)個(gè)體、一般個(gè)體和排擠個(gè)體;

（9）分別計(jì)算次優(yōu)個(gè)體以及排擠個(gè)體與最優(yōu)個(gè)體的共享度Si，得到調(diào)整適應(yīng)度f(wàn)s（i）;

（10）設(shè)置動(dòng)態(tài)變異策略參數(shù)，遺傳操作;

（11）生成新的個(gè)體種群，返回第三步。

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

為了驗(yàn)證改進(jìn)的GEP在解決傳統(tǒng)GEP進(jìn)化后期種群多樣性軟弱，過(guò)早收斂，隨機(jī)操作性等問(wèn)題是否有效，設(shè)計(jì)模擬實(shí)驗(yàn)分析改進(jìn)效果。

根據(jù)函數(shù)y=a3-a2-a-1在取值范圍[-5，5]中隨機(jī)選取，得到平均分布的30組數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，其他的參數(shù)設(shè)置如表1所示。

4 結(jié)論與分析

從圖1我們可以發(fā)現(xiàn)，隨著進(jìn)化代數(shù)不斷增加，傳統(tǒng)GEP中種群平均共享度距離明顯降低，也就是說(shuō)此時(shí)種群多樣性也隨之降低，由于種群多樣性的不足，算法容易出現(xiàn)過(guò)早收斂或者陷入局部收斂，無(wú)法達(dá)到全局最優(yōu)，導(dǎo)致在對(duì)函數(shù)的挖掘過(guò)程中出現(xiàn)挖掘不成功的現(xiàn)象，而改進(jìn)的GEP在進(jìn)化代數(shù)增加的過(guò)程中，仍然能夠保持較大的種群平均共享度距離，也就是能夠保持種群多樣性，這樣也就能夠避免算法過(guò)早收斂或陷入局部收斂，也不會(huì)出現(xiàn)函數(shù)挖掘不成功的現(xiàn)象;從表2我們可以看出，改進(jìn)的GEP在達(dá)到收斂的平均代數(shù)遠(yuǎn)遠(yuǎn)小于傳統(tǒng)GEP，改進(jìn)的GEP在收斂速度上要優(yōu)于傳統(tǒng)GEP。

為此，我們可以得出結(jié)論，利用小生境算法與傳統(tǒng)基因表達(dá)式編程算法相結(jié)合，采用本文提出的小生境雙重劃分半徑對(duì)種群中的個(gè)體進(jìn)行劃分，對(duì)劃分的個(gè)體分類遺傳操作，并設(shè)計(jì)動(dòng)態(tài)變異策略實(shí)施個(gè)體動(dòng)態(tài)調(diào)整變異概率，得到改進(jìn)的基因表達(dá)式編程算法，能夠有效的解決傳統(tǒng)GEP中種群多樣性軟弱的問(wèn)題，防止過(guò)早收斂和陷入局部收斂，通過(guò)收斂速度的對(duì)比我們可以發(fā)現(xiàn)，由于改進(jìn)的GEP采用個(gè)體分類操作和動(dòng)態(tài)變異策略，能夠有效地解決傳統(tǒng)GEP隨機(jī)操作性過(guò)大的問(wèn)題，同時(shí)在收斂速度上也有所提高，也就意味著本文中對(duì)傳統(tǒng)GEP的改進(jìn)是具有效果的。

參考文獻(xiàn)：

[1]元昌安，彭昱忠，覃曉，等.基因表達(dá)式編程算法原理與應(yīng)用[M].北京：科學(xué)出版社，2010.

[2]Fatih Ozcan. Gene expression programming based formulations for splitting tensile strength of concrete[J].Construction and Building MATERIALS，2012，26（1）：404-410.

[3]Piotr， Ewa. Agent～Based Gene Expression Programming for Solving the RCPSP/max Problem[J]. ICANNGA 2009， LNCS 5495， 2009：203-212.

[4]劉小生，李勝，趙相博.基于基因表達(dá)式編程的PM_（2.5）濃度預(yù)測(cè)模型研究[J].江西理工大學(xué)學(xué)報(bào)，2013，05：1-5.

[5]王艷.基因表達(dá)式編程在時(shí)序變形數(shù)據(jù)處理中的應(yīng)用[J].河南科技，2014，24：153.