基因表达式编程教学4精品PPT课件
- 格式:ppt
- 大小:325.50 KB
- 文档页数:46
基因表达式编程(GeneExpressionProgramming,GEP)前⾔该算法旨在在⼀组数据点中,⽤基因表达式编程的⽅法,根据基因遗传定律,物竞天择、优者⽣存,劣者淘汰的思想,不断进化种群,找出适宜度最⾼的染⾊体来模拟出数据点之间所存在的数学表达式关系。
通常该算法⽤来解决符号回归问题:符号回归(Symbolic Regression)作为⼀种⼀种监督学习⽅法,试图发现某种隐藏的数学公式,以此利⽤特征变量预测⽬标变量。
符号回归的优点就是可以不⽤依赖先验的知识或者模型来为⾮线性系统建⽴符号模型。
符号回归基于进化算法,它的主要⽬标就是利⽤进化⽅法综合出尽可能好的解决⽤户⾃定义问题的⽅法(数学公式,计算机程序,逻辑表达式等)。
1 编码规则1.1 基因⼀段基因由两部分组成:头部和尾部,形如:其中,红⾊部分为头部基因,其长度为9,绿⾊部分为尾部基因,其长度为8。
基因中的每个元素分为两种形式:函数和终点,它们分别从函数集和终点集中进⾏选择:函数集算术运算符:例如+、-、*、/等初等数学函数,例如:sin、开⽅、cos等其它⼀些函数,例如:max、min等布尔运算符:例如与、或、⾮关系运算符:例如<、>、=等条件运算符:例如 if 等终点集变量数值:例如x1、x2常量数值:例如π、e⽆参函数:例如rand()等基因头部长度我们⽤h表⽰,尾部长度⽤t表⽰,函数集所需最⼤参数⽤n表⽰,⽐如⼀个函数集为{+、-、*、/、sin、cos},其中所需参数的最⼤个数为2,则n为2那么h、t、n三者之间的关系是:t=h∗(n−1)+1维持这样的关系,可以保证产⽣的基因编码都是合法编码。
1.2 基因编码原理⽐如下⽅的数学表达式:翻译成表达式树为,其中Q表⽰开⽅:那么可以得到它的基因型为:下⾯来看看⼀个基因型翻译成表达式的过程:基因型如下:基因的起点对应表达式树的根:Q(开⽅)需要⼀个参数,那么往后取⼀个参数:乘法需要两个参数,往后取两个参数:以此类推,可以画出该基因型的表达式树为:我们可以看出,表达式树的根⼀定要是函数集的元素,叶⼦节点⼀定是终点集的元素。
基因表达式编程基因表达式编程(Gene Expression Programming,GEP)是由葡萄⽛科学家Candida Ferreira 2001年提出来的⼀种新型遗传算法,其特点是将基因型和表现型分离。
GEP 继承了GA的快速、易⽤和GP的易变、多能,⽐GA,GP提⾼速度100 - 1000000倍。
⽽GEP与遗传算法(GA)和遗传编程(GP)的根本区别在于它们的个体性质不同,在GA中个体是固定长度的线性串(染⾊体),GP中个体是长度和形状不同的⾮线性实体,⽽在GEP中个体编码成固定长度的线性串(基因组或者染⾊体),然后被表达成不同长度和形状的⾮线性实体(表达式树)。
相⽐之下,GEP具有染⾊体简单,线性和紧凑、易于遗传操作等特点。
GEP中有两个主体:表达式树和染⾊体,遗传信息在染⾊体中,⽽表达式树则是染⾊体的表达。
因此,遗传操作在固定长度的线性编码的染⾊体上进⾏,⽽个体评价是在染⾊体解码得到的表达式树上进⾏,即操作和评价相分离。
染⾊体由若⼲个基因组成,每个基因由头部和尾部组成,头部可以包含是函数符号和终结符号(包括编程中的输⼊,常量,或者没有参数的函数),尾部仅有终结符号。
⽽且基因的起始点总是第⼀个符号,终⽌点并不⼀定是最后⼀个符号,终⽌点后的符号组成GEP基因的⾮编码区。
GEP算法的过程是:先随机产⽣初始化染⾊体,再将染⾊体换化成表达式树,评价表达式树,判断是否已经进化成最终⽬标,是就输出最终⽬标,否则利⽤轮盘赌进⾏选择机确定下⼀代的个体,再利⽤遗传操作,⽣成新⼀代染⾊体,回到第⼆步。
其中,对表达式评价就是要评测表达式计算得到的数据和训练数据的符合程度。
主要有两个公式测评:基于绝对误差的适应度函数和基于相对误差的适应度函数,在GEP中,⼀般采⽤第⼆个公式。
进化遗传操作包括复制和遗传算⼦。
复制算⼦只复制选择算⼦所选择的个体,不会产⽣基因的多样性。
GEP基因结构性和简单线性编码,使得GEP的遗传算⼦⽐较丰富,主要有:变异、逆串、插串、根插串、基因插串、单点重组、双点重组、基因重组等⼋⼤算⼦。