遗传算法中适应度评估的改进
陈小平 （苏州大学电子信息学院，苏州，215021） 李云飞 （苏州大学计算机科学与技术学院，苏州，215021）
摘 要：针对遗传算法中的适应度评估过程进行了改进，提出了遗传个体库的概念，个体库中保存个体的编码和适应度信息。采用查询个体库的方法，可以避免相同个体的适应度函数的重复计算，节省了适应度评估的时间，提高了遗传算法的性能。两个测试函数和FIR数字滤波器设计的实验结果说明这种改进的有效性。
关键词：遗传算法；适应度；个体库；滤波器
引 言
遗传算法（Genetic algorithm，GA）是受Dar－win生物进化理论的哲学思想启发的搜索技术。GA的基本概念和理论框架，是由Holland首先提出的［1］，并由Goldberg作了广泛的探索［2］。GA最具有吸引力的特点是它不需要指导搜索的附加知识。遗传算法诞生以来，许多研究人员对其全局收敛性进行了分析。关于遗传算法性能改进的研究报道也是屡见不鲜，性能改进的研究主要是对算法的各种操作算子和控制参数的改进。Goldberg和Segrest［3］首先使用Markov链分析了遗传算法，Eiben［4］等用Markov链证明了保留最优个体（Eli－tist）的遗传算法的概率性全局收敛，Rudolph［5］用齐次有限Markov链证明了带有复制、交叉、变异操作的标准遗传算法收敛不到全局最优解，不适合于静态函数优化问题，建议改变复制策略以达到全局收敛。Qi和Palmieri［6］对浮点数编码的遗传算法进行了严密的数学分析，用Markov链建模，进行了全局收敛性分析，但其结果是基于群体数为无穷大这一假设的。由于这些收敛性结论均建立在计算时间趋于无穷这个条件上，遗传算法的计算复杂度问题是实际应用更为关心的问题。Buck［7］和Muh－lenbein［8］研究了达到全局最优解的遗传算法的时间复杂性问题。
1 适应度评估的改进及个体库
GA通常由选择、交叉、变异三个基本操作组成。给定一个优化的问题，GA将参数编码成一定长的位字符串，然后以随机的方法组合基于适应度函数重复使用三种操作，执行拷贝字符串，交换字符串的一部分及改变字符串的某一位的值的基本操作，最后发现和解码GA的解。
适应度评估是GA中一个必不可少的步骤，个体的选择概率就是根据个体的适应度计算出的。以往GA中适应度评估对每一代的每一个个体都进行适应度评估，这种评估方法存在的问题是：如果新生成的个体在前一代或前几代出现过，就会对同样的个体重复进行适应度评估，造成算法运行时间的增加，尤其是当适应度函数计算比较复杂时。我们观察GA运行的过程，发现新一代中的个体在前代出现的概率是相当高的，且在近几代中出现相同的个体的机会要大于较前者。
作者改进了适应度评估方法：建立个体库，对新的个体进行适应度评估时，首先查询个体库，若个体库中已有此个体，则直接取出此个体的适应度；否则，对此个体进行适应度函数计算，并将此个体和其适应度加入到个体库中。个体库中每条记录由两部分信息（两个字段）组成：个体编码和个体适应度。个体库的大小一般取GA群体规模的2～4倍，评估过程中若个体库已满，又有新的个体需加入，则删除最先加入的个体，即先进先出的原则，以保证个体库保留的是近几代的个体。改进后的GA流程如图1所示，图中省略了算法的结束条件判断。改进后的适应度评估中的查找记录的时间一般小于适应度函数计算时间，这样就可以节省适应度评估的时间，提高了GA的运行速度。
2 实验结果
2．1 测试函数
选取2个具有相当复杂度的测试函数［9］，这两个测试函数都包含多个已知的极大值。所选函数如下
函数f1有无数个局部极大点，但只有一个（0，0）为全局最大点，最大值为1。此函数的最大峰周围有两圈脊，它们的取值分别为0．990 284和0．962 776，因此优化过程中很容易停滞在这些局部极大点。函数f2是一个多峰函数，但只有一个全局最大点（0，0），最大值也为1。图2是这两个测试函数的三维图形。