海量種群基因表達(dá)式編程的內(nèi)存刪冗算法

鐘堅(jiān)成,彭 瑋

(1.湖南師范大學(xué)工程與設(shè)計(jì)學(xué)院,長沙410081;2.昆明理工大學(xué)信息工程與自動化學(xué)院,昆明650093)

海量種群基因表達(dá)式編程的內(nèi)存刪冗算法

鐘堅(jiān)成1,彭 瑋2

(1.湖南師范大學(xué)工程與設(shè)計(jì)學(xué)院,長沙410081;2.昆明理工大學(xué)信息工程與自動化學(xué)院,昆明650093)

在大樣本、多種群、高進(jìn)化代數(shù)的情況下,基因表達(dá)式編程(GEP)容易產(chǎn)生冗余個體染色體有效串,從而影響計(jì)算性能。為解決該問題,提出一種基于內(nèi)存檢測種群冗余的算法MPRRGEP。分析單基因、多基因?qū)ΨN群冗余性的影響,設(shè)計(jì)個體染色體有效性的測度方法。提出內(nèi)存Hash種群映射刪冗算法,在內(nèi)存中索引個體染色體數(shù)據(jù),減少相同有效串的重復(fù)計(jì)算次數(shù),大幅提高GEP計(jì)算性能。實(shí)驗(yàn)結(jié)果表明,相比傳統(tǒng)GEP算法,MPRRGEP算法平均減少60%以上的計(jì)算時間。

基因表達(dá)式編程;刪冗;哈希表;基因有效串;多基因;關(guān)鍵蛋白質(zhì)預(yù)測

1 概述

基因表達(dá)式編程(Gene Expression Programming, GEP)作為進(jìn)化算法的一種[1],融合了遺傳算法和遺傳編程的優(yōu)勢。在GEP中采用一個固定長度的個體染色體可用來表達(dá)一個非線性的算術(shù)表達(dá)式、邏輯表達(dá)式。通過一系列變異、交叉、置換、重組等遺傳算子操作,個體染色體可進(jìn)化成一個新的個體。新個體在生存函數(shù)下進(jìn)行優(yōu)勝劣汰[2-3]。GEP可用于解決分類問題、公式演化問題、優(yōu)化問題、關(guān)聯(lián)規(guī)則挖掘等。從現(xiàn)有研究來看,對GEP的研究主要集中在3大方面: (1)對GEP算法框架的改進(jìn),如文獻(xiàn)[4]運(yùn)用多核CPU并行計(jì)算能力提出了基于多線程評估的GEP算法;文獻(xiàn)[5]針對傳統(tǒng)GEP存在局部收斂的不足提出了快速進(jìn)化,避免局部最優(yōu)的VPS-GEP算法;文獻(xiàn)[6]將差分突變搜索、混沌重組和變異操作、災(zāi)變算子運(yùn)用于GEP,提高了GEP的精度和收斂速度;文獻(xiàn)[7]提出了一種新的基于多層染色體基因表達(dá)式編程的遺傳進(jìn)化算法M2GEP。(2)GEP與其他機(jī)器學(xué)習(xí)或統(tǒng)計(jì)方法結(jié)合的算法研究,如文獻(xiàn)[8]融合模擬退火和GEP算法;文獻(xiàn)[9]基于GEP和Baum-Welch算法訓(xùn)練HMM模型。(3)GEP的應(yīng)用研究,如文獻(xiàn)[10]運(yùn)用GEP與滑動窗口方法來預(yù)測變壓器油中溶解氣體濃度;文獻(xiàn)[11]運(yùn)用GEP估算曼寧阻力系數(shù)。上述優(yōu)化GEP的文獻(xiàn)中大部分都涉及提升計(jì)算性能、提高種群多樣性、擴(kuò)展GEP的全局搜索能力,但從實(shí)驗(yàn)參數(shù)來看大部分種群數(shù)為500以下,進(jìn)化次數(shù)為500以下,很少考慮大樣本、多種群、高進(jìn)化代數(shù)的情況,特別是海量種群數(shù)和超高進(jìn)化次數(shù)的情況下GEP計(jì)算量及優(yōu)化問題。目前有較多針對大樣本數(shù)據(jù)的分類和聚類問題,如:關(guān)鍵蛋白質(zhì)識別問題,復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)掘問題等。采用多種群可提高群體的多樣性,避免早熟現(xiàn)象,但會使得傳統(tǒng)的GEP算法運(yùn)行效率降低。進(jìn)化代數(shù)為算法運(yùn)行的結(jié)束條件,文獻(xiàn)[12]采用基因表達(dá)式編程種群多樣性自適應(yīng)調(diào)控算法分別對一元函數(shù)發(fā)現(xiàn)問題和五元函數(shù)發(fā)現(xiàn)問題進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)1的進(jìn)化次數(shù)為400次,實(shí)驗(yàn)2的進(jìn)化次數(shù)為2 000次,實(shí)驗(yàn)結(jié)果表明為獲得問題的最優(yōu)解需要超過1 000次的進(jìn)化代數(shù)。

