[科普中国]-模式定理

基本概念

模式(Schema)：编码的字符串中具有类似特征的子集。 例如上述五位二进制字符串中，模式“*111*”可代表4个个体。个体和模式的一个区别就是，个体是由{0，1}组成的编码串，模式是由{0，1，*}组成，‘*’为通配符1。

模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。 模式示例：10**1

定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10**1)=3 。

定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距，记作δ(H)。例如δ(10**1)=4 。

模式阶(Schema Order)：表示模式中已有明确含义的字符个数，记为o(s)，s代表模式。例如o(*111*)=3; 阶数越低，说明模式的概括性越强，所代表的编码串个体数也越多。其中阶数为零的模式概括性最强。模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。

模式定义长度(Schema Defining Length)：指第一个和最后一个具有含义的字符之间的距离，其可表示该模式在今后遗传操作中被破坏的可能性，越短则越小，长度为0最难被破坏。

模式数目：在二进制字符串中，假设字符长度为 λ，字符串中每一个字符可取(0,1,*)三个符号中任意一个，则可能组成的模式数目最多是 3^λ，扩展为一般情况，单个字符的取值有 k 种，则字符串组成的模式数目 n 为 (k+1)^λ。

编码字符串（一个个体编码串）所含模式总数：在二进制字符串中，假设字符长度为 λ，则可能组成的模式数目最多是 2^λ。因为每个个体编码串均已有数字，只能在既定值和‘*’之间选择。扩展为一般情况，单个字符的取值有 k 种，则字符串组成的模式数目 n 为 k^λ。

群体所含模式数：在长度为 λ 规模为 M 的二进制编码字符串群体中，一般含有 2^λ ~ M*2^λ 个模式2。

总结模式定理是适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算法的迭代过程中将按指数规律增长。该定理深刻地阐明了遗传算法中发生“优胜劣汰”的原因。在遗传过程中能存活的模式都是定义长度短、阶次低、平均适应度高于群体平均适应度的优良模式。遗传算法正是利用这些优良模式逐步进化到最优解。

模式能够划分搜索空间，而且模式的阶越高，对搜索空间的划分越细致。模式定理告诉我们：GA 根据模式的适应度、长度和阶次为模式分配搜索次数。为那些适应度较高，长度较短，阶次较低的模式分配的搜索次数按指数率增长；为那些适应度较低，长度较长，阶次较高的模式分配的搜索次数按指数率衰减3。