遗传规划GeneticProgramming.ppt

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