遗传算法模式定理推导

8.3遗传算法基本定理1、模式的概念所谓模式就是一个相同的构形，它描述的是一个数字串的子集合，在这个集合中的所有数字串之间、在某些确定位置上是相同的。模式一般用大写字母H表示。用3个字符的字母表V=[0,1,*]组成的三元组来描述模式，其中，符号*代表不确定数字，即在特定位置上可以与数字0或1相匹配。例如，字符串长为5的模式H=*11*0，并称数字串A=01110是模式H的一个代表串，这是因为数字串A与模式H在确定位置2、3和5上相匹配。遗传算法的操作过程非常简单，从一个含有N个染色体的初始群体出发，不断循环地执行选择、交叉和变异运算。看起来遗传算法是按这种简单的模式直接作用在一个个数字串组成的群体上，实际上，在每一代的计算过程中，这种数字串的显式操作过程蕴含了大量模式的隐含操作。这里，首先讨论选择、交叉和变异算子对模式作用的影响。对于由N个二进制数字串组成的群体中，至多包含有N2乙个模式(所有符号*都为确定数字时)，式中L为数字串长。在遗传算法的执行过程中，所有的模式并不是以同等的机会发生的。有些模式比起其他的模式更明确，例如，模式011*1和模式0****相比，在相似性方面，模式011*1就比较明确。有些模式的跨度要比另一些模式的长，例如，模式1***1和模式1*1**相比，在长度方面，模式1***1要跨越整个串长。为了定量地描述模式，下面介绍两个基本概念:模式的定义长度和模式的阶。模式H的定义长度是指模式H中第1个常数位置与最后1个常数位置之间的距离，用8(H)表示。例如，模式H广011*1**的定义长度为6(H1)=4，这是因为模式H1中第1个常数的位置为1，最后回个常数的位置为5，它们之间的距离为5-1=4；另一个模式^=0******中仅有1个常数位置，即第1个和最后1个常数位置是同一个位置，2因此其定义长度6(H)=0。模式H的阶是指出现在模式H中常数的个数，用O(H)表示。在二进制数字串中，一个模式H的阶就是模式中所有1和0的个数。例如，模式H广011*1**的阶为4，可记为O(H1)=4，同样地，模式H2=0******阶为1，可记为0(H)=1。模式、模式的定义长度以及模式的阶对于讨论和区分数字串的相似性是有用的标志，并且它们提供了一个基本的方法来分析遗传算子对包含在群体中的基因的作用效果。下面分别考虑选择、交叉和变异操作对包含在群体中的模式作用的单独效果和联合效果，并最终导出模式定理。2、选择操作的效果假设在给定时间t代，一个特定的模式H有m个代表数字串包含在群体A(r)中，记为m=m(H,t)，在不同的时间t代，不同的模式H可能有不同数量的代表数字串。在选择操作阶段，每个数字串根据它的适应度函数值进行选择，一个数字串A.(t)的选择率P为

