基于尖Γ云模型的基因表達式編程算法研究

姜 玥，何林霖，劉 倩

(西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院，四川 成都 610041)

基因表達式編程(Gene Expression Programming，GEP)是函數(shù)關(guān)系挖掘的新方法，它繼承和發(fā)展了遺傳算法(Genetic Algorithm，GA)和遺傳編程(Genetic Programming，GP)[1]，克服了 GA與 GP的不足，更適合于函數(shù)關(guān)系的挖掘.然而，文獻[2]提出的GEP算法，采用了固定的變異率和交叉率，沒有考慮樣本的具體分布和適時進化狀態(tài).文獻[3-6]將GEP算法應(yīng)用于多個領(lǐng)域.文獻[7-8]對遺傳算法進行改進，分別應(yīng)用到AGV最優(yōu)路徑規(guī)劃和堆石料的參數(shù)反演.文獻[9]提出采用交叉模型的GA，改進了交叉的方式，但是依然忽略了變異率的動態(tài)變化，并且GA是線性編碼解決簡單問題，難以解決復(fù)雜問題.文獻[10]研究了遺傳規(guī)劃中，遺傳算子對種群多樣性的影響.文獻[11]在遺傳規(guī)劃中，采用分級與截取相結(jié)合的選擇方法，動態(tài)選擇變異的策略.但是，忽略了個體適應(yīng)度分布的形態(tài)變化.中國的李德毅教授提出的云模型[12]已成功應(yīng)用于數(shù)據(jù)挖掘、智能控制和入侵檢測等領(lǐng)域.眾多的統(tǒng)計分布都和Γ分布有關(guān).由于許多客觀事物的特征具有模糊性，為了讓GEP算法能模擬人的思維方式對進化過程中的核心參數(shù)進行識別和調(diào)整，本文提出基于將Γ型隸屬函數(shù)引入GEP算法，改進傳統(tǒng)GEP的變異和交叉，使GEP算法在進化過程中跳出早熟和局部最優(yōu)，有效地提高收斂速度，延長有效進化壽命.

1 基本概念

Γ型隸屬函數(shù)是模糊集理論中常用的一種.由于Γ分布于指數(shù)分布的等價性，常簡化為指數(shù)形式.指數(shù)分布是在可靠性研究中最常用的一種分布形式.在進化的種群中，指數(shù)形式可以用來近似地描述個體分布.為了方便描述，定義了以下概念，其中exp為指數(shù)函數(shù).

定義1 設(shè)Ex，En和He分別為期望值，熵和超熵，G為種群

1)(云模型)設(shè)U＝{x}，T為U上的語言子集，CT(x):U?[0，1]，?x∈U，稱CT(x)在 U 上的分布為云模型.

2)(尖Γ云模型)設(shè) R(Ex，En，He)為尖 Γ分布的隸屬函數(shù)，滿足方程組:

的數(shù)據(jù)對 Drop(xi，ui)(i＝1，2，…)組成的 CT(X)稱為尖Γ云模型，簡稱尖Γ云，記為(Ex，En，He).組成CT(X)的數(shù)據(jù)對(xi，ui)稱為尖Γ云滴.尖Γ云如圖1所示.

3)(GEP模式)設(shè)N為個體數(shù)，M為基因數(shù)，Q為種群數(shù)，則 GEP模式 ＝(N，M，Q)，即

4)(適應(yīng)度隸屬度)設(shè)fi為Indi的適應(yīng)度值，則

稱為Indi的適應(yīng)度隸屬度.

圖1 尖Γ云Fig.1 Cusp Gamma Cloud

2 尖Γ云調(diào)整算法

觀察1 恒定的變異率或交叉率使進化早熟收斂.

進化過程中，如果自始至終采用恒定的變異率或交叉率，而不考慮進化的當(dāng)前狀態(tài)，減小了個體的多樣性，導(dǎo)致進化早熟收斂，達不到全局最優(yōu).

