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

　　摘要:分析了基因表达式编程(GEP)算法的性能关键，指出提升的一个重要瓶颈是在个体评估阶段；结合多核CPU并行计算能力，提出了基于多线程评估的GEP算法(MTEGEP)，并通过实验验证了MTEGEP的高效性：在双核CPU环境下MTEGEP运算速度是传统GEP的1.89倍，而在8核CPU环境下达到了6.48倍。实验结果表明该算法能有效提升GEP算法的性能。
　　关键词:数据挖掘；基因表达式编程；多线程；多核CPU；评估
　　中图分类号: TP311 文献标志码:A
　　�
　　Gene expression programming algorithm based on multi.threading evaluator
　　�
　　NI Sheng.qiao���*�, TANG Chang.jie, YANG Ning, ZUO Jie
　　
　　College of Computer Science, Sichuan University, Chengdu Sichuan 610064, China
　　Abstract:
　　Combines the advantage of Multi.core CPU and Multi.Threading technology, introduces a new Gene Expression Programming （GEP） algorithm with Multi.Threading Evaluator which greatly improves the efficiency of the GEP algorithm. The experimental results demonstrate that the new proposed algorithm MTEGEP is more efficiency than traditional GEP. Furthermore，comparing to the traditional GEP，MTEGEP achieves 1.89 times faster speed in average with a dual.core CPU, and 6.48 times faster speed with an eight.core CPU.
　　
　　Combining the advantages of multi.core CPU and multi.threading technology, a new Gene Expression Programming （GEP） algorithm with multi.threading evaluator was introduced, which greatly improved the efficiency of the GEP algorithm. The experimental results demonstrate that the new proposed algorithm MTEGEP is more efficient than traditional GEP. Furthermore，compared to the traditional GEP，MTEGEP achieves 1.89 times faster speed in average with a dual.core CPU, and 6.48 times faster speed with an eight.core CPU.
　　
　　�Key words:
　　data mining; Gene Expression Programming (GEP); multi.threading; multi.core CPU; evaluator
　　�
　　
　　0 引言�
　　从海量信息中挖掘有效知识是数据库技术研究的重要课题。进化计算作为数据挖掘的一类重要方法，有着广泛的应用，是当前的研究热点。基因表达式编程(Gene Expression Programming，GEP)算法是进化算法家族中的新兴技术，它综合了遗传算法(Genetic Algorithm,GA)和遗传编程(Genetic Programming,GP)的优点，具有更强的解决问题的能力，其最大特点是优化的基因序列表示结构，它消除了传统遗传算法在进化过程可能产生无效基因的缺陷，是效率较为理想的数据挖掘方法��［1］�。特别在函数挖掘方面，涌现出了许多新的GEP研究和应用成果，参见文献［2-10］。与此同时，众多学者在传统GEP算法基础上，针对不同应用提出了效率更高、适应性更强的改进算法。文献［11］提出了基于搜索空间划分和Sharing函数的粒子群优化算法；文献［12］对传统GEP的评估算法进行研究，提出了具有线性复杂度的GEP适应度评价算法；文献［13］研究了基于基因表达式编程的多目标优化算法;此外文献［14-17］分别针对不同领域提出了改进的GEP新算法。�
　　目前关于基因表达式编程的研究主要集中在对GEP理论分析和算法优化和改进，尚未见到利用高性能硬件资源来提高GEP性能的研究。在实践中，作者发现目前的GEP算法没有充分发挥计算机硬件的性能，算法效率不尽如人意。例如：在种群规模较大、进化代数较多、训练数据规模较大的情
　　
　　
　　况下，从开始运行GEP程序到得出结果，往往需要等上几分钟、十几分甚至是几十分钟的时间。本文旨在利用当前中央处理器(Central Processing Unit，CPU)加速GEP进化过程，大幅提升GEP算法性能，即在用硬件加速进化计算方面作有益的探索。�
　　1 基因表达式编程�
　　GEP是Candida Ferreira在研究GA和GP的基础上，发展出的新概念。传统的GEP算法见图1。在整个GEP的流程中，创建初始种群的染色体是一个随机生成染色体字符串的过程，而选择则是根据各个染色体的适应度，使用一定的选择算子，如轮盘赌选择算子、锦标赛选择算子等进行选择，保证适应度高的个体有更高的选中概率。整个过程周而复始，直到达到一定的结束条件：找到最优解、达到一定代数、适应度达到某个值或者运行时间达到预设时间等。�
　　GEP与GA 、GP最本质的区别是：在GA中个体由固定长度的线性串(染色体)来表示；在GP中个体则是由不同大小和形状的非线性实体(解析树)所表示的；而GEP将个体先编码为固定长度的线性串，再表示成大小、形状都不同的非线性实体。这样，GEP就克服了GA损失功能复杂性的可能性和GP难以再产生新的变化的可能性。GEP的创始人Candida研究证实：GEP在解决复杂问题的时候，比传统的遗传编程方法效率高出2～4个数量级。�
　　
　　2 GEP性能提升新思路�
　　尽管GEP比GP快了2～4个数量级，但随着数据规模的增大和运行次数的递增，GEP程序的运行速度还不尽如人意。实践中，为了追求效果，常需提高种群规模和测试数据规模，在海量数据条件下，运行一次GEP程序需要几分钟到几十分钟。为解决这一问题，本文提出了挖掘硬件潜力来提升GEP性能的新思路。�2.1 GEP运行时间的测试标准及分析方法�
　　为找出GEP算法运算中影响速度的关键因素：把GEP算法分成以下几个阶段。�
　　1)种群初始化阶段:随机产生初始种群。�
　　2)个体评估阶段:包括对个体的解析(生成表达式)，对个体适应度的评估(表达式的运算)。�
　　3)个体选择阶段:选择最优的个体并保留。�
　　4)个体进化阶段:对保留的个体通过遗传算子进行进化，产生新的种群。�
　　
　　定义1
　　设�n�是GEP进化代数，�r是种群初始化需要的时间，e�i、c�i、g�i，i∈［0,n］分别是第i代进化过程中个体评估阶段、个体选择阶段和个体进化阶段所占用的时间，T�是GEP算法进化�n代需要的总时间，那么容易得到：�
　　T=r+∑ni=0(e�i+c�i+g�i)�
　　
　　设种群规模是m，测试数据规模是k，根据定义1考察分析如下。�
　　1)种群初始化阶段在整个算法过程中只运行一次，它负责随机产生m个体，运算时间有限，即r的取值确定且很小。�
　　2)由于初始化阶段消耗时间有限，又每代个体评估、选择、进化的时间是比较稳定的，即e�i+c�i+g�i�的值是稳定的，所以可以预计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.2 GEP算法改进策略�
　　由上分析，改进评估算法，减少评估时间，能提升GEP整体性能。考虑到GEP中个体的评估是相互独立的，本文把多线程技术引入GEP的评估阶段，提出了基于多线程评估的GEP(GEP with Multi.Threading Evaluator，MTEGEP)算法，并进行了详实的实验验证。�
　　3 MTEGEP算法设计与实现�
　　3.1 传统GEP适应度评估算法�
　　传统GEP算法采用单线程评估策略，未能充分发挥CPU的多线程并行处理能力，也未尝试过在多核CPU上进行评估工作，限制了GEP算法的性能。传统算法，对所有个体采用单线程技术逐个评估，算法描述如下。�
　　
　　分析算法1，容易得到：传统GEP适应度评估算法中，需要逐个对所有个体进行独立的解码和计算(对应算法1的第3）～8）行)。所以如果将算法1的3）～8）行设计成多线程并行运算，必定能大幅提高GEP评估效率，从而提升GEP整体性能。�
　　3.2 MTEGEP算法的评估线程数量选择�
　　确定了评估策略，还要确定评估线程的数量。为了平衡各评估线程的运算任务，尽量把种群个体均匀地分配给每个评估线程。假定种群规模为�SIZE，线程个数为N，�体分配算法思想如下。�
　　1)记每个线程分配个体的是平均数目为��AverageNumber=��SIZE/N」(向下取整)。��
　　2)如果�HeavyNumber=SIZE%N�不为0，即�SIZE不能被N整除，�那么前�HeavyNumber�个评估线程多增加1个个体评估任务。�
　　3)考虑到GEP算法设计中，种群的个体是线性存储的(一维数组的形式存储)，我们只要记录每个评估线程负责的第1个个体位置和负责的个体数量就可以确定具体分组情况。�
　　为了对分组个体进行相互独立的适应度评估，作者设计了专门的分组评估器EThread，它只对负责的分组个体进行评估。评估器EThread的评估算法描述如下。�
　　
　　4 实验结果与分析�
　　4.1 实验说明�
　　本文所有实验都是通过GEP进行函数挖掘来测试运行时间。�
　　1) 选择来自参考文献［1］的拟合函数 �F1：�
　　10+�sin��(�1x�)�(x－0.16)�2+0.1； 0

推荐访问:表达式 多线程 算法 基因