GP(Genetic Programming)算法.ppt

1、GP（Genetic Programming）算法,目录,一 概述 二 GP算法的模式理论 三 一般方法步骤 四 GP算法的基本原理,一 概述,1989年John R.Koza提出了GP（Genetic Programming）算法，该方法属于进化计算（Evolutionary Computation，EC）模型的一种，是受自然选择启发的一种强有力的搜索方法，基本思想是演化候选的程序种群以解决一个特定的问题。种群中每个个体解决目标问题的能力都通过适应度函数被评估。然后对个体进行复制、交叉等基因操作。一旦复制和根据给定概率进行的交叉操作执行完毕，新生成的个体被重新用适应度函数评估。这个过程被重复

2、进行直至运行到制定的代数或者最优个体被找到。,一 概述,GP算法提出了一种全新的结构描述方法，其实质是用广义的层次化计算机程序描述问题。这种广义的计算机程序能根据环境状况动态改变其结构和大小，在工程中具有广泛的代表性，因为很多工程问题可以归结为对特定的输出的计算机程序。,一 概述,GP算法求解问题的主要特征如下： 1、产生的结果具有层次化的特点。 2、随着进化的延续，个体不断朝问题答案的方向动态地发展。 3、不需事先确定或限制最终答案的结构或大小，GP算法将根据环境自动确定。这样，系统观测物理世界的窗口得以扩大，最终导致找到问题的真实答案。 4、输入、中间结果和输出是问题的自然描述，无需或少需

3、对输入数据的预处理和对输出结果的后处理。由此而产生的计算机程序便是由问题自然描述的函数组成的。,二 GP算法的模式理论,GP算法中对模式的定义为：模式是群体中含有一个或多个特定子树的所有个体（树）的集合。也就是说，一个模式是一个具有某些共同特征的符号表达式的集合。 假设某个共同特征是一个由s个特定点组成的子树，即在该树内没有不定点（即GA算法中的*点），则该子树用下式表达： 式中 H由s个特定点组成的子树； ai特定结点i，i1, 2, ,s； 子树的结构关系。,二 GP算法的模式理论,具有某个共同特征的个体的集合也是一个包含同一特定子树的所有树的集合。假设用 表示包含共同特征为 、结点数为

4、的树，一般情况下这样的树的个数是无限的，即： 然而在实际中，我们要限制其数目和其形态大小。比如说，我们可限制一棵树的形态大小为W（用最大结点数表示）。一旦W给定，那么由所有不超过W个结点，且包含特定子树的树的集合是有限的，即,二 GP算法的模式理论,在GP算法中，模式的平均适应度简单地定义为该模式中所有个体适应度的平均值，即 式中 N 具有共同特征 H 的个体数； f(Ti(gi, H)个体的适应度。,二 GP算法的模式理论,在GP算法中，模式因进化而出现的数目增长或衰减取决于模式的平均适应度与群体平均适应度的比值。即 ： 式中 群体平均适应度； 子代模式的平均适应度； 子代属于模式的个体数；

5、 模式破坏的概率。,二 GP算法的模式理论,在GP算法中，若作为模式标志的子树很小，或者子树之间的距离很小，则模式因交换而破坏的可能性也很小。对于按单一子树定义的模式来说，复制和交换的最终效果相当于从高适应度的树中分离出结点少的子树作为积木块，以一种近似最优的方式来构筑新的个体。一定时间后，搜索空间收缩成维数不断衰减、适应度不断增加的符号表达式。,二 GP算法的模式理论,上述论断也适用于包含特定子树多于一个的模式。当接近最优解时，如果存活的模式中不但该模式的子树结点数相当少，而且该模式的诸子树的距离也相当小，那么复制和交换的最终效果相当于从具有高适应度的树中分离出小而近的子树作为积木块，并以一

6、种近似最优的方式来构筑新的个体。,三 一般方法步骤,遗传规划的工作步骤可归纳如下： (1)确定个体的表达方式，包括函数集F及终止符集T。 (2)随机产生初始群体。 (3)计算各个体的适应度。 (4)根据遗传参数，用下述操作产生新个体： 1)复制。将已有的优良个体复制，加入新群体中，并相应删除劣质个体 2)交换。将选出的两个个体进行交换，所产生的两个新个体插入新群体中。 3)突变。随机改变个体某一部分，将新个体插入新群体中。 (5)反复执行(3)及(4)直至取得满意结果。,四 GP算法的基本原理,1 、个体的描述方法 2、初始群体的生成 3、适应性度量 4、基本算子 5、辅助算子 6、终止准则

