深度广度联合解码的基因表达式程序设计.pdf

C N4 31 2 5 8 T P 计算机工程与科学 第3 6 卷第1 0 期2 0 1 4 年1 0 月 I S S N1 0 0 71 3 0 X C o m p u t e rE n g i n e e r i n g & S c i e n c e V o l 3 6 ，N o 1 0 ，O c t 2 0 1 4 文章编号：1 0 0 71 3 0 X ( 2 0 1 4 ) 1 01 9 6 60 6 深度广度联合解码的基因表达式程序设计。 张建明，唐勇，周书仁，吴宏林 ( 长沙理工大学计算机与通信工程学院，湖南长沙4 1 0 1 1 4 ) 摘要：基因表达式程序设计( G E P ) 在时间序列分析、分类、自动程序设计、多目标优化、海量数据分 析等领域中有着广泛的应用。在G E P 解码过程中，将深度优先和广度优先技术的优点相结合，提出了基 于深度广度联合解码的G E P 算法，从而既能适量地增加种群中个体的多样性，又能适当地保留较优的子 树信息( s u bE T ) 。实验表明，相比标准G E P 算法，新算法在进化时间增加不多的情况下提高了平均适应 度，获得了更高的成功率。 关键词：深度；广度；解码；基因表达式程序设计；符号回归 中图分类号：T P 3 1 1 文献标志码：A d o i ：1 0 3 9 6 9 j i s s n 1 0 0 71 3 0 X 2 0 1 4 1 0 0 2 0 G e n ee x p r e s s i o np r o g r a m m i n gc o m b i n i n g d e p t h - - f i r s ta n db r e a d t h _ _ f i r s td e c o d i n gp r i n c i p l e s Z H A N GJ i a nr u i n g T A N GY o n g 。Z H O US h u r e n ，W UH o n gl i n ( S c h o o lo fC o m p u t e ra n dC o m m u n i c a t i o nE n g i n e e r i n g ，C h a n g s h aU n i v e r s i t yo fS c i e n c ea n dT e c h n o l o g y ，C h a n g s h a4 1 0 1 1 4 ) A b s t r a c t ：G e n eE x p r e s s i o nP r o g r a m m i n g ( G E P ) i sa na u t o m a t i cp r o g r a m m i n ga p p r o a c hw i d e l yu s e d n 1n l a n ya r e a s ! s u c ha St i m es e r i e sa n a l y s i s ! c l a s s i f i c a t i o n ! m u l t io b j e c t i v eo p t i m i z a t i o na n d m a s s J v ed a t aa n a l y s i s An e wG E Pa l g o r i t h mi sp r o p o s e db yc o m b i n i n gt h ea d v a n t a g e so ft h ed e p t h f i r s ta n db r e a d t h f i r s tt e c h n o l o g i e si nt h eG E Pd e c o d i n gp r o c e s s T h en e wa l g o r i t h mc a ni n c r e a s et h ed i v e r s i t yo fi n d i v i d u a l sa n dp r o p e r l yp r e s e r v eb e t t e rs u b E T s T h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ，c o m p a r e dw i t ht h es t a n d a r dG E Pa l g o r i t h m ，t h en e wa l g o r i t h mc a ni m p r o v et h em e a nf i t n e s sw i t h o u ti n c r e a s i n gt o om u c he v o l u t i o n a r yt i m e ，t h u sa c h i e v i n gah i g h e rs u c c e s sr a t e K e yw o r d s ：d e p t h ；b r e a d t h ；d e c o d i n g ；G E P ；s y m b o l i cr e g r e s s i o n 引言 基因表达式程序设计G E P ( G e n eE x p r e s s i o n P r o g r a m m i n g ) 起源于遗传程序设计G P ( G e n e t i c P r o g r a m m i n g ) ，是由F e r r e i r aC 1 ，2 1 在2 0 0 1 年提出 的一种自适应演化算法，在机器学习和知识发现方 面具有强大的进化能力。可以通过使用线性定长 的染色体来表示不同形状和尺寸的表达式树E T ( E x p r e s s i o nT r e e ) 。与传统的遗传程序设计相 比，基因型和表现型的分开使得G E P 更加灵活以 及具有搜索整个解空问的能力。由于G E P 的这种 优良特性，在符号回归、最优化、时问序列分析、分 类、多目标优化等领域取得了较好的应用效果。 文献r 1 ，2 主要介绍基因表达式程序设计的基 本概念及理论，为进一步地研究算法本身和其应用 方面奠定了基础。文献 3 提出基于深度优先的多 基因表达式程序设计，使单个染色体能够同时表示 多个解，显著地改善G E P 性能。文献 4 证明 G E P 的相关收敛定理及推广的应用，为G E P 理论 鉴霎是智；笞篆召簧撵f 攀星星饕盂磊占：8 。6 1 2 0 2 0 2 4 3 9 ) ；湖南省教育厅优秀青年资助项目( 1 2 8 0 0 3 ) ；湖南省交通厅科技计划资助项目基金项目：国家自然科学基金资助项目() ；湖南省教育厅优秀青年资助项目( 1 j ；湖南锱父遍厅科技计划贫助工贝目 ( 2 0 1 3 3 4 ) 通信地拦：41。114湖南省长沙市长沙理工态a学tio计n算E机ngAddressS c h 0 0 1o fC o m p u t e ra n d ( J O n T t n T t n nc a t i o nE n g 与i n e 通e r 信i n g j U 磐h 学a n 院g s ，h a U n l v e r s l t Yo l 3 c l e n c ea n o 、T e c ，n n 。1 。g Y ，c h 。g s h 。4 1 0 1 1 4 1， 1u l u ，L n a I l 苎s I l a4 u 1 4 H u n a n ，P R C h i n a 万方数据 张建明等：深度广度联合解码的基因表达式程序设计 1 9 6 7 打下坚实基础。文献 5 将权值引入到G E P 的初 始种群中，使种群的多样性得到提高，更快得到最 优解，但需事先设定基因中各符号概率。文献 6 将混沌重组、灾变算子和差分突变搜索运用到 G E P 中，用以提高算法的收敛速度，从而避免不成 熟收敛。文献 7 利用G E P 来估计高性能混凝土 的抗压强度，其效果比一般的回归模型要好。动态 多目标优化是较热的研究课题，具有较好的应用前 景，文献E s I 利用G E P 强大的搜索解空问能力将其 运用到动态多目标优化，该算法能较快收敛，提高 算法进化效率。文献 9 提出D G G E P 算法，减少 G E P 在演化过程中的停滞代数，使得群体的平均 适应度提高。 从G E P 研究现状来说，G E P 应用范围广，涉 及多个领域，但影响G E P 性能的因素有很多，如适 应度函数、个体表示、遗传算子等口。G E P 应用层 面简单，利于自动化程序设计的发展，但是在设计 和实现时仍存在较大难题：G E P 的基因型和表现 型是由两种不同的表示形式所表示，因此必须正确 处理好基因型和表现型的相互转换。纵观现有 G E P 的解码方法，采用广度技术实现相关转换。 不难看出，G E P 的转换规则一直未受关注。本文 在标准G E P 算法基础上开展基于深度广度联合解 码的基因表达式程序设计D B G E P ( D e p t hf i r s ta n d B r e a d t hf i r s tG e n eE x p r e s s i o nP r o g r a m m i n g ) 的新 型G P 的探究工作。通过改变G E P 的转换规则而 得。与标准G E P 算法相比，该算法在进化过程中 更易得到问题的最优解。 2 基因表达式程序设计 2 1 标准G E P 算法流程 G E P 算法主要分为五个步骤： 步骤1 设置交叉率、变异率、基因头部长度 等参数，初始化种群。 步骤2 根据种群中个体得到的表现型，经适 应度函数计算出个体的适应值，从而评估个体。如 符合终止条件转步骤5 ，否则继续执行。 步骤3 遗传操作产生下一代。 步骤3 1 保留最好个体。 步骤3 2 进行各类遗传操作。 步骤4 转步骤2 。 步骤5 把适应度值最好的个体作为问题的 解。 在G E P 的流程中，初始种群是由特定数目的 线性定长染色体所构成，该染色体都是随机生成 的，然后染色体通过转换机制转化成表达式树，通 过适应度函数。对个体适应度进行求解并评估个 体。对新产生的种群进行各种遗传操作( 选择、交 叉、变异和基因翻转等) 。相同的进化过程将不会 停止，直到达到一定的终止条件。选择是基于个体 的适应度，由带有精英的轮盘赌算子来决定，确保 当前最优个体能被保留下来并参与下一代种群的 操作。 本文第3 节提出的深度广度联合解码的基因 表达式程序设计( D B G E P ) 是在标准G E P 基础上 改进的，算法流程与标准G E P 相同，同样包括五 个步骤。二者的区别在于步骤2 中的转换规则，即 标准G E P 算法采用广度进行解码，改进算法采用 深度广度技术联合解码，在原有基础上能够保留较 优的子树结构信息。改进算法同样具有个体、种 群、遗传算子和适应度函数等概念。 2 2 G E P 的基本结构和编码规则 在G E P 中，基因由两部分构成：头部和尾部。 头部可随机选择函数符和终结符中的符号来表示， 尾部只能随机选择终结符的符号来表示。头部的 长度h 由所要解决的问题决定，而尾部长度则需 计算得到。 一h * ( 咒1 ) + 1( 1 ) 其中咒表示函数集中所需变量数最多的函数的参 数个数( 也称为最大操作数) 。这些编码后的基因 称为K 表达式。文献 1 1 证明在此条件的约束 下，遗传操作总能产生有效基因，不会产生非法个 体，不需对个体进行额外的有效性判断，提高算法 的演化性能。 染色体( 基因) 承载遗传信息，直接参与遗传操 作，总能产生有效染色体，不会产生非法个体。表 达式树作为遗传信息的表示形式，由函数符和终结 符组成树形结构表示，最终由算术表达式表示。表 达式树与染色体可通过编码和解码规则直接进行 转化，使遗传操作简单、进化结果直观快速。 2 3 适应度函数与选择 通过