第三章 遗传算法的理论基础

#被淘汰，有害的基因可能被保留。引起群体结构发生变化的主要因素是随机波动的——遗传漂移，它也是产生未成熟收敛的一个主要原因。对此可以采用增大群体容量的方法来减缓遗传漂移，但这样做可能导致算法效率的降低。上述三个方面都有可能产生未成熟收敛现象，即群体中个体的多样性过早地丢失，从而使算法陷入局部最优点。在遗传算法处理过程的每个环节都有可能导入未成熟收敛的因素。遗传算法未成熟收敛产生的主要原因是，在迭代过程中，未得到最优解或满意解以前，群体就失去了多样性。具体表现在以下几个方面：在进化初始阶段，生成了具有很高适应度的个体X。在基于适应度比例的选择下，其它个体被淘汰，大部分个体与X一致。相同的两个个体进行交叉，从而未能生成新个体。通过变异所生成的个体适应度高但数量少，所以被淘汰的概率很大。群体中的大部分个体都处于与X一致的状态。3.4.2未成熟收敛的防止在分析了未成熟收敛产生的原因后，下面要解决的是如何防止该现象的发生，即如何维持群体多样性以保证在寻找到最优解或满意解以前，不会发生未成熟收敛现象。解决的方法有以下几种。1．重新启动法这是实际应用中最早出现的方法之一。在遗传算法搜索中碰到未成熟收敛问题而不能继续时，则随机选择一组初始值重新进行遗传算法操作。假设每次执行遗传算法后陷入不成熟收敛的概率为Q(0冬Q<1)，那么做n次独立的遗传算法操作后，可避免未成熟收敛的概率为F(n)二1-Qn，随着n的增大，F(n)将趋于1。但是，对于Q较大的情况，如果优化对象很复杂以及每次执行时间都很长的情况，采用该办法显然是不合适的。配对策略(MatingStrategies)为了维持群体的多样性，可以有目的地选择配对个体。一般情况下，在物种的形成过程中要考虑配对策略，以防止根本不相似的个体进行配对。因为在生物界，不同种族之间一般是不会杂交的，这是因为它们的基因结构不同，会发生互斥作用，同时杂交后会使种族失去其优良特性。因此，配对受到限制，即大多数是同种或近种相配，以使一个种族的优良特性得以保存和发扬。然而，这里所说的匹配策略有不同的目的。其目的是，由不同的父辈产生的个体试图比其父辈更具有多样性，Goldberg的共享函数(SharingFunction)就是一种间接匹配策略。该策略对生物种(Species)内的相互匹配或至少对占统治地位的物种内的相互匹配有一定限制。Eshelman提出了一种可以更直接地防止相似个体交配的方法——防止乱伦机制(IncestPreventionMechanism)。参与交配的个体是随机配对的，但只有当参与配对的个体间的海明距离超过一定阈值时，才允许它们进行交配。最初的阈值可采用初始群体海明距离的期望平均值，随着迭代过程的发展，阈值可以逐步减小。尽管Eshelman的方法并不能明显地阻止同辈或相似父辈之间进行交配，但只要个体相似，它就有一定的影响。匹配策略是对具有一定差异的个体进行配对，这在某种程度上可以维持群体的多样性。但它同时也具有一定的副作用，即交叉操作会使较多的模板遭到破坏，只有较少的共享模板得以保留。重组策略(RecombinationStrategies)重组策略就是使用交叉算子。在某种程度上，交叉操作试图产生与其父辈不同的个体，从而使产生的群体更具多样性。能使交叉操作更具有活力的最简单的方法就是，增加其使用的频率和使用动态改变适应度函数的方法，如共享函数方法。另一种方法是把交叉点选在个体的具有不同值的位上。只要父辈个体至少有两位不同，所产生的子代个体就会与其父辈不相同。维持群体多样性的更基本的方法是，使用更具有破坏性的交叉算子，如均匀交叉算子。该算子试图交叉近一半的不同位，因而保留的模板比单点或两点交叉所保留的模板要少得多。总之，重组策略主要是从使用频率和交叉点两方面考虑，来维持群体的多样性。这对采用随机选择配对个体进行交叉操作可能有特定的意义，但对成比例选择方式，其效果则不一定明显。4替代策略(ReplacementStrategies)匹配策略和重组策略分别是在选择、交叉阶段，通过某种策略来维持群体的多样性。而替代策略是确定在选择、交叉产生的个体中，选择哪一个个体进入新一代群体。DeJong采用排挤(Crowding)模式，用新产生的个体去替换父辈中类似的个体。Syscuda和Whiteley也采用类似的方法，他们仅把与父辈各个个体均不相似的新个体添加到群体中。这种替换策略仅从维持群体的多样性出发，存在一定的负面影响，即交叉操作会破坏较多模板，但这种影响比前两种策略的要少。性能评估遗传算法的实现涉及到它的五个要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作设计和控制参数设定，而每个要素又对应不同的环境，存在各种相应的设计策略和方法。不同的策略和方法决定了各自的遗传算法具有不同的性能或特征。因此，评估遗传算法的性能对于研究和应用遗传算法是十分重要的。目前，遗传算法的评估指标大多采用适应度值。特别在没有具体要求的情况下，一般采用各代中最优个体的适应度值和群体的平均适应度值。以此为依据，DeJong提出了两个用于定量分析遗传算法的测度:离线性能(Off-linePerformance)测度和在线性能(On-linePerformance)测度，得到两个评估准则。1．在线性能评估准则定义3・8设X(s)为环境e下策略s的在线性能，f(t)为时刻t或第t代中相应于环境eee的目标函数或平均适应度函数，则X(s)可以表示为eX(s)二1丈f(t)(3.9)eTet=1式(3.9)表明，在线性能可以用从第一代到当前的优化进程的平均值来表示。2．离线性能评估准则定义3・9设X*(s)为环境e下策略s的离线性能，则有e1TX*(s)=工f*(t)(3.10)eTet=1式中，f*(t)=best{f(1),f(2),f(t)}。eeee式(3.10)表明，离线性能是特定时刻或特定代的最佳性能的累积平均。具体地说，在进化过程中，每进化一代就统计目前为止的各代中的最佳适应度或最佳平均适应度，并计算对进化代数的平均值。DeJong指出：离线性能用于测量算法的收敛性，在应用时，优化问题的求解可以得到模

