基于多線程評(píng)估的基因表達(dá)式編程算法

—論文發(fā)表專家—論文發(fā)表專家一m國手朮友叢網(wǎng)m國學(xué)朮發(fā)叢廚—論文發(fā)表專家基于多線程評(píng)估的基因表達(dá)式編程算法摘要：分析了基因表達(dá)式編程(gep)算法的性能關(guān)鍵，指出提升的一個(gè)重要瓶頸是在個(gè)體評(píng)估階段；結(jié)合多核cpu并行計(jì)算能力，提出了基于多線程評(píng)估的gep算法(mtegep)，并通過實(shí)驗(yàn)驗(yàn)證了mtegep的高效性：在雙核cpu環(huán)境下mtegep運(yùn)算速度是傳統(tǒng)gep的1.89倍，而在8核cpu環(huán)境下達(dá)到了6.48倍。實(shí)驗(yàn)結(jié)果表明該算法能有效提升gep算法的性能。關(guān)鍵詞：數(shù)據(jù)挖掘；基因表達(dá)式編程；多線程；多核cpu；評(píng)估geneexpressionprogrammingalgorithmbasedonmulti.threadingevaluatornisheng.qiao,tangchang.jie,yangning,zuojienisheng.qiaocollegeofcomputerscienee,sichuanuniversity,chengdusichuan610064,chinaabstract:combinestheadvantageofmulti.corecpuandmulti.threadingtechnology,introducesanewgeneexpressionprogramming（gep）algorithmwithmulti.threadingevaluatorwhichgreatlyimprovestheefficiencyofthegepalgorithm.theexperimentalresultsdemonstratethatthenewproposedalgorithmmtegepismoreefficiencythantraditionalgep.furthermore,comparingtothetraditionalgep,mtegepachieves1.89timesfasterspeedinaveragewithadual.corecpu,biningtheadvantagesofmulti.corecpuandmulti.threadingtechnology,anewgeneexpressionprogramming(gep)algorithmwithmulti.threadingevaluatorwasintroduced,whichgreatlyimprovedtheefficiencyofthegepalgorithm.theexperimentalresultsdemonstratethatthenewproposedalgorithmmtegepismoreefficientthantraditionalgep.furthermore,comparedtothetraditionalgep,mtegepachieves1.89timesfasterspeedinaveragewithadual.corecpu,and6.48timesfasterspeedwithaneight.corecpu.keywords:datamining;geneexpressionprogramming(gep);multi.threading;multi.corecpu;evaluator0引言從海量信息中挖掘有效知識(shí)是數(shù)據(jù)庫技術(shù)研究的重要課題。進(jìn)化計(jì)算作為數(shù)據(jù)挖掘的一類重要方法，有著廣泛的應(yīng)用，是當(dāng)前的研

