鐘堅成,彭 瑋

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

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

鐘堅成1,彭 瑋2

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

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

基因表達式編程;刪冗;哈希表;基因有效串;多基因;關鍵蛋白質(zhì)預測

1 概述

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

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

2 個體染色體有效串

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

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

圖1 單基因染色體及其表達式樹

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

圖2 多基因染色體及其表達式樹

定義1 基因有效串

基因的長度為GL:

其中,h為基因頭部字符個數(shù);ni為基因頭部中第i個函數(shù)符的參數(shù)個數(shù)?；蜃址杏糜谡_描述表達式樹的前L個字符為基因有效串?；蛴行Т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ā)生了變更不會影響個體染色體串生成表達式樹,即也不會影響樣本計算后適應性函數(shù)評價的結果。針對上例中的多基因個體染色體“-b*babbab*Qb+abbba-* Qabbaba”,該染色體分為3個基因,其中每個基因都有自身的有效串,如基因1的有效串為“-b*ba”、基因2的有效串為“*Qb+ab”、基因3的有效串為“-*Qabb”,個體染色體的有效串為3個基因有效串的連接“-b*ba*Qb+ab-*Qabb”。圖2中Valid Pos箭頭后方到所在基因尾部字符發(fā)生了變更也不會影響個體染色體串生成表達式樹。

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

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

數(shù)據(jù)描述:在個體染色體中每一個字符,將其描述為元素結點,CNode=(pElement,iParaCount),當元素為函數(shù)集中元素,iParaCount大于0;若為終結集元素,iParaCount等于0;因此,基因為元素集合,其數(shù)據(jù)描述如下:

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

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

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

輸入 基因串,頭部長度

輸出 有效基因串位置

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

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

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

輸出 個體染色體有效串

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

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

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

輸出 種群索引

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

4 實驗與分析

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

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

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

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

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

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

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

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

5 結束語

在大樣本、多種群、高進化代數(shù)情況下,本文將內(nèi)存種群冗余刪除策略引入至傳統(tǒng)的GEP中,通過提取個體染色體有效串,擴充有效串,并采用內(nèi)存HASH映射,大副降低相同染色體有效串的重復計算量、提高GEP計算性能。實驗結果表明,相對于傳統(tǒng)的GEP算法,MPRRGEP節(jié)約大量的重復計算時間。此外,MPRRGEP關注GEP在進化過程中產(chǎn)生的相同個體染色體有效串對樣本重復計算的問題,算法可與已有的GEP優(yōu)化算法結合使用,從而更高效地優(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] 元昌安,彭昱忠,覃 曉,等.基因表達式編程的原理與算法應用[M].北京:科學出版社,2010.

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

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

[6] 賈麗媛,張 弛.自適應基因表達式程序設計研究及應用[J].中南大學學報:自然科學版,2012,43(6):2210-2214.

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

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

[9] 張增銀,元昌安,胡建軍,等.基于GEP和Baum-Welch算法訓練HMM模型的研究[J].計算機工程與設計, 2010,31(9):2027-2029.

[10] 胡資斌,朱永利,段振鋒,等.基于GEP滑動窗口模型的變壓器油中溶解氣體含量預測[J].華北電力大學學報,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] 李太勇,唐常杰,吳 江,等.基因表達式編程種群多樣性自適應調(diào)控算法[J].電子科技大學學報,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)秀青年基金資助項目(12B080);湖南省科技計劃基金資助項目(2010GK3023);湖南師范大學教學改革基金資助項目(2013)。

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

2013-08-28

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