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

2011 5 之来龙去脉 广西师范学院科学计算与智能信息处理广西高校重点实验室 GeneExpressionProgramming 2020 1 24 2 创始人 CandidaFerreira于1995年在里斯本大学获得生物学博士后 一直从事与生物基因和生物化学相关的研究 当时遗传算法 GA 和遗传编程 GP 已日臻成熟 在生物基因表达的启示下 她融合了GA和GP的优点 经过五年时间的酝酿 终于使得GEP瓜熟蒂落 实现了又一次跨学科的革新 2020 1 24 3 引入国内 川大数据库与知识工程研究所的研究团队的博士生们 特别是左劼博士 在FerreiraC原创性论文在网上出现10多天 尚未正式发表时 以特有的兴趣和学术敏感 捕捉了机会 把GEP引入到国内 在国际会议WAIM2002上 左劼 唐常杰等发表了国内学者第一篇关于GEP的研究论文 在元昌安教授带领的广西师范学院 科学计算与智能信息处理 研究团队中 各个成员在汲取GEP带来的甘露 同时也在收获着丰硕的果实 2020 1 24 4 一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用 2020 1 24 5 GEP基本概念 GEP GeneExpressionProgramming 基因表达式编程GEP是借用了生命科学中基因 染色体等概念和思路 通过遗传进化进行数据挖掘 公式发现 以及最优化的一种新算法 GEP是在数据挖掘的沃土中 从遗传计算这棵老树上开出的新花 2020 1 24 6 基因是构成染色体的基本单位 知识点 知识基因 基因 sqrt 1 a b c d sin x cos x 基因分类函数符 运算符 函数 例如 sqrt sin x cos x 终结符 变量 常量 例如 a b c d 1 基因 2020 1 24 7 基因是构成染色体的基本单位 知识点 知识基因 基因 sqrt 1 a b c d sin x cos x 基因分类函数符 运算符 函数 例如 sqrt sin x cos x 终结符 变量 常量 例如 a b c d 1 基因 不仅仅是01位串 2020 1 24 8 基因是构成染色体的基本单位 知识点 知识基因 基因 sqrt 1 a b c d sin x cos x 基因分类函数符 运算符 函数 例如 sqrt sin x cos x 终结符 变量 常量 例如 a b c d 1 基因 2020 1 24 9 基因 在GEP中 有两个主体 染色体和表达式树 遗传信息在染色体中 而表达式树则是染色体的表达 从染色体到表达式树的解码过程称为翻译 GEP的基因码是染色体与其所表示的函数与终结符之间一对一的关系 翻译的规则决定了函数与终结符在表达式树中的空间位置以及在复合系统中子表达式树之间的交互类型在GEP中 基因组或染色体是一个线性的固定长度的符号串 是不同形状和大小的表达式树的编码 GEP的基因与生物基因的ORF OpenReadingFrame 的形式相似 而GEP基因的起始点总是第一个符号 终止点并不一定是最后一个符号 终止点后的符号组成GEP基因的非编码区 2020 1 24 10 终结符 终结符是提供给系统值的最末端结构 终结符自己提供信息 但不处理另外的信息 通常 终结符包括GEP程序中的输入 常量或者无参数函数 如果用树形结构来表示程序 终结符代表树的这些叶节点 当程序运行的时候 这些叶节点要么接受外部的输入 要么自己就是一个常量或者自己就能计算产生一个量 它们向系统中提供信息 以供系统处理 通常用T或者TGEP表示一个GEP算法的终结符集合 用t T表示终结符集合中的终结符 2020 1 24 11 函数 GEP中的函数概念相当广泛 它包括系统的中其他任何非终结符的中间结构 函数集合可以包括与应用有关的问题领域的运算符号 也可以包括程序设计语言中的程序构件 甚至是表示系统中间层次的一种符号 如果用树形结构来表示程序 函数一般位于表达式树的非叶节点 2020 1 24 12 函数 续 对于常见的以公式发现为目标的应用中 以下是一些常见的函数 算术运算符 例如 等 初等数学函数 例如sin cos等 其他一些函数 例如max min等 布尔运算符 例如 等 关系运算符 例如 等 条件运算符 if then else 自定义函数 2020 1 24 13 函数 续 通常用F或FGEP表示一个GEP算法的终结符 函数符号 集合 每一个函数f F记为f p1 p2 pm 其参数个数记为 f m函数参数的最大个数为函数集合中所有函数的参数个数的最大值 记为 F max f f F 2020 1 24 14 基因组 Genome 多个基因按照一定规则构成的基因串 称为基因组 实例参数 头长h 函数符 终结符 a b 0123456 abaaa结构头部函数符 终结符尾部终结符规则t h n 2020 1 24 15 基因组 Genome 多个基因按照一定规则构成的基因串 称为基因组 实例参数 头长h 函数符 终结符 a b 0123456 abaaa结构头部函数符 终结符尾部终结符规则t h n 2020 1 24 16 基因组 Genome 多个基因按照一定规则构成的基因串 称为基因组 实例参数 头长h 函数符 终结符 a b 0123456 abaaa结构头部函数符 终结符尾部终结符规则t h n 2020 1 24 17 基因组 Genome 多个基因按照一定规则构成的基因串 称为基因组 实例参数 头长h 函数符 终结符 a b 0123456 abaaa结构头部函数符 终结符尾部终结符规则t h n 2020 1 24 18 基因组 Genome 多个基因按照一定规则构成的基因串 称为基因组 实例参数 头长h 函数符 终结符 a b 0123456 abaaa结构头部函数符 终结符尾部终结符规则t h n 例 n 2 2020 1 24 19 染色体 Chromosome 一个或多个基因组构成一个染色体 单基因组染色体实例 abaaa 多基因组染色体实例 abaaa bbabb bbbba 多个基因按照一定规则构成的基因串 称为基因组 2020 1 24 20 染色体 Chromosome 一个或多个基因组构成一个染色体 单基因组染色体实例 abaaa 多基因组染色体实例 abaaa bbabb bbbba 2020 1 24 21 染色体构成 基因基因组染色体 数学表达式 2020 1 24 22 染色体 基因基因组染色体 数学表达式 2020 1 24 23 染色体 基因基因组染色体 数学表达式 2020 1 24 24 染色体数学表达式 解析过程 染色体表达式树 ET 数学表达式 2020 1 24 25 染色体数学表达式 解析过程 染色体表达式树 ET 数学表达式 2020 1 24 26 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 0123456 2020 1 24 27 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 0123456 2020 1 24 28 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 0123456 2020 1 24 29 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 为两目运算 0123456 2020 1 24 30 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 0123456 2020 1 24 31 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 0123456 2020 1 24 32 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 0123456 2020 1 24 33 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 直到叶结点全为终结符 b a a 表示怎样一个表达式 0123456 2020 1 24 34 单基因单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 b a a 2020 1 24 35 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 b a a 2020 1 24 36 单基因组染色体的解析 单基因组染色体 abaaa表达式 树 解析规则 从上到下 从左到右 b a a 2020 1 24 37 GEP基因的非编码区 GEP基因长度是固定的 但K 表达式的长度一般是等于或小于基因的长度 从上面的例子可以看出 K 表达式的结束子在位置4 从位置5到位置6都是基因的非编码区 基因的非编码区是GEP演化的关键 正是因为它 才使得对基因组使用任何遗传操作成为可能 abaaa看下面的例子 0123456 2020 1 24 38 对应的表示树为 K 表达式 0123456789012345678901234567890 b a aQab b babbabbbababbaaa 表示树的结束点在7 而基因的结束位置在30 终结符组成的非编码区长度为23 对编码区做变异操作 将位置6的符号 Q 变成 现在K 表达式为 0123456789012345678901234567890 b a a ab b babbabbbababbaaa对应的表示树为 2020 1 24 39 如果变异发生在位置5 符号 a 变成 K 表达式变为 0123456789012345678901234567890 b a Qab b babbabbbababbaaa对应的表达式树为 K 表达式 0123456789012345678901234567890 b a aQab b babbabbbababbaaa 2020 1 24 40 变异也有可能使得表达式树变小 如 假设变异发生在位置2 符号 变成 Q K 表达式变为 0123456789012345678901234567890 bQa aQab b babbabbbababbaaa它对应的表达式树为 K 表达式 0123456789012345678901234567890 b a aQab b babbabbbababbaaa 2020 1 24 41 在GEP中 变化的不是基因的长度 而是ORF的长度 所以尽管基因的长度是固定的 但其对应的表达式树却有着不同的大小和形状 最简单的情况是 当基因的第一个元素来自于终端符号集T中 此时ORF的长度为1 当基因头部的所有元素均来自于函数符号集F 且对应的操作数均为最大操作数时 则ORF长度达到最大 与基因的长度相等 2020 1 24 42 复合染色体 GEP的复合染色体 是指一个染色体包含多个等长的基因 设计一个问题的染色体时 其中基因的数目 基因的头部长度是要优先考虑的 复合染色体的每个基因的编码区对应一个子表示树 这些子表示树相互影响而形成一个更复杂的实体 关注的问题 如何从复合染色体中的各个基因构造各自的表示树 2020 1 24 43 例 有一长度为39的染色体 其中包含3个基因 每个基因长度为13 头部长度为6 如下 012345678901201234567890120123456789012 Qb bbbabab a QbQbbababa ba bbaaaaa为清晰起见 每个基因的起始点都定位0 这个起始点也是子表示树的第一个符号 每个子表示树的结束点在表示树中非常清楚 AsshowninFigure thefirstORFendsatposition9 sub ET1 thesecondORFendsatposition6 sub ET2 andthelastORFendsatposition2 sub ET3 2020 1 24 44 总之 GEP的染色体包含多个ORF 每个ORF是一个子表示树的结构化和函数化编码 在进化过程中 子表示树或者按它们各自的适应度被选取 或者这些子表示树组合成更复杂的复合子表示树 按总体的适应度被选取 如前所述 GEP的染色体可以隐含着不同的表示树的结构 以这些结构编码的个体的复杂程度各不相同 大致有以下三种情况 1 最简单的情况 一个个体只有一个基因 与它对应的表示树也只有一个 2 个体中有多个基因 每个基因各表示不同的子表示树结构 这些子表示树结构用一种特殊的连接函数连接起来 3 染色体对应着不同的子表示树 每一个子表示树对应着求解问题的一个解 2020 1 24 45 当基因组中有多个基因 而每一个基因都能独立的翻译为一个子表示树时 则有两种情况需要讨论 1 所有的子表示树被一种特殊的连接函数直接连接起来 2 这些子表示树没有被直接连接 但它们都表示某个具体问题的解 例 包含多个基因的染色体 情况1 012345678901234567890123456789AOaabaaaabNabaaaaaabINNbababaa 将三个基因对应的子表示树如下 一般情况下 这些子表示树可以通过特殊连接函数符号连接成为一个更大的表示树 如果使用AND或OR作为连接函数 则得到两个不同的复合表示树 代表了两个不同的程序 在这个例子中 遗传信息的翻译从构造子表示树开始 到将所有子表示树连接起来结束 2020 1 24 46 例 包含多个基因的染色体 情况2 下面是分类问题的一个染色体 其中包含三个基因 每个基因表示一种类型 012345678901201234567890120123456789012 dac dacaccd aacbbbabcd d c dbdbacd 对应的子表示树如下 三个表示树 每一个都代表一个代数式 假设在分类任务中 为了便于处理 规定当子表示树的输出小于某个阈值时则转换为0 否则转换为1 则这些子表示树可以按下面的公式决定分类 IF Sub ET1 1ANDSub ET2 0ANDSub ET3 0 THENClass1 IF Sub ET1 0ANDSub ET2 1ANDSub ET3 0 THENClass2 IF Sub ET1 0ANDSub ET2 0ANDSub ET3 1 THENClass3 2020 1 24 47 一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用 2020 1 24 48 GEP与GA GP的关系 GEP继承了GA的快速 易用和GP的易变 多能比GA GP提高速度100 1000000倍 GA特点 线性定长简单编码解决简单问题 GP特点 不定长非线性树结构复杂编码解决复杂问题 GEP特点 线性定长 非线性树结构简单编码解决复杂问题 2020 1 24 49 GEP与GA GP的关系 GEP继承了GA的快速 易用和GP的易变 多能GEP比GA GP提高速度100 1000000倍 GA特点 线性定长简单编码解决简单问题 GP特点 不定长非线性树结构复杂编码解决复杂问题 GEP特点 线性定长 非线性树结构简单编码解决复杂问题 2020 1 24 50 GEP与GA GP的关系 GEP继承了GA的快速 易用和GP的易变 多能GEP比GA GP提高速度100 1000000倍 GA特点 线性定长简单编码解决简单问题 GP特点 不定长非线性树结构复杂编码解决复杂问题 GEP特点 线性定长 非线性树结构简单编码解决复杂问题 2020 1 24 51 一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用 2020 1 24 52 GEP发展状况 2000 2002草创阶段2002 2003开始普及阶段2004 至今深入研究阶段 2020 1 24 53 第一阶段2000 2002 F Candida开创论文网上发表2000 12正式发表2001 122002 1第一本专著正式出版 基本概念基因 染色体 K 表达式 适应度评估函数 大量的探索性研究 如 太阳黑子预测 函数发现 逻辑电路设计 模拟神经网络等等特点 一花独放 基于实验 2020 1 24 54 第二阶段2002 2003开始普及 开始受到关注基于GEP的分类ChiZhou PeterC Nelson WeiminXiao andThomasM Tirpak DiscoveryofClassificationRulesbyUsingGeneExpressionProgramming InProceedingsoftheInternationalConferenceonArtificialIntelligence pages1355 1361 LasVegas USA 2002 paper基于GEP的关联规则ZuoJie TangChangjieandZhangTianqing MiningPredicateAssociationRulebyGeneExpressionProgramming WAIM02 InternationalConferenceforWebInformationAge2002 LNCS LectureNotesInComputerscience Vol 2419 pp 92 103 editedby SpringerVerlagBerlingHeidelberg2002 8 ISBN 2020 1 24 55 第二阶段2002 2003开始普及 一维混沌映射YorickHardy GeneExpressionProgrammingandOne DimensionalChaoticMaps InternationalJournalofModernPhysicsC 2002Vol 13 1 13 24 2020 1 24 56 第三阶段2004 至今研究深入 研究者增多 研究工作比较深入用GEP进行时间序列预测挖掘微分方程探讨了GEP中的常数探讨了收敛性分析问题探讨了各种改进算法探讨了基于GEP的智能模型库系统的实现等等 2020 1 24 57 第三阶段2004 至今研究深入 ZuoJie TangChangjie LiChuan YuanChang anandChenAn long TimeSeriesPredictionbasedonGeneExpressionProgramming WAIM04 InternationalConferenceforWebInformationAge2004 LNCS LectureNotesInComputerscience Vol 3129 55 64 讨论了两种新的基于GEP的时间序列模型构造方法 一种是传统的滑动窗口预测法 GEP SWPM 即找到在一个窗口大小内的前后数据之间的函数关系 然后使用该关系来进行预测 另外一种则是通过分析整个测试数据 建立关于时间序列的微分方程 然后通过该微分方程进行预测 GEP DEPM 2020 1 24 58 第三阶段2004 至今研究深入 段磊 唐常杰 左劼 元昌安等 基于基因表达式编程的抗噪声数据的函数挖掘方法 计算机研究与发展 2004 41 10 1684 1689 EI收录 借鉴生物具有的趋利避害 seekadvantage avoiddisadvantage 天性 提出了 弱适应模型 Weak AdaptiveModel 设计了在弱适应模型下基于相对误差计算适应度的算法 REFA 2020 1 24 59 第三阶段2004 至今研究深入 黄晓冬 唐常杰 李智等 基于基因表达式编程挖掘函数关系 软件学报 增刊 2004 15 suppl 96 105提出并实现了任意维定义域上的一致表达式和分域表达式的挖掘方法 提出了GEP UEM 一致函数表达式的挖掘 算法和GEP MEM 分域函数表达式挖掘 算法以及GEP BDM 二域式挖掘 算法 从而实现了分段函数的挖掘 2020 1 24 60 第三阶段2004 至今研究深入 张欢 唐常杰 余弦 等 基于转基因技术的基因表达式编程 EB OL 中国科技论文在线 教育部 张欢唐常杰余弦乔少杰汪锐左劼 基于转基因技术的基因表达式编程 GeneExpressionProgrammingBasedonTransgenesisTechnology 计算机科学2005 增刊 p278 280提出了基于转基因技术的基因表达式编程方法 通过注入转基因 引导进化方向 控制知识发现过程 2020 1 24 61 第三阶段2004 至今研究深入 彭京 唐常杰 元昌安等 基于重叠表达的多基因进化算法 EB OL 中国科技论文在线 教育部 JingPeng Chang jieTang JingZhang Chang anYuan EvolutionaryAlgorithmBasedonOverlappedGeneExpression ICNC2005 LNCS3612 pp 194 204 2005 pp 194 204 2005IDSNumber BDA32SCI检索号000232246700023 对基于重叠表达的多基因进化算法进行了研究 借鉴生物基因片段重叠表达 引入重叠基因概念 节约了表达空间 2020 1 24 62 第三阶段2004 至今研究深入 M GEP 基于多层染色体基因表达式编程的遗传进化算法 彭京 唐常杰李川 胡建军 计算机学报 Vol 28No 9 Sept 2005 p1459 1466 EIAccessionNumber 05419405741 该文提出了一种新的基于多层染色体基因表达式编程的遗传进化算法M GEP 新算法引入了多层染色体的概念 利用染色体构建的层次调用模型对个体进行表达 在解决实际函数发现 电路进化等实际问题中取得了良好效果 该文主要贡献包括 1 提出了基于多染色体的基因表达式编程算法 M GEP 2 建立了不同染色体的层次调用模型及存储结构 3 提出并实现了基于染色体的重组算子和基因随机重组算子 对多基因GEP和单基因GEP的对比实验结果表明 平均进化辈数仅为后者的29 81 2020 1 24 63 第三阶段2004 至今研究深入 贾晓斌 唐常杰 左劼 陈安龙 段磊 汪锐 基于基因表达式编程的频繁函数集挖掘 计算机学报 Vol 28 No 8Aug 2005p1247 1254 EIAccessionnumber 05359331320作者做了如下工作 提出了描述能力更强的频繁函数集FFS概念 提出并实现了基于基因表达式编程的频繁函数集挖掘算法FFSM 算法中采用了精度阈值队列策略PTQ 有效地提高了FFSM的成功率 用实验证实了FFS更强的描述能力和PTQ的有效性 其中FFS在挖掘高精度复杂函数时PTQ使FFS的成功率提高了55倍 2020 1 24 64 第三阶段2004 至今研究深入 谢方军唐常杰元昌安左劼陈安龙 基于基因表达式的演化硬件进化和优化算法 计算机辅助设计与图形学报 Vol 17 No 17p1415 1420 2005 7EIAccessionnumber 05319278321本文针对电路进化设计作了如下工作 1 融合了数据挖掘 基因表达式编程 GeneExpressionProgramming GEP 与传统电路进化技术 提出两阶段电路进化方法 该方法包括基于ETGP ExpressTreeGeneticProgramming 进化算法的电路进化阶段和基于MFDC MiningFrequencyDigitalCircuit 算法的电路优化阶段 2 给出了详尽的实验 实验表明6次多项式函数发现的平均进化代数为442代 乘法器电路的平均进化代数为2292代 比CGP CertainGeneticProgramming NEHF NovelEvolvableHardwareFramework 快6倍以上 用MFDC对乘法器电路进化结果进行挖掘后 得到了比传统电路更有效的乘法器电路 2020 1 24 65 第三阶段2004 至今研究深入 钟义啸 唐常杰 陈宇 等 提高基因表达式编程发现知识效率的回溯策略 EB OL 中国科技论文在线 教育部 钟义啸 唐常杰 陈宇 段磊 魏大刚 提高基因表达式编程发现知识效率的回溯策略 四川大学学报Vol 43 No 2pp299 304 2006 4 ZhongYixiao TangChangjie ChenYu DuanLei WeiDagang ImproveKDDEfficiencyofGeneExpressionProgrammingbyBacktrackingStrategy JournalofSichaunUniversiry NaturalScienceEdition Vol 43 No 2pp299 304 2006 4 通过回溯策略 对提高基因表达式编程发现知识效率进行了研究 借鉴生物 返祖现象 引入回溯检查点概念和可回溯GEP算法 设计了等比递增检查点序列和加速递增检查点序列 约束回溯过程 2020 1 24 66 第三阶段2004 至今研究深入 元昌安 唐常杰 左劼等 基于基因表达式编程的函数挖掘 收敛性分析与残差制导进化算法 四川大学学报 工程科学版 2004 36 6 100 105 EI收录 Chang anYuan Chang jieTang Yuan guangWen JieZuo JingPeng Jian junHu CONVERGENCYOFGENETICREGRESSIONINDATAMININGBASEDONGENEEXPRESSIONPROGRAMMINGANDOPTIMIZEDSOLUTION InternationalJournalofComputersandApplications国际杂志录用提出了残差制导进化算法 RGEA 算法的主要思想是对GEP的遗传操作进行改进 以使下一代群体中残差平方和小于上一代最小残差平方的染色体个数尽可能多 算法对几种有可能产生比当前最佳染色体更好的个体的遗传操作 分配指标任务 即要求该遗传操作在每一代操作中生成的残差平方和小于上一代最小残差平方的染色体个数至少要达到规定的阈值 若没有完成 则在本代遗传操作中调整其遗传率 重新进行遗传操作 2020 1 24 67 第三阶段2004 至今研究深入 元昌安 唐常杰等 基于基因表达式编程的智能模型库系统的实现 四川大学学报 工程科学版 2005 37 3 99 104 EIAccessionnumber 05269184570 IntelligentFunctionModelDiscoverySystemBaseduponGeneExpressionProgramming 将由杂志 JournalofComputationalInformationSystems 正刊发表 Ei收录 提出了显式智能模型 隐式智能模型 显式模型基因的概念 给出了基于GEP的隐式智能模型 ImplicitIntelligentModel IIM 的挖掘算法 GEP IIMA 在此基础上实现智能模型库系统 研究了隐式智能模型库 IIMB 系统与GIS的接口技术 IIMB是真正意义的无先验知识的智能模型库 其模型的类型和参数的求解均由程序自己来实现 2020 1 24 68 第三阶段2004 至今研究深入 改进初始种群生成策略 胡建军 李太勇博士分别在2007 和2010年提出相关改进改进GEP的编码方式 李川 彭昱忠等研究者提出改进 不用构建表达式树而直接解码求的表达式值的线性求解法 如 基于Scale的GEP 基于堆栈的GEPGEP中关于数值常量问题的研究 左劼 饶元和彭昱忠等研究者做了大量研究 如 由算法本身产生常数 在基因尾部附加DC域和直接将常量作为终结符 GEP与其他算法的融合神经网络陶俊剑 2010 邓松 2006 模拟退火饶元 2008 2020 1 24 69 关于GEP当前研究的着眼点主要集中在以下四个方面 用实验验证GEP各种遗传策略的效率 即对GEP进行 内部比较 针对解决问题的特性 提出了一系列新概念和新算法 将GEP技术应用于其他学科的研究中 探究多学科交叉融合方法及其用 对GEP的形式化和收敛性等进行理论分析和研究 旨在探讨GEP的机理 旨在理论上保证GEP方法的可靠性和可行性 2020 1 24 70 一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用 2020 1 24 71 输出最终目标 随机产生初始染色体Chromosomes 染色体 表达式树 ET 评价表达式树 新一代染色体 遗传操作复制 变异 重组等 Yes No 已经进化到最终目标 GEP算法过程 用轮盘赌进行选择 2020 1 24 72 输出最终目标 随机产生初始染色体Chromosomes 染色体 表达式树 ET 评价表达式树 新一代染色体 遗传操作复制 变异 重组等 Yes No 已经进化到最终目标 GEP算法过程 用轮盘赌进行选择 GEP特色 2020 1 24 73 输出最终目标 随机产生初始染色体Chromosomes 染色体 表达式树 ET 评价表达式树 新一代染色体 遗传操作复制 变异 重组等 Yes No 已经进化到最终目标 GEP算法过程 用轮盘赌进行选择 算法收敛的关键 2020 1 24 74 评价个体 对表达式评价就是要评测表达式计算得到的数据和训练数据的符合程度 基于绝对误差的适应度函数基于相对误差的适应度函数 其中 M是一个常数 表示选择的带宽 在这个范围内种群开始进化 C i j 表示根据第i个染色体对应的函数表达式利用第j个样本中的变量数据求得的函数值 T j 表示第j个样本中包含的实际测量得到的该目标函数的真实值 Ct表示样本的数目 显然 当C i j T j 时适应度函数的取值将取得最大fi fmax Ct M 2020 1 24 75 评价个体 由于用绝对误差并不能完全评价近似值的精确度 而相对误差不仅能表示出绝对误差来 而且在估计近似值运算结果的误差时 比绝对误差更能反映出误差的特性 所以在GEP中基于误差的适应度计算普遍采用第二个公式 对于更加复杂的问题可以使用以下的适应度函数 n是适应度实例正确地被评估的数量 Ct是适应度实体的总数 问题的解决很大程度上取决于适应度函数的设计方式 2020 1 24 76 选择 在GEP中 个体由轮盘赌转轮采样选择 戈尔登伯格GOLDBERG1989 每个个体根据它的适应度的按比例得到一个轮盘赌转轮的切片 然后转轮转动的次数达到能够使个体在群体中满足群体大小从一代到另一代维持进化 可能在一些文献中发现其它选择模式 但是最普遍的是使用 轮盘赌 决定论 和锦标赛方法选择 2020 1 24 77 进化操作 复制遗传算子 2020 1 24 78 复制 选择算子根据适应度和比例选择 赌轮选择方法 来随机确定下一代的个体 复制算子只复制选择算子所选择的个体 这些个体组成了下一代的初始群体 2020 1 24 79 复制 例子 0代的0号个体是有最大适应度值的个体之一它有两个后代其一是1号个体其二是3号个体均是通过选择复制产生的个体 2020 1 24 80 复制如果只是进行选择和复制 到13代之后 群体失去了多样性 所有的个体都是同一个个体的后代 复制和选择一样不会产生基因的多样性他们的作用只是基因的转移但是实际世界中生物是存在基因的变异 2020 1 24 81 变异 生物的变异在生物的遗传和自然进化过程中 其细胞的分裂和复制环节有可能会因为某些偶然的因素的影响而产生一些复制差错 这样就会使某些基因发生某种变异 所以GEP中也引入了变异 从而产生新的个体 考虑到基因的长度 GEP的变异率要远远大于自然界的变异率 2020 1 24 82 变异定义 在单个染色体上 对染色体的每一位进行随机测试 如果满足变异的概率 则重新产生该位的编码 由于要保持染色体的结构所以 头部变异时可以选择所有的符号尾部变异时只能选择终结符因为尾部是只是终结符组成这是与GA的不同之处 GA的变异是不分头和尾的 2020 1 24 83 变异 01234560123456ANbbabcAOcaabc 6AabbabcAOcbabc 8父代有两处发生了变异染色体结构的变化 2020 1 24 84 Neutral变异 中立 变异操作对基因结构不会产生影响 2020 1 24 85 插串 插串是GEP所特有的遗传算子 它随机在基因中选择一段子串 然后将该子串插入到头部的随机指定的一个位置 但不能是第0个位置 将头部的其他符号向后顺延 超过头部长度的编码将被截去 2020 1 24 86 插串 01234567890123456 a b bbbabbaab01234567890123456 a bab bbbbabbaab它选择了第10 12位置的编码插入到第3个位置父染色体中的第567位置的编码被截掉了 2020 1 24 87 根插串 插串算子不允许将选择的串插入到第0个位置 而根插串算子则是专门将选择的子串插入到第0个位置 根插串算子从头部的随机选择的一个位置开始向后扫描 找到第一个函数 然后以该位置为起始 选择一段子串 将该子串插入到第0个位置 头部编码依次后移 超过头部的部分被截去 如果扫描过程没有找到函数 则不做任何事情 01234567890123456 a b bbbabbaab01234567890123456 b a bbbbabbaab它选择了第345位置的编码插入到第1个位置 父染色体中的第567位置的编码被截掉 2020 1 24 88 基因插串 顾名思义 随机选择一个基因 把整个基因插到染色体的头部 其余的基因依次顺延 超出的基因被删除 所有的遗传操作中只有基因插串能够移动一个完整的基因 012345601234560123456AabcaacOObbacaNaaaaccNaaaaccAabcaacOObbaca 2020 1 24 89 One pointrecombination 单点重组 单点重组作用在两个父代染色体上 随机选择一个交叉位置 互换交叉点后面的染色体部分 得到两个子代染色体 01234567890123456P1 a b bbbabbaabP2 a a b aabbababa 01234567890123456P1 a b bbbabbaabP2 a a b aabbababa 2020 1 24 90 One pointrecombination 01234567890123456P1 a b bbbabbaabP2 a a b aabbababa 01234567890123456S1 a a b aabbababaS2 a b bbbabbaab 2020 1 24 91 One pointrecombination 2020 1 24 92 One pointrecombination 2020 1 24 93 One pointrecombination 2020 1 24 94 One pointrecombination A要求两个运算符 N只要一个运算符 2020 1 24 95 One pointrecombination 按照K 表达式的方法重组 按照K 表达式的方法重组 2020 1 24 96 Two pointrecombination 双点重组 双点重组也是作用在两个父代染色体上 在染色体上随机选择两个交叉点 然后互换交叉点之间的染色体部分 2020 1 24 97 Two pointrecombination 01234567890123456P1 a b bbbabbaabP2 a a b aabbababa 2020 1 24 98 01234567890123456P1 a b bbbabbaabP2 a a b aabbababa Two pointrecombination 2020 1 24 99 01234567890123456S1 a a b aababbaabS2 a b bbbbababa 01234567890123456P1 a b bbbabbaabP2 a a b aabbababa Two pointrecombination 2020 1 24 100 Generecombination 基因重组 基因重组只作用于多基因的染色体 随机选择一个基因 然后交换两个父代染色体的相对因的基因 2020 1 24 101 AcaabbcabAOaAcbbcb AOaaaabacAbbObcaba NNOAcbbbc NONNbcbbb Generecombination 012345678012345678012345678 2020 1 24 102 一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用 2020 1 24 103 SolvingasimpleproblemwithGEP 目标公式 定义域 10 10 2020 1 24 104 SolvingasimpleproblemwithGEP 选用的适应度公式 绝对误差 2020 1 24 105 SolvingasimpleproblemwithGEP 观测值 2020 1 24 106 SolvingasimpleproblemwithGEP GEP参数 2020 1 24 107 SolvingasimpleproblemwithGEP 实验结果 2020 1 24 1