文法演化的模型理论

文法演化（GE）是十分重要的遗传程序设计方法，应用面很广，特别适合类型、领域知识的刻画，被视为解决多目标决策问题、软件复用工程、CASE等复杂问题分析和设计的强有力的工具。研究旨在建立具有明显性能优势的文法演化理论，即文法演化的模型理论（MGE）。内容包括演化框架、基因模块性、个体的抽象表示、解释器、复杂性等方面的理论、技术和方法。研究贡献在于率先以文法为手段获得模块描述的创新方法和关键技术的突破；以有穷自动机为工具系统地、可视地揭示文法形式概念、解的推导和演化的不确定性之间的关系。为此，开展MGE研究非常重要，它为利用形式化方法探究高性能GE的设计开辟了新途径。

遗传程序设计（Grnrtic Programming, GP）是Koza借鉴遗传算法（Genetic Algorithm，GA）思想设计的自动程序设计方法。本课题就应用十分广泛的一类GP变体，即文法演化（Grammatical Evolution，GE），进行了深入探讨,涉及演化框架，基因的模块性，个体表示等。所以选用GE进行研究,是因为它有很强描述力,还可对接嵌入其他GP变体、智能计算方法。.文法演化（Grammatical Evolution, GE）最早由Ryan、O’Neill等共同提出，尔后经由许多研究者不断完善。由于引入了文法，GE在诸多方面优于GP，如易于描述类型和领域知识，在研究、实践者中赢得广泛关注。.给定一个2型文法，GE算法可由GP算法结构修正如下：.a).创建由若干密码子序列（即个体）构成的初始种群；.b).依据所谓基因型到表现型（genotype-to-phenotype, g2p）的转换法则将个体译为程序。.c).评估个体的适应值；.d).用遗传算子产生新个体和种群；如果终止条件成立，则结束演化过程，否则继续执行步骤b。.表示是GP（包括这里的GE）研究领域的公开性难题，与GP高性能实现有着密切关系。理想的表示方法一般宜满足以下要求，而这正是现有GE所欠缺的。.a).可理解性要好；.b).功能描述的重用性要好，并且便于开展块意义上的结构分析和语义重用；.c).有助评估性能的提升。.为解决GE的以上缺陷，我们从模型角度对它进行了深入研究，提出基于模型的文法演化（Model-based Grammatical Evolution，MGE）方法. 新方法中，个体由产生式序列表示，因而它们可以表示为具有语义承载能力的正规式，既方便块结构、模式的定义与描述，又便于利用形式语言学有关成就、结论进行系统化的科学处理。在此基础上，我们可以看到：MGE没有散失精准性和描述力，但较GE有效率性能的明显提升；确立深度优先解码原则下，不仅GE，而且GEP（Gene Expression Programming）等都能统一到具有语义承载能力的正规式表示基础上。这为统一GP变体的统一性研究奠定了基础。MGE是一个高性能GE平台，也可以嵌入其他GP变体，智能计算方法。为此，还开展了相关计算智能方法研究，为日后融合、深化应用做了铺垫。