荷兰的模式定理

描述

考虑长度为6的二进制字符串，模式1*10*1描述了长度为6的所有字符串的集合，其中1、3和6的位置为1，4的位置为0。*是通配符，这意味着位置2和5可以有1或0的值。模式o ( H ) {displaystyle o(H)} 的顺序被定义为模板中固定位置的数量，而定义长度δ ( H ) {displaystyle \delta ( H)} 是第一个和最后一个特定位置之间的距离。1*10*1的顺序为4，其定义长度为5。 一个模式的适配度是所有与该模式匹配的字符串的平均适配度。一个字符串的适配度是对编码问题解决方案的价值的衡量，由特定问题的评估函数计算得出。利用遗传算法的既定方法和遗传算子，模式定理指出，具有高于平均适配度的短的低阶模式在连续几代中呈指数增长。表示为一个方程式。

E ( m ( H , t + 1 ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] 。{displaystyle\operatorname {E}(m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p]。}

这里m ( H , t ) {displaystyle m(H,t)} 是属于模式H {displaystyle H} 在t代{displaystyle t} 的字符串的数量。f ( H ) {displaystyle f(H)} 是模式H {displaystyle H} 的观测平均适配度，a t {displaystyle a_{t}} 是t代{displaystyle t} 的观测平均适配度。破坏的概率p {displaystyle p} 是交叉或突变会破坏模式H {displaystyle H} 的概率。它可以表示为：。

p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={delta (H) \over l-1}p_{c}+o(H)p_{m}}.

其中o ( H ) {displaystyle o(H)} 是模式的顺序，l {displaystyle l} 是代码的长度，p m {displaystyle p_{m}} 是突变的概率，p c {displaystyle p_{c} } 是交叉的概率。因此，定义长度较短的模式δ ( H ) {displaystyle \delta (H)} ，被破坏的可能性较小。
一个经常被误解的观点是，为什么模式定理是一个不等式而不是一个平等式。答案其实很简单：该定理忽略了这样一个小概率，即属于模式H {displaystyle H} 的字符串将由上一代不属于H {displaystyle H} 的单个字符串（或两个字符串的重新组合）的突变而 "从头开始 "创建。

限制条件

图式定理在保持无限大种群的遗传算法的假设下成立，但并不总是能延续到（有限的）实践中：由于初始种群的抽样误差，遗传算法可能收敛于没有选择优势的图式。这种情况尤其发生在多模态优化中，一个函数可能有多个峰值：种群可能漂移到偏爱其中一个峰值，而忽略其他峰值。

模式定理不能解释遗传算法的威力的原因是，它对所有的问题实例都成立，不能区分遗传算法表现差的问题和遗传算法表现好的问题。