遗传规划：geneticprogramming.pptVIP

遗传规划：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）条件表达式：IF―THEN―ELSE （5）可迭代函数：DO―UNTIL、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）完全法：每一叶子的深度都等于给定的最大深度。 实现方法：若待定结点的深度小于给定结点的最大深