—論文發(fā)表專家一m國學(xué)朮發(fā)舌網(wǎng)www,究熱點(diǎn)?；虮磉_(dá)式編程(geneexpressionprogramming,gep)算法是進(jìn)化算法家族中的新興技術(shù)，它綜合了遺傳算法(geneticalgorithm,ga)禾口遺傳編程(geneticprogramming,gp)的優(yōu)點(diǎn)，具有更強(qiáng)的解決問題的能力，其最大特點(diǎn)是優(yōu)化的基因序列表示結(jié)構(gòu)，它消除了傳統(tǒng)遺傳算法在進(jìn)化過程可能產(chǎn)生無效基因的缺陷，是效率較為理想的數(shù)據(jù)挖掘方法：1］甘別在因數(shù)挖掘方面，涌現(xiàn)出了許多新的gep研究和應(yīng)用成果，參見文獻(xiàn)］2-10］。與此同時(shí)，眾多學(xué)者在傳統(tǒng)gep算法基礎(chǔ)上，針對(duì)不同應(yīng)用提出了效率更高、適應(yīng)性更強(qiáng)的改進(jìn)算法。文獻(xiàn)［11］提出了基于搜索空間劃分和sharing函數(shù)的粒子群優(yōu)化算法；文獻(xiàn)］12］對(duì)傳統(tǒng)gep的評(píng)估算法進(jìn)行研究，提出了具有線性復(fù)雜度的gep適應(yīng)度評(píng)價(jià)算法；文獻(xiàn)］13］研究了基于基因表達(dá)式編程的多目標(biāo)優(yōu)化算法；此外文獻(xiàn)［14-17］分別針對(duì)不同領(lǐng)域提出了改進(jìn)的gep新算法。目前關(guān)于基因表達(dá)式編程的研究主要集中在對(duì)gep理論分析和算法優(yōu)化和改進(jìn)，尚未見到利用高性能硬件資源來提高gep性能的研究。在實(shí)踐中，作者發(fā)現(xiàn)目前的gep算法沒有充分發(fā)揮計(jì)算機(jī)硬件的性能，算法效率不盡如人意。例如：在種群規(guī)模較大、進(jìn)化代數(shù)較多、訓(xùn)練數(shù)據(jù)規(guī)模較大的情況下，從開始運(yùn)行g(shù)ep程序到得出結(jié)果，往往需要等上幾分鐘、十幾分甚至是幾十分鐘的時(shí)間。本文旨在利用當(dāng)前中央處理器—論文發(fā)表專家一LB國學(xué)朮發(fā)叢網(wǎng)www,（centralprocessingunit,cpu）力口速gep進(jìn)化過程，大幅提升gep算法性能，即在用硬件加速進(jìn)化計(jì)算方面作有益的探索。1基因表達(dá)式編程gep是candidaferreira在研究ga禾口gp的基礎(chǔ)上，發(fā)展出的新概念。傳統(tǒng)的gep算法見圖1。在整個(gè)gep的流程中，創(chuàng)建初始種群的染色體是一個(gè)隨機(jī)生成染色體字符串的過程，而選擇則是根據(jù)各個(gè)染色體的適應(yīng)度，使用一定的選擇算子，如輪盤賭選擇算子、錦標(biāo)賽選擇算子等進(jìn)行選擇，保證適應(yīng)度高的個(gè)體有更高的選中概率。整個(gè)過程周而復(fù)始，直到達(dá)到一定的結(jié)束條件：找到最優(yōu)解、達(dá)到一定代數(shù)、適應(yīng)度達(dá)到某個(gè)值或者運(yùn)行時(shí)間達(dá)到預(yù)設(shè)時(shí)間等。gep與ga、gp最本質(zhì)的區(qū)別是：在ga中個(gè)體由固定長度的線性串（染色體）來表示；在gp中個(gè)體則是由不同大小和形狀的非線性實(shí)體（解析樹）所表示的；而gep將個(gè)體先編碼為固定長度的線性串，再表示成大小、形狀都不同的非線性實(shí)體。這樣，gep就克服了ga損失功能復(fù)雜性的可能性和gp難以再產(chǎn)生新的變化的可能性。gep的創(chuàng)始人candida研究證實(shí)：gep在解決復(fù)雜問題的時(shí)候，比傳統(tǒng)的遺傳編程方法效率高出2?4個(gè)數(shù)量級(jí)。2gep性能提升新思路盡管gep比gp快了2?4個(gè)數(shù)量級(jí)，但隨著數(shù)據(jù)規(guī)模的增大和運(yùn)行次數(shù)的遞增，gep程序的運(yùn)行速度還不盡如人意。實(shí)踐中，為了

