GEP的来龙去脉PPT系统学习.ppt

* * 第三阶段　 2004-至今　研究深入 改进初始种群生成策略。 胡建军、李太勇博士分别在2007，和2010年提出相关改进 改进GEP的编码方式。 李川、彭昱忠等研究者提出改进，不用构建表达式树而直接解码求的表达式值的线性求解法。如，基于Scale 的GEP、基于 堆栈的GEP GEP中关于数值常量问题的研究。 左劼、饶元和彭昱忠等研究者做了大量研究。如，由算法本身产生常数，在基因尾部附加DC域和直接将常量作为终结符。 GEP与其他算法的融合 神经网络 陶俊剑（2010）、邓松（2006） 模拟退火 饶元（2008） * * 关于GEP当前研究的着眼点主要集中在以下四个方面 用实验验证GEP各种遗传策略的效率, 即对GEP进行”内部比较”。 针对解决问题的特性,提出了一系列新概念和新算法。 将GEP技术应用于其他学科的研究中,探究多学科交叉融合方法及其用。 对GEP的形式化和 收敛性等进行理论分析和研究，旨在探讨GEP的机理，旨在理论上保证GEP方法的可靠性和可行性。 * * 一　GEP基本概念 二　GEP特点 三　GEP研究状况 四　GEP算法过程 五 简单应用　 　 * * 输出最终目标 随机产生初始染色体 Chromosomes 染色体 ? 表达式树（ET） 评价 表达式树　 新一代 染色体 遗传操作 复制，变异， 重组等 Yes No 已经进化到最终目标? GEP算法过程 用轮盘赌进行选择 进化操作 * * 输出最终目标 随机产生初始染色体 Chromosomes 染色体 ? 表达式树（ET） 评价 表达式树　 新一代 染色体 遗传操作 复制，变异， 重组等 Yes No 已经进化到最终目标? GEP算法过程 用轮盘赌进行选择 GEP特色 * * 输出最终目标 随机产生初始染色体 Chromosomes 染色体 ? 表达式树（ET） 评价 表达式树　 新一代 染色体 遗传操作 复制，变异， 重组等 Yes No 已经进化到最终目标? GEP算法过程 用轮盘赌进行选择 算法收敛的关键 * * 评价个体 对表达式评价就是要评测表达式计算得到的数据和训练数据的符合程度。 基于绝对误差的适应度函数 基于相对误差的适应度函数 其中，M是一个常数，表示选择 的带宽，在这个范围内种群开始 进化；C(i,j)表示根据第i个染色体 对应的函数表达式利用第j个样本 中的变量数据求得的函数值；T( j) 表示第j个样本中包含的实际测量 得到的该目标函数的真实值；Ct 表示样本的数目。显然，当C(i,j) = T( j) 时适应度函数的取值将取 得最大 fi = fmax = Ct * M。 * * 评价个体 由于用绝对误差并不能完全评价近似值的精确度，而相对误差不仅能表示出绝对误差来，而且在估计近似值运算结果的误差时，比绝对误差更能反映出误差的特性，所以在GEP中基于误差的适应度计算普遍采用第二个公式。 对于更加复杂的问题可以使用以下的适应度函数: n 是适应度实例正确地被评估的数量, Ct 是适应度实体的总数。 问题的解决很大程度上取决于适应度函数的设计方式。 * * 选择 在GEP中, 个体由轮盘赌转轮采样选择(戈尔登伯格GOLDBERG 1989) 。每个个体根据它的适应度的按比例得到一个轮盘赌转轮的切片。然后转轮转动的次数达到能够使个体在群体中满足群体大小从一代到另一代维持进化。 可能在一些文献中发现其它选择模式,但是最普遍的是使用: 轮盘赌, 决定论, 和锦标赛方法选择 * * 进化操作 复制 遗传算子 * * 复制 选择算子根据适应度和比例选择（赌轮选择方法）来随机确定下一代的个体。 复制算子只复制选择算子所选择的个体。 这些个体组成了下一代的初始群体。 * * 复制 例子 0代的0号个体是有最大适应度值的个体之一 它有两个后代其一是1号个体 其二是3号个体 均是通过选择复制产生的个体 * * 复制如果只是进行选择和复制，到13代之后，群体失去了多样性。所有的个体都是同一个个体的后代。 复制和选择一样 不会产生基因的多样性 他们的作用只是基因的转移 但是实际世界中 生物是存在基因的变异 * * 变异 生物的变异 在生物的遗传和自然进化过程中，其细胞的分裂和复制环节有可能会因为某些偶然的因素的影响而产生一些复制差错， 这样就会使某些基因发生某种变异。 所以GEP中也引入了变异。从而产生新的个体。考虑到基因的长度，GEP的变异率要远远大于自然界的变异率。 * * 变异定义 在单个染色体上，对染色体的每一位进行随机测试，如果满足变异的概率，则重新产生该位的编码。 由于要保持染色体的结构所以： 头部变异时 可以选择所有的符