《一种新型的ＧＥＰ算法及应用研究.doc》由会员分享，可在线阅读，更多相关《一种新型的ＧＥＰ算法及应用研究.doc（8页珍藏版）》请在三一文库上搜索。
1、一种新型的算法及应用研究0 引言 在进化计算家族中，遗传算法(GA)1用固定长度的线性串表示个体。由于遗传操作简单，目前已广泛应用于各行各业的优化组合、图像处理、机器人等问题中；但却丧失了功能的复杂性2。在遗传规划(GP)3,4中，个体是长度和形状不同的非线性实体（分裂树），所以能够表示复杂问题而被应用于复杂函数建模、时间序列预测等领域；但遗传操作复杂、演化时间长。基因表达式编程(GEP)2，5，6则将个体编码成固定长度的线性串（基因组或染色体），然后将其转换为不同长度和形状的非线性实体（表达式树），从而实现了用简单编码表示复杂问题，同时易于遗传操作，并且通过遗传操作所产生的新个体在语法上都是
2、有效的，不需要对新个体进行有效性判断和处理，在速度上比GP提高了24个数量级。但GEP在将染色体串表示成表达式树，再遍历表达式树（通常是求后缀表达式，也称逆波兰式）来计算适应度值过程中，由于树的构造和遍历操作非常耗时，大大影响了算法的效率。对此，本文提出了一种新的染色体解码方法（Gene Postfix Expression Decoding，GPED）。该方法只需对染色体作简单处理，即可直接得到染色体相对应的后缀表达式，不需要构造和遍历表达式树，可进一步提高演化效率。文中给出了GPED的有关性质证明，以及与其相对应的表达式树的另一种构造方法。在GPED基础上，提出了一种新的GEP算法GPEP
3、(Gene Postfix Expression Programming)。 1 GEP中染色体基因和表达式树的互相转换 GEP的基因由头部和尾部构成。头部可以含有函数符号和终端符号，而尾部只包含终端符号。在具体问题中，头部长度h是根据求解问题的复杂度而选定的；而尾部长度t则由式（1）计算得到。其中n是带有最多参数的函数的参数个数。 从左到右逐个读取该基因中的字符。根据其语义，按层次顺序构成表达式树(ET)2，如图1所示。对于给定的表达式树，按从上到下、从左到右的顺序层次遍历ET中的节点，得到的符号序列即为基因编码的有效部分，如遍历图1中的表达式树可得到序列CS*a/eb。 2 一种新的GEP
4、解码方法和对应表达式树构造方法及其优点 在GEP中，要计算个体适应度值，就必须将个体染色体或基因组转换为表达式树；然后遍历表达式树得到相应的函数式；最后根据适应度函数计算适应度值。通常的做法就是后序遍历表达式树得到后缀表达式，如图1中表达式树的后缀表达式为aeb/*SC。这样就可以由后缀表达式计算表达式值。由于要进行大量的构造树和遍历树操作，成为影响GEP算法效率的瓶颈。本文提出一种新的针对GEP基因的解码方法。 定义1(基因后缀表达式解码) 下述过程称为基因后缀表达式解码。首先，设置一个计数量nCount并初始化为1。从左到右逐个读取基因中的字符，按下列规则改变nCount的值，直到nCou
5、nt为0。 性质1 对任意一个有效的GEP，即GEP的头部和尾部满足式(1)，基因后缀表达式解码扫描完基因串之前，计数量nCount必定已等于0。 性质1保证了绝不会出现当基因后缀表达式解码扫描完基因串后，nCount 的值还不为0的情况。 下面介绍一种新的表达式树构造方法。过程如下：基因的首字符对应树的根节点；从左到右逐个读取基因串的字符，并按照从右到左、深度优先的顺序构造表达式树，直到树中所有叶节点都是终端字符。与GEP一样，每个函数节点连接的子分支数目为该节点的参数个数，而终端字符节点只作为叶节点。以式(2)为例，用新方法构造的表达式树如图2所示。按照从右到左、深度优先的顺序遍历该表达式
6、树，即可得到基因的有效编码部分，如按这种方法遍历图2中的表达式树得到CS*a/eb。它正是式(2)的基因有效编码部分。为了与GEP中的表达式树区别，将这种新方法构造的树称为后缀表达式树 (Postfix Expression Tree，PET)。 性质2 任意一个有效的GEP基因通过基因后缀表达式解码得到的都是一个在语义上合法的后缀表达式。 证明 由PET的构造过程可知，若函数的参数个数为n，则该函数节点有n个分支，即该节点的出度为n。当节点不为根节点时，函数节点和终端节点入度均为1；当为根节点时，入度均为0。为了统一，不妨设一个虚节点指向PET的根节点，这样每个节点不管其是不是根节点，其入度
7、均为1。构造PET时设置一个计数变量nCount，每增加一个新节点时，nCount加上新节点的出度数并减去新节点的入度数。因为虚节点出度为1，所以令nCount初始值为1。如果新节点为函数节点，则出度为n，入度为1，所以nCount要加上n-1；如果新节点为终端节点，则出度为0，入度为1，所以nCount应减去1。而树中所有节点的出度之和等于入度之和，所以当nCount为0时，PET树将构造完毕。一个PET的构造步骤与GPED步骤是一一对应的。根据PET的构造过程可知，PET的后序遍历结果即PET的后缀表达式，刚好是基因有效编码部分的逆序。而PET在语义上代表一个合法的数学或逻辑表达式，因此得
8、到的后缀表达式也必定是一个合法的表达式。证毕。 从上面可以看到，基因后缀表达式解码也同样能将一个基因表达成一种新的表达式树。作为基因的表现性，并且任何一个GEP表达式树，均可以通过变换得到一个语义相同（对符号回归问题即同一函数）而形状不同的PET 树，因此基因表示问题的能力和算法性能不会改变。但是，通过GPED可以由基因串直接得到PET树的后缀表达式，而无须构造和遍历表达式树。将新解码方法应用于GEP算法，可望比原解码方法具有更高的效率。这正是GPED的优越性所在。下面将通过实验验证。 3 基于GPED的GEP算法及与基本GEP算法比较 本文将基因后缀表达式解码与基本GEP算法2相结合，提出一
9、种新的算法GPEP。为了验证GPED的效率，GPEP采用与基本GEP一样的算法流程、参数设置，具体参见文献2，5。GPEP与GEP不同的是基因解码方法（表达式树的构造方法），以及个体的表现型。用文献2中SI问题来验证。SI问题是一个符号回归问题，文献2用N=5n4+4n3+3n2+2n+1来产生10个样本2，然后在这些样本上通过GEP演化发现一个好的函数来拟合。由于这些样本不含噪声，可以通过演化得到精确解(即每次独立运行找到的最优解刚好是上式)，用成功率作为衡量算法性能的精确尺度。表2给出了GPEP与GEP的比较。对于参数的不同设置，用GPEP和GEP各独立运行20次（本文所有实验均在P4 2
10、.4GHz的PC机上运行）。 可见GPEP表示问题的能力和搜索效率,与GEP相比并不会降低；然而由于GPEP算法采用了GPED方法，无须频繁构造和遍历树操作，在同样条件下演化时间大大降低。当问题越复杂，群体规模、演化代数、基因头长、基因个数等参数越大时， GPEP的演化效率就越明显。 为了进一步增强GPEP算法在实际问题中的求解精度和演化效率，对其作如下改进：遗传操作只选用多点重组、IS变换、倒置和变异四种算子。多点重组指当染色体由多个基因组成时，对每个基因均进行单点重组。这样m个基因的染色体就进行m点重组。为降低选择压力，保持种群多样性，新算法中采用每个个体只与其儿子竞争的选择机制。当一个个
11、体通过遗传操作产生一个新个体时，如果新个体的适应度大于父个体，则替换父个体。另外，算法采用邻域变异搜索来提高局部搜索能力。为了提高初始解的质量，先生成五倍于群体规模N的个体，按适应度选取较大的前N个个体作为初始群体演化。这样可以加快收敛速度，提高演化效率。对于实际应用中的复杂问题，为了克服最优解停滞（演化很多代都没找到更好解），本算法采用突变算子7对群体中部分适应度低的个体进行再生。但过多使用这种突变算子，不仅增加了计算开销，也破坏了进化的稳定性，即优良的或有潜力的个体可能被破坏掉，所以本文设定一阈值MAXNO。当最优个体没有更新的代数超过MAXNO时，对群体进行排序，选择适应度小于10%的个
12、体进行突变。实验证明，这种改进是有效的。GPEP算法描述如下： 4 基于GPED的GPEP在碎石桩复合地基承载力预测中的应用 碎石桩复合地基是目前处理软弱地基常用的方法之一。由于地基土的物理、力学性能比较复杂,碎石桩复合地基承载力的计算公式还无法确定。用改进遗传神经网络8和GP方法9虽然提供了预测碎石桩复合地基承载力较为有效的途径，但精度仍不尽如人意。本文利用上面的新算法GPEP对文献8，9中的数据进行演化建模，并与GAANN和GP的结果进行比较。GPEP函数集取+,-, *, /, Ln, Exp, Sqrt, Pow10, Sin, Cos，Tan，变量集合(表3)取a,b,c,d,e,f
13、,g,x,y,z。参数设置：群体大小为200，演化代数为5 000，基因头长为15，基因个数为7，表达式树用+连接，IS变换概率为0.5，倒置概率为0.5，变异概率为0.01。以15个样本中前13个作为训练数据（表3前13行），后2个作为检验样本（表3最后2行）。 从表3中可以看出，无论是训练样本还是检验样本，GPEP得到的模型计算的相对误差都要远小于GP模型得到的相对误差。表4进一步将GPEP预测结果与GA_ANN8、GP7以及钱鸿缙计算方法8的预测结果作了比较。结果显示GPEP的预测精度均高于这些方法。 用GPEP得到的模型为 5 结束语 本文分析了GEP中染色体由基因串到表达式树解码过程
14、的不足，提出了表达式树的另一种构造方法,以及与之对应的新解码方法GPED，并对有关定义和性质作了详细探讨。新解码方法的优点在于：它在评价个体适应度时不必构造和遍历表达式树，大大节约了演化时间。本文通过实验证明了在同样参数条件下这种新方法的速度比GEP快一倍左右。最后，将该方法应用于GEP中，并从初始群体生成、选择策略、遗传算子等方面作了新的改进，提出了一种新的算法GPEP。通过在碎石桩复合地基承载力预测中的应用，GPEP算法的演化精度要大大高于遗传神经网络、GP等算法。由于GPEP算法事先不需要专业领域的知识和影响基因变量各要素之间的关系，演化精度较高且简单有效，适合于复杂问题的预测，值得进一步研究和应用。 本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。