On this page

    ☰

    模式理论

    我们在分析编码字符串时， 常常只关心某一位或某几位字符， 而对其他字符不关心。

    换句话讲， 我们只关心字符的某些特定形式， 如$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\]

    模式的长度代表该模式在今后遗传操作(交叉、变异)中被破坏的可能性；

    模式长度越短， 被破坏的可能性越小， 长度为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$高出一个定值$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}\]

    适应度高于群体平均适应度的， 长度较短， 低阶的模式在遗传算法的迭代过程中将按指数规律增长。