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

更新时间:2024-03-04 作者:用户投稿原创标记本站原创 点赞:6613 浏览:22528

摘 要:分析了基因表达式编程(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.TheexperimentalresultsdemonstratethatthenewproposedalgorithmMTEGEPioreefficiencythantraditionalGEP.Furthermore,paringtothetraditionalGEP,MTEGEPachieves1.89timeasterspeedineragewithadual.coreCPU,and6.48timeasterspeedwithaneight.coreCPU.

Combiningtheadvantagesofmulti.coreCPUandmulti.threadingtechnology,anewGeneExpressionProgramming(GEP)algorithmwithmulti.threadingevaluatorwasintroduced,whichgreatlyimprovedtheefficiencyoftheGEPalgorithm.TheexperimentalresultsdemonstratethatthenewproposedalgorithmMTEGEPioreefficientthantraditionalGEP.Furthermore,paredtothetraditionalGEP,MTEGEPachieves1.89timeasterspeedineragewithadual.coreCPU,and6.48timeasterspeedwithaneight.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,也就是说评估阶段的时间消耗主要取决于种群规模、测试数据规模以及单个个体进行一次评估的平均时间.


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)如果HeyNumber等于SIZE%N不为0,即SIZE不能被N整除,那么前HeyNumber个评估线程多增加1个个体评估任务.

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

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

4实验结果与分析

4.1实验说明

本文所有实验都是通过GEP进行函数挖掘来测试运行时间.

1)选择来自参考文献[1]的拟合函数F1:

10+sin(1x)(x-0.16)2+0.1;0

2)F1随机生成的测试数据作为进化环境.

3)实验参数见表1.

4)相同参数的实验重复做10次,取运行时间的平均值.测试数据规模单位是组,运行时间单位是秒.

5)考虑到进化代数、种群规模和测试数据规模对GEP算法的性能影响是等效的(都是线性的).所以这里选择固定进化代数和种群规模,而改变数据规模的情况下进行实验来观察,MTEGEP算法与传统GEP算法的性能差异.

5结语

通过对MTEGEP算法和传统GEP算法在双核CPU环境和8核CPU环境上的实验验证和分析,总结如下.

1)在多核CPU环境下,MTEGEP算法能够较传统GEP算法有较大的性能提升.

2)在8核CPU环境下,当开设的评估线程数量不超过8个的时候,MTEGEP算法性能随评估线程数量的增加而稳步提升.

3)在8核CPU环境下,开设8个评估线程能够使MTEGEP达到最佳的性能.

4)由于考虑到CPU还要负责整个计算机系统的其他运算和管理,同时需完成各线程之间的调度工作,所以在8核CPU环境下,MTEGEP算法不能较传统GEP算法提升8倍的速度,但是其最佳的提升速度接近8倍.

5)不难推断在N核CPU环境下能够得到与8核CPU的性能提升的相同情况,所以MTEGEP算法是一个高效、实用的算法.参考文献:

[1]

FERREIRAC.Geneexpressionprogramming:Mathematicalmodelingbyanartificialintelligence[M].2nded.NewYork:SpringerPress,2006.

[2]

陈建明,陈宇,李志蜀,等.基于GEP的路径覆盖测试用例生成方法[J].计算机工程,2010,36(15):86-88.

[3]

唐常杰,陈瑜,张欢,等.基于转基因GEP的公式发现[J].计算机应用,2007,27(10):2358-2360,2364.

[4]

贾晓斌,唐常杰,左,等.基于基因表达式编程的频繁函数集挖掘[J].计算机学报,2005,28(8):1247-1254.

[5]

廖勇,唐常杰,元昌安,等.基于基因表达式编程的股票指数时间序列分析[J].四川大学学报:自然科学版,2005,42(5):931-936.

[6]

刘海涛,元昌安,刘海龙,等.基于GEP的遥感数字图像模糊聚类研究[J].计算机工程,2010,36(10):199-200,238.

[7]

龙珑,宁葵.基于GEP的Web怎么写作器安全防护技术研究[J].计算机技术与发展,2011,24(10):241-245.

[8]

黄立昕,董悦坤.基于因子分析和基因表达式编程的电流互感器故障诊断[J].电力科学与工程,2011,27(10):26-30,56

[9]

何家莉,王培.基因表达式中含有等式约束的处理方法[J].计算机技术与发展,2011,21(9):92-94,98.

[10]

元昌安,唐常杰,左,等.基于基因表达式编程的函数挖掘――收敛性分析与残差制导进化算法[J].四川大学学报:工程科学版,2004,36(6):100-105.

[11]

苏辉,唐常杰,乔少杰,等.基于搜索空间划分和Sharing函数的粒子群优化算法[J].四川大学学报:自然科学版,2007,44(5):985-989.

[12]

陈瑜,唐常杰,李川,等.LDecode:具有线性复杂度的GEP适应度评价算法[J].四川大学学报:工程科学版,2008,44(10):107-112.

[13]

向勇,唐常杰,曾涛,等.基于基因表达式编程的多目标优化算法[J].四川大学学报:工程科学版,2007,39(4):124-129.

[14]

朱明放,唐昌杰,代术成,等.基于中性突变的朴素基因表达式编程[J].计算机研究与发展,2010,47(2):292-299.

[15]

吴江,李太勇,姜,等.基于多样化进化策略的基因表达式编程算法[J].吉林大学学报:信息科学版,2010,28(4):376-403.

[16]

龚杰,唐常杰,徐开阔,等.CC.GEP:基于聚类竞争的基因表达式编程新算法[J].四川大学学报:自然科学版,2010,47(3):530-536.

[17]

李太勇,唐昌杰,吴江,等.基因表达式编程种群多样性自适应调控算法[J].电子科技大学学报,2010,39(2):279-283.