本文探討GEP在大種群數(shù)及多次進(jìn)化環(huán)境下的GEP性能優(yōu)化算法,分析個體染色體有效串,提出針對單基因、多基因個體染色體有效性長度的測度算法,并運(yùn)用內(nèi)存映射刪冗算法將個體染色體有效串和對應(yīng)的結(jié)果數(shù)據(jù)在內(nèi)存中索引,減少相同有效串的重復(fù)計(jì)算次數(shù)。

2 個體染色體有效串

GEP中采用固定長度的字符串來描述個體基因,個體基因分為頭部Head和尾部Tail 2個部分,在頭部中可放置函數(shù)符號和終結(jié)符號,而尾部只能放置終結(jié)符號。個體基因可解析為一個表達(dá)式樹(Expression Tree),函數(shù)符號后可接相應(yīng)的參數(shù),即為表達(dá)式樹的中間結(jié)點(diǎn),而終結(jié)符號是表達(dá)式樹的葉子結(jié)點(diǎn)。GEP根據(jù)染色體中包含基因的個數(shù)分為單基因染色體和多基因染色體。以下是單基因染色體和多基因染色體及其對應(yīng)的表達(dá)式樹的例子。

設(shè)單基因染色體串為“+Q-/b*aaQ+aabaabba aab”,其頭部長度為10,對應(yīng)的表達(dá)式樹如圖1所示。

圖1 單基因染色體及其表達(dá)式樹

設(shè)多基因染色體串為“-b*babbab*Qb+abbba-*Qabbaba”,其基因頭部長度為4,基因數(shù)目為3,對應(yīng)的表達(dá)式樹如圖2所示。

圖2 多基因染色體及其表達(dá)式樹

定義1 基因有效串

基因的長度為GL:

其中,h為基因頭部字符個數(shù);ni為基因頭部中第i個函數(shù)符的參數(shù)個數(shù)。基因字符串中用于正確描述表達(dá)式樹的前L個字符為基因有效串。基因有效串長度L小于等于基因長度GL。在圖1和圖2中Valid Pos所指向的位置為L。

定義2 個體染色體有效串CL