尖Γ云模型改善了嚴格規(guī)范和過度確定的弱點，它將概念的模糊性和隨機性集成在一起.變異率和交叉率是決定GEP性能的關(guān)鍵.利用模糊集理論中的尖Γ型的隸屬函數(shù)，擴展為尖Γ云，設(shè)計尖Γ云調(diào)整算法將模糊性溶于使變異率和交叉率的主動調(diào)整中，跟隨適應(yīng)度適時動態(tài)改變.

定義2 設(shè)種群 G，?Indi，Indj∈G，favg＝∑fi/Q，fmax＝Max(fi)，fmin＝ Min(fi)，1≤i≤Q，Q 為種群數(shù)，Max為最大值函數(shù)，Min為最小值函數(shù)，fi為Indi的適應(yīng)度.期望值 Ex＝favg，熵 En＝Cn(fmax-fmin)，超熵 He＝CeEn，En’ ＝ R(En，He)，Cn，Ce為常數(shù)，調(diào)節(jié)因子.

(1)(尖Γ云變異率)則尖Γ云變異率

(2)(尖Γ云交叉率)則尖Γ云交叉率

定理1 設(shè)尖Γ云變異率Pm.當(dāng)fi＝α?xí)r，Pm＝Cm；當(dāng) fi＞ ＞α 時，Pm∞0.

證明:因為式(6)

當(dāng)fi＝α?xí)r，即個體的適應(yīng)度與種群平均適應(yīng)度一樣，反映了該個體與種群中的個體比較相似，那么就必須加大變異率，以刺激種群多樣性的產(chǎn)生；反之，當(dāng)fi＞＞α?xí)r，即個體的適應(yīng)度遠遠高于種群平均適應(yīng)度，進化良好，因此，此時不適合立刻加大種群的變異，而應(yīng)讓此時的良性進化持續(xù)一定時間.

定理1表明正態(tài)分布廣泛存在于自然界、生產(chǎn)及科學(xué)技術(shù)的許多領(lǐng)域中.但是，在實際應(yīng)用中，盡管有大量因素影響著結(jié)果，但是各因素的權(quán)重不同，往往可能只是其中的少數(shù)幾個因素處于核心地位.因此，直接將正態(tài)分布應(yīng)用于實際，無法真實地反映客觀情況.定理1中的α是形狀參數(shù)，形狀參數(shù)a越大，形狀越扁.將尖Γ隸屬函數(shù)擴展到云模型.通過云模型中的量化云滴，能比較好地進行解釋.He反映某幾個因素的不均衡性.指數(shù)分布e(k)的期望值和標(biāo)準(zhǔn)差均為1/k.尖Γ云的生成算法分為兩步，(1)通過給定的數(shù)字特征值(Ex，En，He)得到 k；(2)通過 k生成指數(shù)隨機數(shù)[17].

定理2 設(shè)尖Γ云交叉率Pc.當(dāng)fi＝α?xí)r，Pc＝Cc；當(dāng) fi＞ ＞ α 時，Pc∞0.

定理2的證明與定理1的證明同理.

采用尖Γ云調(diào)整算法的基本思想是:①計算Ex，En和He；②生成以1/En為參數(shù)的指數(shù)隨機數(shù)E(1/En)；③生成以1/He為參數(shù)的指數(shù)隨機數(shù)E(1/He)；④計算尖 Γ云變異或交叉率 Pm或 Pc，令(fi，Pm)或(fi，Pc)為云滴.尖Γ云變異或交叉率發(fā)生器如圖2所示，尖Γ云發(fā)生器通過輸入3個數(shù)值特征形成合乎條件的云滴.

圖2 尖Γ云發(fā)生器Fig.2 Cusp Gamma Cloudy Generator

算法1(CGCAA):尖 Γ云調(diào)整算法(Cusp Gamma Cloudy Adjust Algorithm，CGCAA)

輸入:尖Γ云的控制參數(shù)Cn，Ce，種群Population

輸出:云滴Drop(fi，Pm)或Drop(fi，Pc)

算法1中第13行和第14行分別通過尖Γ云變異和交叉發(fā)生器生成Pm和Pc.Ex和En的變化影響云的水平位置和陡峭程度，He和云滴的離散程度呈正比.He控制著云滴沿著期望曲線上下的分布情況.該算法生成的變異或交叉率自然地具有不均勻厚度的特征.

