计算机论文：深度优先的多基因表达式程序设计

    摘 要 基因表达式程序设计( GEP) 是应用十分广泛的自动程序设计方法． 就解码方法而言，它主要依据广度优先原则来实施从个体表示到表达式的转换． 这代表基因片段的含义会因环境的变化而变化． 为此，现有 GEP 对个体的评估缺乏并发支持能力． 本文从理论与实验两个方面证实: 深度优先原则及个体多解技术，即让单个染色体编码多个解的技术，既可解决以上 GEP 困境也可显着改善其性能．
    关键词 演化计算，遗传程序设计，基因表达式程序设计，多表达式程序设计，符号回归
    1 引 言自动程序设计一直是计算机科学的中心议题之一，求解十分困难． Stanford 大学的 Koza在该领域有过开创性的工作，曾成功地提出面向 LISP 语言的启发式程序生成方法． 这一方法因以 Holland 的遗传算法( Genetic Algorithm，GA)为基础，所以又被叫做遗传程序设计( Genetic Programming，GP) ．时至今日 GP 的面世已逾 20 年，应用早已不再局限于 LISP 意义上的探讨． 如果说不同语言程序的生成是 GP 的传统应用，那么将之逐步改造、完善以致成为应对多目标优化、金融预测、海量数据分析、信息安全、软件危机等复杂问题的高效利器的研究也十分普遍．GP 家族包括: 基因表达式程序设计 ( GeneExpression Programming，GEP) 、多表达式程序设计( Multi Expression Programming，MEP) 、文法演化( Grammatical Evolution，GE) 、线性遗传程序设计( Linear Genetic Programming，LGP) 、笛卡尔遗传程序设计( Cartesian Genetic Programming，CGP) 、栈式遗传程序设计( Stack Based Genetic Programming，SB-GP) 、强类型遗传程序设计 ( Strongly Typed GeneticProgramming，STGP ) 、霍尔语义型遗传程序设计( Hoare Logic-Based Genetic Programming，HGP) 以及模 型 式 遗 传 程 序 设 计 ( Model-Based GeneticProgramming，MGE) 等众多变体． 从个体表示角度看，它们主要分为两类，各自沿着树形与线性基因型两个不同的表示方向发展．表示、算子、评估等都是相互制约、高度影响 GP性能的公开性难题． 线性 GP 如 GEP、MEP 等虽然应用层面简洁，但对设计和实现而言，依然存在较大难度，即必须解决好基因型到表现性型的转换问题． 综观现有解码方法，GEP 采用广度优先建树法则实现有关转换，MEP 则据引用关系自下而上，实际最终效果或进化辈数过大，或基因多样性有限，或理论上难以支持高效的分布并行评估过程． 本文工作包括: 1) 融合 GEP、MEP 各自的优势，提出一种新颖的线性遗传程序设计方法 MGEP( 多基因表达式程序设计) ，并继而在理论、实验证实深度优先转换更利于高效解码和评估这一事实上倡议将深度优先作为现行 GEP 解码机制的强有力的替代者; 2) 借鉴MEP 多基因评估原理与思想，对 GEP 的基因选择性给予适当支持来有效提高精准性和成功率． 这一方法不仅综合体现 GEP、MEP 的优势特色，而且可为解决 GEP 分布评估、重用等复杂度高的问题开辟新的途径．
       2 背景与动机多基因表达式程序设计( Multi-Gene ExpressionProgramming，MGEP) 隶属线性遗传程序设计，并与GEP、MEP 等自动程序设计方法及遗传算法有密切关系． 本节拟先对其成因与背景做一简要交待．GEP、MEP 分别由 Ferreira和 Oltean 等提出． 它们是 GA 的具体应用，继承了个体( 染色体) 、种群、遗传算子、评估等概念． 当对这些环节施以不同的处理方式即得 GP 的各式变体． 为方便 GA搜索，把个体分为基因型与表现型两层概念，这样评估就依赖一个负责将基因型转化为表现型的转换而实现．GEP、MEP 算法包括 5 个步骤:step 1 随机产生一个关于个体的初始种群( 俗称初始化) ;step 2 针对种群个体，在转换获得的表现型基础上计算适应值、评估个体: 若满足终止条件则转step 5，否则继续执行 step 3;step 3 用遗传算子产生新个体及种群;step 4 转 step 2 执行;step 5 结束演化过程，取适应值最好的个体所对应的表现型为问题的近似解．两种方法的细微区别在于个体的表示及 step 2涉及的转换和评估机制． 如，为保证由基因型能正确解码并获得有意义的表达式，GEP 对个体结构有关于头部、尾部及长短规格方面的特殊要求( 参见后续讨论) ; 而 MEP 则以不影响引用关系的计算为原则来约束、刻画个体的生成． 示意 GEP 与 MEP的表示及转换原理． 特别是，MEP 以在一个染色体内同时编码多个表达式来备选问题最佳解的做法是其十分显着的特点．以上方法已在符号回归、分类、软件工程、电路设计、生物制药、信息安全等诸多领域得到广泛应用． 文献［着重探讨函数挖掘与数学建模问题． 在文献中，作者探讨 GEP 在分类问题中的应用，文献则从算子角度对 GEP8 20模式识别与人工智能 26 卷予以改进，以期加快收敛速度和提高精度． 除此之外，鉴于物种的多样性和基因的多样性是群体进化及遗传算法能搜索到全局最优解的重要保障，研究者还就 GEP 的性能改善问题开展深入讨论． 文献提出 DG-GEP 算法，减少 GEP 在演化过程中的停滞代数，使得群体的平均适应度提高． 文献改进 GEP 产生初始种群的算法，增加初始群体基因的多样性，从而提高演化效率． 这些研究都在不同程度上增加 GEP 演化过程中种群的多样性，提高它们的函数挖掘能力．GEP 等线性 GP 虽说有广泛的应用、研究基础，但其缺点也同样明现，值得进一步去留意和解决． 从上述工作不难发现，GEP 的转换规则、解的意义界定问题几乎一直未受关注． 事实上，广度优先法则很不利于重用、分布处理意义上的高效评估． 文献通过多种 GP 技术证实: 单个染色体若能编码多个解则可显着改善演化搜索性能． 文章同时指出，可变长染色体有利于保存不同复杂程度的解，而多解技术正是 MEP 借助固定长度染色体实现这一可变性功效的关键所在．本文拟在 GEP 算法基础上开展一种叫做多基因表达式程序设计( MGEP) 的新型 GP 探究工作．该工作通过改变 GEP 的转换和吸纳 MEP 关于多解评估技术的思想而得． MGEP 中的"多基因"即源于后者． 实验表明，在个体表示保持不变的前提下，深度 MGEP 的进化辈数、精度、成功率等性能指标值均获得显着改善．
      3 多基因表达式程序设计原理MGEP 作为线性遗传程序设计同样包括 GEP的 5 个步骤．改变 GEP 的转换原则及解的界定方式( 引入 MEP 的多解评估思想) ，即可得新型 GP． 这样，将广度优先和深度优先建树、解码策略分别与 MEP 的多解评估思想予以组合，便得以下广度优先 MGEP 和深度优先 MGEP ( 分别记作MGEP-Breadth，MGEP-Depth) ． 实验证实: MGEP 因多解评估技术的引入而使得演化性能得到显着改善． 而理论结论则表明: 深度优先解码法能为 GEP的重用、高效的分布评估赋予更多期待．
      3． 1 表示与解码3． 1． 1 个体表示MGEP 的个体表示与 GEP 类似，除限于单基因考量外，都由头部和尾部组成． 当依据具体问题将头部的长度设为 h时，尾长则由公示h* ( n － 1) + 1确定． 这里 n 表示函数集中所需参数最多的函数的目数． 因此在给定函数集 F = { +，* ，/，S} ( S 代表 sin函数) ，终端集 T = { a，b} 及头长 h = 7 时，MGEP 的个体 或 染 色 体 C 可 用 正 规 式 刻 画 为( F ∪ T)h·Th* ( n －1) +1． 为方便理解，以下将用 C1= + / * aSb +bbababab 作为染色体进行解释和说明．
       3． 1． 2 解码方法解码是指由个体表示到表达式的转换过程，主要包括表达式树( ET 树) 的构建及中序遍历两个环节． 原则上 ET 树的构建既可依广度优先，也可依深度优先原则进行，现行 GEP 是依前者解码的．前小节个体 C1在两种原则下所对应的ET树． 大体说，广度优先建树思路是从根开始，仅当 i 层上的所有节点依次创建完毕才按层次递增方式生成树的下一层有关节点． 深度优先建树思路是，优先纵深方向节点的创建，即由左向右一枝一枝地完成树的有关构造． MGEP 采用多解技术，解码时分别使用深度优先和广度优先建树原则． 有关解码的详细形式描述参见第 5 节．广度 MGEP 解码步骤如下．step 1 从头部的第一个符号开始扫描 K 表达式，并按广度优先算法建立一棵完整的 ET 树． 如以基因 C1为例经此步得图 1 的第一个子图;表 1 GEP 与 MEP 的比较Table 1 Comparison of GEP and MEPGEP MEP个体长度为 17( 用例)头长为 8，尾长为 9+ * ba / c － baacbbcbab长度为 6( 用例)1 2 3 4 5 6a b * 1，2 － 2，3 c / 4，1表现型 a* ( c/( b － a) ) + b a b a* b b － ( a* b) c ( b － ( a* b) ) /a转换原则 广度优先据引用关系( 基因中做参数使用的下标值必须小于当前下标值) 自下而上构造抽象语法树和表达式问题的解 a* ( c/( b － a) ) + b 据目标要求评估 6 个表现型，并取其中最好者作为问题的 深度优先的多基因表达式程序设计821step 2 判断基因头部的第二个位置是否为函数符，若为函数符则从基因的第二位置即对 C2=/ * aSb + bbababab 继续扫描，同样按广度优先算法建树，否则该基因为死基因不建立表达式树． 以此类推分解出所有有效基因:
