1. 绪言
1.1 遗传编程概述
遗传编程继承了遗传算法的思想，但其采用分层结构作为解的表示形式。这种结构以问题原始变量为叶节点，通过组合函数构成中间节点，每个完整结构既对应问题的一个解，也可视为解决该问题的计算机程序。通过遗传操作持续调整这些结构，系统最终能演化出有效的可行程序。
1.2 传统遗传算法的局限性
遗传算法通过对字符串的进化操作实现优化，其理论框架经过多年发展已较为完善。但定长字符串编码限制了应用范围，主要缺陷包括：
（1）无法表达层次结构：实际问题如数学表达式f(x)=ax+b本质是层次化结构，如图1所示，而线性字符串难以有效描述；
（2）程序表达能力受限：无法直接表示方程求解、数据回归及包含分支/循环/递归的程序；
（3）结构刚性缺陷：固定长度字符串难以动态调整，制约问题表征能力。 遗传编程通过非线性树状结构突破这些限制，其本质是通过广义计算机程序求解问题。该方法建立初始种群后，基于适者生存原则持续应用遗传操作，通过迭代进化使个体逐步逼近最优解。作为遗传算法的扩展，该进化算法具有更强的通用性。
2.遗传编程
2.1 遗传编程基础
遗传编程中的个体是由函数符号集F={f1,f2,⋅⋅⋅,fn}与终止符集T={t1,t2,⋅⋅⋅,tm}通过属性层次结构组合而成。函数符集 F内的函数可以为：
算法运算符： +、-、×、÷ 等。（其中除号为防止计算机溢出，规定分母不为零，称为保护性除法，一旦遇到分母为零时，最简单的处理方法令其商为被除数，或重新选择算术运算符）；
超越函数： sin、cos、log、exp 等。其中 log 要防止处理小于或等于零的自变量，采用保护性对数；
布尔运算符： AND、OR、NOT 等；
条件表达式： If-then-else、Switch-case 等；
循环表达式： Do-until、While-do、For-do 等；
控制转移说明语句： Go to、Call、Jump 等；
变量赋值函数： a=1， Read、Write 等；
其他定义的函数；
终止符集是变量或常量。
例如，设函数符集为：F={+,×,÷,cos}，终止符集为：T={x,y,p}，图2表示了一个由 F 和 T 组成的个体的层次化结构。
表达结构方式；从下往上，从左往右
2.2 初始个体生成原理
初始群体由众多初始个体组成，初始个体为所要解决问题的各种可能的符号表达式，它通过随机方法产生。
开始时在函数集 F 中按均匀分布随机地选出一个函数作为算法树的根结点。通常把根结点限制在函数集 F 中是为了生成一个层次化的复杂结构；相反，若从终止符 T 中随机选取根结点，则生成只有一个终止符的退化结构。一般情况下，从函数集中选出的函数 f 如果具有Z(f) 个自变量，那么就要从该结点发出Z(f)个子节点。然后，对于每个子节点，从函数集 F 和终止符 T 的并集 C =F∪T 中再按均匀分布随机地选出一个元素作为该条线的尾结点。如果此时选出的是一个函数，则重复执行上述过程。如果从并集C 中选出的是终止符，它作为从节点发出的尾节点，则该分支点上的树就终止生长。上述过程从上到下，从左到右不断重复，直到一棵完整的树生成位置
初始群体中的初始个体通过某种随机方法产生，图3描述了一个初始个体的创建过程。