利用CGCAA算法產(chǎn)生的變異率和交叉率應(yīng)用到傳統(tǒng)GEP算法[1]，來改善傳統(tǒng)GEP算法的性能，GEP算法的細節(jié)參考文獻[2].

算法2(GEP-CGC):基于尖Γ云的GEP算法(Eene Expression Programming Based on Cusp Gamma Cloud)輸入:樣本數(shù)據(jù)集

輸出:最優(yōu)個體

算法2中，ε為誤差閾值，MGeneration為最大進化代數(shù).

命題1 算法2的時間復(fù)雜度為O(Q2)，其中Q為種群規(guī)模.

證明:外循環(huán)掃描每一個個體時的時間復(fù)雜度為O(Q)，在每一趟操作中，內(nèi)循環(huán)的時間復(fù)雜度為O(Q).所以，總的時間復(fù)雜度是O(Q2).命題得證.

3 實驗與性能分析

為了驗證和比較策略的性能和有效性，將GEPCGC算法和傳統(tǒng)GEP算法的實際運行效果進行實驗和討論，采用了Visual C＋＋6.0，運行平臺為Intel Pentium 3.4GHz，4GB的 RAM 內(nèi)存，1TB 硬盤，Windows 7操作系統(tǒng).實驗選擇了學(xué)術(shù)界公認的3個函數(shù)進行測試.

對各類GEP算法使用的參數(shù)如表1所示，其中S表示Sin函數(shù).對以上函數(shù)產(chǎn)生的樣本數(shù)據(jù)集重復(fù)80次挖掘?qū)嶒?，統(tǒng)計結(jié)果的進化性能如圖3所示.

表1 GEP和GEP-CGC參數(shù)設(shè)置Table 1 Parameters for GEP and CGC

圖3 進化性能Fig.3 The Performance of the Evolution

圖3(a)是最優(yōu)個體的平均適應(yīng)度比較，可以看出GEP-CGC算法能夠更好地跳出局部最優(yōu)，尋求到更優(yōu)解，最高適應(yīng)度提高達7%.期望Ex反映了適應(yīng)度云滴群的中心；熵En也就是論域中被模糊概念所接受的范圍；超熵He即熵的熵，表現(xiàn)了云滴的離散程度，間接地反映了云的厚度.

圖3(b)是最優(yōu)個體的最高適應(yīng)度比較，可以看出GEP-CGC算法明顯提高了最高適應(yīng)度.新算法通過尖Γ云模糊化改進后的算子使得種群根據(jù)種群當(dāng)前狀態(tài)調(diào)整變異和交叉的進程，增加了種群多樣性，因而種群可以探索的空間擴大，進化收斂被延遲.種群可以更加活躍地進化，去逼近全局最優(yōu)解.

延緩種群的過早同化.個體的相似是GEP進化的絆腳石，GEP算法要發(fā)揮良好的性能，需要個體的千姿百態(tài)為基礎(chǔ).GEP-CGC算法根據(jù)種群進化的現(xiàn)狀，自動調(diào)整變異率和交叉率，明顯改善了GEP的搜索性能，提高最高適應(yīng)度約8%.尖Γ云借助云模型的定性定量間的不確定轉(zhuǎn)換改進變異率和交叉率.Ex的變化掩蓋了En取值不同帶來的進化結(jié)果的差異.

尖Γ云模型具有最基本的云的特點，云是由許多云滴構(gòu)成.與我們事實上觀察一致的是，越靠近云的中心位置或者遠離云的中心位置，隸屬度的隨機性就越?。痪嚯x云的中心位置不近不遠的，隸屬度的隨機性就大[17].CGCAA算法生成的調(diào)整云自然地具有云的特性，通過R(Ex，En，He)，三個特征值足以很好地描述整個云的形態(tài).圖3(c)是最優(yōu)個體的平均進化代數(shù)比較.說明CGCAA算法充分發(fā)揮云的作用來改善收斂速度，并且，也能避免進化過早結(jié)束.有效的進化過程被延緩，同時，有效進化的進程被加速，平均減少進化代數(shù)約10%.

