3遗传规划(1).ppt

河北大学 吴彬 wubinbb 1 3遗传规划 1 遗传规划技术介绍 河北大学 2 吴彬 wubinbb 遗传算法的局限性 遗传算法不适合描述层次化问题遗传算法缺乏动态可变性001110101110011000000010101001000 河北大学 3 吴彬 wubinbb 遗传算法的局限性 遗传算法不适合描述计算机程序计算机程序可看成是一种层次化结构 i 1 while i 20 i i 1 河北大学 4 吴彬 wubinbb 遗传算法的局限性 总之遗传算法一般用来解决能用定长字符描述的问题 遗传算法用字符串表达问题 遗传规划一般用来解决需用不确定长度字符描述的问题 遗传规划采用层次化结构表达问题 遗传算法求解的是数值性结果 遗传规划求解的是方法性结果 函数 河北大学 5 吴彬 wubinbb 遗传规划步骤 1 确定个体表达方式确定函数集和终止集 2 随机产生初始种群 3 计算各个个体的适应度 4 根据下面一系列操作产生新个体复制交换突变 5 重复执行 3 4 直到取得满意结果 河北大学 6 吴彬 wubinbb 河北大学 7 吴彬 wubinbb 3 3遗传规划基本技术 一 问题的表达函数集算术运算符超越函数布尔表达式条件表达式循环表达式控制转移说明变量赋值函数其他 河北大学 8 吴彬 wubinbb 3 3 1问题表达 终止集常数变量输入 河北大学 9 吴彬 wubinbb 3 3 1问题表达 将函数集和终止符集结合在一起可形成层次状个体以奇 偶判断函数为例 河北大学 10 吴彬 wubinbb 奇 偶判断函数 三个变量的奇 偶判断函数d0 d1 d2为变量 河北大学 11 吴彬 wubinbb 奇 偶判断函数 二个变量的奇 偶判断函数d0 d1为变量 河北大学 12 吴彬 wubinbb 3 3 2初始群体生成 生成步骤1从函数集中按均匀分布选取一个函数作为根结点根结点从函数集中选取若函数有个变量 则结点下有条连线2从按均匀分布选取作为该线的尾结点新结点仍然是函数 重复上述过程新结点是终止符 该线停止生长3从左到右 从上到下重复上述过程 直到形成一颗完整的树为止 河北大学 13 吴彬 wubinbb 3 3 2 1初始群体生成原理 例子 河北大学 14 吴彬 wubinbb 3 3 2 2初始种群的生成方法 完全法生长法混合法 河北大学 15 吴彬 wubinbb 3 3 2 2初始种群的生成方法 完全法用完全法产生的初始个体 每一叶子的深度都等于给定叶子的最大深度1从函数集中选择根结点2根据给定的最大深度分别从函数集和终止集中选择元素2 1如果待定结点深度小于给定的最大深度 从函数集F中选取结点2 2如果待定结点深度等于给定的最大深度 从终止集T中选取结点 河北大学 16 吴彬 wubinbb 3 3 2 2初始种群的生成方法 例子 假设给定的最大深度为3 河北大学 17 吴彬 wubinbb 3 3 2 2初始种群的生成方法 生长法用生长法形成的初始个体 每一叶子深度不一定都等于给定的最大深度 但是算法树的最大深度要等于给定值 河北大学 18 吴彬 wubinbb 3 3 2 2初始种群的生成方法 选取方法1从函数集中选择根结点 2根据给定的最大深度分别从函数集和终止集中选择元素 2 1如果待定结点深度小于给定的最大深度 从函数集F及终止集T的并集C F T中选取结点 2 2如果待定结点深度等于给定的最大深度 从终止集T中选取结点 河北大学 19 吴彬 wubinbb 3 3 2 2初始种群的生成方法 例子 假设给定的最大深度为4 河北大学 20 吴彬 wubinbb 3 3 2 2初始种群的生成方法 混合法为了提高种群的多样性 可采用混和法 确定每个初始个体的算法树深度 初始个体的深度在2至给定的最大深度之间均匀选取 每一深度下初始个体数目所占百分比为 D为给定的最大深度 例 当D 6时 2 3 4 5 6的个体各占20 其次在每一深度中50 用完全法 50 用生长法 河北大学 21 吴彬 wubinbb 3 3 3适应度分配 适应度是衡量个体优劣的尺度 也是遗传规划实现自然选择的依据 后面的选择算子是根据适应度来进行个体的选择的 河北大学 22 吴彬 wubinbb 目标值与适应度 目标值是目标函数的结果 适应度是对目标值的进一步改变 改变后的值作为 选择 算子选择的依据 河北大学 23 吴彬 wubinbb 适应度 标准适应度调整适应度适应度调整的一种方法 归一化适应度 河北大学 24 吴彬 wubinbb Ranking适应度分配 思想 按某一原则对目标函数排序 适应度的分配根据排序后该个体在排序中的位置来分配 河北大学 25 吴彬 wubinbb 线性Ranking 线性分级q为最优个体的相对适应度 选择概率 d为相邻个体的相对适应度之差 相邻个体的选择概率之差 写成通式下面的问题是q和d如何确定 河北大学 26 吴彬 wubinbb 线性Ranking 为了确定q或d的范围考虑两种极端情况 1 d 0 2 d最大 即q M 1 d 0 河北大学 27 吴彬 wubinbb 线性Ranking 把两种情况代入 计算得到q的变换范围 在范围内任选q 之后可根据下式计算d的大小 河北大学 28 吴彬 wubinbb 线性Ranking M种群中个体数目最优个体被选中概率最差个体被选中概率为了使得M保持常数 河北大学 29 吴彬 wubinbb 线性Ranking 等价推导 河北大学 30 吴彬 wubinbb 3 3 4 1复制 比例选择法竞技选择法截断选择法 河北大学 31 吴彬 wubinbb 比例选择法 实质思想 是个体适应度越大 被选中的机会越大选中的概率为各个个体的适应度概率累加产生 0 1 均匀分布的随机数若则选个体i进入下一代 河北大学 32 吴彬 wubinbb 竞技选择法 1 从第t代群体中随机选择k个个体 2 比较k个个体的适应度 复制适应度最大者进入第t 1代 被复制的个体仍保留在第t代 3 重复执行 1 2 直至产生要求的个体数目为止 竞技选择法可以减小计算量 因为它不需要对所有个体进行集中适应度评价 河北大学 33 吴彬 wubinbb 截断选择法 源于进化策略 又称选择法 从父代个个体选出个最优个体作为子代由于采用确定性选择法 缺乏种群多样性 河北大学 34 吴彬 wubinbb 3 3 4 2交换 河北大学 35 吴彬 wubinbb 3 3 4 2交换 河北大学 36 吴彬 wubinbb 3 3 4 2交换 为了防止产生巨型新个体 要用树的最大允许深度进行控制 如果有一个子代新个体的算法树深度超过允许值 则删除巨型新个体 河北大学 37 吴彬 wubinbb 其他交换方法 子树交换自身交换模块交换 河北大学 38 吴彬 wubinbb 子树交换 河北大学 39 吴彬 wubinbb 自身交换 河北大学 40 吴彬 wubinbb 模块交换 河北大学 41 吴彬 wubinbb 3 3 4 3突变 河北大学 42 吴彬 wubinbb 3 3 4 3突变 对产生的新子树的要求新子树产生的方法与原树产生方法相同 新子树添加后树的深度小于允许的最大深度 或新子树深度小于某一深度 最大突变深度 河北大学 43 吴彬 wubinbb 其他突变方法 点突变排列突变主从突变扩张突变收缩突变 河北大学 44 吴彬 wubinbb 点突变 点突变 河北大学 45 吴彬 wubinbb 排列突变 排列突变 河北大学 46 吴彬 wubinbb 主从突变 主从突变 河北大学 47 吴彬 wubinbb 扩张突变 扩张突变 河北大学 48 吴彬 wubinbb 收缩突变 收缩突变 河北大学 49 吴彬 wubinbb 3 3 5终止 1 指定最大进化代数 2 对于某些目标明确的问题 可以用 误差要求 作为