7、7、结果标定 8、控制参数,四 GP算法的基本原理 个体的描述方法,GP算法中首先所要解决的问题是如何用一系列可行的函数对个体进行描述，而这种函数能反复地由Nf 个函数 和Nterm个终止符组合而成。函数集F中每个特定的函数 fi 假定有 z(fi), i = 1, 2, , Nf 个自变量，则对函数f1，f2，fNf 来说，相应有的自变量个数分别为：,四 GP算法的基本原理 个体的描述方法,问题的表达 遗传规划是用层次结构可变的形式表达问题，在表达中主要用函数和终止符两类组分。简单地说，终止符表示问题的值，函数表示对值的处理。综合在一起，遗传规划的个体表示对各种值(终止符)的处理过程(函数)

8、。 在函数集Ff1, f2, , fn中，函数fi可以是运算符、函数、说明等，具体有： (1) 算术运算符，如+, -, *, /等。其中除号为防止计算机溢出，规定不允许用零作分母，称保护性除法(Protected Division)，用标记。一旦遇到分母为零时，最简单的处理方法是令其商为1、或是重新选择算术运算符。,四 GP算法的基本原理 个体的描述方法,(2)超越函数，如sin, cos, tan, log, exp等。其中log要防止处理小于或等于零的数值，称保护性对数，记为Rlog其处理方法类似于。 (3)布尔运算符，如AND、OR或NOT等。 (4)条件表达式，如If-then-el

9、se, Switch-Case等。 (5)循环表达式，如Do-until, while-do, For-do等。 (6)控制转移说明，如Go to, Call, Jump等。 (7)变量赋值函数，如a:1, Read, Write等。 (8)其他定义的函数。,四 GP算法的基本原理 个体的描述方法,终止符集Tt1, t2, , tn 包括各种常数、输入、变量等，具体有： (1) 常数，如、180o等， (2) 变量，如x, y, z等。 (3) 输入，如a, b, c等。 顾名思义，终止符是个体表达的终点。,四 GP算法的基本原理 个体的描述方法,将函数集和终止符集综合在一起，便可形成层次状个

10、体。例如，有下列函数集： F=AND, OR, NOT 和终止符集： T=D0, D1 式中，D0，D1为布尔变量。 上述函数集和终止符集的并集C为： C=AND，OR，NOT，D0，D1,四 GP算法的基本原理 个体的描述方法,设有一个有两个自变量的奇偶判断函数的例子：若该函数有偶数个自变量，则该函数返回真；否则返回假。这种布尔型函数的符号表达式为： NOT(D0) AND NOT(D1) OR (D0 AND D1) 图一描述了上述符号表达式的层次化结构（树）。,四 GP算法的基本原理 个体的描述方法,图一 奇偶判断函数的算法树,四 GP算法的基本原理 初始群体的生成,初始个体的生成原理

11、初始群体由众多初始个体组成，初始个体为所要解决问题的各种可能的符号表达式（算法树），它通过随机方法产生。图二描述了函数“”（具有2个自变量）为根结点的算法树，函数“”是随机地从函数集F中选出的。一般情况下，从函数集F中选出的函数f如果有z(f)个自变量，那么就要从节点发出z(f)条线。然后，对于每条从节点发出的线，从中再按均匀分布随机地选出一个元素作为该条线的尾节点。如果此时选出的是一个函数，则重复执行上述过程。例如若函数“”从并集C中被选出，则函数“”将作为非根内结点，如图三所示。上述过程从上到下、从左到右不断重复，直到一棵完整的树生成为止。,四 GP算法的基本原理 初始群体的生成,图二 具

12、有函数“”根结点的算法树（第一次选择）,四 GP算法的基本原理 初始群体的生成,图三 具有函数“”非根内结点的算法树(第二次选择),四 GP算法的基本原理 初始群体的生成,初始个体生成的几种方法 常用的方法有三种：完全法、生长法和混合法 (1)完全法。用完全法产生的初始个体，每一子叶的深度都等于给定的最大深度（叶子的深度是指叶子距树根的层数，如图四所示的树深度为3）。其实现的方法是：若待定结点的深度小于给定的最大深度，则该结点的选择将限制在函数集内；若待定结点的深度等于给定的最大深度，则该结点仅从终止符集内选择。,四 GP算法的基本原理 初始群体的生成,图四 终止符A、B、C被选出作为叶子的算

13、法树 （第35次选择）,四 GP算法的基本原理 初始群体的生成,(2)生长法。用生长法产生的初始个体具有不同的形态，每一叶子的深度不一定都等于给定的最大深度。其实现方法是：若待定结点的深度小于给定的最大深度，则该结点的选择将限制在函数集与终止符集组成的并集中；若待定结点的深度等于给定的最大深度，则该结点仅从仅从终止符集内选择。 (3)混合法。混合法是完全法和生长法的综合。其实现方法是：初始个体的深度在2至给定的最大深度之间均匀选取，这时每一种深度下的初始个体数所占百分比n为： n=100/(给定的最大深度21) 在每一深度中，50的初始个体用完全法产生，另50的初始个体用生长法产生。,四 GP