4 結(jié)論

傳統(tǒng)GEP算法使用一成不變的變異率和交叉率，不能很好地適應(yīng)動態(tài)變化的進化過程.本文針對這一問題，在傳統(tǒng)GEP算法的基礎(chǔ)之上，提出了引入尖Γ云模型，并加以解決.實驗表明GEP-CGC算法增加了個體的多樣性，體現(xiàn)出較快的搜索速度，較好的收斂結(jié)果，具有很強的擺脫局部最優(yōu)的能力.實驗結(jié)果表明，平均適應(yīng)度提高達7%，最高適應(yīng)度提高8%，平均進化代數(shù)下降達10%.

下一步的工作，我們將在本文的基礎(chǔ)上繼續(xù)研究通過自學(xué)習(xí)逐步修正所選的近似的隸屬函數(shù)，使之更加符合客觀實際問題.

[1] 賈曉斌，唐常杰，左劼，等.基于基因表達式編程的頻繁函數(shù)集挖掘[J].計算機學(xué)報，2005，28(8):1247-1254.

[2] CANDIDA.Ferreira Gene Expression Programming:A New Adaptive Algorithm for Solving Problems.Complex Systems[J]，2001，13(2):87-129.

[3] 彭昱忠，元昌安，李潔，等.個體最優(yōu)共享GEP算法及其氣象降水?dāng)?shù)據(jù)預(yù)測建模[J].智能系統(tǒng)學(xué)報，2016，11(3):402-409.

[4] 姜玥，談文蓉，崔孟天，等.基于種群密集度的GEP算法挖掘藥物不良反應(yīng)[J].計算機應(yīng)用研究，2015，32(10):2943-2946.

[5] 王斌，張迅，盛津芳，等.優(yōu)化的GEP算法在爆破振動預(yù)測中的應(yīng)用[J].計算機工程與應(yīng)用，2016，52(22):212-217.

[6] 張銳，侯沙沙.種群多樣性的GEP算法在預(yù)測中的研究和應(yīng)用[J].哈爾濱理工大學(xué)學(xué)報，2017，22(4):18-22.

[7] 趙大興，余明進，許萬.基于高適應(yīng)度值遺傳算法的AGV最優(yōu)路徑規(guī)劃[J].計算機工程與設(shè)計，2017，38(6):1635-1641.

[8] 曾輝，廖露梅，曾予劍.遺傳算法—支持向量機在面板堆石壩堆石料的參數(shù)反演分析的應(yīng)用[J].江蘇水利，2017，8:34-37.

[9] 楊新武，楊立軍.基于交叉模型的改進遺傳算法[J].控制與決策，2016，31(10):1837-1844.

[10] 周冬梅，孫俊.遺傳規(guī)劃中遺傳算子對種群多樣性的影響[J].計算機工程與應(yīng)用，2016，52(20):39-45.

[11] 郝艷偉，李祖樞.一種改進的遺傳規(guī)劃算法[J].重慶理工大學(xué)學(xué)報(自然科學(xué)版)，2011，25(4):74-78.

[12] 李德毅，孟海軍，史雪梅.隸屬云和隸屬云發(fā)生器[J].計算機研究與發(fā)展，1995，32(6):15-20.

[13] 姜玥，崔孟天，吳江，等.基于條件云的基因表達式編程算法[J].計算機應(yīng)用研究，2015，32(4):1107-1109.

[14] CANDIDA.Ferreira Gene Expression Programming[EB/OL].[2018-02-08]. http://www.gene-expression-programming.com/gep/Gep-Book/Chapter4/Section1/SS2.htm.

[15] ZBIGNIEW MICHALEWICZ.Genetic Algorithms＋Data Structures＝Evolution[M].Berlin Heidelberg:Springer-Verlag，1999:349-350.

[16] NGA LAM LAW，SZETO K Y.Adaptive Genetic Algorithm with Mutation and Crossover Matrices[C].IJCAI-07:2330-2333.

[17] 李梅.不完備信息下的河流健康風(fēng)險預(yù)估模型研究[D].西安:西安理工大學(xué)，2007.