WORD格式可编辑
第三章 遗传算法的理论基础
遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。
3.1 模式定理
不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。
定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。
以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。
引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容
定义3.2 模式H中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。
显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。
定义3.3 模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作?(H)。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。
模式的阶数和定义距描述了模式的基本性质。
下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令A(t)表示第t代中串的群体，以Aj(t)(j?1,2,?,n)表示第t代中第j个个体串。
1．选择算子
在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下：
设在第t代种群A(t)中模式所能匹配的样本数为m，记为m(H,t)。在选择中，一个位串
Aj以概率Pj?fj/?fi被选中并进行复制，其中fj是个体Aj(t)的适应度。假设一代中群体
大小为n，且个体两两互不相同，则模式H在第t?1代中的样本数为：
专业知识分享
WORD格式可编辑
m(H,t?1)?m(H,t)nf(H)?fi(3.1)
式中，f(H)是在t时刻对应于模式的位串的平均适值。
令群体平均适值为f?_?fi/n，则有
f(H)f_m(H,t?1)=m(H,t) (3.2)
现在，假定模式H的平均适值高于群体平均适值，且设高出部分为cf,c为常数，则有
_m(H,t?1)=m(H,t)f?cff___?(1?c)m(H,t) (3.3)
假设从t?0开始，c保持为常值，则有
m(H,t?1)?m(H,0)(1?c) (3.4)
2．交叉算子
然而仅有选择操作，并不能产生新的个体，即不能对搜索空间中新的区域进行搜索，因此引入了交叉操作。下面讨论模式在交叉算子作用下所发生的变化，这里我们只考虑单点交叉的情况。
模式H只有当交叉点落在定义距之外才能生存。在简单交叉(单点交叉) 下H的生存概率Ps?1??(H)/(t?1)。例如一个长度为5的串以及隐含其中的两个模式为
A = 010110 H1 = *1* * *0 H2 =* * *11*
我们注意到模式H1的定义距为4，那么交叉点在6-1=5个位置随机产生时，H1遭破坏的概率Pd??(H2)/(m?1)?1/5，即生存概率为4/5。
而交叉本身也是以一定的概率Pc发生的，所以模式H的生存概率为
Ps?1?PcPd?1?Pc??(H2)/(m?1) (3.5)
现在我们考虑交叉发生在定义距内，模式H不被破坏的可能性。在前面的例子中，若与A交叉的串在位置2、6上有一位与A相同，则H1将被保留。考虑到这一点，式(3.5) 给出的生存概率只是一个下界，即有
Ps1?Pc??(H)/(m?1) (3.6)
可见，模式在交叉算子作用下长度短的模式将增多。 3．变异算子
假定串的某一位置发生改变的概率为Pm，则该位置不变的概率为1－Pm，而模式H在变异算子作用下若要不受破坏，则其中所有的确定位置(‘0’或‘1’的位) 必须保持不变。因此模式
专业知识分享
WORD格式可编辑
H保持不变的概率为(1?Pm)算子作用下的生存概率为
o(H)，其中o(H)为模式H的阶数。当Pm??1时，模式H在变异
Ps?(1?Pm)o(H)?1?o(H)Pm (3.7)
综上所述，模式H在遗传算子选择、交叉和变异的共同作用下，其子代的样本数为
m(H,t?1)?m(H,t)f(H)f_[1?Pc?(H)l?1][1?o(H)Pm]
(3.8)
式(3.8) 忽略了极小项Pc??(H)/(l?1)?o(H)?Pm。通过式(3.8) ，我们就可以给出模式定理。 定理3.1(模式定理) 在遗传算子选择、交叉和变异的作用下，具有阶数低、长度短、平均适值高于群体平均适应度的模式在子代中将以指数级增长。
统计学的研究表明：在随机搜索中，要获得最优的可行解，则必须保证较优解的样本呈指数级增长，而模式定理保证了较优的模式(遗传算法的较优解) 的样本呈指数级增长，从而给出了遗传算法的理论基础。另外，由于遗传算法总能以一定的概率遍历到解空间的每一个部分，因此在选择算子的条件下总能得到问题的最优解。
3.2 积木块假设
由模式定理可知，具有阶数低、长度短、平均适值高于群体平均适值的模式在子代中将以指数级增长。这类模式在遗传算法中非常重要，在这一节给这些模式一个特别的名字——积木块(Building block)。
定义3.4 阶数低、长度短和适值高的模式称为积木块。
由模式定理可知，积木块将以指数级增长。正如搭积木一样，这些“好”的模式在遗传操作下相互拼搭、结合，产生适应度更高的串，从而得到更优的可行解，这正是积木块假设所揭示的内容。
假设3.1 (积木块假设(Building Block Hypothesis)) 阶数低、长度短、适应度高的模式(积木块) 在遗传算子作用下，相互结合，能生成阶数高、长度长、适值高的模式，可最终生成全局最优解。
与积木块一样，一些好的模式在遗传算法操作下相互拼搭、结合，产生适应度更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容。下面用图来说明遗传算法中积木块生成最优解的过程。
假设每代种群规模为8，Si表示每代群体中第i个个体，问题的最优解由积木块AA、BB、CC组成。图3.1为初始种群，个体S1、S7含有AA，个体S4、S8含有BB，个体S3含有CC。
S1 S2 S3 S4 S5 S6 S7 S8
AA AA BB BB 图3.1 初始种群
CC 当种群进化一代后，图3.2为第二代种群，个体S1、S3、S7含有AA，个体S2、S7含有BB，个体S3、S6含有CC。个体S3含有AA、CC，个体S7含有AA、BB。当种群进化到第二代后，
专业知识分享
第三章遗传算法的理论基础