14、算法的基本原理 适应性度量,常见的适应性测度有下列四种：原始适应度、标准适应度、调整适应度和归一化适应度。 (1) 原始适应度(Raw Fitness) 原始适应度是问题适应性自然描述的一种度量。例如，人工蚂蚁问题中研究蚂蚁吃掉的食物块数，吃掉的食物块数越多越好，原始适应度便是被蚂蚁吃掉的食物块数。当原始适应度定义为误差时，也就是在一组适应度计算试例中个体返回值与实测值之间的距离之和。如果符号表达式是整数型或浮点型，那么距离之和表现为符号表达式的返回值与实测值之间的距离绝对值的总和。在群体中，子代 t 中某一个体 i 的原始适应度r(i, t) 定义为,四 GP算法的基本原理 适应性度量,式中

15、 个体 i 在适应度计算式例 j 下的返回值； 适应度计算试例数； 适应度计算式例j的实测值或正确值。,四 GP算法的基本原理 适应性度量,如果符号表达式是布尔型或字符型，那么距离之和表现为符号表达式的返回值与实测值之间的符号不匹配的个数。 如果符号表达式是实数型，那么距离之和可用其平方和的平方根来代替，这样可增加距离对适应性的影响。 由于原始适应度是问题的自然表达，因此原始适应度的最佳值或为越小越好（当原始适应度为误差时），或越大越好（当原始适应度为吃掉的食物块数时）。,四 GP算法的基本原理 适应性度量,(2) 标准适应度(Standardized Fitness) 标准适应度 S(i,

16、t) 是原始适应度又一描述，即标准适应度总是表现为数值越小越好。于是有两种情况发生： 对于某些问题，若原始适应度越大越好，则标准适应度可定义如下 式中 rmax 为原始适应度所能达到的最大值。 对于另外一些问题，若原始适应度越低越好，则标准适应度即为原始适应度，即 S(i, t) = r(i, t) 。,四 GP算法的基本原理 适应性度量,(3)调整适应度(Adjusted Fitness) 子代 t 中个体 i 的调整适应度 a(i, t) 由标准适应度计算而得，即 通常 , 则 ,且调整适应度值越大，个体越优良。,四 GP算法的基本原理 适应性度量,(4)归一化适应度(Normalized

17、 Fitness) 归一化适应度 由调整适应度计算而得， 即 适应度值越大，个体越优良。 ,四 GP算法的基本原理 -基本算子,（1） 复制 当复制操作发生时，一个亲代个体繁殖一个后代个体。复制过程由两部分组成：首先，根据适应度按照不同的选择方法从群体中选出一个亲代个体；其次，被选出的亲代个体在未经任何变化的条件下从当前代复制到新一代中。,四 GP算法的基本原理 -基本算子,根据适应度有以下几种亲代选择方法： 适应度比例选择法。其含义是个体适应度越高，被选中的概率越大。 贪婪选择法。将个体按归一化适应度从大到小排序，将群体分为、两组，组由归一化适应度较高的优良个体组成；余下的归为组。进行个体选

18、择时，80的时间在组中选择，20的时间在组中选择。,四 GP算法的基本原理 -基本算子,级差选择法。这种方法将个体按适应度的大小分成许多个级别，个体根据群体中个体适应度的级别进行选择。适应度较高的个体具有适当的选择优势。 竞争选择法。首先从群体中随机选出一组个体，然后在该组个体中选出一个具有较高适应度的个体。,四 GP算法的基本原理 -基本算子,（2）交叉 交叉操作的实现方法 与复制过程相类似，第一个亲代个体根据上述的某种选择方法从群体中选出，第二个亲代个体也采用同样的选择方法从群体中选出，但两者选择过程独立。这样一来，所选出的两个亲代个体结构、大小可能均不相同。交叉时，在每个亲代个体的算法树

19、上分别按均匀概率分布随机选择一个交叉点，于是产生一棵以交叉点为根的子树，该子树包括交换点以下的所有子树。具有这样特点的一颗子树成为一个交叉段。有时，一个交叉段仅是一个叶子。,四 GP算法的基本原理 -基本算子,为了生成第一个子代个体，第一个亲代个体删掉其交叉段后，将第二个亲代个体的交叉段插入到它的交叉点处，这样第一个子代个体便产生了。同样，第二个子代个体也是通过第二个亲代个体删掉其交叉段后，将第一个亲代个体的交叉段插入到它的交叉点后而形成。交叉过程如图五、图六和图七所示。,四 GP算法的基本原理 -基本算子,图五 两个亲代个体（符号表达式）,NOT,四 GP算法的基本原理 -基本算子,图六 两