其中,GN為個體染色體中基因的個數(shù),根據(jù)GN的取值可分為單基因和多基因個體染色體:單基因個體染色體中GN取值為1,其有效串與基因有效串相同;多基因個體染色體中GN取值大于1,個體染色體有效串為各基因有效串的連接。針對上例中單基因的個體染色體“+Q-/b*aaQ+aabaabbaaab”的有效串為“+Q-/b*aaQ+aab”。有效串后的字符,如圖1中Valid Pos箭頭指向后方字符發(fā)生了變更不會影響個體染色體串生成表達(dá)式樹,即也不會影響樣本計(jì)算后適應(yīng)性函數(shù)評價(jià)的結(jié)果。針對上例中的多基因個體染色體“-b*babbab*Qb+abbba-* Qabbaba”,該染色體分為3個基因,其中每個基因都有自身的有效串,如基因1的有效串為“-b*ba”、基因2的有效串為“*Qb+ab”、基因3的有效串為“-*Qabb”,個體染色體的有效串為3個基因有效串的連接“-b*ba*Qb+ab-*Qabb”。圖2中Valid Pos箭頭后方到所在基因尾部字符發(fā)生了變更也不會影響個體染色體串生成表達(dá)式樹。

3 內(nèi)存種群冗余刪冗算法MPRRGEP

染色體有效串生成表達(dá)式用于計(jì)算實(shí)驗(yàn)樣本,當(dāng)實(shí)驗(yàn)樣本量增大時,個體表達(dá)式計(jì)算量也隨之增加。個體通過適應(yīng)性函數(shù)評價(jià)后,將優(yōu)良的個體保留,并將其進(jìn)行交叉、變異、置換等遺傳算子操作,擴(kuò)充成原始種群數(shù)。同時,隨著GEP的種群數(shù)和進(jìn)化次數(shù)增加,個體染色體有效串與隔代之間的個體染色體有效串相同的概率將隨之增大。這導(dǎo)致基于大樣本的情況下,將耗費(fèi)大量CPU時間來做重復(fù)的計(jì)算工作。基于以上考慮,提出一種內(nèi)存種群冗余刪冗算法(Memory Population Reducing Redundant GEP,MPRRGEP),該算法包括3個部分:快速檢測基因有效串,構(gòu)建個體染色體有效串以及內(nèi)存Hash種群映射刪冗。

數(shù)據(jù)描述:在個體染色體中每一個字符,將其描述為元素結(jié)點(diǎn),CNode=(pElement,iParaCount),當(dāng)元素為函數(shù)集中元素,iParaCount大于0;若為終結(jié)集元素,iParaCount等于0;因此,基因?yàn)樵丶?其數(shù)據(jù)描述如下:

個體染色體為Gene集合,其數(shù)據(jù)描述如下:

隨著種群進(jìn)化,基因串不斷變化,算法1根據(jù)輸入的基因獲取該基因有效串的長度。該算法復(fù)雜度為線性時間O(N),N為基因串的長度。算法判斷了有效串長度小于基因頭部長度、等于基因頭部長度和大于基因頭部長度等情況。

算法1 基因有效長度檢測算法

輸入 基因串,頭部長度

輸出 有效基因串位置

算法2在算法1的基礎(chǔ)上獲取個體染色體有效串。在該算法中由于基因數(shù)目是常量C,其算法復(fù)雜度為O(CN),N為基因串長度。

算法2 個體染色體有效串獲取算法

輸入 個體染色體串,基因數(shù)

輸出 個體染色體有效串

在此基礎(chǔ)上,由于相同的個體染色體有效串計(jì)算出的適應(yīng)性函數(shù)值相同,然而GEP進(jìn)化過程中,容易產(chǎn)生不同的個體染色體與前代的個體染色體具有相同的有效串的情況。為避免重復(fù)計(jì)算,算法3基于內(nèi)存Hash機(jī)制對GEP種群映射刪冗。算法在內(nèi)存中開辟空間、組織索引減少相同個體染色體有效串的計(jì)算次數(shù),在保證種群多樣性的情況下大幅提高GEP計(jì)算性能。除此之外,考慮在多基因個體染色體情況下,若連接符可支持交換律,如:A + B=B+A,A*B=B*A等,多基因個體染色體有效串可進(jìn)行變換擴(kuò)展。該算法的時間復(fù)雜度為O(N),具體算法如下:

算法3 內(nèi)存Hash種群映射刪冗

