网站位置: >> 论文 >> 本科论文 >> 免费论文范文阅读

算法相关论文格式,关于基于多线程评估的基因表达式编程算法相关毕业论文开题报告范文

此文是一篇算法论文范文,算法相关论文范本,与基于多线程评估的基因表达式编程算法相关毕业论文开题报告范文。适合不知如何写算法及自然科学及计算机技术方面的本科论文专业大学硕士和本科毕业论文以及算法类开题报告范文和职称论文的作为写作参考文献资料下载。

摘 要:分析了基因表达式编程(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.


怎么写算法硕士毕业论文
播放:39097次 评论:3024人

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.svfree.net/benkelunwen/060369597.html

4)在个体选择和进化阶段,由于都是采用了固定的极有限的几个操作步骤(主要是对个体适应度进行比较,找出适应度最大的个体,进行保留和进化),消耗的时间是很有限的,当种群进化一代的评估时间m×k×p较大(m×k×p的值远远大于选择和进化时间)的时候,个体选择和进化操作的时间可以忽略.

上述分析表明,GEP的运行时间瓶颈是评估阶段,GEP运行的总时间T近似于n×m×k×p,即GEP算法的时间复杂度是O(n×m×k×p).

2.2GEP算法改进策略

由上分析,改进评估算法,减少评估时间,能提升GEP整体性能.考虑到GEP中个体的评估是相互独立的,本文把多线程技术引入GEP的评估阶段,提出了基于多线程评估的GEP(GEPwithMulti.ThreadingEvaluator,MTEGEP)算法,并进行了详实的实验验证.

3MTEGEP算法设计与实现

3.1传统GEP适应度评估算法

传统GEP算法采用单线程评估策略,未能充分发挥CPU的多线程并行处理能力,也未尝试过在多核CPU上进行评估工作,限制了GEP算法的性能.传统算法,对所有个体采用单线程技术逐个评估,算法描述如下.

分析算法1,容易得到:传统GEP适应度评估算法中,需要逐个对所有个体进行独立的解码和计算(对应算法1的第3)~8)行).所以如果将算法1的3)~8)行设计成多线程并行运算,必定能大幅提高GEP评估效率,从而提升GEP整体性能.

3.2MTEGEP算法的评估线程数量选择

确定了评估策略,还要确定评估线程的数量.为了平衡各评估线程的运算任务,尽量把种群个体均匀地分配给每个评估线程.假定种群规模为SIZE,线程个数为N,体分配算法思想如下.

1)记每个线程分配个体的是平均数目为AverageNumber等于SIZE/N」(向下取整).

2)如果HeavyNumber等于SIZE%N不为0,即SIZE不能被N整除,那么前HeavyNumber个评估线程多增加1个个体评估任务.

3)考虑到GEP算法设计中,种群的个体是线性存储的(一维数组的形式存储),我们只要记录每个评估线程负责的第1个个体位置和负责的个体数量就可以确定具体分组情况.

为了对分组个体进行相互独立的适应度评估,作者设计了专门的分组评估器EThread,它只对负责的分组个体进行评估.评估器EThread的

1 2

参考文献:

一种新的软聚类方法在入侵检测中的应用

两种分类器算法adaboostM1和multiclassclassifier对中草药数据分类的比较

基于K—means的改进人工蜂群聚类算法

营区扫描式监控中的运动目标检测

《计算机组成原理与汇编语言》课程教学改革

数据为主线的计算机组成原理教学

基于多线程评估的基因表达式编程算法word版本

高中可以自考本科吗

自考护士本科

本科论文检测吗

本科论文翻译

本科论文抄袭检测

本科生毕业论文目录

自考本科论文范文

本科日语毕业论文

本科论文提纲格式

自考本科论文格式

算法相关论文



相关频道推荐