【LSP】【遗传编程/基因规划】Genetic Programm

无名

背景介绍
“物竞天择，优胜劣汰”， 达尔文提出了著名的生物进化理论，即所有的动植物都是由较早期、较原始的形式演变而来的。而遗传编程（遗传规划）则在数学和计算机科学领域应用了这一演化过程：从基数较为庞大的原始、粗糙的程序种群中通过评估适应性选择父系、进行遗传操作生成新一代种群，再判断终止条件决定是否再次迭代、生成下一代种群。类比如下：


对照上面的流程图，我们可以来简单理清GP系统做了什么、想要做什么。

初始化：在给定初始条件（包括terminal sets, function sets和参数）后生成随机种群
通过(多种方法)比较，评估适应性(fitness evaluation)
依据fitness进行概率性选择——“probabilistically selected based on fitness”
被选择的程序作为父系，通过交叉(Crossover) ，变异(Mutation)， 复制(Reproduction)等遗传算子(genetic operators)生成下一代(next generation)
判断是否符合终止标准(Termination Criterion)，没符合的话继续迭代
程序表示
遗传编程，Genetic Programming (GP)， 属于进化算法(Evolutionary Algorithms)的一种。GP继承了遗传算法(Genetic Algorithms)的基本思想， 即从父辈中择优繁育子辈；不同于遗传算法(GA)的传统编码（固定长度基因）模式，GP的个体是计算机程序，具备多样的表现形式。最常见的是基于树状(Tree-based)的遗传编程，可用树形结构来清晰地表达。GP在发展过程中自然也拓展了多种种类与表现形式，如线性(Linear GP)，基于图的遗传编程(Cartesian GP)等。
"Field Guide"一书提到在GP中，程序多用以syntax tree（如上）的方式来表现。关于syntax tree的结构定义如下：

“树叶”部分被称为 终止符(Terminals) , 是程序中的变量、常量和无参函数等。
树形内部节点被称为函数(Functions), 有时也被称为primitives，涵盖程序中的函数与操作。
GP系统的Primitive set为允许、可行的Functions和Terminals的集合。
在上面的max(x+x, x+3y)树状表示图中，终止符为x，y，3，函数为，+，，max。则他们分别的集合为：函数集(function set) F = {+, *, max}，终止集(terminal set) T = {x, y, 3}
注意：“函数”未必一定包含在函数集(function set)中，无参函数可能在终止集(terminal set)中

在一些GP中程序可能由多个部分组成，如下图，用一组由特殊根节点(root)连接结合的树形分支(sub-trees branches)来表示。

初始化 (Initialization)
在上文流程图部分，已提到GP的初始种群(initial population)一般是给定函数集，终止集和参数随机生成的。参数包括种群数量(population size)，决策树深度(depth)等。抛开参数、限制、种类不谈，我们可以将随机生成个体的事件视作从函数集和终止集随机取得元素，创建节点(根节点root或子节点)并为其指定连接的随机子节点的随机过程。

Depth定义
但如果抛开限制，树形结构种群会变得过于冗长笨拙、杂乱不堪，所以我们引入一个重要概念：深度。Field Guide 给出如下定义:
还是以上文中的 max(x+x, x+3*y) 树形表示为例：根节点 函数max的深度(depth)为0，观察右侧的子节点 函数 * ， 这个子节点的深度为2。从max到最底层“树叶” 3 和 y 走过了3条edges，故整个树的深度为3。
通过指定树的深度，我们可以控制树的大小以及复杂性、种群系统的复杂程度。注：并不是depth越大越好。depth越大，整体系统就越复杂、越难以理解，有可能产生过拟合。

回到初始化过程中来，随机生成个体的两种最早期、最简单的方法分别为grow method 和 full method。在两种方法中，初始个体深度都不能超过(用户)所指定的深度。