輸入 個體染色體串,種群索引,基因數(shù)

輸出 種群索引

MPRRGEP基于Hash算法策略,對個體染色體有效串和對應(yīng)的適應(yīng)函數(shù)值進(jìn)行索引,將其全部保存在內(nèi)存的Hash表中。個體計(jì)算之前先訪問Hash表,若個體染色體存在于Hash表中,算法以較快的速度直接訪問該個體染色體所對應(yīng)的適應(yīng)性函數(shù)值。由于算法對于個體染色體有效串在內(nèi)存中僅保留了一個副本,有效地控制了其冗余性。

4 實(shí)驗(yàn)與分析

為滿足大樣本、多種群、高進(jìn)化代數(shù)的需求,實(shí)驗(yàn)平臺采用的硬件環(huán)境為:CPU Intel Xeon E5-2650 2 GHz、內(nèi)存128 GB,操作系統(tǒng)環(huán)境為Windows 2003 Server,整個實(shí)驗(yàn)是基于C++語言環(huán)境。

為了評估算法的性能以及節(jié)省的計(jì)算量,用MPRRGEP和GEP來解決生物上著名的關(guān)鍵蛋白識別問題[13]。關(guān)鍵蛋白質(zhì)是生物生存和繁殖必不可少的那類蛋白質(zhì)。識別關(guān)鍵蛋白質(zhì)能在理解生命體維持生命活動所需的基本需求,設(shè)計(jì)新抗生素的藥物標(biāo)靶以及探索人類疾病基因方面意義重大。目前計(jì)算方法識別關(guān)鍵蛋白主要是利用關(guān)鍵蛋白在蛋白質(zhì)相互作用網(wǎng)絡(luò)上的拓?fù)浜蜕锓矫娴奶卣鱽碜R別。這實(shí)際上是個二元分類問題。本文實(shí)驗(yàn)主要通過抽取蛋白質(zhì)的拓?fù)浜蜕锏奶卣鲗傩圆⑦\(yùn)用MPRRGEP生成特征表達(dá)式對蛋白質(zhì)的關(guān)鍵性進(jìn)行判別。數(shù)據(jù)樣本集來自于DIP[14]據(jù)庫的S.cerevisiae數(shù)據(jù)集,該數(shù)據(jù)集包含蛋白質(zhì)相互作用網(wǎng)絡(luò)和關(guān)鍵蛋白質(zhì)信息等,數(shù)據(jù)樣本包含5 093個蛋白質(zhì)信息,其中有1 167個關(guān)鍵蛋白質(zhì)。蛋白質(zhì)相互作用網(wǎng)絡(luò)中共計(jì)24 743條邊。基于蛋白質(zhì)相互作用網(wǎng)絡(luò),實(shí)驗(yàn)抽取網(wǎng)絡(luò)拓?fù)鋵傩宰鳛榈鞍踪|(zhì)關(guān)鍵性的特征屬性[15],并融合蛋白質(zhì)亞細(xì)胞定位特征數(shù)據(jù)[16],如拓?fù)渲行男詫傩?DC,IC,EC,SC, BC,CC,Soecc,Pec,P&E)、同源性屬性ION、亞細(xì)胞定位屬性。將收集的特征屬性作為MPRRGEP的終結(jié)符集,并引 +,-,*,=,/,Sqrt,Log,Exp, Abs,Max,Min等作為其函數(shù)符集,最終生成計(jì)算表達(dá)式用于關(guān)鍵蛋白質(zhì)的預(yù)測。具體參數(shù)如表1所示。

表1 參數(shù)描述及其設(shè)置