拟，在一定的优化进程停止准则下，当前最好的解可以被保存和利用；而在线性能用于测量算法的动态性能，在应用时，优化问题的求解必须通过真实的实验在线实现，可以迅速得到较好的优化结果。但是，从遗传算法的运行机理可知，在遗传算子的作用下，群体的平均适应度呈现增长的趋势，因此，定义3.8和定义3.9中的f(t)和f*(t)相差不大，它们所反映ee的性质也基本一样。下面以最优化方法的收敛速度和收敛准则来讨论遗传算法的性能。一般优化问题可描述为求x二(x,x,,x)t，使/(x)达到最小(或最大)。最优化方法12n通常采用迭代方法求它的最优解，其基本思想为：给定一个初始点x，按照某一迭代规则产0生一个点列｛x｝，使得当｛x｝为有穷点列时，其最后一个点是最优化问题的最优解。当｛x｝是iii无穷点列时，它有极限点，且其极限点是最优化问题的最优解。一个好的优化算法为：当x能i稳定地接近全局极小点(或极大点)的邻域时，迅速收敛于x*，当满足给定的收敛准则时，迭代终止。假设一算法产生的迭代点列｛x｝在某种范数意义下收敛，即ilim卜-x=0(3.11)is1式中，x=x+a，a为步长因子。i+1iii若存在实数a>0及一个与迭代次数无关的常数q>0，使得limis(3.12)limis(3.12)则称此算法产生的迭代点列｛x｝具有q-a阶收敛速度(a为迭代步长因子)。因为||x-x||ii+1i是代-x*||的一个估计，所以在实际中，一般用比+]-x||代替卜厂x*||，作为迭代终止判决条件。当a=1，q>0时，称｛x｝具有q线性收敛速度。i当1<a<2，q>0或1，q=0时，称｛x｝具有q超线性收敛速度。i当a=2时，称｛x｝具有q二阶收敛速度。i具有超线性收敛速度和二阶收敛速度的迭代算法的收敛速度比较快。关于算法的终止准则，实际应用中可以使用各种不同的方法进行确定。Himmeblau提出了下面的终止准则。当||x』>e和|f(x」>e时，采用

x-xx-x—i+1iXi<£(3.13)否则采用|x-X|<£或If(X)-f(X)|<£(3.14)i+1ii+1i式中，£为根据实际问题要求精度给出的适当小的正数。根据以上Himmeblau提出的终止准则，实际中可以用各代适应度函数的均值之差来衡量遗传算法的收敛特性。定义收敛性测量函数为：C(s)二[£[f(t+1)-f(t)](3.15)eTeet=1式中，f'(t)为时刻t或第t代中相应于环境e的目标函数或平均适应度函数。e从优化问题中寻找最优解或最优解组的角度考虑，可以定义部分在线特性：f(s)=1丈f'e(t)(3.16)nTet=1式中，f'e(t)为群体中对应于最优解或最优解组的个体适应度的均值。小生境技术和共享函数Cavicchio提出只有在子串的适应度超过父代的情况下，子串才能替代父串进入下一代群体的预选择机制，该机制趋向于替换与其本身相似的个体，能够维持群体的分布特性，并且不断地以优秀个体来更新种群，使种群不断被优化。DeJong提出基于排挤的机制，其思想来源于一个有趣的生物现象：在一个有限的生存空间中，各种不同的生物为了延续生存，必须相互竞争各种有限的生存资源。差别较大的个体由于生活习性不同而很少竞争。处于平衡状态的大小固定的种群，新生个体将代替与之相似的旧个体。排挤机制可以维护当前种群的多样性，排挤机制用海明距离来度量个体之间的相似性。这就是小生境技术。Glodberg和Richardson利用共享函数来度量两个个体