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

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,单击此处编辑母版标题样式,2011.5,之来龙去脉,广西师范学院,科学计算与智能信息处理广西高校重点实验室,Gene Expression Programming,1,2,2,2,创始人,Candida Ferreira,于,1995,年在里斯本大学获得生物学博士后，一直从事与生物基因和生物化学相关的研究，当时遗传算法（,GA,）和遗传编程（,GP,）已日臻成熟。在生物基因表达的启示下，她融合了,GA,和,GP,的优点，经过五年时间的酝酿，终于使得,GEP,瓜熟蒂落，实现了又一次跨学科的革新。,2,3,引入国内,川大数据库与知识工程研究所的研究团队的博士生们，特别是左劼博士，在,Ferreira C,原创性论文在网上出现,10,多天，尚未正式发表时，以特有的兴趣和学术敏感，捕捉了机会，把,GEP,引入到国内，在国际会议,WAIM 2002,上，左劼、唐常杰等发表了国内学者第一篇关于,GEP,的研究论文。,在元昌安教授带领的广西师范学院“科学计算与智能信息处理”研究团队中，各个成员在汲取,GEP,带来的甘露，同时也在收获着丰硕的果实。,2,4,一,GEP,基本概念,二,GEP,特点,三,GEP,研究状况,四,GEP,算法过程,五 简单应用,2,5,GEP,基本概念,GEP,（,Gene Expression Programming,）,基因表达式编程,GEP,是借用了生命科学中,基因,、,染色体,等概念和思路，通过,遗传进化,进行数据挖掘、公式发现，以及最优化的,一种新算法,。,GEP,是在数据挖掘的沃土中，,从遗传计算这棵老树上开出的新花,2,6,基因,是构成染色体的,基本单位,.,知识点,(,知识基因）,基因,+,-,*,/,sqrt,1,a,b,c,d,，,sin(x),cos(x),基因分类,函数符（运算符，函数）,例如：,+,-,*,/,sqrt,，,.,sin(x),cos(x),终结符（变量，常量）,例如：,a,b,c,d,，,1.,基因,2,7,基因,是构成染色体的,基本单位,.,知识点,知识基因）,基因,+,-,*,/,sqrt,1,a,b,c,d,，,sin(x),cos(x),基因分类,函数符（运算符，函数）,例如：,+,-,*,/,sqrt,，,.,sin(x),cos(x),终结符（变量，常量）,例如：,a,b,c,d,，,1.,基因,不仅仅是,01,位串,2,8,基因,是构成染色体的,基本单位,.,知识点,(,知识基因）,基因,+,-,*,/,sqrt,1,a,b,c,d,，,sin(x),cos(x),基因分类,函数符（运算符，函数）,例如：,+,-,*,/,sqrt,，,.,sin(x),cos(x),终结符（变量，常量）,例如：,a,b,c,d,，,1.,基因,2,9,基因,在,GEP,中，有两个主体：染色体和表达式树，遗传信息在染色体中，而表达式树则是染色体的表达。从染色体到表达式树的解码过程称为翻译。,GEP,的基因码是染色体与其所表示的函数与终结符之间一对一的关系，翻译的规则决定了函数与终结符在表达式树中的空间位置以及在复合系统中子表达式树之间的交互类型,在,GEP,中，基因组或染色体是一个线性的固定长度的符号串，是不同形状和大小的表达式树的编码。,GEP,的基因与生物基因的,ORF(Open Reading Frame),的形式相似，而,GEP,基因的起始点总是第一个符号，终止点并不一定是最后一个符号，终止点后的符号组成,GEP,基因的非编码区。,2,10,终结符,终结符是提供给系统值的最末端结构。,终结符自己提供信息,但不处理另外的信息。通常,终结符包括,GEP,程序中的输入、,常量或者无参数函数。,如果用树形结构来表示程序，,终结符代表树的这些叶节点。当程序运行的时候，,这些叶节点要么接受外部的输入、要么自己就是一个常量或者自己就能计算产生一个量。它们向系统中提供信息，,以供系统处理。,通常用,T,或者,T,GEP,表示一个,GEP,算法的终结符集合，用,t,T,表示终结符集合中的终结符。,2,11,函数,GEP,中的函数概念相当广泛,它包括系统的中其他任何非终结符的中间结构。,函数集合可以包括与应用有关的问题领域的运算符号,也可以包括程序设计语言中的程序构件,甚至是表示系统中间层次的一种符号。,如果用树形结构来表示程序，函数一般位于表达式树的非叶节点。,2,12,函数,(,续,),对于常见的以公式发现为目标的应用中，,以下是一些常见的函数,：,算术运算符，例如,+,、,-,、*、,等；,初等数学函数，例如,sin,，,cos,等,；,其他一些函数,，,例如,max,，,min,等；,布尔运算符，例如,、,等,;,关系运算符,例如,、,=,、,、,等；,条件运算符，,if-then-else,；,自定义函数。,2,13,函数,(,续,),通常用,F,或,F,GEP,表示一个,GEP,算法的终结符,(,函数符号),集合，每一个函数,f,F,记为,f,(,p,1,，,p,2,，,p,m,),其参数个数记为,(,f,)=,m,函数参数的最大个数为函数集合中所有函数的参数个数的最大值,记为,(,F,)=max(,(,f,)|,f,F,),2,14,基因组（,Genome,）,多个基因,按照,一定规则,构成的基因串，称为,基因组,。,实例,参数：头长,h,，函数符,+,*,/,终结符,a,，,b,0 1 2 3 4 5 6,*,+a,b a a a,结构,头部,函数符终结符,尾部,终结符,规则,t,h,（,n,）,2,15,基因组（,Genome,）,多个基因,按照,一定规则,构成的基因串，称为,基因组,实例,参数：头长,h,，函数符,+,*,/,终结符,a,，,b,0 1 2 3 4 5 6,*,+a,b a a a,结构,头部,函数符终结符,尾部,终结符,规则,t,h,（,n,）,2,16,基因组（,Genome,）,多个基因,按照,一定规则,构成的基因串，称为,基因组,。,实例,参数：头长,h,，函数符,+,*,/,终结符,a,，,b,0 1 2 3 4 5 6,*,+a,b a a a,结构,头部,函数符终结符,尾部,终结符,规则,t,h,（,n,）,2,17,基因组（,Genome,）,多个基因,按照,一定规则,构成的基因串，称为,基因组,。,实例,参数：头长,h,，函数符,+,/,终结符,a,，,b,0 1 2 3 4 5 6,*,+a,b a a a,结构,头部,函数符终结符,尾部,终结符,规则,t,h,（,n,）,2,18,基因组（,Genome,）,多个基因,按照,一定规则,构成的基因串，称为,基因组,。,实例,参数：头长,h,，函数符,+,*,/,终结符,a,，,b,0 1 2 3 4 5 6,*,+a,b a a a,结构,头部,函数符终结符,尾部,终结符,规则,t,h,（,n,）,例：,+,-,*,/,n=2,2,19,染色体,(Chromosome),一个,或,多个,基因组构成一个,染色体,。,单基因组染色体,实例：,*,+a,b a a a,多基因组染色体,实例：,*,+a,b a a a,+/+,b b a b,b/b,b b b a,多个基因,按照,一定规则,构成的基因串，称为,基因组,。,2,20,染色体,(Chromosome),一个,或,多个,基因组构成一个,染色体,。,单基因组染色体,实例：,*,+a,b a a a,多基因组染色体,实例：,*,+a,b a a a,+/+,b b a b,b/b,b b b a,2,21,染色体构成,基因基因组染色体,数学表达式,？,2,22,染色体,基因基因组染色体,数学表达式,？,2,23,染色体,基因基因组染色体,数学表达式,？,2,24,染色体数学表达式,解析过程：,染色体表达式树（,ET,）数学表达式,2,25,染色体数学表达式,解析过程：,染色体表达式树（,ET,）数学表达式,2,26,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,0 1 2 3 4 5 6,2,27,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,0 1 2 3 4 5 6,2,28,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,0 1 2 3 4 5 6,2,29,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,*为两目运算,0 1 2 3 4 5 6,2,30,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,0 1 2 3 4 5 6,2,31,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,0 1 2 3 4 5 6,2,32,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,0 1 2 3 4 5 6,2,33,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右，直到叶结点全为终结符。,（,b,a,）,a,表示怎样一个表达式,?,0 1 2 3 4 5 6,2,34,单基因单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：从上到下，从左到右,（,b,a,）,a,2,35,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右,（,b,a,）,a,2,36,单基因组染色体的解析,单基因组染色体：,*,+a,b a a a,表达式（树）,解析规则：,从上到下，从左到右,（,b,a,）,a,2,37,GEP,基因的非编码区,GEP,基因长度是固定的，但,K-,表达式的长度一般是等于或小于基因的长度，从上面的例子可以看出，,K-,表达式的结束子在位置,4,，从位置,5,到位置,6,都是基因的非编码区。基因的非编码区是,GEP,演化的关键，正是因为它，才使得对基因组使用任何遗传操作成为可能。,*,+a,b a a a,看下面的例子：,0 1 2 3 4 5 6,2,38,对应的表示树为,:,K-,表达式：,0123456789012345678901234567890,*b+a-aQab+/+b+,babbabbbababbaaa,表示树的结束点在,7,，而基因的结束位置在,30,。终结符组成的非编码区长度为,23,。,对编码区做变异操作，将位置,6,的符号“,Q”,变成“*”，现在,K-,表达式为：,0123456789012345678901234567890,*b+a-a,*,a b+/+b+,babbabbbababbaaa,对应的表示树为：,2,39,如果变异发生在位置,5,，符号“,a”,变成“,+”,，,K-,表达式变为：,0123456789012345678901234567890,*b+a-,+,Qab+/+b+,babbabbbababbaaa,对应的表达式树为：,K-,表达式：,0123456789012345678901234567890,*b+a-aQab+/+b+,babbabbbababbaaa,2,40,变异也有可能使得表达式树变小，如：假设变异发生在位置,2,，符号“,+”,变成“,Q”,，,K-,表达式变为：,0123456789012345678901234567890,*b,Q,a-aQab+/+,b+,babbabbbababbaaa,它对应的表达式树为：,K-,表达式：,0123456789012345678901234567890,*b+a-aQa,b+/+b+babbabbbababbaaa,2,41,在,GEP,中，变化的不是基因的长度，而是,ORF,的长度。所以尽管基因的长度是固定的，但其对应的表达式树却有着不同的大小和形状，最简单的情况是：,当基因的第一个元素来自于终端符号集,T,中，此时,ORF,的长度为,1,。,当基因头部的所有元素均来自于函数符号集,F,，且对应的操作数均为最大操作数时，则,ORF,长度达到最大，与基因的长度相等。,2,42,复合染色体,GEP,的复合染色体，是指一个染色体包含多个等长的基因。设计一个问题的染色体时，其中基因的数目、基因的头部长度是要优先考虑的。复合染色体的每个基因的编码区对应一个子表示树，这些子表示树相互影响而形成一个更复杂的实体。,关注的问题：如何从复合染色体中的各个基因构造各自的表示树？,2,43,例：有一长度为,39,的染色体，其中包含,3,个基因，每个基因长度为,13,，头部长度为,6,。如下：,0 123456789 012 01234 56789012 0123456789012,*Qb+*/,bbbabab,-a+QbQ,bbababa,/ba-/*,bbaaaaa,为清晰起见，每个基因的起始点都定位,0,，这个起始点也是子表示树的第一个符号。每个子表示树的结束点在表示树中非常清楚：,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 2(sub-ET3).,2,44,总之，,GEP,的染色体包含多个,ORF,，每个,ORF,是一个子表示树的结构化和函数化编码。在进化过程中，子表示树或者按它们各自的适应度被选取，或者这些子表示树组合成更复杂的复合子表示树，按总体的适应度被选取。如前所述，,GEP,的染色体可以隐含着不同的表示树的结构，以这些结构编码的个体的复杂程度各不相同。大致有以下三种情况,；,（,1,）,最简单的情况，一个个体只有一个基因，与它对应的表示树也只有一个；,（,2,）个体中有多个基因，每个基因各表示不同的子表示树结构，这些子表示树结构用一种特殊的连接函数连接起来；,（,3,）染色体对应着不同的子表示树，每一个子表示树对应着求解问题的一个解。,2,45,当基因组中有多个基因，而每一个基因都能独立的翻译为一个子表示树时，则有两种情况需要讨论：,（,1,）所有的子表示树被一种特殊的连接函数直接连接起来。,（,2,）这些子表示树没有被直接连接，但它们都表示某个具体问题的解。,例：包含多个基因的染色体（情况,1,）,01 234567890 123456789012345 6789,AO,aabaaaab,Nab,aaaaaab,INN,bababaa,将三个基因对应的子表示树如下：,一般情况下，这些子表示树可以通过特殊连接函数符号连接成为一个更大的表示树。如果使用,AND,或,OR,作为连接函数，则得到两个不同的复合表示树，代表了两个不同的程序。,在这个例子中，遗传信息的翻译从构造子表示树开始，到将所有子表示树,连接起来结束。,2,46,例：包含多个基因的染色体（情况,2,）,下面是分类问题的一个染色体，其中包含三个基因，每个基因表示一种类型。012345678901201234567890120123456789012,-/dac/,dacaccd,/-aac,bbbabcd,-d/+c*,dbdbacd,对应的子表示树如下：,三个表示树，每一个都代表一个代数式。,假设在分类任务中，为了便于处理，规定当子表示树的输出小于某个阈值时则转换为,0,，否则转换为,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;,IFSub-ET1=0 AND Sub-ET2=0 AND Sub-ET3=1),THEN Class 3.,2,47,一,GEP,基本概念,二,GEP,特点,三,GEP,研究状况,四,GEP,算法过程,五 简单应用,2,48,GEP,与,GA,、,GP,的关系,GEP,继承了,GA,的 快速，易用,和,GP,的 易变，多能,比,GA,GP,提高速度,100-1000000,倍,GA,特点：,线性定长,简单编码解决简单问题,GP,特点：,不定长非线性树结构,复杂编码解决复杂问题,GEP,特点：,线性定长,，,非线性树结构,简单,编码解决,复杂,问题,2,49,GEP,与,GA,、,GP,的关系,GEP,继承了,GA,的,快速,，,易用,和,GP,的,易变,，,多能,GEP,比,GA,GP,提高速度,100-1000000,倍,GA,特点：,线性定长,简单编码解决简单问题,GP,特点：,不定长非线性树结构,复杂编码解决复杂问题,GEP,特点：,线性定长,，,非线性树结构,简单,编码解决,复杂,问题,2,50,GEP,与,GA,、,GP,的关系,GEP,继承了,GA,的,快速,，,易用,和,GP,的,易变,，,多能,GEP,比,GA,GP,提高速度,100-1000000,倍,GA,特点：,线性定长,简单编码解决简单问题,GP,特点：,不定长非线性树结构,复杂编码解决复杂问题,GEP,特点：,线性定长,，,非线性树结构,简单,编码解决,复杂,问题,2,51,一,GEP,基本概念,二,GEP,特点,三,GEP,研究状况,四,GEP,算法过程,五 简单应用,2,52,GEP,发展状况,2000-2002,草创阶段,2002-2003,开始普及阶段,2004-,至今 深入研究阶段,2,53,第一阶段,2000-2002,F.Candida,开创论文 网上发表,2000.12,正式发表,2001.12,2002.1,第一本专著 正式出版。,、,基本概念,基因、染色体、,K-,表达式、适应度评估函数,、大量的探索性研究,，如：太阳黑子预测、函数发现、,逻辑电路设计、模拟神经网络等等,特点：,一花独放，基于实验,2,54,第二阶段,2002-2003,开始普及,开始受到关注,基于,GEP,的分类,Chi Zhou,Peter C.Nelson,Weimin Xiao,and Thomas M.Tirpak,Discovery of Classification Rules,by Using Gene Expression Programming.In,Proceedings of the,International Conference on Artificial Intelligence,pages 1355-1361,Las Vegas,USA,2002.,paper,基于,GEP,的关联规则,Zuo Jie,Tang Changjie,and Zhang Tianqing,，,Mining,Predicate Association Rule,by Gene Expression Programming,WAIM02(International Conference for Web Information Age 2002).LNCS(Lecture Notes In Computer science)Vol.2419,pp.92-103,edited by,Springer Verlag Berling Heidelberg2002.8,ISBN,2,55第二阶段,2002-2003,开始普及,一维混沌映射,Yorick Hardy.Gene Expression Programming and One-Dimensional Chaotic Maps,International Journal of Modern Physics C,2002 Vol.13(1):13-24,2,56,第三阶段,2004-,至今研究深入,研究者增多，研究工作比较深入,用,GEP,进行,时间序列预测,挖掘,微分方程,探讨了,GEP,中的,常数,探讨了,收敛性,分析问题,探讨了各种,改进算法,探讨了基于,GEP,的,智能模型库,系统的实现,等等,2,57,第三阶段,2004-,至今研究深入,Zuo Jie,Tang Changjie,Li Chuan,Yuan Chang-an and Chen An-long,Time Series Prediction based on Gene Expression Programming,WAIM04(International Conference for Web Information Age 2004).LNCS(Lecture Notes In Computer science)Vol.3129:55-64.,讨论了两种新的基于,GEP,的时间序列模型构造方法。一种是传统的滑动窗口预测法(,GEP-SWPM)，,即找到在一个窗口大小内的前后数据之间的函数关系，然后使用该关系来进行预测。另外一种则是通过分析整个测试数据，建立关于时间序列的微分方程，然后通过该微分方程进行预测(,GEP-DEPM)。,2,58,第三阶段,2004-,至今研究深入,段磊，唐常杰，左劼，元昌安等.基于基因表达式编程的抗噪声数据的函数挖掘方法.计算机研究与发展,2004,41(10):1684-1689.（,EI,收录）,借鉴生物具有的趋利避害(,seek advantage，avoid disadvantage),天性，提出了,“,弱适应模型,”,(,Weak-Adaptive Model)，,设计了在弱适应模型下基于相对误差计算适应度的算法（,REFA）。,2,59,第三阶段,2004-,至今研究深入,黄晓冬，唐常杰，李智等,基于基因表达式编程挖掘函数关系,软件学报(增刊),2004,15(,suppl.):96-105,提出并实现了任意维定义域上的一致表达式和分域表达式的挖掘方法，提出了,GEP-UEM（,一致函数表达式的挖掘）算法和,GEP-MEM(,分域函数表达式挖掘)算法以及,GEP-BDM(,二域式挖掘)算法。从而实现了分段函数的挖掘。,2,60,第三阶段,2004-,至今研究深入,张欢,唐常杰,余弦,等,.,基于转基因技术的基因表达式编程,EB/OL.,中国科技论文在线,(,教育部,).,www.paper.,张欢 唐常杰 余 弦 乔少杰 汪锐 左劼,基于转基因技术的基因表达式编程,Gene Expression Programming Based on Transgenesis Technology,计算机科学 2005(增刊）,p278-280,提出了基于转基因技术的基因表达式编程方法，通过注入转基因，引导进化方向，控制知识发现过程。,2,61,第三阶段,2004-,至今研究深入,彭京,唐常杰,元昌安等.基于重叠表达的多基因进化算法,EB/OL.,中国科技论文在线(教育部).,www.paper.,Jing Peng,Chang-jie Tang,Jing Zhang,Chang-an Yuan,Evolutionary Algorithm Based on Overlapped Gene Expression,ICNC 2005,LNCS 3612,pp.194 204,2005,pp.194 204,2005,IDS Number:BDA32SCI,检索号 000232246700023.,对基于重叠表达的多基因进化算法进行了研究，借鉴生物基因片段重叠表达，引入重叠基因概念，节约了表达空间。,2,62,第三阶段,2004-,至今研究深入,M,-,GEP:,基于多层染色体基因表达式编程的遗传进化算法,彭京,唐常杰李川,胡建军,计算机学报，,Vol.28 No,9.Sept.2005.p1459-1466.(,EI,Accession,Number:,05419405741),该文提出了一种新的基于多层染色体基因表达式编程的遗传进化算法,M-GEP,新算法引入了多层染色体的概念,利用染色体构建的层次调用模型对个体进行表达,在解决实际函数发现、电路进化等实际问题中取得了良好效果,.,该文主要贡献包括,:(1),提出了基于多染色体的基因表达式编程算法,(,M,-,GEP);(2),建立了不同染色体的层次调用模型及存储结构,;(3),提出并实现了基于染色体的重组算子和基因随机重组算子,.,对多基因,GEP,和单基因,GEP,的对比实验结果表明,平均进化辈数仅为后者的,29%,81%.,2,63,第三阶段,2004-,至今研究深入,贾晓斌,唐常杰,左劼,陈安龙,段磊,汪锐,基于基因表达式编程的频繁函数集挖掘.计算机学报，,Vol.28,No.8 Aug,2005 p1247-1254.,EI Accession number:05359331320,作者做了如下工作:提出了描述能力更强的频繁函数集,FFS,概念,;,提出并实现了基于基因表达式编程的频繁函数集挖掘算法,FFSM,算法,中采用了精度阈值队列策略,PTQ,，,有效地提高了,FFSM,的成功率,;,用实验证实了,FFS,更强的描述能力和,PTQ,的有效性,其中,FFS,在挖掘高精度复杂函数时,PTQ,使,FFS,的成功率提高了,55,倍.,2,64,第三阶段,2004-,至今研究深入,谢方军 唐常杰 元昌安 左劼 陈安龙 基于基因表达式的演化硬件进化和优化算法,计算机辅助设计与图形学报,Vol.17,No.17 p1415-1420,2005.7,EI Accession number:05319278321,本文针对电路进化设计作了如下工作：（,1,）融合了数据挖掘、基因表达式编程,(,Gene Expression Programming,GEP),与传统电路进化技术，提出两阶段电路进化方法，该方法包括基于,ETGP(Express Tree Genetic Programming),进化算法的电路进化阶段和基于,MFDC(Mining Frequency Digital Circuit),算法的电路优化阶段。（,2,）给出了详尽的实验，实验表明,6,次多项式函数发现的平均进化代数为,442,代、乘法器电路的平均进化代数为,2292,代。比,CGP(Certain Genetic Programming),、,NEHF,（,Novel Evolvable Hardware Framework,）,快,6,倍以上。用,MFDC,对乘法器电路进化结果进行挖掘后，得到了比传统电路更有效的乘法器电路。,2,65,第三阶段,2004-,至今研究深入,钟义啸,唐常杰,陈宇等,.,提高基因表达式编程发现知识效率的回溯策略,EB/OL.,中国科技论文在线,(,教育部,).,.,钟义啸,唐常杰,陈宇,段磊,魏大刚,提高基因表达式编程发现知识效率的回溯策略,四川大学学报,Vol.43,No.2 pp299-304,2006.4,Zhong Yixiao,Tang Changjie,Chen Yu,Duan Lei,Wei Dagang.Improve KDD Efficiency of Gene Expression Programming by Backtracking Strategy,Journal of Sichaun Universiry(Natural Science Edition),Vol.43,No.2 pp299-304,2006.4,通过回溯策略，对,提高基因表达式编程发现知识效率进行了研究，,借鉴生物,“,返祖现象,”,，引入回溯检查点概念和可回溯,GEP,算法、设计了等比递增检查点序列和加速递增检查点序列，约束回溯过程。,2,66,第三阶段,2004-,至今研究深入,元昌安，唐常杰，左劼等.基于基因表达式编程的函数挖掘-收敛性分析与残差制导进化算法.四川大学学报（工程科学版）,2004,36(6):100-105.（,EI,收录）,Chang-an Yuan,Chang-jie Tang,Yuan-guang Wen,Jie Zuo,Jing Peng,Jian-jun Hu.,CONVERGENCY OF GENETIC REGRESSION IN DATA MINING BASED ON GENE EXPRESSION PROGRAMMING AND OPTIMIZED SOLUTION.,International Journal of Computers and Applications,国际杂志录用,提出了残差制导进化算法,(,RGEA),，,算法的主要思想是对,GEP,的遗传操作进行改进，以使下一代群体中残差平方和小于上一代最小残差平方的染色体个数尽可能多。算法对几种有可能产生比当前最佳染色体更好的个体的遗传操作，分配指标任务，即要求该遗传操作在每一代操作中生成的残差平方和小于上一代最小残差平方的染色体个数至少要达到规定的阈值，若没有完成，则在本代遗传操作中调整其遗传率，重新进行遗传操作。,2,67,第三阶段,2004-,至今研究深入,元昌安,，唐常杰等.基于基因表达式编程的智能模型库系统的实现.四川大学学报（工程科学版）,2005,37(3):99-104,(,EI,Accession number:05269184570),Intelligent Function Model Discovery System Based upon Gene Expression Programming,将由,杂志,Journal of Computational Information Systems,正刊发表,(,Ei,收录),提出了显式智能模型，隐式智能模型，显式模型基因的概念,给出了基于,GEP,的隐式智能模型(,Implicit Intelligent Model,IIM),的挖掘算法(,GEP-IIMA)，,在此基础上实现智能模型库系统；研究了隐式智能模型库(,IIMB),系统与,GIS,的接口技术。,IIMB,是真正意义的无先验知识的智能模型库，其模型的类型和参数的求解均由程序自己来实现。,2,68,第三阶段,2004-,至今研究深入,改进初始种群生成策略。,胡建军、李太勇博士分别在,2007,，和,2010,年提出相关改进,改进,GEP,的编码方式。,李川、彭昱忠等研究者提出改进，不用构建表达式树而直接解码求的表达式值的线性求解法。如，基于,Scale,的,GEP,、基于 堆栈的,GEP,GEP,中关于数值常量问题的研究。,左劼、饶元和彭昱忠等研究者做了大量研究。如，由算法本身产生常数，在基因尾部附加,DC,域和直接将常量作为终结符。,GEP,与其他算法的融合,神经网络 陶俊剑（,2010,）、邓松（,2006,）,模拟退火 饶元（,2008,）,2,69,关于,GEP,当前研究的着眼点主要集中在以下四个方面,用实验验证,GEP,各种遗传策略的效率,即对,GEP,进行内部比较,”,。,针对解决问题的特性,提出了一系列新概念和新算法。,将,GEP,技术应用于其他学科的研究中,探究多学科交叉融合方法及其用。,对,GEP,的形式化和,收敛性等进行理论分析和研究，旨在探讨,GEP,的机理，旨在理论上保证,GEP,方法的可靠性和可行性。,2,70,一,GEP,基本概念,二,GEP,特点,三,GEP,研究状况,四,GEP,算法过程,五 简单应用,2,71,输出最终目标,随机产生初始染色体,Chromosomes,染色体,表达式树（,ET,）,评价 表达式树,新一代 染色体,遗传操作,复制，变异，,重组等,Yes,No,已经进化到最终目标,?,GEP,算法过程,用轮盘赌进行选择,进化操作,2,72,输出最终目标,随机产生初始染色体,Chromosomes,染色体,表达式树（,ET,）,评价 表达式树,新一代 染色体,遗传操作,复制，变异，,重组等,Yes,No,已经进化到最终目标,?,GEP,算法过程,用,轮盘赌进行选择,GEP,特色,2,73,输出最终目标,随机产生初始染色体,Chromosomes,染色体,表达式树（,ET,）,评价 表达式树,新一代 染色体,遗传操作,复制，变异，,重组等,Yes,No,已经进化到最终目标,?,GEP,算法过程,用,轮盘赌进行选择,算法收敛的关键,2,74,评价个体,对表达式评价就是要评测表达式计算得到的数据和训练数据的符合程度。,基于绝对误差的适应度函数,基于相对误差的适应度函数,其中，,M,是一个常数，表示选择,的带宽，在这个范围内种群开始,进化；,C(,i,j,),表示根据第,i,个染色体,对应的函数表达式利用第,j,个样本,中的变量数据求得的函数值；,T(,j,),表示第,j,个样本中包含的实际测量,得到的该目标函数的真实值；,Ct,表示样本的数目。显然，当,C(,i,j,),=,T(,j,),时适应度函数的取值将取,得最大,f,i,=fmax=Ct*M,。,2,75,评价个体,由于用绝对误差并不能完全评价近似值的精确度，而相对误差不仅能表示出绝对误差来，而且在估计近似值运算结果的误差时，比绝对误差更能反映出误差的特性，所以在,GEP,中基于误差的适应度计算普遍采用第二个公式。,对于更加复杂的问题可以使用以下的适应度函数,:,n,是适应度实例正确地被评估的数量,C,t,是适应度实体的总数。,问题的解决很大程度上取决于适应度函数的设计方式。,2,76,选择,在,GEP,中,个体由轮盘赌转轮采样选择,(,戈尔登伯格,GOLDBERG 1989,),。每个个体根据它的适应度的按比例得到一个轮盘赌转轮的切片。然后转轮转动的次数达到能够使个体在群体中满足群体大小从一代到另一代维持进化。,可能在一些文献中发现其它选择模式,但是最普遍的是使用,:,轮盘赌,决定论,和锦标赛方法选择,2,77,进化操作,复制,遗传算子,2,78,复制,选择算子根据适应度和比例选择（赌轮选择方法）来随机确定下一代的个体。,复制算子只复制选择算子所选择的个体。,这些个体组成了下一代的初始群体。,2,79,复制,例子,0,代的,0,号个体是有最大适应度值的个体之一,它有两个后代其一是,1,号个体,其二是,3,号个体,均是通过选择复制产生的个体,2,80,复制,如果只是进行选择和复制，到,13,代之后，群体失去了多样性。所有的个体都是同一个个体的后代,。,复制和选择一样 不会产生基因的多样性,他们的作用只是基因的转移,但是实际世界中 生物是存在基因的变异,2,81,变异,生物的变异,在生物的遗传和自然进化过程中，其细胞的分裂和复制环节有可能会因为某些偶然的因素的影响而产生一些复制差错，,这样就会使某些基因发生某种变异。,所以,GEP,中也引入了变异。从而产生新的个体。考虑到基因的长度，,GEP,的变异率要远远大于自然界的变异率。,2,82,变异定义,在单个染色体上，对染色体的每一位进行随机测试，如果满足变异的概率，则重新产生该位的编码。,由于要保持染色体的结构,所以：,头部变异时 可以选择所有的符号,尾部变异时 只能选择,终结符,因为尾部是只是终结符组成,这是与,GA,的不同之处。,GA,的变异是不分头和尾的。,2,83,变异,0 1 2 3 4 5 6 0 1 2