分別采用單基因和多基因個體染色體做實(shí)驗(yàn),單基因的參數(shù)為P2選擇1,P3選擇60,P4選擇20,多基因的參數(shù)為P2選擇3,P3選擇19,P4選擇9。在不同的進(jìn)化次數(shù)下,MPRRGEP和GEP的計(jì)算量如圖3所示。圖中的計(jì)算量表示為進(jìn)化過程中每一代種群需要多少個體染色體對全體樣本進(jìn)行計(jì)算。在蛋白質(zhì)關(guān)鍵性預(yù)測的實(shí)驗(yàn)中,采用10倍交叉驗(yàn)證個體染色體模型,樣本量為4 582。實(shí)驗(yàn)中取12 000的海量種群。在傳統(tǒng)的GEP中:總體的計(jì)算量為27 492 000 000(=12 000×4 582×500)次,實(shí)驗(yàn)總計(jì)花費(fèi)約49 h;而MPRRGEP單基因和多基因個體染色體的總計(jì)算次數(shù)分別為:8 693 717 266和4 780 556 388,實(shí)驗(yàn)的時間分別約為15 h和11 h。

圖3 不同進(jìn)化次數(shù)下MPRRGEP與GEP的計(jì)算量比較

圖3表明MPRRGEP能很好地避免GEP進(jìn)化出現(xiàn)不同的個體染色體具有相同的個體染色體有效串而重復(fù)對樣本的計(jì)算。為比較不同參數(shù)對算法性能影響,將不同參數(shù)進(jìn)行組合來考查MPRRGEP算法的計(jì)算量情況。參數(shù)設(shè)置為:種群規(guī)模分別選5 000和12 000,進(jìn)化次數(shù)分別選100次和500次,基因個數(shù)分別取單個和3個。不同參數(shù)組合情況下算法計(jì)算量如表2所示。

表2 不同參數(shù)組合情況下算法計(jì)算量

表 2表明,隨著種群規(guī)模、進(jìn)化次數(shù)增加, MPRRGEP算法的計(jì)算量也隨之降低。相比GEP而言,在 12 000的種群規(guī)模和 500次進(jìn)化次數(shù)下, MPRRGEP單基因和多基因個體染色體實(shí)驗(yàn)的平均計(jì)算量分別節(jié)約了83%和68.974 2%。實(shí)驗(yàn)結(jié)果表明,本文算法節(jié)約大量的重復(fù)計(jì)算時間,有效地提高了計(jì)算效率。

5 結(jié)束語

在大樣本、多種群、高進(jìn)化代數(shù)情況下,本文將內(nèi)存種群冗余刪除策略引入至傳統(tǒng)的GEP中,通過提取個體染色體有效串,擴(kuò)充有效串,并采用內(nèi)存HASH映射,大副降低相同染色體有效串的重復(fù)計(jì)算量、提高GEP計(jì)算性能。實(shí)驗(yàn)結(jié)果表明,相對于傳統(tǒng)的GEP算法,MPRRGEP節(jié)約大量的重復(fù)計(jì)算時間。此外,MPRRGEP關(guān)注GEP在進(jìn)化過程中產(chǎn)生的相同個體染色體有效串對樣本重復(fù)計(jì)算的問題,算法可與已有的GEP優(yōu)化算法結(jié)合使用,從而更高效地優(yōu)化GEP算法框架。

[1] Ferreira C.GeneExpression Programming:A New Adaptive Algorithm for Solving Problems[J].Complex Systems,2001,13(2):87-129.

[2] Ferreira C.Gene Expression Programming:Mathematical Modeling by an Artificial Intelligence[M].New York, USA:Springer-Verlag,2006.

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

[4] 倪勝巧,唐常杰,楊 寧,等.基于多線程評估的基因表達(dá)式編程算法[J].計(jì)算機(jī)應(yīng)用,2012,32(4): 986-989.

