论文部分内容阅读
基因表达式程序设计(Gene Expression Programming，简称GEP)是Candida Ferreira根据遗传算法和遗传程序设计发展而来、基于基因型和表现型的一种新型演化算法。该算法模仿生物体内DNA复制繁殖和蛋白质变异的机制，使得利用演化算法进行数学建模变得更加简单高效。GEP的出现为自动程序设计开辟了一条新路，但它处在一个正在发展而尚未成熟的阶段，亟需得到不断完善和推广。本文主要对GEP的原理和应用进行了研究，同时对其作了不少改进和完善。
本文第一章介绍了遗传算法、遗传程序设计以及GEP的提出背景、发展现状。第二章阐述了GEP的基本原理。第三、四、五章是本文的重点，主要阐述了作者针对GEP所作的研究成果，这些研究成果主要是对GEP算法的分析与改善：
1、研究了“头-身-尾”三段构造的新基因结构并分析了其复杂度。对基因结构进行改造，使得新的基因结构更加强健也更便于学习机制的引入。
2、提出了两种新的解码方法，分析了解码方法的时间和空间复杂度。第一种解码算法遵循C.Ferreira所提出的基因型和表现型之间的映射关系。因为GEP是一个基因型与表现型(染色体与表达式树)相结合的系统，似乎构造表达式树成为一个必不可少的环节，实际上我们完全可以略过这一个步骤，在计算个体适应值时，并不需要基因型与表现型的相互翻译，本文提出了一种新的解码和适应值计算方法，这一方法可以直接在染色体上进行运算从而计算出相应表达式的值和染色体的适应值，也可以直接将其翻译成表达式。第二种新的解码方法是在不改变基因构造规则的情况下，利用栈来计算适应值和获取表达式。这种方法获取的表达式已经不遵循原始GEP基因型和表现型之间的映射关系，但它的演化能力没有丝毫减弱。
3、拓展了同源基因的构造思想。C.Ferreira在其著作(第一版)中没有对GEP中提到的同源基因作较多的研究，本文借鉴软件工程中的程序重用技术，深入探讨了同源基因的构建技术，两级同源基因的使用扩大了可重用元素的范围。
4、引入基因库技术和新算子。基因库技术在不少改进的演化算法中一直扮演了非常重要的角色，考虑到GEP中基因构造与解码的特点不便于随意截取染色体的一部分作为基因库中的基因，因此在GEP中，基因库技术通常应用在染色体由多个基因构成且单个基因有效表达式长度较短的情况下，此时优秀个体中单个基因即可用来构造基因库。新算子主要有基因嵌入(替换)算子和针对第二种解码方法而重新设计的两点重组算子。
5、使用二次演化。二次演化可以进一步提高演化的精度，即在第一次演化完毕后使用第一次演化结果的误差作为目标值用同样的算法再次演化，以两次演化得到的表达式之代数和作为最终结果。
6、嵌入参数优化算法。一个好的结果表达式是由一个优秀的结构加合适的参数构成的，GEP对结构的优化能力远胜于其对参数的优化能力，因此在演化过程中使用多父体杂交算子和柯西变异算子相结合的遗传算法对一些优良结构进行参数优化通常能得到更好的表达式。
7、融入分布评估算法。新基因结构的引入使得头部基因位状态有限，便于分布评估算法统计头部各基因位出现相应函数符号的频率，建立的概率模型使变异过程具有方向性。结合PBIL学习算法使其具备全局学习能力。
8、并行化算法。尽管现在的处理器速度越来越快，但演化计算的问题搜索空间通常都是相当大的，GEP有着一般遗传算法的内在并行性特点，研究表明将GEP算法并行化能更快地解决问题。
第六章讨论了基因表达式程序设计在一般符号回归问题、分类问题、组合逻辑电路演化中的应用。第七章总结了论文的主要内容，并展望了后续工作。