《遗传规划GeneticProgramming.ppt》由会员分享，可在线阅读，更多相关《遗传规划GeneticProgramming.ppt（29页珍藏版）》请在三一办公上搜索。
1、遗传规划：Genetic Progamming,1 概述,一、GA的局限性（1）不能描述层次化问题：许多问题的自然描述往往是一种层次化的计算机程序。例：,但在许多情况下，程序的结构和大小在问题解决之前无法知道用何种函数逼近。,（2）不能描述计算机程序：即使程序确定，采用定长的字符串方法也不能描述 计算机程序。例：求 的程序,（3）缺少动态可变性 定长的字符串描述不具备动态可变性。二、遗传规划的基本知识 例：某地10月份降雨量与预报因子的实例数据：,用函数拟合，以便进行预报（1）（2）（3）（4）找到一种函数能最好地拟合表中的数据。a、初始群体的形成 初始群体由随机产生的计算机程序组成，而计算
2、机程序又由函数和变量组成。,如上例：,b、个体适应性测度：群体中的个体的适应度取决于其逼近真实解的好坏程度，这种测度称为适应度：,c、复制和交换操作 复制操作根据适应度的比例原则。交换操作：从当代群体中选择双亲个体进行交换产生新 的个体，在交换过程中由于双亲个体可能具 有不同的结构和大小，产生的子代也会大不 相同。例：将个体2淘汰，个体4被复制分数为2,复制操作：根据适应度比例原则，个体适应度越好进行 交换的概率就越大。假定2、3交换，1、4交换：部分交换,计算适应度,d、遗传规划的重要特征：（1）产生的结果具有层次化特征。（2）随着进化的延续，个体不断朝问题答 案的方向动态地发展。（3）不需
3、要先确定或限制最终答案的结构 或大小。（4）输入中间结果和输出是问题的自然描 述。,三、遗传规划的一般方法和步骤：（1）随机产生初始群体，即产生众多函数和变量随机组成 的计算机程序。（2）运行群体中的每一个计算机程序（个体），计算适应 度。（3）生成下一代群体。根据适应度随机复制新一代个体 通过在双亲个体随机选定的部位进行交换产生新的 个体，双亲个体也依据适应度随机选定。（4）迭代执行（2）（3）直到终止准则满足为止。,流程图：,2 遗传规划的基本原理,一、个体的描述方法 用一系列可行的函数对个体进行描述：个函数：终止符个数：函数 有 个自交点。函数集内的函数可以是：（1）算术运算符：、（2）
4、标准数学函数：SIN、COS、EXP、LOG（3）布尔运算符：AND、OR、NOT,（4）条件表达式：IFTHENELSE（5）可迭代函数：DOUNTIL、REPEAT（6）可递归函数（7）自定义函数：终止符：变量：常量：（布尔型NIL）例：函数集：F=AND、OR、NOT 终止符集：T=DO、DI DO、DI 布尔变量，无 自变量。,F与T的并集：考虑：若函数有偶个自变量则该函数返回“T”否则“NIL”：,二、初始群体的生成 a、初始个体生成原理 用随机方法产生所需解决问题的各种符号表达式（算法树）。在函数集合F中按均匀分布随机选出一个函数作为算法树的根结点。例：随机选取“”两个自变量,从函
5、数F与T终止符中的并集随机选取一个元素作为尾结点。如：“”若是终止符，则该结点不在生长。A、B、C为终 止符，不断重复直到一棵完整的树。,b、初始个体生成的几种方法（1）完全法：每一叶子的深度都等于给定的最大深度。实现方法：若待定结点的深度小于给定结点的最大深 度，则该结点的选择限制在函数集内 F。（2）生长法：每一叶子的深度不一定等于给定的最大深度。实现方法：若待定结点的深度小于给定的最大深度，则该结点选择限制在FUT。（3）混合法：完全法和混合法的综合。初始个体的深度在2至给定的最大深度之间 均匀选取。,三、适应性度量 a、原始适应度（Raw Fitness）计算个体值与实测 值之间的距离
6、。子代t 在某一个体i：适应度：个体i在适应度计算试例j下的返回值；：适应度计算试例数；：适应度试例j的实测值或正确值；,b、标准适应度（Standardized Fitness）适应度最大越好的问题：c、调整适应度d、归一化适应度,四、基本算子 a、复制（1）适应度比例选择法：,复制概率：（2）贪婪选择法：当群体中的个体数超过1000时，进化过程耗时大 长将个体分为两组、。（组适应度高，组适应 度低）80的时间在组选择，20的时间在组选 择。（3）级差选择法：按适应度将个体分成等级，个体根据级别进行选择。,（4）竞争选择法：首先从群体中随机选取一组个体，然后从该组中 选出具有较高适应度的个体
7、。b、交换 交换的实现方法：在父代群体随机选取两个个体。在选中的个体中随机选取一个交换 节点。例：,交换后：c、终止准则 最大代数G 满足给定的条件,3 辅组算子,一、突变（Mutation）依适应值或比例的概率随机选一个体；在算法树上随机选定一个结点；然后删去突变结点及以下的子树；用随机方法产生一棵子树插入到突变处。二、排列（Permutation）随机选取一个体；随机选定个体的算法树的内结点；如果该结点有k个自变量，那么可以ki排列中随机选；出一种，对自变量进行随机排列。,三、编辑（Editing）随机选取一个体；如果一个函数只有常量和变量就用函数值来代替。四、封装（Encapsulation）随机选取个体算法树的内节点，将该节点以下的子 树复制下来；将子树定义成一棵可被引用的新函数，命以不可的 名字；新封装的函数可作为终止符看待。,在突变时对该函数不起作用：五、自残（Decimation）为了使群体的多样性，当大部分个体出现相同时，在复制过程中使一些个体自行消失。,x,B,C,