—*二丈發(fā)去專家一m國學(xué)朮發(fā)叢網(wǎng)www,qikanwa追求效果，常需提高種群規(guī)模和測(cè)試數(shù)據(jù)規(guī)模，在海量數(shù)據(jù)條件下，運(yùn)行一次gep程序需要幾分鐘到幾十分鐘。為解決這一問題，本文提出了挖掘硬件潛力來提升gep性能的新思路。2.1gep運(yùn)行時(shí)間的測(cè)試標(biāo)準(zhǔn)及分析方法為找出gep算法運(yùn)算中影響速度的關(guān)鍵因素：把gep算法分成以下幾個(gè)階段。1）種群初始化階段：隨機(jī)產(chǎn)生初始種群。2）個(gè)體評(píng)估階段：包括對(duì)個(gè)體的解析（生成表達(dá)式），對(duì)個(gè)體適應(yīng)度的評(píng)估（表達(dá)式的運(yùn)算）。3）個(gè)體選擇階段：選擇最優(yōu)的個(gè)體并保留。4）個(gè)體進(jìn)化階段：對(duì)保留的個(gè)體通過遺傳算子進(jìn)行進(jìn)化，產(chǎn)生新的種群。定義1設(shè)n是gep進(jìn)化代數(shù)，r是種群初始化需要的時(shí)間，ei、ci、gi,i€[0,n]分別是第i代進(jìn)化過程中個(gè)體評(píng)估階段、個(gè)體選擇階段和個(gè)體進(jìn)化階段所占用的時(shí)間，t是gep算法進(jìn)化n代需要的總時(shí)間，那么容易得到：t=r+刀ni=0（ei+ci+gi）設(shè)種群規(guī)模是m測(cè)試數(shù)據(jù)規(guī)模是k,根據(jù)定義1考察分析如下。5上：5上：JI5上：5上：JI1）種群初始化階段在整個(gè)算法過程中只運(yùn)行一次，它負(fù)責(zé)隨機(jī)產(chǎn)生m個(gè)體，運(yùn)算時(shí)間有限，即r的取值確定且很小。2）由于初始化階段消耗時(shí)間有限，又每代個(gè)體評(píng)估、選擇、進(jìn)化的時(shí)間是比較穩(wěn)定的，即ei+ci+gi的俏是穩(wěn)定的，所以可以預(yù)計(jì)gep的運(yùn)行時(shí)間與進(jìn)化的代數(shù)n乜線性增3）種群每進(jìn)化一代，都需要對(duì)m個(gè)體分別進(jìn)行k次評(píng)估運(yùn)算，共計(jì)mxk次運(yùn)算。假設(shè)單個(gè)個(gè)體進(jìn)行一次評(píng)估運(yùn)算的平均時(shí)間是p（在函數(shù)挖掘中，可以看作是一個(gè)算數(shù)表達(dá)式的解析和計(jì)算時(shí)間是P），那么種群進(jìn)化一代所需要的評(píng)估時(shí)間是mxkxp,也就是說評(píng)估階段的時(shí)間消耗主要取決于種群規(guī)模、測(cè)試數(shù)據(jù)規(guī)模以及單個(gè)個(gè)體進(jìn)行一次評(píng)佔(zhàn)的平均時(shí)間。4）在個(gè)體選擇和進(jìn)化階段，由于都是采用了固定的極有限的幾個(gè)操作步驟（主要是對(duì)個(gè)體適應(yīng)度進(jìn)行比較，找出適應(yīng)度最大的個(gè)體，進(jìn)行保留和進(jìn)化），消耗的時(shí)間是很有限的，當(dāng)種群進(jìn)化一代的評(píng)估時(shí)間mxkxp較大（mxkxp的俏抗尬大丁選扌f-和逬化時(shí)間）的時(shí)候，個(gè)體選擇和進(jìn)化操作的時(shí)間可以忽略。上述分析表明，gep的運(yùn)行時(shí)間瓶頸是評(píng)估階段，gep運(yùn)行的總時(shí)間t近似于nxmxkxp,即gep算法的時(shí)間復(fù)雜度是o（nxmxkxp）。2.2gep算法改進(jìn)策略由上分析，改進(jìn)評(píng)估算法，減少評(píng)估時(shí)間，能提升gep整體性能。1=im國學(xué)朮發(fā)舌廚考慮到gep中個(gè)體的評(píng)估是相互獨(dú)立的，本文把多線程技術(shù)引入gep的評(píng)估階段，提出了基于多線程評(píng)估的gep（gepwithmulti.threadingevaluator，mtegep）算法，并進(jìn)行了詳實(shí)的實(shí)驗(yàn)驗(yàn)證3mtegep算法設(shè)計(jì)與實(shí)現(xiàn)3.1傳統(tǒng)gep適應(yīng)度評(píng)估算法傳統(tǒng)gep算法采用單線程評(píng)估策略，未能充分發(fā)揮cpu的多線程并行處理能力，也未嘗試過在多核cpu上進(jìn)行評(píng)估工作，限制了gep算法的性能。傳統(tǒng)算法，對(duì)所有個(gè)體采用單線程技術(shù)逐個(gè)評(píng)估，算法描述如下。分析算法1,容易得到：傳統(tǒng)gep適應(yīng)度評(píng)估算法中，需要逐個(gè)對(duì)所有個(gè)體進(jìn)行獨(dú)立的解碼和計(jì)算（對(duì)應(yīng)算法1的第3）?8）行）。所以如果將算法1的3）?8）行設(shè)計(jì)成多線程并行運(yùn)算，必定能大幅提高gep評(píng)估效率，從而提升gep整體性能。3.2mtegep算法的評(píng)估線程數(shù)量選擇確定了評(píng)估策略，還要確定評(píng)估線程的數(shù)量。為了平衡各評(píng)估線程的運(yùn)算任務(wù)，盡量把種群個(gè)體均勻地分配給每個(gè)評(píng)估線程。假定種群規(guī)模為size，線程個(gè)數(shù)為n,休分配算法思想如卜"1）記每個(gè)線程分配個(gè)體的是平均數(shù)目為averagenumber二size/n」（向下取整）。2）如果heavynumber二size%n小為0,即size不能被n整