　　C3= * aSb + bbababab，C4= Sb + bbababab，C5= + bbababab;step 3 遍历所有有效基因对应的的表达式树，便得图 1 诸表达式．深度 MGEP 解码步骤与广度 MGEP 类似，仅需将后者的广度建树原则替换为深度优先原则即可．算法建树所面临的有效基因为C1= + / * aSb + bbababab，C2= / * aSb + bbababab，C3= * aSb + bbababab， C4= Sb + bbababab，C5= + bbababab．它们对应的表达式．C1的广度优先解码结果Fig． 1 Decoding results of C1by breadth-first principle C1的深度优先解码结果Fig． 2 Decoding results of C1by depth-first principle易见，MGEP 既充分发挥 GEP 编码简单的优势，又实现一条单基因染色体包含多个表达式的思想． 这使得 MGEP 较传统 GEP 在基因多样性上有较大提升，从而借助固定长度染色体实现它的可变长功效，提高函数挖掘的演化性能．3． 2 初始化用 GEP 初始化方法随机产生满足个体要求，即( F ∪ T)hTh* ( n －1) +1所刻画的 MGEP 初始种群．如给定 F，T 情形下，根据基因头长和指定的染色体数目所产生的MGEP 种群个体都是由线性等长的符号串组成的． 其中基因头( 长为 h) 由函数符和终结符组成，而基因尾( 长为 h* ( n － 1) + 1) 只包含终结符． 这些编码后的基因称为 K 表达式． 对这种编码方法合理使用广度优先建树原则就可保证构造出语法规则正确的表达式树．个体评估MGEP 的一条染色体通常包含多个解决问题的方案． 这里采用 MEP 的评估方式去评估 MGEP 个体，即计算单染色体中所有子表达式的适应值，然后以最佳值来表征个体适应值．