模式和遗传算法的搜索机制

在“遗传算法初步解析”中，相信看过的人已经初步了解这个算法的过程。但在最后有一个问题，遗传算法的选择，交叉，变异的操作是怎么影响到最后的结果的？在讲解这个问题前，先了解一个概念：模式。下图是一个官方的定义：

其实模式就是一个概括的东西，我的理解是把大家都有的东西抽象出来就是一个模式，定义比较难懂，举个例子就明白了，先看下面一组染色体：
111 100 101 110 ---------（一）

这就是一个模式，他是一个（1××）模式，其中×表示任意的0或者1，

再比如

1100 1101 1000 1001 -------（二）

也是一个模式，它是（1×0×）模式。模式的确定位很好理解，就是确定了的位数，模式（一）模式的阶就是确定位的长度，上面模式（一）的阶是1，模式（二）的阶是2，模式的定义长度是第一个确定位到最后一个确定位的距离，模式（一）的定义长度是0，模式（二）的定义长度是2.还有一个比较重要的概念：极小模式，在上面的(二)中，它们既属于（1*0*）模式，也属于（1×××）模式，也属于（××0×）模式，但是只有（1×0×）是它的极小模式。

现在来看看选择交叉变异这些操作对遗传算法的影响，首先画个图：

在上面这张图中，a代表种群A的空间，b代表种群A的极小模式，c代表全局空间，当对种群A进行选择操作时，搜索范围只会出现在a空间，对种群A进行交叉操作时，搜索范围会限于b空间，只有加上变异操作，才能对整个空间进行搜索。举个简单的例子：

假如种群A是： 1100 1101 1000 1001 它的极小模式是（1×0×）

则a就是种群本身，对应选择操作的范围，b是模式（1×0×），对应交叉操作的范围，c是整个4位二进制串（××××），对应变异操作的范围。

从上面的描述来看，如果把选择和交叉看作是局部最优解的话，变异则是保证全局最优解的必要条件。所以说没有变异操作的遗传算法能够得到最优解的条件是初始种群的极小模式包含最优解。

顺便附带说一下遗传算法的模式定理： 在标准遗传算法中，具有低阶，短定义长度，平均适应度高出种群平均适应度的模式将依指数级增长。

附两张《计算智能》一书中的图，介绍模式定理的证明过程：

参考：计算智能一书。作者徐宗本