20、个由亲代个体产生的交叉段,四 GP算法的基本原理 -基本算子,图七 两个由亲代个体产生的子代个体,四 GP算法的基本原理 -基本算子, 交叉操作的一般特征 由于交叉时整个子树被交换，因此不管亲代个体和交叉点如何选择，交叉所产生的新的（子代）符号表达式总是语法上合法的表达式。 交叉操作的特殊作用 如果群体中相对其它个体来说有一个适应度特别好的个体，复制将促使该个体延续许多代，即使该个体在搜索空间中就整体来讲特别平庸也是如此。在GP算法中，当两个相同的个体进行交叉时，所产生的子代个体一般不相同，除非交叉点恰好相同，但这种机会很小，在GP算法中交叉操作将施加一个偏离同一化趋势的反平衡作用。因此，在G

21、P算法中同一化的发生是不可能的。,四 GP算法的基本原理 -辅助算子,有五个辅助算子：突变、排列、编辑、封装、自残 （1）突变（Mutation） 产生突变的方法是：首先在符号表达式的算法树上随机选定一个结点，该结点称为突变点，突变点可以是树的内结点（即函数），也可以是树的叶子（终止符）；然后删掉突变点和突变点以下的子树，用随机方式产生一棵新子树（方法同初始个体的产生）插入到该突变点处。该新子树由参数控制，控制参数主要是树的大小（用深度表示）。如图八（a）中点3（即D0）被选为突变点，随机生成的子树为NOT(D1)，突变后的树如（b）所示。,四 GP算法的基本原理 -辅助算子,图八 个体的突变

22、(a),四 GP算法的基本原理 -辅助算子,图八 个体的突变(b),四 GP算法的基本原理 -辅助算子,（2）排列（Permutation） 排列操作方法：首先选定一个个体的算法树的内结点（即函数），如果在选定点的函数有k个变量，那么可从k!种可能排列中选出一种；然后对选定点的函数的自变量进行随机排列。如图九所示，图中点4（即“/”）被选为排列点，排列前的树为（a），排列后的树为（b）。,四 GP算法的基本原理 -辅助算子,图九 排列操作的方法 (a),四 GP算法的基本原理 -辅助算子,图九 排列操作的方法 (b),四 GP算法的基本原理 -辅助算子,（3）编辑（Editing） 编辑算子提

23、供了一种编辑和简化符号表达式的手段。编辑操作仅在单个个体上进行，编辑操作的结果是产生一个新的子代个体。编辑操作可反复地将预先建立起来的编辑规则集应用于群体中每个符号表达式上。 一般的编辑规则如下：如果一个函数只有常数自变量，而且它对符号表达式中其他内容不产生负面影响，那么该函数就用具体的函数值来代替。例如，数学表达式12可用3来代替。 此外，编辑操作还应用一套与值域有关的编辑规则集。例如，对于数字值域问题，一个可能的编辑规则为：当一个子表达式自身相减时，则该表达式用零代替。,四 GP算法的基本原理 -辅助算子,编辑操作有两种使用方法： 编辑操作完全在外部执行，与GP算法的运行独立，这样可在输出

24、结果中同时观看编辑前和编辑后的个体； 编辑操作在进化过程中运行，这样在输出结果中只可观看编辑后的个体。 编辑操作由一频率参数控制，以确定是否以及如何对每一代实施编辑操作。例如频率参数fed = 1，则表示对每一代实施编辑操作。,四 GP算法的基本原理 -辅助算子,（4）封装（Encapsulation） 封装算子用于标明潜在有用的子树，并给它命名以便能在以后得到引用。封装操作仅在单个个体上进行，该个体的选择原则仍同于复制和交换，其结果是产生一个新的封装函数。 封装操作方法：随机选定一个个体的算法树的内节点（即函数点），从原树上将该子树复制下来（但原树仍不变），将该子树定义成一棵可被引用的新函数

25、。这个新的封装函数可当作终止符看，其形状为一棵原来位于选择点的子树，而且在产生时便命以不同的名称。,四 GP算法的基本原理 -辅助算子,调用封装函数是将其插入树的选择点处。问题的终止符集随后被增广成包含这些封装函数的终止符集。于是，当实施突变操作时，在突变点处能容纳新的封装函数。例如，考虑下列符号表达式：ABC 在图十中，点3被选为封装操作点，则形成的无自变量的封装函数E0为E0=BC。在原函数中，子树（BC）即被新的封装函数E0代替，产生的结果为AE0，如图十一所示。 封装函数的作用在于：被选为封装函数的子树在新生成的个体中不再因交换操作而被瓦解。,四 GP算法的基本原理 -辅助算子,图十 点3被选为封装操作点,四 GP算法的基本原理 -辅助算子,图十一 新的字符表达式,四 GP算法的基本原理 -辅助算子,（5）自残（Decimation） 对于一些复杂的问题，