姜 玥，何林霖，劉 倩

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

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

1 基本概念

Γ型隸屬函數(shù)是模糊集理論中常用的一種.由于Γ分布于指數(shù)分布的等價(jià)性，常簡化為指數(shù)形式.指數(shù)分布是在可靠性研究中最常用的一種分布形式.在進(jìn)化的種群中，指數(shù)形式可以用來近似地描述個(gè)體分布.為了方便描述，定義了以下概念，其中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ù)對(duì) Drop(xi，ui)(i＝1，2，…)組成的 CT(X)稱為尖Γ云模型，簡稱尖Γ云，記為(Ex，En，He).組成CT(X)的數(shù)據(jù)對(duì)(xi，ui)稱為尖Γ云滴.尖Γ云如圖1所示.

3)(GEP模式)設(shè)N為個(gè)體數(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 恒定的變異率或交叉率使進(jìn)化早熟收斂.

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

尖Γ云模型改善了嚴(yán)格規(guī)范和過度確定的弱點(diǎn)，它將概念的模糊性和隨機(jī)性集成在一起.變異率和交叉率是決定GEP性能的關(guān)鍵.利用模糊集理論中的尖Γ型的隸屬函數(shù)，擴(kuò)展為尖Γ云，設(shè)計(jì)尖Γ云調(diào)整算法將模糊性溶于使變異率和交叉率的主動(dòng)調(diào)整中，跟隨適應(yīng)度適時(shí)動(dò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＞ ＞α 時(shí)，Pm∞0.

證明:因?yàn)槭?6)

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

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

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

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

采用尖Γ云調(diào)整算法的基本思想是:①計(jì)算Ex，En和He；②生成以1/En為參數(shù)的指數(shù)隨機(jī)數(shù)E(1/En)；③生成以1/He為參數(shù)的指數(shù)隨機(jī)數(shù)E(1/He)；④計(jì)算尖 Γ云變異或交叉率 Pm或 Pc，令(fi，Pm)或(fi，Pc)為云滴.尖Γ云變異或交叉率發(fā)生器如圖2所示，尖Γ云發(fā)生器通過輸入3個(gè)數(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算法的細(xì)節(jié)參考文獻(xiàn)[2].

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

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

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

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

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

3 實(shí)驗(yàn)與性能分析

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

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

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

圖3 進(jìn)化性能Fig.3 The Performance of the Evolution

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

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

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

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

4 結(jié)論

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

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

[1] 賈曉斌，唐常杰，左劼，等.基于基因表達(dá)式編程的頻繁函數(shù)集挖掘[J].計(jì)算機(jī)學(xué)報(bào)，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] 彭昱忠，元昌安，李潔，等.個(gè)體最優(yōu)共享GEP算法及其氣象降水?dāng)?shù)據(jù)預(yù)測(cè)建模[J].智能系統(tǒng)學(xué)報(bào)，2016，11(3):402-409.

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

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

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

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

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

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

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

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

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

[13] 姜玥，崔孟天，吳江，等.基于條件云的基因表達(dá)式編程算法[J].計(jì)算機(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)險(xiǎn)預(yù)估模型研究[D].西安:西安理工大學(xué)，2007.