2.3 遗传算法的理论基础
2.3.1 模式定理
模式定义：模式是描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板。
不失一般性，考虑二值字符集{0，1}，由此可以产生通常的0、1字符串。增加一个符号“*”，该符号称作“通配符”，即“*”既可以当作“0”，也可以当作“1”。这样，二值字符集{0，1}就扩展为三值字符集{0，1，*}，由此可以产生诸如0110、0*1 1**、**0 1*0之类的字符串。
基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串，称作模式。这里需要强调的是，“*”只是一个描述符，而并非遗传算法中实际的运算符号，它仅仅是为了描述上的方便而引入的符号。
“模式”的概念可以简明地描述具有相似结构特点的个体编码字符串。在引入了模式概念之后，遗传算法的本质是对模式所进行的一系列运算，即通过选择操作将当前群体中的优良模式遗传到下一代群体中，通过交叉操作进行模式的重组，通过变异操作进行模式的突变。通过这些遗传运算，一些较差的模式逐步被淘汰，而一些较好的模式逐步被遗传和进化，最终就可以得到问题的最优解。
多个位串中隐含着多个不同的模式。确切地说，长度为L的位串，隐含着2L个不同的模式，而不同的模式所匹配的位串的个数是不同的。为了反映这种确定性的差异，引入“模式阶”概念。
模式阶定义：模式H中确定位置的个数称作该模式的模式阶，记作O(H)。
比如模式011*1*的阶数为4，而模式0*****的阶数为1。显然，一个模式的阶数越高，其样本数就越少，因而确定性就越高。但是，模式阶并不能反映模式的所有性质。即使具有相同阶数的模式，在遗传操作下，也会有不同的性质。为此，再引入“定义距”概念。
定义距定义：在模式 H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作D(H)。
模式定理：在遗传算法选择、交叉和变异算子的作用下，具有低阶、短定义距，并且其平均适应度高于群体平均适应度的模式，在子代中将呈指数级增长[2]。
模式定理又称为遗传算法的基本定理。模式定理阐述了遗传算法的理论基础，说明了模式的增加规律，同时也给遗传算法的应用提供了指导。根据模式定理，随着遗传算法一代一代地进行，那些定义距短、位数少、适应度高的模式将越来越多，因而可期望最后得到的位串的性能越来越得到改善，并最终趋向全局的最优点。
模式的思路提供了一种简单而有效的方法，使能够在有限字符表的基础上讨论有限长位串的严谨定义的相似性；而模式定理从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。
2.3.2 积木块假设
模式定理说明：具有某种结构特征的模式，其在遗传进化过程中的样本数目将呈指数级增长。这种模式在遗传算法中非常重要，将其定义为“积木块”。
积木块定义：具有低阶、短定义距以及高平均适应度的模式，称作积木块。之所以称之为积木块，是由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐构造出适应度越来越高的个体编码串。
模式定理说明了积木块的样本数呈指数级增长，也就说明了用遗传算法寻求最优样本的可能性，但它并未指明遗传算法一定能够寻求到最优样本。而下面引入的“积木块假设”说明了遗传算法的这种能力。
积木块假设：个体的积木块通过选择、交叉、变异等遗传算子的作用，能够相互结合在一起，形成高阶、长距、高平均适应度的个体编码串[3-4]。
积木块假设说明了用遗传算法求解各类问题的基本思想，即通过基因块之间的相互拼接能够产生对问题的更好的解，最终生成全局最优解。
从遗传算法的模式定理可知：具有高适应度、低阶、短定义矩的模式，其数量会在种群的进化中呈指数级增长，从而保证了该算法获得最优解的一个必要条件。另一方面，积木块假设则指出：遗传算法有能力使优秀的模式向着更优的方向进化，即遗传算法有能力搜索到全局最优解。