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

遗传规划(GP)
祈廖佐形寡晃冰印柞乎硕莆跃茁瓢祁准殃瘁猩引淫酵虽明愧险拙葫漆丈炸2012计算智能--
GP概述
发展: 1989年,美国斯坦福大学J. Koza首先提出
典型应用:
机器学习(预测,分类…)
特性:
与神经网络解决的问题相似(竞争)
需要较大的种群(上千个)
速度较慢
独有特点:
非线性染色体:树、图
存在非必要的变异操作(争议!)
痔腻传越碉变沮邓然臆陀比较陌惮蒙搽罪蛀悄矮饮墓洲汐策萍饺俩累擎罚2012计算智能--
引子: 信用评分
银行需要辨别信用良好的和不良的申请人
模型需要和历史数据相匹配
ID
No of children
Salary
Marital status
OK?
ID-1
2
45000
Married
0
ID-2
0
30000
Single
1
ID-3
1
40000
Divorced
1
…
节首珊棉讼绍失驭膨尽诧溢略馏泣虾震弱桥耙善爪殊蚊妨冲堪盅亡川掩淬2012计算智能--
引子: 信用评分
一个可能的模型
IF (NOC = 2) AND (S > 80000) THEN good ELSE bad
一般化:
IF formula THEN good ELSE bad
我们希望获取formula
我们的搜索空间(表现型)是一个formula集合
适应值:能够被规则所代表的模型准确区分的样本比例
Formula的表现形式(基因型)是:树
搪田痢庐茵哭异宠效舜应予荧滇壶刷缓窘昨毡御佑辖戍新昏怎艳蛮挚议喻2012计算智能--
引子: 信用评分
IF (NOC = 2) AND (S > 80000) THEN good ELSE bad
表示的树结构如下:
AND
S
2
NOC
80000
>
=
德矩陵误笛靳仿肿麓姻戍称零靴仲极阐可乍磨瞧绕启卢置肄喳捍胡靛珍杂2012计算智能--
基于树结构的表示
树结构是一种通用表示形式,可以表示多种表达式,如:
算术表达式
逻辑表达式
程序
(x  true) (( x  y ) (z (x  y)))
i =1;
while (i < 20)
{
i = i +1
}
傅业衷膳填焦尖言逛迟娃藩瞬二蚤绸猫妨案度臀蜘伞诱促枚删性伴砰枯馒2012计算智能--
基于树结构的表示
掏隙奈宁七曳太骡毁揖或赴惠礁膛暴埃景罐曹诚她抡仰硷麻萎神黑烛逗话2012计算智能--
基于树结构的表示
i =1;
while (i < 20)
{
i = i +1
}
乳膏渭螺品闺贩啼先蒸院俭啃在吮马秆踞奖丁绢赣择盛苑崇寂沽铝桓狂漳2012计算智能--
与GA染色体的区别
遗传算法的染色体是线性结构(比特串,整数串,实值向量,文字组合等)
树结构的染色体是非线性结构
遗传算法的染色体长度是固定的
GP中的各个子树可以有不同的宽度和深度
先凄遥沮葫末碴忠氧趟充妙孩哈吁裳羽挝箕刁彝门爷贿胯劳迪沪真礼夏吐2012计算智能--
基于树结构的表示
符号表达式可以用如下集合定义:
终端节点集合 T
函数节点集合 F
判断其是否为合法的树结构:
对于任意的t  T,都是一个合法的表达式
如果ties(f)=n 并且e1, …, en 是合法的表达式, 那么f(e1, …, en)是一个合法的表达式
不存在其他形式的合法表达式
饥复巴癸物擒躬肢驼拳茂灸沏朴腔诚同绸诈慎淖探暂酗霞刀腺爷娠煽糟刮2012计算智能--