遗传算法中适应度评估的改进

时间：2015-12-20 22:17:14 所属分类：智能科学技术 浏览量:

遗传算法中适应度评估的改进 陈小平 （苏州大学电子信息学院，苏州，215021） 李云飞 （苏州大学计算机科学与技术学院，苏州，215021） 摘 要：针对遗传算法中的适应度评估过程进行了改进，提出了遗传个体库的概念，个体库中保存个体的编码和适应度信息。采

遗传算法中适应度评估的改进
陈小平 （苏州大学电子信息学院，苏州，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〕研究了达到全局最优解的遗传算法的时间复杂性问题。

本文针对遗传算法中的适应度评估过程进行了改进，提出了遗传个体库的概念，个体库中保存个体的编码和适应度信息。这种改进方法在有些应用场合可以大大节省适应度评估的时间，从而获得较快的收敛速度，改进了算法的性能。两个测试函数和FIR数字滤波器设计的实验结果说明这种改进的有效性。
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是这两个测试函数的三维图形。


遗传算法中适应度评估的改进 : 　
所选实验方法为：
SGA——标准GA，交叉概率pc＝0．9，变异概率pm＝0．01，按比例选择并保留最优个体；
MGA——本文适应度评估改进后的GA（称之为记忆遗传算法），交叉概率pc＝0．9，变异概率pm＝0．01，按比例选择并保留最优个体。

SGA和MGA两种方法均采用二进制字符串编码，长度为32位，前16位表示x，后16位表示y。两种算法群体规模均设为100，总进化代数设为100，在MGA中个体库的大小为200，即群体规模的2倍。在PIV866微机上（内存128M）分别用两种方法实验20次。所得结果如表1所示，表中x，y，f（x，y）为算法结束时的典型值，t表示算法平均运行时间（单位为s），Count为整个算法中新个体在个体库中的重复总次数，p为重复概率（＝Count／10 000）。从表1中可以看出，重复概率还是相当高的，但算法的运行时间并未明显减少，改进后的GA效果并不是太明显，这是由于这两个测试函数的适应度计算所需时间较短，以至于与查询个体库所需时间相当的缘故。
论文遗传算法中适应度评估的改进

2．2　FIR数字滤波器设计
有限冲激响应（Finite impulse response，FIR）滤波器是数字信号处理中一类重要的数字滤波器。将GA用于FIR数字滤波器设计的频率采样法中〔10〕，确定过渡带样本值，解决了传统的查表法不能保证数据是最优的问题，使FIR滤波器性能较查表法得到了改善。采用GA进行FIR滤波器设计时，个体的适应度计算非常复杂，需进行快速傅里叶计算（FFT），涉及到矩阵运算（快速傅里叶计算），而且随着采样点数的增加，矩阵越庞大，计算适应度消耗的时间会更多。采用本文适应度评估改进后的GA，较大地提高了算法的效率。
例1　用频率抽样法设计FIR低通滤波器。技术指标：通带边缘频率ωp＝0．2π／rad，阻带边缘频率ωs＝0．3π／rad，最大通带波动rp＝0．8dB，最小阻带衰减as＝40dB。
实验方法同3．1中的SGA和MGA，此例中只有一个参数——过渡带样本值T需要估计，采用二进制字符串编码，长度为16位。算法中设群体规模60，交叉概率pc＝0．9，变异概率pm＝0．01，总进化代数为50，均采用最优个体保留，在MGA中个体库的大小为200，即群体规模的3倍多。在PIV866，128M RAM微机上运行MATLAB语言编制的GA程序，反复运行多次，最后结果见表2和图3，表中T为过渡带样本值，As是实际最小阻带衰减，Rp是最大实际通带波动，两者均为典型值，t表示算法平均运行时间（单位为s），Count为算法中新个体在个体库中的重复总次数，p为重复概率（＝Count／3 000）。从表2中可以看出，此例MGA比SGA的运行时间明显减少，效率得到了提高。图3是基于GA的低通滤波器幅度响应曲线。
由上述两个例子发现，遗传算法中经交叉变异生成新个体的重复概率是相当高的，例1中为27．7％和41．6％，例2中为62．6％，产生这种现象的机理值得进一步研究。但重复概率肯定与编码字符串长度和个体库的大小有关，字符串长度越短，重复概率越大，个体库越大，重复概率也会越大，但库太大势必造成算法搜索库的时间增加，在本文所述实验中发现库的大小以2～4倍群体规模为宜。
3　结束语
时间复杂度是遗传算法研究人员十分关心的问题。本文探讨了遗传算法的适应度评估的一种基于遗传个体库的改进方法，对新的个体进行适应度评估时，首先查找个体库，可以避免对相同个体进行适应度的重复计算，提高算法的效率，实验中还发现个体重复概率非常高，这种现象的机理值得进一步研究。两个测试函数和FIR数字滤波器设计的实验结果，尤其是适应度计算复杂的后者，说明这种改进方法的有效性。参考文献


遗传算法中适应度评估的改进 : 　
〔1〕　Holland JH．Adaptation in Natural and ArtificialSystems〔M〕．University of Michigan，Ann Arbor，MI，1975．1～22
〔2〕　Goldberg D E．Genetic algorithms：in search opti－mization＆machine learning〔M〕．Addison－WesleyPublishing Company Inc，1989．70～84
〔3〕　Goldberg D E，Segrest P．Finite Markov chain anal－ysis of genetic algorithm〔A〕．In：Proc ofthe second IntConf on Genetic Algorithms〔C〕．1987．1～8
〔4〕　Eiben A E，Aarts E H，etal．Globalconvergence ofgenetic algorithms：an infinite Markov chain analysis〔A〕．In：Proc ofthe firstConf on ParallelPro－blemSolving from Nature〔C〕．Heidelberg，Berlin：Springer－verlag，1991．4～12
〔5〕　Rudolph G．Convergence properties of canonical ge－netic algorithms〔J〕．IEEE Tran on Neural Net－works，1994，5（1）：96～101
〔6〕　QiX，PalmieriF．Theoreticalanalysis ofevolution－ary algorithmswith an infinite population sizein con－tinuous space，Part I：basic properties of selectionand mutation〔J〕．IEEE Tran on NeuralNetworks，1994，5（1）：102～119
〔7〕　Buck T．The interaction of mutation rate，selection，and self－adaption within genetic algorithms〔A〕．In：Proc ofthe Second Conf on ParallelProblem Solvingfrom Nature〔C〕．Amsterdam，North Holland，1992．84～94
〔8〕　Muhlenbein H．How genetic algorithms really work．I：mutation and hillclimbing〔A〕．In：Proc of theSecond Conf on Parallel Problem Solving from Na－ture〔C〕．Amsterdam，North Holland，1992．15～25
〔9〕　候格贤，吴成柯．遗传算法的性能分析〔J〕．控制与决策，1999，14（3）：257～260
〔10〕　陈小平，于盛林．遗传算法在FIR滤波器设计——频率抽样法中的应用〔J〕．电子学报，2000，28（10）： 118～120


遗传算法中适应度评估的改进 :

转载请注明来自：http://www.zazhifabiao.com/lunwen/dzxx/znkxjs/28177.html