[5] 胡建軍,唐常杰,彭 京,等.快速跳出局部最優(yōu)的VPS-GEP算法[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2007, 39(1):128-133.

[6] 賈麗媛,張 弛.自適應(yīng)基因表達(dá)式程序設(shè)計(jì)研究及應(yīng)用[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,2012,43(6):2210-2214.

[7] 彭 京,唐常杰,李 川,等.M-GEP:基于多層染色體基因表達(dá)式編程的遺傳進(jìn)化算法[J].計(jì)算機(jī)學(xué)報(bào), 2005,28(9):1459-1466.

[8] 饒 元,元昌安.基于模擬退火的基因改進(jìn)型GEP算法[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版,2008,45(4): 767-772.

[9] 張?jiān)鲢y,元昌安,胡建軍,等.基于GEP和Baum-Welch算法訓(xùn)練HMM模型的研究[J].計(jì)算機(jī)工程與設(shè)計(jì), 2010,31(9):2027-2029.

[10] 胡資斌,朱永利,段振鋒,等.基于GEP滑動窗口模型的變壓器油中溶解氣體含量預(yù)測[J].華北電力大學(xué)學(xué)報(bào),2012,39(4):42-46.

[11] Azamathulla H M,Jarrett R D.Use of Gene-expression Programming to Estimate Manning'sRoughness Coefficient forHigh GradientStreams[J].Water Resources Management,2013,27(3):715-729.

[12] 李太勇,唐常杰,吳 江,等.基因表達(dá)式編程種群多樣性自適應(yīng)調(diào)控算法[J].電子科技大學(xué)學(xué)報(bào),2010, 39(2):279-283.

[13] Jeong H,Mason S P,Barabási A L,et al.Lethality and Centrality in Protein Networks[J].Nature,2001,411 (6833):41-42.

[14] Xenarios I,Salwinski L,Duan X J,et al.DIP,the Database of Interacting Proteins:A Research Tool for Studying Cellular Networks of Protein Interactions[J]. Nucleic Acids Research,2002,30(1):303-305.

[15] Peng Wei,Wang Jianxin,Wang Weiping,et al.Iteration Method forPredicting EssentialProteinsBased on Orthology and Protein-protein Interaction Networks[J]. BMC Systems Biology,2012,6(1):87.

[16] Pierleoni A,Martelli P L,Fariselli P,et al.eSLDB: Eukaryotic SubcellularLocalization Database[J]. Nucleic Acids Research,2007,35(s1):208-212.

編輯 顧逸斐

Memory Reducing Redundant Algorithm of Gene Expression Programming with Mass Population

ZHONG Jian-cheng1,PENG Wei2
(1.College of Engineering and Design,Hunan Normal University,Changsha 410081,China;
2.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650093,China)

Under the condition of large-sample,multi-population and high-evolution computation,Gene Expression Programming(GEP)is prone to produce redundant valid strings of chromosome,which impacts its performance dramatically.To address the problem,this paper proposes a new strategy named Memory Population Reducing Redundant GEP(MPRRGEP), which checks repeat valid strings of chromosome and reduces the redundant in memory.It analyses the influence of valid strings in both single-gene and multi-gene chromosome on the performance of GPE.And a method that can effectively measure the validity of individual chromosome is designed.By using Hash technique,the index of the data of valid individual chromosome is constructed in memory so as to reduce the amount of times that compute the same valid strings and improve the performance of GEP.Experimental results show that the method can averagely save the computing time for above 60%.

Gene Expression Programming(GEP);reducing redundant;Hash table;valid gene string;multi-gene; crucial protein prediction

1000-3428(2014)09-0233-05

A

TP18

10.3969/j.issn.1000-3428.2014.09.047

湖南省教育廳優(yōu)秀青年基金資助項(xiàng)目(12B080);湖南省科技計(jì)劃基金資助項(xiàng)目(2010GK3023);湖南師范大學(xué)教學(xué)改革基金資助項(xiàng)目(2013)。

鐘堅(jiān)成(1981-),男,講師、博士研究生,主研方向:機(jī)器學(xué)習(xí),生物信息學(xué);彭 瑋(通訊作者),講師、博士研究生。

2013-08-28

2013-10-22E-mail:superzjc@163.com