2012计算智能-4.遗传规划

遗传规划(GP)

2012计算智能-4.遗传规划

GP概述

发展: 1989年，美国斯坦福大学J. Koza首先提出 典型应用:

机器学习(预测，分类…) 与神经网络解决的问题相似(竞争) 需要较大的种群(上千个) 速度较慢 非线性染色体：树、图 存在非必要的变异操作(争议！)

特性：

独有特点:

2012计算智能-4.遗传规划

引子: 信用评分

银行需要辨别信用良好的和不良的申请人 模型需要和历史数据相匹配ID ID-1 ID-2 ID-3 … No of children 2 0 1 Salary 45000 30000 40000 Marital statusMarried Single Divorced

OK? 0 1 1

2012计算智能-4.遗传规划

引子: 信用评分一个可能的模型 IF (NOC = 2) AND (S > 80000) THEN good ELSE bad 一般化： IF formula THEN good ELSE bad 我们希望获取formula 我们的搜索空间(表现型)是一个formula集合 适应值：能够被规则所代表的模型准确区分的样本比 例 Formula的表现形式(基因型)是：树

2012计算智能-4.遗传规划

引子: 信用评分IF (NOC = 2) AND (S > 80000) THEN good ELSE bad 表示的树结构如下：AND

=

>

NOC

2

S

80000

2012计算智能-4.遗传规划

基于树结构的表示

树结构是一种通用表示形式 ，可以表示多种 表达式，如： y 2 ( x 3) 算术表达式 5 1 逻辑表达式(x true) (( x y ) (z (x y))) i =1; while (i < 20) { i = i +1 }

程序

2012计算智能-4.遗传规划

基于树结构的表示y 2 ( x 3) 5 1

2012计算智能-4.遗传规划

基于树结构的表示i =1; while (i < 20) { i = i +1 }

2012计算智能-4.遗传规划

与GA染色体的区别

遗传算法的染色体是线性结构(比特串，整数串， 实值向量，文字组合等) 树结构的染色体是非线性结构 遗传算法的染色体长度是固定的

GP中的各个子树可以有不同的宽度和深度

2012计算智能-4.遗传规划

基于树结构的表示

符号表达式可以用如下集合定义：

终端节点集合 T 函数节点集合 F

判断其是否为合法的树结构：1. 2.

3.

对于任意的t T,都是一个合法的表达式 如果ties(f)=n 并且e1, …, en 是合法的表达式， 那么f(e1, …, en)是一个合法的表达式 不存在其他形式的合法表达式

2012计算智能-4.遗传规划

初始化种群

设置树最大深度Dmax 完全法(每一个子树的深度depth = Dmax ):

如果节点深度d < Dmax,随机从函数集F中选择节点 如果节点深度d = Dmax ,随机从终端节点集T中选择节点 如果节点深度d < Dmax,随机从函数集和终端节点集F T中 选择节点 如果节点深度d = Dmax ,随机从终端节点集T中选择节点

生长法(每一个子树的深度depth <= Dmax )

一般的GP初始化方法：“各半法” 种群中一半个体使用完全法生成，另一半使用生长法 生成

2012计算智能-4.遗传规划

选择

根据适应值进行比例选择 超量选择(具有较大规模种群)

根据适

应值对种群中的个体进行排序，并将其分割为两组 组1:最好的x%个个体，组2:其他 (100-x)%个个体 x%一般根据经验确定 例如. 种群规模 size = 1000, 2000, 4000, 8000 x = 32%, 16%, 8%, 4% 从组1中选择80%的个体，从组2中选择其他20%生成子代

生存选择:

保持最优个体，其他个体使用适应值比例选择

2012计算智能-4.遗传规划

变异

常用的变异方法: 用随机生成的子树替换随机 选择的子树

2012计算智能-4.遗传规划

变异

变异具有两个参数：

变异概率pm 选择子树的每个内部节点的概率

Pm建议为零(Koza’92) 或者非常小，如0.05(Banzhaf et al. ’98) 子代个体的大小可能会超过父代个体的大小

2012计算智能-4.遗传规划

重组(交叉)

最常见的重组方式：随机交换两个父代个体的 子树 重组具有两个参数：

重组概率pc在每个父代子树中选择内部节点的概率

后代的大小可能会超过父代个体

2012计算智能-4.遗传规划

Parent 1

Parent 2

Child 1

Child 2

2012计算智能-4.遗传规划

膨胀

膨胀=“较胖的个体生存到下一代”,具体原 因有待进一步的研究 反制策略

探测并阻止能够产生“巨” 子树的操作(重组、 变异) 惩罚原则：对“巨”子树施加较大的选择压力

2012计算智能-4.遗传规划

GA 流程

GP流程

2012计算智能-4.遗传规划

应用实例:符号回归

给定实数空间R2中的一些点 (x1, y1), … , (xn, yn) 目标：找到函数f(x),满足 i = 1, …, n : f(xi) = yi 利用GP求解：

确定符号集 F = {+, -, *, sin, cos}, T = R {x} 确定适应值：误差 n err ( f ) ( f ( xi ) yi ) 2 误差定义为： i 1 确定种群数目：size = 1000, 使用“各半法”生成初始种群 终止条件：迭代次数n到达50000或者满足适应值要求( err(f) < 0.0001 )

2012计算智能-4.遗传规划

应用实例y k 0.8u 2 k 1 1.2y k 1 0.9y k 2 0.2生成模拟数据4 3

21 0 -1 -2 0 20 40 60 80 100

(y) + 4% 噪声 (u)

GP辨识结果

y k 0.816u k 1 u k 1 1.175 y k 1 0.890 y k 2 0.205