无关符与匹配串的模式定理：三值字符集中的通配符的匹配方式与阶数

定义9.3.1　若符号“*”既可作为“0”，也可作为“1”，则称“*”为“无关符”或“通配符”。

有了通配符“*”后，二值字符集｛0，1｝就可扩展为三值字符集｛0，1，*｝，由此可以产生诸如0101*、*10*1、1*1*0、0**01、10**1等新字符串。

定义9.3.2　字符串的位数称为字符串的长度l。例如，*101*的字符串的长度为5，1*0011*的字符串长度为7，等等。

定义9.3.3　基于三值字符集｛0，1，*｝所产生的字符串称作模式（schema）。例如，01010、*1*00、01*10等都是模式。但不含通配符*的模式，只描述了一个串的集合，如模式01010只描述了｛01010｝一个串的集合，而模式*1*00却描述了四个串的集合｛01000，01100，11000，11100｝。一般而言，模式描述了某些结构相似的字符串集，即某些位为常值的那些字符串集。

显然，一个长度为l的二进制编码的三值字符串，有（2+1）l个模式。例如前述的5位字串，每一位可取0、1或*，因此总共有35=243种模式。一般而言，若串的基为k，长度为l，则总共有（k+1）l种模式。可见模式的数量要大于实际串的数量kl。

定义9.3.4　称一个模式与一个特定的串相匹配是指：该模式中的1与串中的1相匹配，模式中的0与串中的0相匹配，模式中的*可以匹配串中的0或1。例如：模式01*10匹配两个串为｛01010，01110｝，模式1*0*1匹配四个串为｛10001，10011，11001，11011｝。可以看出，定义模式的好处就是使我们容易描述串的相似性。

我们还可以从另一个角度来看匹配，即一个确定的字符串可以是若干与其相匹配的模式的成员。例如，10这个串就可以是下列四种模式的成员：**，*0，1*，10。一般地，一个串若有l位，则此串可以是2l种模式的成员（又称此串包含有2l种模式）。例如，串10110是25种模式的成员，因为它可以与每个串位是*或这个串位的原确定代码的任一模式相匹配，即每一匹配模式的每一位可以有2种选择（或者是*，或者是原来的确定代码），如10110，1011*，101*0，101**，等等。因此，对于大小为n的种群（若其个体串的长度为l），则包含有最多达n×2l种模式。

模式与模式之间是有差别的。例如，模式01*1**比模式***0*包含更加确定的相似性，而模式1***1*比模式1*1**跨越的长度要长。为此，我们又引入两个有关模式属性的定义：模式H的阶O（H）与模式H的定义距（定义长度）δ（H）。

定义9.3.5　模式H中确定代码（0或1）位置的个数称为该模式的阶，记作O（H）。

比如模式H=011*0*的阶数为4，记为O（H）=4，而模式H=***0*的阶数为1，记为O（H）=1。显然，一个模式的阶数越高，其匹配的个体串（又称样本）数越少，因而确定性越高，样本的相似性越高。

定义9.3.6　模式H中第一个确定代码位置和最后一个确定代码位置之间的距离（用位数来表示）称为该模式的定义距，记作δ（H）。

比如模式H=011*1**的第一个确定代码位置是第1位，最后一个确定代码位置是第5位。其定义距为5-1=4，记为δ（H）=4，而模式H=****0*的定义距为0，记为δ（H）=0。

以下，我们来分析遗传算法的几个重要的操作对模式H的影响。

1.复制（选择）对模式的影响

用A（t）表示t代种群，A（t）可用二进制串表示

这里每个ai代表一个二值代码（也称基因），i=1，2，…，l，所以每个个体串的总长度是l。A（t）中的个体串记为A（j=1，2，…，n），表示t代种群中的第j个个体串。群体A（t）中模式H所能匹配的样本数为m，记为

在复制中，一个串是按适应度f进行复制的，更确切地说是按概率pi=进行选择复制的，其中fi是个体A（t）的适应度。假设一代中群体大小（群体中个体的总数）为n，且个体两两互不相同，则模式H在第t+1代中的样本数

式中：f（H）是模式H所有样本的平均适应度。令群体平均适应度为，则有(www.xing528.com)

可见，经过复制操作后，特定模式数量的增减，按该模式的平均适应度与群体的平均适应度的比值成比例地改变。那些平均适应度高于群体平均适应度的模式，特定模式数量将在下一代中增加，而那些平均适应度低于群体平均适应度的模式，特定模式数量将在下一代中减少。

假设模式H的平均适应度一直高于群体平均适应度，高出部分为c，则有

于是上面的方程可以写成如下的差分方程

若c为常数，则有

可见，高于平均适应度的模式数量将呈指数形式增长。

对复制过程进行分析可知，复制能按适者生存的原则，控制着高适应度的模式数量呈指数增长，或丢弃某些低适应度的个体，但不会产生新的模式结构，因而性能的改进是有限的。

2.交换对模式的影响

交换是串之间的有规则的信息交换，它能创建新的模式结构，但又最低限度地破坏了复制过程所选择的高适应度的模式。

为了搞清楚在交换过程中模式遭破坏（或生存）的概率，我们举个具体的实例来进行说明。

设有下述l=6的串及此串所包含的两个模式

假定A被选中进行交换，交换点的选择是等概率的，即交换点落在左起1、2、3、4、5位置的概率相同。这里不妨假定交换点在位置3后，并以分隔符“|”表示交换点的位置，即有

由于H1的确定位（第2位的“1”与第6位的“0”）在分隔符的两边，而H2的确定位（第4位的1与第5位的“1”）在分隔符的同一边（右边），所以当A与任何其他的串A＇交换时，除非A＇的确定位与模式H1的确定位相同，在其他情况下，交换后模式H1将遭到破坏（即交换后的下一代不可能是模式H1的成员，或称下一代中不能隐含H1模式），而H2模式将依然生存。因为H2中的确定位4的“1”和确定位5的“1”，不管A＇为何串，都将传入下一代。例如A＇=101001，则A与A＇交换后产生的后代为A1=010001，A2=101110，显然A1与A2都不是H1的样本，但却是H2的样本。

当然交换点如果选在位置4，则H2模式的确定位就位于分隔线的两边，H2也可能遭到破坏，不能生存到交换后的下一代中。但是从概率的观点看，由于交换点是等概率产生的，所以模式H1遭破坏的概率（在位置2、3、4、5交换都遭破坏）大大超过模式H2遭破坏的概率（只在位置4交换遭破坏），即H2的“生命力”要强于H1。

显然，模式H的定义距（头尾两个确定位之间的位数）越大则确定位被分隔在交换分隔符两边的概率越大，也就是遭破坏的概率越大，例如H1的定义距为4，那交换点在6-1=5个位置随机产生时，H1遭破坏的概率为

式（9.3.12）表示了下述的模式定理。

定理9.3.1（模式定理）　在遗传算子选择、交换、变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将以指数级增长。

模式定理是遗传算法的理论基础，其意义是深远的。根据模式理论，在遗传算法的迭代过程中，那些短的、低阶数的、高适应度的模式越来越多，最终趋向全局的最优解。