论文网
算法相关论文范本,与基于多线程评估的基因表达式编程算法相关论文格式
本论文是一篇算法相关论文格式,关于基于多线程评估的基因表达式编程算法相关在职研究生毕业论文范文。免费优秀的关于算法及自然科学及计算机技术方面论文范文资料,适合算法论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。
摘 要:分析了基因表达式编程(GEP)算法的性能关键,指出提升的一个重要瓶颈是在个体评估阶段；结合多核CPU并行计算能力,提出了基于多线程评估的GEP算法(MTEGEP),并通过实验验证了MTEGEP的高效性：在双核CPU环境下MTEGEP运算速度是传统GEP的1.89倍,而在8核CPU环境下达到了6.48倍.实验结果表明该算法能有效提升GEP算法的性能.
关 键 词:数据挖掘；基因表达式编程；多线程；多核CPU；评估
中图分类号:TP311文献标志码:A
Geneexpressionprogrammingalgorithmbasedonmulti.threadingevaluator
NISheng.qiao*,TANGChang.jie,YANGNing,ZUOJie
CollegeofComputerScience,SichuanUniversity,ChengduSichuan610064,China
Abstract:
CombinestheadvantageofMulti.coreCPUandMulti.Threadingtechnology,introducesanewGeneExpressionProgramming（GEP）algorithmwithMulti.ThreadingEvaluatorwhichgreatlyimprovestheefficiencyoftheGEPalgorithm.TheexperimentalresultsdemonstratethatthenewproposedalgorithmMTEGEPismoreefficiencythantraditionalGEP.Furthermore,paringtothetraditionalGEP,MTEGEPachieves1.89timesfasterspeedinaveragewithadual.coreCPU,and6.48timesfasterspeedwithaneight.coreCPU.
Combiningtheadvantagesofmulti.coreCPUandmulti.threadingtechnology,anewGeneExpressionProgramming（GEP）algorithmwithmulti.threadingevaluatorwasintroduced,whichgreatlyimprovedtheefficiencyoftheGEPalgorithm.TheexperimentalresultsdemonstratethatthenewproposedalgorithmMTEGEPismoreefficientthantraditionalGEP.Furthermore,paredtothetraditionalGEP,MTEGEPachieves1.89timesfasterspeedinaveragewithadual.coreCPU,and6.48timesfasterspeedwithaneight.coreCPU.
Keywords:
datamining,GeneExpressionProgramming(GEP),multi.threading,multi.coreCPU,evaluator
0引言
从海量信息中挖掘有效知识是数据库技术研究的重要课题.进化计算作为数据挖掘的一类重要方法,有着广泛的应用,是当前的研究热点.基因表达式编程(GeneExpressionProgramming,GEP)算法是进化算法家族中的新兴技术,它综合了遗传算法(GeicAlgorithm,GA)和遗传编程(GeicProgramming,GP)的优点,具有更强的解决问题的能力,其最大特点是优化的基因序列表示结构,它消除了传统遗传算法在进化过程可能产生无效基因的缺陷,是效率较为理想的数据挖掘方法［1］.特别在函数挖掘方面,涌现出了许多新的GEP研究和应用成果,参见文献［2-10］.与此同时,众多学者在传统GEP算法基础上,针对不同应用提出了效率更高、适应性更强的改进算法.文献［11］提出了基于搜索空间划分和Sharing函数的粒子群优化算法；文献［12］对传统GEP的评估算法进行研究,提出了具有线性复杂度的GEP适应度评价算法；文献［13］研究了基于基因表达式编程的多目标优化算法,此外文献［14-17］分别针对不同领域提出了改进的GEP新算法.
目前关于基因表达式编程的研究主要集中在对GEP理论分析和算法优化和改进,尚未见到利用高性能硬件资源来提高GEP性能的研究.在实践中,作者发现目前的GEP算法没有充分发挥计算机硬件的性能,算法效率不尽如人意.例如：在种群规模较大、进化代数较多、训练数据规模较大的情
况下,从开始运行GEP程序到得出结果,往往需要等上几分钟、十几分甚至是几十分钟的时间.本文旨在利用当前中央处理器(CentralProcessingUnit,CPU)加速GEP进化过程,大幅提升GEP算法性能,即在用硬件加速进化计算方面作有益的探索.
1基因表达式编程
GEP是CandidaFerreira在研究GA和GP的基础上,发展出的新概念.传统的GEP算法见图1.在整个GEP的流程中,创建初始种群的染色体是一个随机生成染色体字符串的过程,而选择则是根据各个染色体的适应度,使用一定的选择算子,如轮盘赌选择算子、锦标赛选择算子等进行选择,保证适应度高的个体有更高的选中概率.整个过程周而复始,直到达到一定的结束条件：找到最优解、达到一定代数、适应度达到某个值或者运行时间达到预设时间等.
GEP与GA、GP最本质的区别是：在GA中个体由固定长度的线性串(染色体)来表示；在GP中个体则是由不同大小和形状的非线性实体(解析树)所表示的；而GEP将个体先编码为固定长度的线性串,再表示成大小、形状都不同的非线性实体.这样,GEP就克服了GA损失功能复杂性的可能性和GP难以再产生新的变化的可能性.GEP的创始人Candida研究证实：GEP在解决复杂问题的时候,比传统的遗传编程方法效率高出2～4个数量级.
2GEP性能提升新思路
尽管GEP比GP快了2～4个数量级,但随着数据规模的增大和运行次数的递增,GEP程序的运行速度还不尽如人意.实践中,为了追求效果,常需提高种群规模和测试数据规模,在海量数据条件下,运行一次GEP程序需要几分钟到几十分钟.为解决这一问题,本文提出了挖掘硬件潜力来提升GEP性能的新思路.2.1GEP运行时间的测试标准及分析方法
为找出GEP算法运算中影响速度的关键因素：把GEP算法分成以下几个阶段.
1)种群初始化阶段:随机产生初始种群.
2)个体评估阶段:包括对个体的解析(生成表达式),对个体适应度的评估(表达式的运算).
3)个体选择阶段:选择最优的个体并保留.
4)个体进化阶段:对保留的个体通过遗传算子进行进化,产生新的种群.
定义1
设n是GEP进化代数,r是种群初始化需要的时间,ei、ci、gi,i∈［0,n］分别是第i代进化过程中个体评估阶段、个体选择阶段和个体进化阶段所占用的时间,T是GEP算法进化n代需要的总时间,那么容易得到：
T等于r+∑ni等于0(ei+ci+gi)
设种群规模是m,测试数据规模是k,根据定义1考察分析如下.
1)种群初始化阶段在整个算法过程中只运行一次,它负责随机产生m个体,运算时间有限,即r的取值确定且很小.
2)由于初始化阶段消耗时间有限,又每代个体评估、选择、进化的时间是比较稳定的,即ei+ci+gi的值是稳定的,所以可以预计GEP的运行时间与进化的代数n呈线性增长.
3)种群每进化一代,都需要对m个体分别进行k次评估运算,共计m×k次运算.假设单个个体进行一次评估运算的平均时间是p(在函数挖掘中,可以看作是一个算数表达式的解析和计算时间是p),那么种群进化一代所需要的评估时间是m×k×p,也就是说评估阶段的时间消耗主要取决于种群规模、测试数据规模以及单个个体进行一次评估的平均时间.
该文来自:http://www.sxsky.net/benkelunwen/060369597.html
4)在个体选择和进化阶段,由于都是采用了固定的极有限的几个操作步骤(主要是对个体适应度进行比较,找出适应度最大的个体,进行保留和进化),消耗的时间是很有限的,当种群进化一代的评估时间m×k×p较大(m×k×p的值远远大于选择和进化时间)的
算法相关论文范本,与基于多线程评估的基因表达式编程算法相关论文格式参考文献资料：