式中，f.为数字串A。)的适应度函数值。当采用没有重叠的N个数字串的群体替代群体A⑺后，人们期望在时间(11)代，模式H在群体A(l1)中有m=m(H,t+1)个代表数字串，则模式H的数量为m（H,m（H,，十1）=,）N・式中，f(H)表示在时间t代模式H包含的所有代表数字串的平均适应度函数值。由于群体的平均适应度函数值可记为:故模式H的选择生长方程可表示为—(‘I)由此式看出，一个特定的模式H按照其适应度函数值与群体的平均适应度函数值之间的比例生长，换句话说，当f(H)>f时，模式H的代表数字串在下一代中将会增多；当f(H)<f时，模式H的代表数字串在下一代中将会减少。群体A(t)中的任一模式H在选择操作下都将按上述规律变化，这种对所有模式数量的增减在选择操作中是并行发生的，遗传算法中隐含的并行机制就在于此。上面定量分析了选择对不同模式的影响，可以看出，在平均适应度函数值以上的模式数量将逐渐增加，平均适应度函数值以下的模式数量将逐渐消失。在此基础上，下面导出一个定量表达式。假设某一特定模式H的适应度函数值保持在高出群体平均适应度函数值以上一个Cf，即f(H)-f=Cf，C为一常数，则模式H的选择生长方程可变为:MH,1)=E)・(/十二(1十C).用(H,F)从时间t=0代开始，模式H的选择生长方程为：He)=MH,O)・(1十CV至此选择的作用已清楚了。当常数C>0时，在群体平均适应度函数值以上的模式数量将会按指数规律增长，而当常数CV0时，在群体平均适应度函数值以下的模式数量将会按指数规律减少。在一定程度上，选择可以把按指数规律增长或减少的模式并行地遗传到下一代。一方面，许许多多不同的模式根据相同的规则，通过利用简单的选择算子被并行地处理；另一方面，仅仅只有选择操作并无助于搜索空间中新的区域，这是因为选择操作并没有搜索新的点。3、交叉操作的效果虽然选择对模式H的数量的影响令人惊奇，但若无交叉操作，它就失去了意义，因为选择不会在数字串空间中产生新的点，它只是一种选择而已。因而，为了检测模式空间中新的区域，需要执行交叉操作。这里，仅考虑简单的一点交

叉的作用效果。一点交叉过程首先是随机选择一对交配数字串，然后随机选择一个交叉位置，将其中一个数字串从交叉位置到右端的子串与另一个交配数字串对应的子串相交换。为了讨论方便，不妨考虑一个长度为6的串以及隐含其中的两个模式。>1=010110耳=许*畀11胃假定A被选中进行交叉，而交叉点以等概率产生，即交叉点落在1、2、3、4、5的概率相同。这里不妨假设交叉点为3,即交叉发生在位置3和位置4之间，并以分隔符“I”表示交叉泣置，即有TOC\o"1-5"\h\z■T=01。|I1。*1*I**0=***iJL#在这种情况下，除了与A进行交叉的串（称作配偶）在确定位（比如位置2、6）相同（这种可能性我们暂且不考虑）外，模式丑］将遭到破坏，因为位置2的“1”和位置6的“0”在交叉产生的子代个体中将被替代为不同的值。比如A的配偶为#=101001，则产生的后代为A=010001，A=101001，都不是H的样本，即发生交叉后，模式气丢失了。而相同情况下，2h却依然存在，因为不论A的配偶为任何串，H中确定位4的“1”和确定位5的“1”都将一块传入子代。可能有的读者会问，2假若交叉点在位置4，H2不也会遭到破坏吗？不错!但有一点可以看出，由于交叉点等概率产生，模式，遭破坏的概率（在位置2、3、4、5交叉都遭破坏）大大超过模式H（只在位置41交叉遭破坏），即H的“生命力”要强于H「22现在定量地讨论一下。我们注意到模式气的定义长度为4，那么交叉点在6-1=5个位置随机产生时，H遭破坏的概率为P=5（H）/（/-1）=4/5，换句话说，其生存概率为1/5；而模式H2的定义长建为1「则H2遭破坏的概率为P=5（H）/（1-1）=1/5，即生存概率为4/5。2d更一般地讲，模式H只有当交叉点落在定义长度之外才能生存。在简单交叉（单点交叉）下的H的生存概率P=1-5（H）/（1-1）。而交叉本身也是以一定S的概率P发生的，所以模式H的生存概率为：CP,eP,e1—R一1)（8.2）现在我们考虑先前暂且忽略的可能性，即交叉发生在定义长度内，模式H不被破坏的可能性。在前面的例子中，若A的配偶在位置2、6上有一位与A相同，则气将被保留。考虑到这一点，式（8.2）给出的生存概率只是一个下界，即有：p,>p,>1-P,--1)（8.3）式（8.3）描述了模式在交叉算子作用下的生存概率。现在考虑模式H在选择和交叉算子的共同作用下的变化。参照式（8.1）和式（8.3），则有：-"勇…「.w，-"•「.・I」"4)由(8.4)式可以看出，在选择和交叉算子的共同作用下，模式的增长(减少)取决于两个因素：(1)模式的平均适应度是否高于群体平均适应度；(2)模式是否具有较短的定义长度。显然，那些平均适应度高于群体平均适应度、具有短定义长度的模式将呈指数级增长。现在考虑选择和交叉结合在一起时对模式的作用效果。当仅考虑选择时，人们感兴趣的是计算一个特定的模式在下一代中期望出现的数目。假设选择和交叉操作是不相关的，可用下式来估算：也〈H、£十I)aH,l)-——1-rfLL-1J(8.5)比较式(8.1)和式(8.3)可以看出，选择和交叉一起对模式的作用效果是，通过把仅有选择作用的模式数量与在交叉作用下的生存概率相乘得到的。模式H的数量增多或减少与一个乘积因子有关。在选择和交叉作用下，这个乘积因子与两个因素有关：模式的适应度函数值f(H)是在群体平均适应度函数值f之上还是之下；模式具有相对短的定义长度还是长的定义长度5(H)。当f(H)越大，8(H)越短，则在下一代中，模式H的数量就越多，且按指数增长率进化发展。4、变异算子的作用效果最后讨论变异算子的作用效果。由变异引起模式H被破坏的概率表示为PO(H)，其中P为变异概率。变异算子是以概率P随机地改变数字串中一个位置上的值，为亍使模式H可以生存下来，所有特定的位置上的值必须存活。因为单个等位基因存活的概率为1-P，并且由于每次变异都是统计独立的，因此，当模式H中个O(H)确定位都存活时，这个模式才存活，因而在变异算子作用下，则模式H的存活概率为(1-P)o(h)。一般情况下P□1，模式H的存活概率可以近似地等于1-PO(H)。""m5、模式定理因此，在考虑选择、交叉和变异作用下，一个特定模式H在下一代中期望产生的数目可近似表示为用(He+1)法用(何，)・^^・[1—Fcyry-(XH)]1-PO(H)乘以(8.5)式：[1-P5^H)][1-PO(H)]=1-P5^