—論文發(fā)表專家一B國學(xué)朮發(fā)叢網(wǎng)www,除，門么前heavynumber個(gè)評(píng)仙裁秤哆壇加1個(gè)個(gè)體評(píng)估任務(wù)。3）考慮到gep算法設(shè)計(jì)中，種群的個(gè)體是線性存儲(chǔ)的（一維數(shù)組的形式存儲(chǔ)），我們只要記錄每個(gè)評(píng)估線程負(fù)責(zé)的第1個(gè)個(gè)體位置和負(fù)責(zé)的個(gè)體數(shù)量就可以確定具體分組情況。為了對(duì)分組個(gè)體進(jìn)行相互獨(dú)立的適應(yīng)度評(píng)估，作者設(shè)計(jì)了專門的分組評(píng)估器ethread，它只對(duì)負(fù)責(zé)的分組個(gè)體進(jìn)行評(píng)估。評(píng)估器ethread的評(píng)估算法描述如下。4實(shí)驗(yàn)結(jié)果與分析4.1實(shí)驗(yàn)說明本文所有實(shí)驗(yàn)都是通過gep進(jìn)行函數(shù)挖掘來測(cè)試運(yùn)行時(shí)間。1）選擇來自參考文獻(xiàn)］1］的擬合函數(shù)fl:10+sin（1x）（x—0.16）2+0.1;0<x<12）f1隨札生成的測(cè)試數(shù)據(jù)作為進(jìn)化壞境°3）實(shí)驗(yàn)參數(shù)見表1。4）相同參數(shù)的實(shí)驗(yàn)重復(fù)做10次，取運(yùn)行時(shí)間的平均值。測(cè)試數(shù)據(jù)規(guī)模單位是組，運(yùn)行時(shí)間單位是秒。5）考慮到進(jìn)化代數(shù)、種群規(guī)模和測(cè)試數(shù)據(jù)規(guī)模對(duì)gep算法的性能影響是等效的（都是線性的）。所以這里選擇固定進(jìn)化代數(shù)和種群規(guī)模，而改變數(shù)據(jù)規(guī)模的情況下進(jìn)行實(shí)驗(yàn)來觀察，mtegep算法與傳統(tǒng)gep算法的性能差異。—論文發(fā)表專家一—論文發(fā)表專家一m國學(xué)朮發(fā)叢廚www.qikanwangnS—論文發(fā)表專家一—論文發(fā)表專家一m國學(xué)朮發(fā)叢廚www.qikanwangnS[2][2][2][2]5結(jié)語通過對(duì)mtegep算法和傳統(tǒng)gep算法在雙核cpu環(huán)境和8核cpu環(huán)境上的實(shí)驗(yàn)驗(yàn)證和分析，總結(jié)如下。1）在多核cpu環(huán)境下，mtegep算法能夠較傳統(tǒng)gep算法有較大的性能提升。2）在8核cpu環(huán)境下，當(dāng)開設(shè)的評(píng)估線程數(shù)量不超過8個(gè)的時(shí)候，mtegep算法性能隨評(píng)估線程數(shù)量的增加而穩(wěn)步提升。3）在8核cpu環(huán)境下，開設(shè)8個(gè)評(píng)估線程能夠使mtegep達(dá)到最佳的性能。4）由于考慮到cpu還要負(fù)責(zé)整個(gè)計(jì)算機(jī)系統(tǒng)的其他運(yùn)算和管理，同時(shí)需完成各線程之間的調(diào)度工作，所以在8核cpu環(huán)境下，mtegep算法不能較傳統(tǒng)gep算法提升8倍的速度，但是其最佳的提升速度接近8倍。5）不難推斷在n核cpu環(huán)境下能夠得到與8核cpu的性能提升的相同情況，所以mtegep算法是一個(gè)高效、實(shí)用的算法。參考文獻(xiàn):[1]ferreirac.geneexpressionprogramming:mathematicalmodelingbyanartificialintelligence[m].2nded.newyork:springerpress,2006.—論文發(fā)表專家一B國學(xué)朮發(fā)叢網(wǎng)www,陳建明，陳宇，李志蜀，等.基于gep的路徑覆蓋測(cè)試用例生成方法[j].計(jì)算機(jī)工程，2010,36(15):86-88.[3]唐常杰，陳瑜，張歡，等.基于轉(zhuǎn)基因gep的公式發(fā)現(xiàn)[j].計(jì)算機(jī)應(yīng)用,2007,27(10):2358-2360,2364.[4]賈曉斌，唐常杰，左劼，等.基于基因表達(dá)式編程的頻繁函數(shù)集挖掘[j].計(jì)算機(jī)學(xué)報(bào)，2005,28(8):1247-1254.[5]廖勇，唐常杰，元昌安，等.基于基因表達(dá)式編程的股票指數(shù)時(shí)間序列分析]j].四川大學(xué)學(xué)報(bào)：自然科學(xué)版，2005,42(5):931-936.[6]劉海濤，元昌安，劉海龍，等.基于gep的遙感數(shù)字圖像模糊聚類研究[j].計(jì)算機(jī)工程，2010,36(10):199-200,238.[7]龍瓏，寧葵.基于gep的web服務(wù)器安全防護(hù)技術(shù)研究[j].計(jì)算機(jī)技術(shù)與發(fā)展，2011,24(10):241-245.[8]黃立昕，董悅坤.基于因子分析和基因表達(dá)式編程的電流互感器故障診斷[j].電力科學(xué)與工程，2011,27(10):26-30,56—論文發(fā)表專家一m國學(xué)朮發(fā)叢網(wǎng)www,[9]何家莉，王培.基因表達(dá)式中含有等式約束的處理方法]j].計(jì)算機(jī)技術(shù)與發(fā)展，20