模式理论
我们在分析编码字符串时， 常常只关心某一位或某几位字符， 而对其他字符不关心。
换句话讲， 我们只关心字符的某些特定形式， 如$1**$, $11$, $0***$， 这种特定的形式就叫模式。
模式、模式阶及模式定义长度
模式集
模式集（Schema）： 指编码的字符串中具有类似特征的子集
以五位二进制字符串为例：
模式$111$ 可代表4个个体： 01110， 01111， 11110， 11111
模式$*0000$ 可代表2个个体： 10000, 00000
个体是由二值字符集$V = {0, 1}$中的元素所组成的一个编码串
模式是由三值字符集$V = {0, 1, *}$中的元素所组成的一个编码串， 其中 * 表示通配符
模式阶
指模式中已有明确含义（二进制字符时值0或1）字符， 记作$o(s)$， 式中s代表模式。
例如：
模式 (011*1**) 含有4个明确含义的字符， 其阶次是4， 记作 o(011*1**) = 4;
模式 (0*******)的阶次是1， 记作o(0*******) = 1.
阶次越低， 模式的概括性越强， 所代表的编码串个体数也越多， 反之亦然;
当模式阶次为零时， 它没有明确含义的字符， 其概括性最强。
\[p_s = (1 - p_m)^{o(s)}\]$p_m$表示变异存活概率
模式的定义长度(Schema Defining Length)
指模式中第一个和最后一个具有明确含义的字符之间的距离， 记作$\delta(s)$。
例如：
模式(011*1**)的第一个字符为0， 最后一个字符为1， 中间有3个字符，其定义长度为4， 记作$\delta(011*1**) = 4$ ;
模式(0******)的长度是0， 记作$\delta(0**) = 0$;
一般地，有式子：
\[\delta(s) = b - a\]- b——模式s中最后一个明确字符的位置
- a——模式s中最前一个明确字符的位置
模式的长度代表该模式在今后遗传操作(交叉、变异)中被破坏的可能性；
模式长度越短， 被破坏的可能性越小， 长度为0的模式最难被破坏。
被破坏的概率：
\[p_d = \frac{\delta(s)}{\lambda - 1}\]编码字符串的模式数目
模式总数
二进制字符串
假设字符的长度为$l$， 字符串每个字符可取$(0, 1, *)$三个符号中任意一个， 可能组成的模式数目最多为：
\[3 \times 3 \times 3 ... \times 3 = (2 + 1)^l\]一般情况
一般情况下， 假设字符串长度为$l$, 字符的取值为$k$种， 字符串组成的数目$n_1$最多为：
\[n_l = (k + 1)^l\]编码字符串(一个个体编码串)所含模式总数
二进制字符串
对于长度为$l$的某二进制字符串， 它含有的模式总数最多为：
\[2 \times 2 \times 2 \times 2 ... \times 2 = 2^l\]Ps： 这个数目是指字符串已经确定为0或1， 每个字符只能在已定值(0/1)中选取；前面所述的$n_1$指字符串未确定， 每个字符可在${0, 1, *}$三者中选取。
一般情况下
长度为$l$、取值有$k$种的某一字符串， 它可能含有的模式数目最多为：
\[n_2 = k^l\]群体所含模式数
在长度为$l$， 规模为$M$的二进制编码字符串群体中，一般包含有$2^l \thicksim M · 2^l$个模式
模式定理
模式定理： 适应度高于群体平均适应度的， 长度较短， 低阶的模式在遗传算法的迭代过程中将按指数规律增长。
复制时的模式数目
公式推导
(1) 假设在第$t$次迭代时， 群体$P(t)$中有$M$个个体， 其中$m$个个体属于模式$s$， 记作$m(s, t)$。
(2) 个体$a_i$按其适应度$f_i$的大小进行复制。从统计意义讲， 个体$a_i$倍复制的概率$p_i$是：
\[p_i = \frac{f_i}{\sum_{j=1}^M f(j)}\](3) 因此复制后在下一代群体$P(t+1)$中，群体内数域模式$s$(或称与模式$s$匹配)的个体数目$m(s, t+1)$可用平均适应度按下式近似计算：
\[m(s, t+1) = m(s, t)·M·\frac{\bar f(s)}{\sum_{j=1}^M f(j)}\](4) 式中$\bar f(s)$表示第$t$代属于模式$s$的所有个体之平均适应度， $M$表示群体中拥有的个体数目。
设第$t$代所有个体(不论它数域何种模式)的平均适应度是$\bar f$， 有等式：
\[\bar f = \frac{\sum_{j=1}^{M} f(j)}{M}\](5) 综合上述两式, 复制后模式$s$所拥有的个体数目可按下式近似计算：
\[m(s, t+1) = m(s, t) · \frac{\bar f(s)}{\bar f}\]结论：
- 上式说明复制后下一代群体中属于模式$s$的个体数目， 取决于该模式的平均适应度$\bar f(s)$与群体的平均适应度$\bar f$之比；
- 只有当模式$s$的平均值$\bar f(s)$大于群体的平均值$\bar f$时， $s$模式的个体数目才能增长。 否则， $s$模式的数目要减少。
- 模式$s$的这种增减规律， 正好复合复制操作的“优胜劣汰”原则， 这也说明模式的确能魔术编码字符串的内部特征。
进一步推导
假设某一模式$s$在复制过程中其平均适应度$\bar f(s)$比群体的平均适应度$\bar f$高出一个定值$c \bar f$, 其中$c$为常数， 则上式改写为：
\[m(s, t+1) = m(s, t)·\frac{\bar f + c \bar f}{\bar f} = m(s, t)·(1+c )\]从第一代开始， 若模式$s$以常数$c$繁殖到$t+1$代， 其个体数目为：
\[m(s, t+1) = m(s, 1) · (1 + c)^t\]结论： 从数学上讲， 上式是一个指数方程，它说明模式$s$所拥有的个体数目在复制过程中以指数形式增加或减少。
交叉
(1) 以单点交叉算子为例
有两个模式： $s_1: 10$， $s_2: **10$
它们有一个共同的可匹配的个体： $a: 0111000$
(2) 选择个体$a$进行交叉
(3)随机选择交叉点
$s_1: 1***0$， 交叉点在2~6之间都可能破坏模式$s_1$
$s_2： *10$， 交叉点在4~5之间才破坏$s_2$
(1) 交换发生在模式$s$的定义长度$\delta(s)$范围内， 即模式被破坏的概率是：
\[p_d = \frac{\delta(s)}{l - 1}\]例：
$s_1$被破坏的概率为$\frac{5}{6}$
$s_2$被破坏的概率为$\frac{1}{6}$
(2) 模式不被破坏， 存活下来的概率为：
\[p_s = 1 - p_d = 1 - \frac{\delta(s)}{l-1}\](3) 若交叉概率为$p_c$， 则模式存活下来的概率为：
\[p_s = 1 - p_c · \frac{\delta(s)}{l - 1} \tag{2}\](4) 经复制、交叉操作后， 模式$s$在下一代群体中所拥有的个体数目为：
\[m(s, t+1) = m(s, t)·\frac{\bar f(s)}{\bar f} · [1 - p_c · \frac{\delta(s)}{l-1}]\]模式I的定义长度对模式的存亡影响很大， 模式的长度越大， 越容易被破坏。
变异
(1) 变异时个体的每一位发生变化的概率是变异概率$p_m$， 也就是说， 每一位存活的概率是$(1 - p_m)$。 根据模式的阶$o(s)$, 可知模式中含有明确含义的字符有$o(s)$个，于是模式$s$存活的概率是：
\[p_s = (1 - p_m)^{o(s)}\](2) 通常$p_m « 1$， 上式用泰勒级数展开取一次项， 可近似表达为：
\[p_s = 1 - p_m · o(s) \tag{3}\]结论： 上式说明， 模式的阶次$o(s)$越低，模式$s$存活的可能性越大， 反之亦然。
综合(1)， (2)， (3)式可以得出遗传算法经复制、交叉、变异操作后， 模式$s$在下一代群体中所拥有的个体数目， 如下式所示：
\[m(s, t+1) \approx m(s, t) · \frac{\bar f(s)}{\bar f} · [1 - p_c · \frac{\delta(s)}{l-1} - p_m · o(s)] \tag{4}\]适应度高于群体平均适应度的， 长度较短， 低阶的模式在遗传算法的迭代过程中将按指数规律增长。
