基因的gep的函数建模

基因的gep的函数建模

基于遗传程序设计的复杂模型在科学领域，人们通常需要分析和结论其内部规律，即函数建模。函数建模问题可以描述为：对于给定的数据(xi,yi)；i=1,2，…，m)，要求在某个函数类的集合中寻找一个函数Φ(x)，使得Φ(xi)尽量逼近yi。求解建模问题的传统方法有数据拟合、回归分析和逼近论等。这些方法需要先选择一个模型f(x,w)，然后再去确定模型中的参数w，从而拟合、逼近已知数据。显然，模型的选择是至关重要的，而这需要用到特定领域的专门知识。而且当模型结构很复杂时，即使掌握了问题的背景知识，选择一个合适的模型以及进行参数估计也是很困难的。针对传统方法在处理建模问题时的局限性，遗传程序设计（GeneticProgramming,GP）提供了一种可行的自动建模方法。它采用树结构来表示函数，通过杂交、变异等遗传操作去改变这些树结构，并一代代地演化下去直到获得合适的解。这种方法不需要了解特定领域的专业知识，利用遗传算法的自适应性和自学习性进行搜索，在函数自动建模方面取得较好的效果。但是，遗传程序设计采用树结构作为编码，这种不定长的复杂编码需要庞大的存储空间，遗传操作也复杂，而且容易产生无效的语法树。基因表达式程序设计（GeneExpressionProgramming,GEP）是葡萄牙学者CandidaFerreira于2000年首次提出的，它是一种新颖的遗传算法，采用等长线性符号作为遗传编码，易于遗传操作，而个体表现型则对应于树结构，因此具有用简单的编码解决复杂问题的优点。GEP在函数自动建模方面体现了优越的性能。1gep的基本原则1.1函数符号的生成GEP的遗传编码是等长的线性符号串，称为GEP染色体。一个染色体可以由多个基因组成。每个GEP基因由头部和尾部组成，头部可以包含终结符和函数符号，而尾部只能包含终结符。终结符是指程序中的输入，常量以及没有参数的函数。函数符号可以是相关问题领域中的运算符号（如+，-，*，\，sin,cos,ln等），也可以是程序设计中的一个程序构件。头部的长度h通常依具体问题而定，而尾部的长度t则由以下公式得到：是一个合法的GEP基因，其中黑体表示尾部。要把GEP基因解码为表达式树，应按照从左到右的顺序逐一读取基因中的字符，然后根据语法规则按照层次顺序排放即可。公式（2）表示如下的表达式树。在这个例子中，尾部的最后一个字符b并没有出现在表达式树中，即有效的基因片段只有12个字符，则称该基因的有效长度为12。如果上述基因的头部第4位发生变异，“S”变成了“+”，则变成如下的基因：其对应的表达式树则变成：在这种情况下，基因中所有的符号都出现在表达式树中，则该基因的有效长度为13。1.2gep中的评价能否成功求出问题的解在很大程度上取决于适应度函数的设计，适应度函数将指导程序演化的方向。对于函数建模问题，程序的最后解答是一个表达式，对该表达式的评价就是指利用该表达式计算得到的数据与训练数据的吻合程度。在GEP中，通常采用残差平方和作为评价标准，或者采用均方差作为评价标准。设有m个样本值（Xi,Yi），Φ(x)表示某个个体（染色体），则残差平方和Q为：均方差为个体Φ(x)的适应度函数为：或者显然，适应值越小，表示误差越小，该个体就越优。算法停机条件是：群体中最优个体的适应值达到预期的误差范围或者程序的演化代数达到预定的演化代数。2提高算法2.1计算有效长度GEP的编码形式是等长线性符号，表现型是表达式树。根据表达式树，可以计算出基因表达式的值。文献介绍了构造表达式树的层次法，然而建立树的过程是复杂和繁琐的。文献提出了一种新的计算方法——基因阅读运算器（GRCM）。这种方法不需要构造树，直接阅读有效长度内的基因片段就能计算出该基因所表示的函数的值。但是文献并没有给出有效长度的计算方法，若用构造树的方法来确定有效长度，则GRCM的高效性就大打折扣。GEP基因由头部和尾部两部分组成，但并非基因中所有的字符都有用。如公式（2）表示的基因的有效长度为12，而公式（3）表示的基因的有效长度为13。本文给出了计算有效长度的伪代码，用简单的方法计算出基因的有效长度，而不需要把基因解码为表达式树。然后结合GRCM方法，快速计算出染色体的适应值。其有效长度的计算过程如图3所示：刚开始，e和p都指向基因第一位“+”，因为p指向双目运算符，则e向后移两位；然后p后移一位，指向单目运算符“S”，则e相应后移一位；p再后移一位，指向终结符“a”，则e保持不边；p再后移，指向双目运算符“*”，则e后移两位。p再后移，超出了基因头部长度，算法结束。此时e即为该基因的有效长度，也即e指向有效基因片段的最后一个基因位。算出有效基因长度后，再结合GRCM方法，可以快速计算出基因的适应值。首先从有效基因长度内的最后一个运算符“*”开始，读取有效基因片段的最后两个基因位结合该运算符进行运算，把计算结果取代该运算符，并将该位标志为终结符，然后基因有效长度减2。依次类推，直到有效长度为1，则基因的第1位中存放的即是该基因的适应值。改进后的算法从计算基因有效长度到最后算出基因的适应值，都不需要转换为表达式树，非常简单。2.2通过函数函数进行优化在函数建模中，常量参数的处理是一个重要的部分。Ferreira在文献中提出一种常量处理方法：事先给每个基因指定一个常量集合，保存在数组中，集合中的常量在演化过程中通过其他遗传操作发生变化；在染色体末尾增加一段与基因尾部长度相同的整数编码，称为常数域，用于指向常数集合中的第几个常数；在基因的终结符集合中增加“？”，表示对常数域的引用。假设有如下基因，其头部长度为6。其对应的表达式树为从常数域中从左到右取出相应的整数,按照从上到下，从左到右的顺序分别代替表达式树中的“？”，则表达式树变为图6。假设指定的常数集合为：把常数集合中相应的常数代入其中，得到图7:这种方法需要额外的遗传操作对常量集合进行优化，实现起来比较复杂。文献提出了一种简化的常量处理方法：MC方法。MC方法也是事先指定一个数值常量集合，所不同的是该常量集合在演化过程中保持不变。不必在基因尾部增加常数域，而是直接把常量集合中的每个元素作为终结符，利用GEP本身进行优化。其中常量集合C定义为：其中δ是一个常量。集合Hn定义为则对任意的di∈Hn，都2能用C上的不超过n个函数组成的表达式表示。假设n=3，则有c1=δ,c2=3δ,c3=9δ,终结符D={a,1,2,3}。假设有以下基因其对应的表达式树为：然后再把树中的1,2,3分别替换为c1,c2,c3的值即可得到最终表达式树。文献也对文献的常数处理方法进行了改进：在终结符中引入符号“？”表示引用随机常数，用一个数组保存随机常数，译码时按顺序用数组中的元素替换基因中的“？”。数组中常量通过专门的杂交，变异操作进行改变。这种方法不需要在基因尾部增加常数域，不需要进行二次索引。以上三种方法都是在演化过程种一边搜索函数结构，一边进行参数的优化。这就可能导致一些结构良好的模型因为其中的参数不够优化而被淘汰掉。本文采用文献中的常数处理方法，另外又在建模算法中加入了参数估计模块，选择当前较优的一些染色体进行参数优化。例如演化中得到较好的个体是：则利用参数估计模块，对其中的“？”在一定数值范围内进行搜索，保存得到最优适应值的那一组参数。2.3整个算法流程详细的算法流程如图9所示。3测试实验中的公共参数设置：每个染色体由3个基因组成，每个基因的头部长度为4，群体规模为20，最大演化代数为2000。3.1x与y关系式某公司为评估对推销员进行培训的天数x与他们所获得的业绩y的数据如表1，试找出x与y的关系式。函数集O={+,-,*,/}，终结符集D={x,?}。计算得到较好的函数模型为：残差平方和为：91.167，这比用最小二乘法得到的模型y=31.71*(1.363)x的精度要好很多。3.2模型求解结果在某个化学反映里，测得生成物得浓度y与时间t的数据表如表2，试找出t与y的关系式。试验的函数集O={+,-,*,/,sin,cos,ln}，终结符集D={t,?}。计算得到较好函数模型为：残差平方和为：0.0467017，均方差为0.216106与文献中的结果进行比较见表3。文献中还给出了另一个模型：均方差为0.129740。（我们把数据代入模型中得到的实际均方差为32.8390826。）文献得到的模型为：4频繁函数集文章介绍了GEP在函数建模中的应用，给出计算有效基因的伪代码，结合GRCM方法阅读基因，不需要转换为树结构就能快速计算出染色体的适应值。关于常数的处理，增加了参数估计模块，对较好模型进行参数优化，试验显示这种方法是有效的。对于难以用单个函数来描述的复杂数据集，文献提出了频繁函数集概念，即通过函数集合来描述数据集。在未来的研究中，我们将把本文算法应用到这样的更复杂的数据集中。其中n表示所使用的函数集中需要变量最多的函数的参数个数。例如符号集O={+，-，