遗传编程
1. 绪言
1.1 遗传编程概述
遗传编程继承了遗传算法的思想，但其采用分层结构作为解的表示形式。这种结构以问题原始变量为叶节点，通过组合函数构成中间节点，每个完整结构既对应问题的一个解，也可视为解决该问题的计算机程序。通过遗传操作持续调整这些结构，系统最终能演化出有效的可行程序。
1.2 传统遗传算法的局限性
遗传算法通过对字符串的进化操作实现优化，其理论框架经过多年发展已较为完善。但定长字符串编码限制了应用范围，主要缺陷包括：
（1）无法表达层次结构：实际问题如数学表达式f(x)=ax+b本质是层次化结构，如图1所示，而线性字符串难以有效描述；
图1 函数 f(x)=ax+b的树形表达
（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.2-(X/11) ))+((7*cos(Y) )) 的树形表达表达结构方式；从下往上，从左往右
2.2 初始个体生成原理
初始群体由众多初始个体组成，初始个体为所要解决问题的各种可能的符号表达式，它通过随机方法产生。
开始时在函数集 F 中按均匀分布随机地选出一个函数作为算法树的根结点。通常把根结点限制在函数集 F 中是为了生成一个层次化的复杂结构；相反，若从终止符 T 中随机选取根结点，则生成只有一个终止符的退化结构。一般情况下，从函数集中选出的函数 f 如果具有Z(f) 个自变量，那么就要从该结点发出Z(f)个子节点。然后，对于每个子节点，从函数集 F 和终止符 T 的并集 C =F∪T 中再按均匀分布随机地选出一个元素作为该条线的尾结点。如果此时选出的是一个函数，则重复执行上述过程。如果从并集C 中选出的是终止符，它作为从节点发出的尾节点，则该分支点上的树就终止生长。上述过程从上到下，从左到右不断重复，直到一棵完整的树生成位置
初始群体中的初始个体通过某种随机方法产生，图3描述了一个初始个体的创建过程。
（a）生产根节点 （b）生成子节点 （c）生产子节点
图3 算法树生成过程
初始个体的生成方法有多种，它们的共同要求是要能产生不同的组合。常用的初始个体的生成方法有三种，即完全法，生长法和混合法。
2.2.1完全法：
完全法产生的初始个体，每一叶子的深度都等于给定的最大深度。所谓叶子的深度是指叶子距树根的层次。首先从函数集 F 中选取元素作为根节点，然后根据给定的最大深度分别从函数集 F 及终止符 T 中选取元素。假若待定节点的深度小于给定的最大深度，则该节点从函数集中随机选取，以便算法树延伸；若待定结点的深度等于给定的最大深度，则该节点从终止符集中选取，以便终止算法树的生长。
图4 完全法随机生成图例（节点数为7，最大深度为2）
2.2.2生长法：
生长法形成的初始个体，每一叶子的深度不一定都等于给定的最大深度，但是算法树的最大深度要等于给定值。它也同样首先从函数集 F 中选取根节点，然后再选取外延的待定节点。假若待定节点的深度小于给定的最大深度，则该节点从函数集 F 及终止符 T 的并集 C =F∪T 中选取。若待定结点的深度等于给定的最大深度，则该节点仅从终止符集中选取，以便终止算法树的生长。
图5 生长法随机生成图例（节点数为5，最大深度为2）
2.2.3混合法
混合法是完全法和生长法的两者的综合。其实现方法是：初始个体的深度2至给定的最大深度之间随机选取，然后一半的初始个体用完全法产生，另一半的初始个体用生长法产生。
在完全发和生长法两者方法中，为了防止产生的初始树节点数目太多，需限定都树的最大深度不超过一个给定的数。可以看出，用完全法将产生非常大的个体树，而用生长法生成的树，大小和形状有更多的差异。
2.3适应度
在遗传编程中，选择算子与遗传算法相同，选择适应度高的树作为父代，交叉变异需根据表达方式来。
2.4交叉
选择和复制出来的个体还要进行交叉，对每一对个体，产生一个随机数，如果这个数小于交叉概率 Pc，将对个体执行交叉操作。
交叉模拟的是自然界中的遗传以及两性生殖过程，父代通过DNA重新组合，产生子代，子代继承了父代的一些基因，同时产生了新的基因。
交叉操作的实现步骤如下：首先选择父代，然后，在每个父代个体中随机选取 某个结点作为交叉点，交换父代中以交叉点为根结点的相应子树得到两个后代。图6给出了交叉的一个例子。
图6 交叉示意图（黑色节点是被选中的交叉点）
2.5 变异
变异模拟的是生物界中基因突变。交叉只对现有的基因进行排列组合，产生不出新的基因材料，容易发生“早熟”现象，而变异有利于形成群体的多样性，使算法有机会从局部最优解中解脱出来。
对于每一个个体，产生一个随机数，如果它小于变异概率 Pm，则对此个体执行变异操作。产生变异的一般的方法是:在个体上随机选定一个变异点，变异点一般选择除根之外的任意节点，删掉以变异点为根的子树,然后用随机方法产生新的子树(方法同初始个体的产生方法相同)插入到该变异点处，变异之后的个体树不能超出最大深度限制。图7给出了一个个体变异的例子。
图7 变异示意图（黑色节点是被选中的变异点）
3.遗传编程的扩展
遗传网络编程（GNP）被认为是遗传编程（GP）基因结构的延伸。GNP的基因结构用有向图表示，与GP的树状结构相比，具有节点可重用性、结构紧凑和考虑过去事件的决策能力等优点。
图8 遗传网络编程结构
程序的基本结构如图8所示，它由三种节点构成，包括
（1）启动节点
（2）判断节点：if-then分支决策函数，对技术分析中常用的技术指标进行检验，根据{A = high, B = low}等判断结果，为下一个节点选择一个分支。
（3）处理节点：动作函数，决定操作。
因此，节点迁移从起始节点开始，根据节点之间的连接顺序执行判断和处理节点。通过遗传算法对连接进行优化，得到较好的动作规则。
图9 遗传网络编程算法演示示例
图9展示了遗传网络编程在金融量化领域中的作用，网络中的判断节点就是一些市场指标，比如衡量价格与均线的偏离程度，识别超买/超卖状态，价格变化速度等。在图9中，t时刻，如果指标X1=A，并且X2、X3也等于A，那么就发出买入股票信号，然后在下一时刻，如果指标X4=B，X5=A则发出卖出信号，以此类推。最后，它会将这些规则分别放入到买入和卖出规则池中，作为个体决策的策略。