基于多線程評估的基因表達式編程算法

—論文發(fā)表專家—論文發(fā)表專家一m國手朮友叢網(wǎng)m國學朮發(fā)叢廚—論文發(fā)表專家基于多線程評估的基因表達式編程算法摘要：分析了基因表達式編程(gep)算法的性能關(guān)鍵，指出提升的一個重要瓶頸是在個體評估階段；結(jié)合多核cpu并行計算能力，提出了基于多線程評估的gep算法(mtegep)，并通過實驗驗證了mtegep的高效性：在雙核cpu環(huán)境下mtegep運算速度是傳統(tǒng)gep的1.89倍，而在8核cpu環(huán)境下達到了6.48倍。實驗結(jié)果表明該算法能有效提升gep算法的性能。關(guān)鍵詞：數(shù)據(jù)挖掘；基因表達式編程；多線程；多核cpu；評估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ù)據(jù)庫技術(shù)研究的重要課題。進化計算作為數(shù)據(jù)挖掘的一類重要方法，有著廣泛的應用，是當前的研

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

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

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