《基于多线程评估的基因表达式编程算法电子版本.doc》由会员分享，可在线阅读，更多相关《基于多线程评估的基因表达式编程算法电子版本.doc（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Good is good, but better carries it.精益求精，善益求善。基于多线程评估的基因表达式编程算法-基于多线程评估的基因表达式编程算法摘要:分析了基因表达式编程(gep)算法的性能关键，指出提升的一个重要瓶颈是在个体评估阶段；结合多核cpu并行计算能力，提出了基于多线程评估的gep算法(mtegep)，并通过实验验证了mtegep的高效性：在双核cpu环境下mtegep运算速度是传统gep的1.89倍，而在8核cpu环境下达到了6.48倍。实验结果表明该算法能有效提升gep算法的性能。关键词:数据挖掘；基因表达式编程；多线程；多核cpu；评估geneexpressi
2、onprogrammingalgorithmbasedonmulti.threadingevaluatornisheng.qiao*,tangchang.jie,yangning,zuojiecollegeofcomputerscience,sichuanuniversity,chengdusichuan610064,chinaabstract:combinestheadvantageofmulti.corecpuandmulti.threadingtechnology,introducesanewgeneexpressionprogramming（gep）algorithmwithmulti
3、.threadingevaluatorwhichgreatlyimprovestheefficiencyofthegepalgorithm.theexperimentalresultsdemonstratethatthenewproposedalgorithmmtegepismoreefficiencythantraditionalgep.furthermore，comparingtothetraditionalgep，mtegepachieves1.89timesfasterspeedinaveragewithadual.corecpu,biningtheadvantagesofmulti.
4、corecpuandmulti.threadingtechnology,anewgeneexpressionprogramming（gep）algorithmwithmulti.threadingevaluatorwasintroduced,whichgreatlyimprovedtheefficiencyofthegepalgorithm.theexperimentalresultsdemonstratethatthenewproposedalgorithmmtegepismoreefficientthantraditionalgep.furthermore，comparedtothetra
5、ditionalgep，mtegepachieves1.89timesfasterspeedinaveragewithadual.corecpu,and6.48timesfasterspeedwithaneight.corecpu.keywords:datamining;geneexpressionprogramming(gep);multi.threading;multi.corecpu;evaluator0引言从海量信息中挖掘有效知识是数据库技术研究的重要课题。进化计算作为数据挖掘的一类重要方法，有着广泛的应用，是当前的研究热点。基因表达式编程(geneexpressionprogramm
6、ing，gep)算法是进化算法家族中的新兴技术，它综合了遗传算法(geneticalgorithm,ga)和遗传编程(geneticprogramming,gp)的优点，具有更强的解决问题的能力，其最大特点是优化的基因序列表示结构，它消除了传统遗传算法在进化过程可能产生无效基因的缺陷，是效率较为理想的数据挖掘方法1。特别在函数挖掘方面，涌现出了许多新的gep研究和应用成果，参见文献2-10。与此同时，众多学者在传统gep算法基础上，针对不同应用提出了效率更高、适应性更强的改进算法。文献11提出了基于搜索空间划分和sharing函数的粒子群优化算法；文献12对传统gep的评估算法进行研究，提出了
7、具有线性复杂度的gep适应度评价算法；文献13研究了基于基因表达式编程的多目标优化算法;此外文献14-17分别针对不同领域提出了改进的gep新算法。目前关于基因表达式编程的研究主要集中在对gep理论分析和算法优化和改进，尚未见到利用高性能硬件资源来提高gep性能的研究。在实践中，作者发现目前的gep算法没有充分发挥计算机硬件的性能，算法效率不尽如人意。例如：在种群规模较大、进化代数较多、训练数据规模较大的情况下，从开始运行gep程序到得出结果，往往需要等上几分钟、十几分甚至是几十分钟的时间。本文旨在利用当前中央处理器(centralprocessingunit，cpu)加速gep进化过程，大幅
8、提升gep算法性能，即在用硬件加速进化计算方面作有益的探索。1基因表达式编程gep是candidaferreira在研究ga和gp的基础上，发展出的新概念。传统的gep算法见图1。在整个gep的流程中，创建初始种群的染色体是一个随机生成染色体字符串的过程，而选择则是根据各个染色体的适应度，使用一定的选择算子，如轮盘赌选择算子、锦标赛选择算子等进行选择，保证适应度高的个体有更高的选中概率。整个过程周而复始，直到达到一定的结束条件：找到最优解、达到一定代数、适应度达到某个值或者运行时间达到预设时间等。gep与ga、gp最本质的区别是：在ga中个体由固定长度的线性串(染色体)来表示；在gp中个体则是
9、由不同大小和形状的非线性实体(解析树)所表示的；而gep将个体先编码为固定长度的线性串，再表示成大小、形状都不同的非线性实体。这样，gep就克服了ga损失功能复杂性的可能性和gp难以再产生新的变化的可能性。gep的创始人candida研究证实：gep在解决复杂问题的时候，比传统的遗传编程方法效率高出24个数量级。2gep性能提升新思路尽管gep比gp快了24个数量级，但随着数据规模的增大和运行次数的递增，gep程序的运行速度还不尽如人意。实践中，为了追求效果，常需提高种群规模和测试数据规模，在海量数据条件下，运行一次gep程序需要几分钟到几十分钟。为解决这一问题，本文提出了挖掘硬件潜力来提升g
10、ep性能的新思路。2.1gep运行时间的测试标准及分析方法为找出gep算法运算中影响速度的关键因素：把gep算法分成以下几个阶段。1)种群初始化阶段:随机产生初始种群。2)个体评估阶段:包括对个体的解析(生成表达式)，对个体适应度的评估(表达式的运算)。3)个体选择阶段:选择最优的个体并保留。4)个体进化阶段:对保留的个体通过遗传算子进行进化，产生新的种群。定义1设n是gep进化代数，r是种群初始化需要的时间，ei、ci、gi，i0,n分别是第i代进化过程中个体评估阶段、个体选择阶段和个体进化阶段所占用的时间，t是gep算法进化n代需要的总时间，那么容易得到：t=r+ni=0(ei+ci+gi
11、)设种群规模是m，测试数据规模是k，根据定义1考察分析如下。1)种群初始化阶段在整个算法过程中只运行一次，它负责随机产生m个体，运算时间有限，即r的取值确定且很小。2)由于初始化阶段消耗时间有限，又每代个体评估、选择、进化的时间是比较稳定的，即ei+ci+gi的值是稳定的，所以可以预计gep的运行时间与进化的代数n呈线性增长。3)种群每进化一代，都需要对m个体分别进行k次评估运算，共计mk次运算。假设单个个体进行一次评估运算的平均时间是p(在函数挖掘中，可以看作是一个算数表达式的解析和计算时间是p)，那么种群进化一代所需要的评估时间是mkp，也就是说评估阶段的时间消耗主要取决于种群规模、测试数
12、据规模以及单个个体进行一次评估的平均时间。4)在个体选择和进化阶段，由于都是采用了固定的极有限的几个操作步骤(主要是对个体适应度进行比较，找出适应度最大的个体，进行保留和进化)，消耗的时间是很有限的，当种群进化一代的评估时间mkp较大(mkp的值远远大于选择和进化时间)的时候，个体选择和进化操作的时间可以忽略。上述分析表明，gep的运行时间瓶颈是评估阶段，gep运行的总时间t近似于nmkp，即gep算法的时间复杂度是o(nmkp)。2.2gep算法改进策略由上分析，改进评估算法，减少评估时间，能提升gep整体性能。考虑到gep中个体的评估是相互独立的，本文把多线程技术引入gep的评估阶段，提出
13、了基于多线程评估的gep(gepwithmulti.threadingevaluator，mtegep)算法，并进行了详实的实验验证。3mtegep算法设计与实现3.1传统gep适应度评估算法传统gep算法采用单线程评估策略，未能充分发挥cpu的多线程并行处理能力，也未尝试过在多核cpu上进行评估工作，限制了gep算法的性能。传统算法，对所有个体采用单线程技术逐个评估，算法描述如下。分析算法1，容易得到：传统gep适应度评估算法中，需要逐个对所有个体进行独立的解码和计算(对应算法1的第3）8）行)。所以如果将算法1的3）8）行设计成多线程并行运算，必定能大幅提高gep评估效率，从而提升gep整
14、体性能。3.2mtegep算法的评估线程数量选择确定了评估策略，还要确定评估线程的数量。为了平衡各评估线程的运算任务，尽量把种群个体均匀地分配给每个评估线程。假定种群规模为size，线程个数为n，体分配算法思想如下。1)记每个线程分配个体的是平均数目为averagenumber=size/n(向下取整)。2)如果heavynumber=size%n不为0，即size不能被n整除，那么前heavynumber个评估线程多增加1个个体评估任务。3)考虑到gep算法设计中，种群的个体是线性存储的(一维数组的形式存储)，我们只要记录每个评估线程负责的第1个个体位置和负责的个体数量就可以确定具体分组情况
15、。为了对分组个体进行相互独立的适应度评估，作者设计了专门的分组评估器ethread，它只对负责的分组个体进行评估。评估器ethread的评估算法描述如下。4实验结果与分析4.1实验说明本文所有实验都是通过gep进行函数挖掘来测试运行时间。1)选择来自参考文献1的拟合函数f1：10+sin(1x)(x0.16)2+0.1；0x12)f1随机生成的测试数据作为进化环境。3)实验参数见表1。4)相同参数的实验重复做10次，取运行时间的平均值。测试数据规模单位是组，运行时间单位是秒。5)考虑到进化代数、种群规模和测试数据规模对gep算法的性能影响是等效的(都是线性的)。所以这里选择固定进化代数和种群规
16、模，而改变数据规模的情况下进行实验来观察，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算法不能较传统
17、gep算法提升8倍的速度，但是其最佳的提升速度接近8倍。5)不难推断在n核cpu环境下能够得到与8核cpu的性能提升的相同情况,所以mtegep算法是一个高效、实用的算法。参考文献:1ferreirac.geneexpressionprogramming:mathematicalmodelingbyanartificialintelligencem.2nded.newyork:springerpress,2006.2陈建明，陈宇，李志蜀，等.基于gep的路径覆盖测试用例生成方法j.计算机工程，2010，36(15):86-88.3唐常杰,陈瑜,张欢,等.基于转基因gep的公式发现j.计算机应用
18、,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黄立昕，董悦坤.基于因子分析和基因表达式
19、编程的电流互感器故障诊断j.电力科学与工程，2011,27(10):26-30,569何家莉，王培.基因表达式中含有等式约束的处理方法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.四川大学学报：工
20、程科学版，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.-