基于小生境技術(shù)的改進基因表達式編程算法的研究

李煜林

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

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

中圖分類號：TP18? ? ? ? ? 文獻標(biāo)志碼：A? ? ? ? ?文章編號：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

引言

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

1 小生境技術(shù)

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

2 算法的改進

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

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

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

2.2 個體進行分類遺傳操作及動態(tài)變異策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（5）按照輪盤賭法選擇輸出個體進行下一步;

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

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

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

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

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

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

3 仿真實驗與分析

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

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

4 結(jié)論與分析

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

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

參考文獻：

[1]元昌安，彭昱忠，覃曉，等.基因表達式編程算法原理與應(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]劉小生，李勝，趙相博.基于基因表達式編程的PM_（2.5）濃度預(yù)測模型研究[J].江西理工大學(xué)學(xué)報，2013，05：1-5.

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