模式定理

本文最初由 SpriteLW 发表于 http://blog.csdn.net/SpriteLW ，[本文中公式图片由http://yexin218.iteye.com 编写]

       首先给模式下定义：模式是一些相似的模块，它描述了在某些位置上具有相似结构特征的个体编码串的一个子集。以二进制为例，个体是由二值字符集V={0,1}构成，而模式却是以三值字符集V={0,1,*}构成。

      

       【模式定理】：遗传算法中，在选择、交叉和变异算子的作用下，具有低阶 、短的定义长度 ，并且平均适应值高于群体平均适应值 的模式将按指数级增长 。

   

    蓝色字代表该模式所必须具备的条件，红色字代表具备该条件时模式将会有的效果。

 

    【结论公式】

     

      

       【说明】

    低阶 ： 要小

    短定义 ： 要小

    平均适应值高于群体平均适应值 ：要大

       ：假设在进化过程中的第t代是时，当前群集P(t)中能与模式H匹配的个体数。

       【推导】

【1平均适应值高于群体平均适应值（ 选择子的作用） 】

             

              【说明】

        ：与模式H所匹配的各个个体Ai能平均复制M*F(Ai)/F(t)个个体到下一代群体中的数量。

              ：与模式H匹配的各个个体Ai

        ：群体中适应度的总和

        ：将适应度均值化

        ：第t代群体中模式 H 所隐含 个体的平均适应度

        ：第t代群体 的平均适应度

        ：模式平均适应值 与 群体平均适应值 之比

       

        设模式H的平均适应度总是高出群体适应度的C倍，则

       

        然后：

       

        由上式可知：

l         若C>0，则m(H,t)呈指数级增长;

l         若C<0，则m(H,t)呈指数级减少。

 

【2低阶（ 交叉算子的作用） 】

交叉操作有可能破坏模式，也可能不破坏，所以有模式的生存率Ps，再考虑交叉操作本身是以交叉率Pc发生的，所以模式H的生存概率下界 为：

    

这样，经过选择算子和交叉算子作用之后，模式H的样本数满足下式：

定义距    越小，则m(H,t)越容易呈指数级增长;

定义距           越大，则m(H,t)越不容易呈指数级增长

【2短定义（ 变异算子的作用） 】

        若某一模式被破坏，则必然是模式描述形式中通配*之处的某一基因值发生了变化，其发生概率是：

当 时，有

由此可见，在变异算子作用下，模式H的生存概率大约是：

l         o(H)越小，模式H越易于生存

l         o(H)越大，模式H越易于破坏

 

综合上式就得出

【模式定理】：遗传算法中，在选择、交叉和变异算子的作用下，具有低阶 、短的定义长度 ，并且平均适应值高于群体平均适应值 的模式将按指数级增长 。