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

2011.52011.5广西师范学院广西师范学院广西师范学院广西师范学院科学计算与智能信息处理广西高校重点实验室科学计算与智能信息处理广西高校重点实验室科学计算与智能信息处理广西高校重点实验室科学计算与智能信息处理广西高校重点实验室GeneExpressionProgramming2024/2/262024/2/26周周一一2 2创始人Candida FerreiraCandida Ferreira 于于19951995年年在里斯本大学在里斯本大学获获得生物学博士后，得生物学博士后，一直从事与生物基因和生物化学相一直从事与生物基因和生物化学相关的研究，当关的研究，当时遗传时遗传算法（算法（GAGA）和）和遗遗传编传编程（程（GPGP）已日臻成熟。在生物基）已日臻成熟。在生物基因表达的启示下，她融合了因表达的启示下，她融合了GAGA和和GPGP的的优优点，点，经过经过五年五年时间时间的的酝酿酝酿，终终于使得于使得GEPGEP瓜熟蒂落，瓜熟蒂落，实现实现了又一了又一次跨学科的革新。次跨学科的革新。2024/2/262024/2/26周周一一3 3引入国内川大数据库与知识工程研究所的研究团队的博士生们，特别是左劼博士，在FerreiraC原创性论文在网上出现10多天，尚未正式发表时，以特有的兴趣和学术敏感，捕捉了机会，把GEP引入到国内，在国际会议WAIM2002上，左劼、唐常杰等发表了国内学者第一篇关于GEP的研究论文。在元昌安教授带领的广西师范学院“科学计算与智能信息处理”研究团队中，各个成员在汲取GEP带来的甘露，同时也在收获着丰硕的果实。2024/2/262024/2/26周周一一4 4一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用2024/2/262024/2/26周周一一5 5GEP基本概念GEP（Gene Expression Programming）基因表达式编程基因表达式编程GEP是借用了生命科学中基因、染色体等概念和思路，通过遗传进化进行数据挖掘、公式发现，以及最优化的一种新算法。GEPGEP是在数据挖掘的沃土中，是在数据挖掘的沃土中，从从遗传计遗传计算算这这棵老棵老树树上开出的新花上开出的新花 2024/2/262024/2/26周周一一6 6 基因基因基因基因是构成染色体的是构成染色体的是构成染色体的是构成染色体的基本基本基本基本单单位位位位.知知知知识识点点点点(知知知知识识基因）基因）基因）基因）基因基因+,-,*,/,sqrt,1,a,b,c,d+,-,*,/,sqrt,1,a,b,c,d，sin(x),cos(x)sin(x),cos(x)基因分基因分基因分基因分类类函数符（运算符，函数）函数符（运算符，函数）例如：例如：+,-,*,/,sqrt+,-,*,/,sqrt，.,sin(x),cos(x).,sin(x),cos(x)终结终结符（符（变变量，常量）量，常量）例如：例如：a,b,c,da,b,c,d ，1.1.基因2024/2/262024/2/26周周一一7 7 基因基因基因基因是构成染色体的是构成染色体的是构成染色体的是构成染色体的基本基本基本基本单单位位位位.知知知知识识点点点点(知知知知识识基因）基因）基因）基因）基因基因+,-,*,/,sqrt,1,a,b,c,d+,-,*,/,sqrt,1,a,b,c,d，sin(x),cos(x)sin(x),cos(x)基因分基因分基因分基因分类类函数符（运算符，函数）函数符（运算符，函数）例如：例如：+,-,*,/,sqrt+,-,*,/,sqrt，.,sin(x),cos(x).,sin(x),cos(x)终结终结符（符（变变量，常量）量，常量）例如：例如：a,b,c,da,b,c,d ，1.1.基因不不仅仅仅仅是是0101位串位串2024/2/262024/2/26周周一一8 8 基因基因基因基因是构成染色体的是构成染色体的是构成染色体的是构成染色体的基本基本基本基本单单位位位位.知知知知识识点点点点(知知知知识识基因）基因）基因）基因）基因基因+,-,*,/,sqrt,1,a,b,c,d+,-,*,/,sqrt,1,a,b,c,d，sin(x),cos(x)sin(x),cos(x)基因分基因分基因分基因分类类函数符（运算符，函数）函数符（运算符，函数）例如：例如：+,-,*,/,sqrt+,-,*,/,sqrt，.,sin(x),cos(x).,sin(x),cos(x)终结终结符（符（变变量，常量）量，常量）例如：例如：a,b,c,da,b,c,d ，1.1.基因2024/2/262024/2/26周周一一9 9基因 在在GEP中，有两个主体：染色体和表中，有两个主体：染色体和表达式树，遗传信息在染色体中，而表达式达式树，遗传信息在染色体中，而表达式树则是染色体的表达。从染色体到表达式树则是染色体的表达。从染色体到表达式树的解码过程称为翻译。树的解码过程称为翻译。GEP的基因码是的基因码是染色体与其所表示的函数与终结符之间一染色体与其所表示的函数与终结符之间一对一的关系，翻译的规则决定了函数与终对一的关系，翻译的规则决定了函数与终结符在表达式树中的空间位置以及在复合结符在表达式树中的空间位置以及在复合系统中子表达式树之间的交互类型系统中子表达式树之间的交互类型 在在GEP中，基因组或染色体是一个线中，基因组或染色体是一个线性的固定长度的符号串，是不同形状和大性的固定长度的符号串，是不同形状和大小的表达式树的编码。小的表达式树的编码。GEP的基因与生物基因的的基因与生物基因的ORF(Open Reading Frame)的形式相似，而的形式相似，而GEP基因基因的起始点总是第一个符号，终止点并不一的起始点总是第一个符号，终止点并不一定是最后一个符号，终止点后的符号组成定是最后一个符号，终止点后的符号组成GEP基因的非编码区。基因的非编码区。2024/2/262024/2/26周周一一1010 终结终结符符符符 终结终结符是提供符是提供给给系系统值统值的最末端的最末端结结构。构。终结终结符自己提供信息符自己提供信息,但不但不处处理另外的信息。通常理另外的信息。通常,终结终结符包括符包括GEPGEP程序中的程序中的输输入、入、常量或者无参数函数。常量或者无参数函数。如果用如果用树树形形结结构来表示程序，构来表示程序，终结终结符代表符代表树树的的这这些些叶叶节节点。当程序运行的点。当程序运行的时时候，候，这这些叶些叶节节点要么接受外部点要么接受外部的的输输入、要么自己就是一个常量或者自己就能入、要么自己就是一个常量或者自己就能计计算算产产生生一个量。它一个量。它们们向系向系统统中提供信息，中提供信息，以供系以供系统处统处理。理。通常用通常用T T 或者或者T TGEPGEP 表示一个表示一个GEPGEP算法的算法的终结终结符集合，符集合，用用t t T T表示表示终结终结符集合中的符集合中的终结终结符。符。2024/2/262024/2/26周周一一1111 函数函数函数函数 GEPGEP中的函数概念相当广泛中的函数概念相当广泛,它包括系它包括系统统的中的中其他任何非其他任何非终结终结符的中符的中间结间结构。构。函数集合可以包括与函数集合可以包括与应应用有关的用有关的问题领问题领域的运域的运算符号算符号,也可以包括程序也可以包括程序设计语设计语言中的程序构件言中的程序构件,甚甚至是表示系至是表示系统统中中间层间层次的一种符号。次的一种符号。如果用如果用树树形形结结构来表示程序，函数一般位于表构来表示程序，函数一般位于表达式达式树树的非叶的非叶节节点。点。2024/2/262024/2/26周周一一1212 函数函数函数函数(续续)对对于常于常见见的以公式的以公式发现为发现为目目标标的的应应用中，用中，以下以下是一些常是一些常见见的函数的函数：算算术术运算符，例如运算符，例如+、-、*、等；等；初等数学函数，例如初等数学函数，例如sinsin，coscos 等等；其他一些函数其他一些函数，例如例如maxmax，min min 等；等；布布尔尔运算符，例如运算符，例如、等等;关系运算符关系运算符,例如例如 、=、等；等；条件运算符，条件运算符，if-then-elseif-then-else；自定自定义义函数。函数。2024/2/262024/2/26周周一一1313 函数函数函数函数(续续)通常用通常用F F 或或F FGEPGEP 表示一个表示一个GEPGEP算法的算法的终结终结符符(函函数符号数符号)集合，集合，每一个函数每一个函数f f F F 记为记为 f f(p p1 1，p p2 2，,p pmm)其参数个数其参数个数记为记为 (f f)=)=mm 函数参数的最大个数函数参数的最大个数为为函数集合中所有函数的函数集合中所有函数的参数个数的最大参数个数的最大值值,记为记为 (F F)=max()=max(f f)|)|f f F F)2024/2/262024/2/26周周一一1414基因组（Genome）多个基因多个基因多个基因多个基因按照按照按照按照一定规则一定规则一定规则一定规则构成的基因串，称为构成的基因串，称为构成的基因串，称为构成的基因串，称为基因组基因组基因组基因组。实例实例实例实例参数：头长参数：头长h h，函数符，函数符+*/,终结符终结符a a，b b 0123456*+abaaa结构结构结构结构头部头部函数符终结符函数符终结符尾部尾部终结符终结符规则规则规则规则t th h（n n）2024/2/262024/2/26周周一一1515基因组（Genome）多个基因多个基因多个基因多个基因按照按照按照按照一定规则一定规则一定规则一定规则构成的基因串，称为构成的基因串，称为构成的基因串，称为构成的基因串，称为基因组基因组基因组基因组。实例实例实例实例参数：头长参数：头长h h，函数符，函数符+*/,终结符终结符a a，b b 0123456*+abaaa结构结构结构结构头部头部函数符终结符函数符终结符尾部尾部终结符终结符规则规则规则规则t th h（n n）2024/2/262024/2/26周周一一1616基因组（Genome）多个基因多个基因多个基因多个基因按照按照按照按照一定规则一定规则一定规则一定规则构成的基因串，称为构成的基因串，称为构成的基因串，称为构成的基因串，称为基因组基因组基因组基因组。实例实例实例实例参数：头长参数：头长h h，函数符，函数符+*/,终结符终结符a a，b b 0123456*+abaaa结构结构结构结构头部头部函数符终结符函数符终结符尾部尾部终结符终结符规则规则规则规则t th h（n n）2024/2/262024/2/26周周一一1717基因组（Genome）多个基因多个基因多个基因多个基因按照按照按照按照一定规则一定规则一定规则一定规则构成的基因串，称为构成的基因串，称为构成的基因串，称为构成的基因串，称为基因组基因组基因组基因组。实例实例实例实例参数：头长参数：头长h h，函数符，函数符+*/,终结符终结符a a，b b 0123456*+abaaa结构结构结构结构头部头部函数符终结符函数符终结符尾部尾部终结符终结符规则规则规则规则t th h（n n）2024/2/262024/2/26周周一一1818基因组（Genome）多个基因多个基因多个基因多个基因按照按照按照按照一定规则一定规则一定规则一定规则构成的基因串，称为构成的基因串，称为构成的基因串，称为构成的基因串，称为基因组基因组基因组基因组。实例实例实例实例参数：头长参数：头长h h，函数符，函数符+*/,终结符终结符a a，b b 0123456*+abaaa结构结构结构结构头部头部函数符终结符函数符终结符尾部尾部终结符终结符规则规则规则规则t th h（n n）例：例：+,-,*,/+,-,*,/n=2 n=22024/2/262024/2/26周周一一1919染色体(Chromosome)一个或多个基因组构成一个染色体。单基因组染色体实例：*+a+abaaabaaa 多基因多基因组组染色体染色体 实实例：例：*+a+a b a a ab a a a +/+/+b b a b b b a b b/b b/b b b b ab b b a 多个基因多个基因多个基因多个基因按照按照按照按照一定一定一定一定规则规则构成构成构成构成的基因串，称的基因串，称的基因串，称的基因串，称为为基因基因基因基因组组。2024/2/262024/2/26周周一一2020染色体(Chromosome)一个或多个基因组构成一个染色体。单基因组染色体实例：*+a+abaaabaaa 多基因多基因组组染色体染色体 实实例：例：*+a+a b a a ab a a a +/+/+b b a b b b a b b/b b/b b b b ab b b a 2024/2/262024/2/26周周一一2121染色体构成基因基因组染色体数学表达式？2024/2/262024/2/26周周一一2222染色体基因基因组染色体数学表达式？2024/2/262024/2/26周周一一2323染色体基因基因组染色体数学表达式？2024/2/262024/2/26周周一一2424染色体数学表达式解析过程：染色体表达式树（ET）数学表达式2024/2/262024/2/26周周一一2525染色体数学表达式解析过程：染色体表达式树（ET）数学表达式2024/2/262024/2/26周周一一2626单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一2727单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一2828单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一2929单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa*为为两目运算两目运算0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一3030单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一3131单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一3232单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一3333单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右，直到叶结点全为终结符。（b ba a）aa表示怎表示怎样样一一个表达式个表达式?0 1 2 3 4 5 0 1 2 3 4 5 6 62024/2/262024/2/26周周一一3434单基因单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右（b ba a）aa2024/2/262024/2/26周周一一3535单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右（b ba a）aa2024/2/262024/2/26周周一一3636单基因组染色体的解析单基因组染色体：*+abaaa表达式（树）解析规则：从上到下，从左到右（b ba a）aa2024/2/262024/2/26周周一一3737GEP基因的非编码区 GEPGEP基因长度是固定的，但基因长度是固定的，但基因长度是固定的，但基因长度是固定的，但K-K-表达式的长度一般是表达式的长度一般是表达式的长度一般是表达式的长度一般是等于或小于基因的长度，从上面的例子可以看出，等于或小于基因的长度，从上面的例子可以看出，等于或小于基因的长度，从上面的例子可以看出，等于或小于基因的长度，从上面的例子可以看出，K-K-表达式的结束子在位置表达式的结束子在位置表达式的结束子在位置表达式的结束子在位置4 4，从位置，从位置，从位置，从位置5 5到位置到位置到位置到位置6 6都是基因都是基因都是基因都是基因的非编码区。基因的非编码区是的非编码区。基因的非编码区是的非编码区。基因的非编码区是的非编码区。基因的非编码区是GEPGEP演化的关键，正演化的关键，正演化的关键，正演化的关键，正是因为它，才使得对基因组使用任何遗传操作成为可是因为它，才使得对基因组使用任何遗传操作成为可是因为它，才使得对基因组使用任何遗传操作成为可是因为它，才使得对基因组使用任何遗传操作成为可能。能。能。能。*+a+abaaabaaa看下面的例子：看下面的例子：看下面的例子：看下面的例子：0 1 2 3 4 5 60 1 2 3 4 5 62024/2/262024/2/26周周一一3838对应对应的表示的表示树为树为:K-K-表达式：表达式：01234567890123456789012345678900123456789012345678901234567890*b+a-aQab+/+b+*b+a-aQab+/+b+babbabbbababbaaababbabbbababbaaa 表示表示树树的的结结束点在束点在7 7，而基因的，而基因的结结束位置在束位置在3030。终结终结符符组组成的非成的非编码编码区区长长度度为为2323。对编码对编码区做区做变变异操作，将位置异操作，将位置6 6的符号的符号“Q”Q”变变成成“*”“*”，现现在在K-K-表达式表达式为为：01234567890123456789012345012345678901234567890123456789067890*b+a-a*b+a-a*a b+/a b+/+b+b+babbabbbababbaaababbabbbababbaaa对应对应的表示的表示树为树为：2024/2/262024/2/26周周一一3939如果变异发生在位置如果变异发生在位置5 5，符号，符号“a”a”变成变成“+”+”，K-K-表达式变为：表达式变为：01234567890123456789012345678900123456789012345678901234567890*b+a-*b+a-+Qab+/+b+Qab+/+b+babbabbbababbaaababbabbbababbaaa对应的表达式树为：对应的表达式树为：K-K-表达式：表达式：01234567890123456789012345678900123456789012345678901234567890*b+a-aQab+/+b+*b+a-aQab+/+b+babbabbbababbaaababbabbbababbaaa2024/2/262024/2/26周周一一4040变异也有可能使得表达式树变小，如：假设变异发生在位置变异也有可能使得表达式树变小，如：假设变异发生在位置2 2，符号，符号“+”+”变成变成“Q”Q”，K-K-表达式变为：表达式变为：01234567890123456789012345678900123456789012345678901234567890*b*bQ Qa-aQab+/+a-aQab+/+b+b+babbabbbababbaaababbabbbababbaaa它对应的表达式树为：它对应的表达式树为：K-K-表达式：表达式：01234567890123456789012345678900123456789012345678901234567890*b+a-aQa*b+a-aQab+/+b+babbabbbababbaaab+/+b+babbabbbababbaaa2024/2/262024/2/26周周一一4141在GEP中，变化的不是基因的长度，而是ORF的长度。所以尽管基因的长度是固定的，但其对应的表达式树却有着不同的大小和形状，最简单的情况是：当基因的第一个元素来自于终端符号集当基因的第一个元素来自于终端符号集T T中，中，此时此时ORFORF的长度为的长度为1 1。当基因头部的所有元素均来自于函数符号集当基因头部的所有元素均来自于函数符号集F F，且对应的操作数均为最大操作数时，则且对应的操作数均为最大操作数时，则ORFORF长长度达到最大，与基因的长度相等。度达到最大，与基因的长度相等。2024/2/262024/2/26周周一一4242复合染色体 GEPGEP的复合染色体，是指一个染色体包含多个等长的基因。设计一个问题的染色体的复合染色体，是指一个染色体包含多个等长的基因。设计一个问题的染色体的复合染色体，是指一个染色体包含多个等长的基因。设计一个问题的染色体的复合染色体，是指一个染色体包含多个等长的基因。设计一个问题的染色体时，其中基因的数目、基因的头部长度是要优先考虑的。复合染色体的每个基因的编时，其中基因的数目、基因的头部长度是要优先考虑的。复合染色体的每个基因的编时，其中基因的数目、基因的头部长度是要优先考虑的。复合染色体的每个基因的编时，其中基因的数目、基因的头部长度是要优先考虑的。复合染色体的每个基因的编码区对应一个子表示树，这些子表示树相互影响而形成一个更复杂的实体。码区对应一个子表示树，这些子表示树相互影响而形成一个更复杂的实体。码区对应一个子表示树，这些子表示树相互影响而形成一个更复杂的实体。码区对应一个子表示树，这些子表示树相互影响而形成一个更复杂的实体。关注的问题：如何从复合染色体中的各个基因构造各自的表示树？关注的问题：如何从复合染色体中的各个基因构造各自的表示树？关注的问题：如何从复合染色体中的各个基因构造各自的表示树？关注的问题：如何从复合染色体中的各个基因构造各自的表示树？2024/2/262024/2/26周周一一4343例：有一长度为例：有一长度为例：有一长度为例：有一长度为3939的染色体，其中包含的染色体，其中包含的染色体，其中包含的染色体，其中包含3 3个基因，每个基因长度为个基因，每个基因长度为个基因，每个基因长度为个基因，每个基因长度为1313，头部长度为，头部长度为，头部长度为，头部长度为6 6。如下：。如下：。如下：。如下：0 123456789 012 01234 56789012 01234567890120 123456789 012 01234 56789012 0123456789012 *Qb+*/*Qb+*/bbbababbbbabab-a+QbQ-a+QbQbbabababbababa/ba-/*/ba-/*bbaaaaabbaaaaa 为清晰起见，每个基因的起始点都定位为清晰起见，每个基因的起始点都定位为清晰起见，每个基因的起始点都定位为清晰起见，每个基因的起始点都定位0 0，这个起始点也是子表示树的第一个符号。每个子表示树的结，这个起始点也是子表示树的第一个符号。每个子表示树的结，这个起始点也是子表示树的第一个符号。每个子表示树的结，这个起始点也是子表示树的第一个符号。每个子表示树的结束点在表示树中非常清楚：束点在表示树中非常清楚：束点在表示树中非常清楚：束点在表示树中非常清楚：As shown in Figure,the first ORF ends at position 9(sub-ET1);the second As shown in Figure,the first ORF ends at position 9(sub-ET1);the second ORF ends at position 6(sub-ET2);and the last ORF ends at position ORF ends at position 6(sub-ET2);and the last ORF ends at position 2(sub-ET3).2(sub-ET3).2024/2/262024/2/26周周一一4444 总之，总之，总之，总之，GEPGEP的染色体包含多个的染色体包含多个的染色体包含多个的染色体包含多个ORFORF，每个，每个，每个，每个ORFORF是一个子表示树的结构化是一个子表示树的结构化是一个子表示树的结构化是一个子表示树的结构化和函数化编码。在进化过程中，子表示树或者按它们各自的适应度被选取，和函数化编码。在进化过程中，子表示树或者按它们各自的适应度被选取，和函数化编码。在进化过程中，子表示树或者按它们各自的适应度被选取，和函数化编码。在进化过程中，子表示树或者按它们各自的适应度被选取，或者这些子表示树组合成更复杂的复合子表示树，按总体的适应度被选取。或者这些子表示树组合成更复杂的复合子表示树，按总体的适应度被选取。或者这些子表示树组合成更复杂的复合子表示树，按总体的适应度被选取。或者这些子表示树组合成更复杂的复合子表示树，按总体的适应度被选取。如前所述，如前所述，如前所述，如前所述，GEPGEP的染色体可以隐含着不同的表示树的结构，以这些结构编码的个的染色体可以隐含着不同的表示树的结构，以这些结构编码的个的染色体可以隐含着不同的表示树的结构，以这些结构编码的个的染色体可以隐含着不同的表示树的结构，以这些结构编码的个体的复杂程度各不相同。大致有以下三种情况体的复杂程度各不相同。大致有以下三种情况体的复杂程度各不相同。大致有以下三种情况体的复杂程度各不相同。大致有以下三种情况；（1 1）最简单的情况，一个个体只有一个基因，与它对应的表示树也只有一个；最简单的情况，一个个体只有一个基因，与它对应的表示树也只有一个；最简单的情况，一个个体只有一个基因，与它对应的表示树也只有一个；最简单的情况，一个个体只有一个基因，与它对应的表示树也只有一个；（2 2）个体中有多个基因，每个基因各表示不同的子表示树结构，这些子表示树）个体中有多个基因，每个基因各表示不同的子表示树结构，这些子表示树）个体中有多个基因，每个基因各表示不同的子表示树结构，这些子表示树）个体中有多个基因，每个基因各表示不同的子表示树结构，这些子表示树结构用一种特殊的连接函数连接起来；结构用一种特殊的连接函数连接起来；结构用一种特殊的连接函数连接起来；结构用一种特殊的连接函数连接起来；（3 3）染色体对应着不同的子表示树，每一个子表示树对应着求解问题的一个解。）染色体对应着不同的子表示树，每一个子表示树对应着求解问题的一个解。）染色体对应着不同的子表示树，每一个子表示树对应着求解问题的一个解。）染色体对应着不同的子表示树，每一个子表示树对应着求解问题的一个解。2024/2/262024/2/26周周一一4545 当基因组中有多个基因，而每一个基因都能独立的翻译为一个子表示树时，则有两当基因组中有多个基因，而每一个基因都能独立的翻译为一个子表示树时，则有两当基因组中有多个基因，而每一个基因都能独立的翻译为一个子表示树时，则有两当基因组中有多个基因，而每一个基因都能独立的翻译为一个子表示树时，则有两种情况需要讨论：种情况需要讨论：种情况需要讨论：种情况需要讨论：（1 1）所有的子表示树被一种特殊的连接函数直接连接起来。）所有的子表示树被一种特殊的连接函数直接连接起来。）所有的子表示树被一种特殊的连接函数直接连接起来。）所有的子表示树被一种特殊的连接函数直接连接起来。（2 2）这些子表示树没有被直接连接，但它们都表示某个具体问题的解。）这些子表示树没有被直接连接，但它们都表示某个具体问题的解。）这些子表示树没有被直接连接，但它们都表示某个具体问题的解。）这些子表示树没有被直接连接，但它们都表示某个具体问题的解。例：包含多个基因的染色体（情况例：包含多个基因的染色体（情况例：包含多个基因的染色体（情况例：包含多个基因的染色体（情况1 1）01 234567890 123456789012345 678901 234567890 123456789012345 6789AOAOaabaaaabaabaaaabNabNabaaaaaabaaaaaabINNINNbababaabababaa将三个基因将三个基因将三个基因将三个基因对应对应的子表示的子表示的子表示的子表示树树如下：如下：如下：如下：一般情况下，一般情况下，一般情况下，一般情况下，这这些子表示些子表示些子表示些子表示树树可可可可以通以通以通以通过过特殊特殊特殊特殊连连接函数符号接函数符号接函数符号接函数符号连连接成接成接成接成为为一个更大的表示一个更大的表示一个更大的表示一个更大的表示树树。如果使用。如果使用。如果使用。如果使用ANDAND或或或或OROR作作作作为连为连接函数，接函数，接函数，接函数，则则得到两个得到两个得到两个得到两个不同的复合表示不同的复合表示不同的复合表示不同的复合表示树树，代表了两个不，代表了两个不，代表了两个不，代表了两个不同的程序。同的程序。同的程序。同的程序。在在在在这这个例子中，个例子中，个例子中，个例子中，遗传遗传信息的翻信息的翻信息的翻信息的翻译译从构造子表示从构造子表示从构造子表示从构造子表示树树开始，到将所有子表示开始，到将所有子表示开始，到将所有子表示开始，到将所有子表示树树连连接起来接起来接起来接起来结结束。束。束。束。2024/2/262024/2/26周周一一4646例：包含多个基因的染色体（情况例：包含多个基因的染色体（情况2 2）下面是分类问题的一个染色体，其中包含三个基因，每个基因表示一种类型。下面是分类问题的一个染色体，其中包含三个基因，每个基因表示一种类型。012345678901201234567890120123456789012012345678901201234567890120123456789012-/dac/-/dac/dacaccddacaccd/-aac/-aacbbbabcdbbbabcd-d/+c*-d/+c*dbdbacddbdbacd对应对应的子表示的子表示的子表示的子表示树树如下：如下：如下：如下：三个表示三个表示树树，每一个都代表一个代数式。，每一个都代表一个代数式。假假设设在分在分类类任任务务中，中，为为了便于了便于处处理，理，规规定当子表示定当子表示树树的的输输出小于某个出小于某个阈值时阈值时则转换为则转换为0 0，否，否则转换为则转换为1 1，则这则这些子表示些子表示树树可以按下面的公式决定分可以按下面的公式决定分类类：IF(Sub-ET1=1 AND Sub-ET2=0 AND Sub-ET3=0),THEN Class 1;IF(Sub-ET1=1 AND Sub-ET2=0 AND Sub-ET3=0),THEN Class 1;IF(Sub-ET1=0 AND Sub-ET2=1 AND Sub-ET3=0),THEN Class 2;IF(Sub-ET1=0 AND Sub-ET2=1 AND Sub-ET3=0),THEN Class 2;IF(Sub-ET1=0 AND Sub-ET2=0 AND Sub-ET3=1),THEN Class 3.IF(Sub-ET1=0 AND Sub-ET2=0 AND Sub-ET3=1),THEN Class 3.2024/2/262024/2/26周周一一4747一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用2024/2/262024/2/26周周一一4848GEP与GA、GP的关系GEPGEP继承了继承了GAGA的的 快速，易用快速，易用 和和GPGP的的 易变，多能易变，多能比比GA,GPGA,GP提高速度提高速度 100-1000000100-1000000倍倍GAGA特点：特点：线线性定性定长长简单编码简单编码解决解决简单问题简单问题GP GP 特点：特点：不定不定长长非非线线性性树结树结构构复复杂编码杂编码解决复解决复杂问题杂问题 GEPGEP特点：特点：线线性定性定长长 ，非非线线性性树结树结构构简单简单编码编码解决解决复复杂杂问题问题2024/2/262024/2/26周周一一4949GEP与GA、GP的关系GEP继承了GA的快速，易用和GP的易变，多能GEP比GA,GP提高速度100-1000000倍GAGA特点：特点：线线性定性定长长简单编码简单编码解决解决简单问题简单问题GP GP 特点：特点：不定不定长长非非线线性性树结树结构构复复杂编码杂编码解决复解决复杂问题杂问题 GEPGEP特点：特点：线线性定性定长长 ，非非线线性性树结树结构构简单简单编码编码解决解决复复杂杂问题问题2024/2/262024/2/26周周一一5050GEP与GA、GP的关系GEP继承了GA的快速，易用和GP的易变，多能GEP比GA,GP提高速度100-1000000倍GAGA特点：特点：线线性定性定长长简单编码简单编码解决解决简单问题简单问题GP GP 特点：特点：不定不定长长非非线线性性树结树结构构复复杂编码杂编码解决复解决复杂问题杂问题 GEPGEP特点：特点：线线性定性定长长 ，非非线线性性树结树结构构简单简单编码编码解决解决复复杂杂问题问题2024/2/262024/2/26周周一一5151一GEP基本概念二GEP特点三GEP研究状况四GEP算法过程五简单应用2024/2/262024/2/26周周一一5252GEP发展状况n n2000-2002草创阶段n n2002-2003开始普及阶段n n2004-至今深入研究阶段2024/2/262024/2/26周周一一5353第一阶段2000-2002n nF.Candida开创论文网上发表2000.12正式发表2001.12n n2002.1第一本专著正式出版。、基本概念基因、染色体、K-表达式、适应度评估函数、大量的探索性研究，如：太阳黑子预测、函数发现、逻辑电路设计、模拟神经网络等等n n特点：一花独放，基于实验2024/2/262024/2/26周周一一5454第二阶段2002-2003开始普及开始受到关注n n基于GEP的分类ChiZhouChiZhou,PeterC.Nelson,WeiminXiao,andThomasM.Tirpak,PeterC.Nelson,WeiminXiao,andThomasM.Tirpak,DiscoveryofClassificationRulesDiscoveryofClassificationRulesbyUsingGeneExpressionbyUsingGeneExpressionProgramming.InProgramming.InProceedings of the Proceedings of the International Conference on International Conference on Artificial IntelligenceArtificial Intelligence,pages1355-1361,LasVegas,USA,2002.,pages1355-1361,LasVegas,USA,2002.paperpape