本文最早发表在本人博客http://www.gotoli.us/?p=1514

遗传算法是一个模拟生物进化的算法，并不是从数学推导出来的。因此很多人直觉认为，遗传算法并不需要数学基础。为什么还有人去探究遗传算法的数学基础呢？一是满足我们的好奇心，二是遗传算法数学基础真的有些用的！！！在介绍遗传算法数学基础之前，先定义一些符号:

因为有各种各样的编码方式、变异操作、交叉操作和选择操作，遗传算法的形态呈现多样性。这里只介绍针对典型遗传算法的分析。那么什么是典型遗传算法呢？典型遗传算法：

1. 编码方式是二进制编码：基因的取值只能是0或者1。
2. 变异操作将所有染色体所有基因位以pm的概率翻转。
3. 交叉操作选择选择相邻的个体，以pc的概率决定是否需要交叉。如果需要交叉，随机选择一个基因位，并交换这个基因位以及之后的所有基因。
4. 选择操作有放回地采样出原种群大小的新一代种群，个体I_i的采样概率如下所示。这种选择操作又被称为轮盘赌选择。

模式定理

模式定理是遗传算法创始人 J.Holland 在其突破性著作《Adaptation in Natural and Artificial Systems》引入的，用于分析遗传算法的工作原理。模式是指编码空间中相似的模块，比如[0，,,1]就是一个模式。染色体[0,1,0,1]和[0,0,0,1]都包含上述的模块。为了引入模式定理，我们还得介绍一些符号。

有了这些符号，我们就可以引入模式定理了。模式定理: 在典型的遗传算法中，下面公式成立。

这个公式是怎么来的呢？我们先来看选择操作对模式H出现概率的影响。根据选择操作，我们很容易得到如下公式。

我们再看变异操作对模式出现概率的影响。变异操作将所有基因位以pm的概率翻转，因此模式H不被破坏的概率为下面第一个不等式。经过变异操作，模式H的出现概率为下面第二个不等式。

最后我们来看交叉操作对模式出现概率的影响。交叉操作选择选择相邻的个体，以pc的概率决定是否需要交叉。如果需要交叉，随机选择一个基因位，并交换这个基因位以及之后的所有基因。因此模式H不被破坏的概率为下面第一个公式。经过交叉操作，模式H的出现概率为第二个公式。

模式定理的通俗说法是这样的，低阶、短长以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。用公式表示便是下面的公式。

马尔科夫链分析

模式定理简单易懂，能够简要地回答人们的疑惑。可能有些偏数学的研究者可能觉得模式定理过于直白，没有数学的“味道”。比如，模式定理没有给出收敛性分析，包括是否收敛和收敛速度等。因此有研究者引入了“正统”的数学分析工具——马尔科夫链，对遗传算法进行收敛性的研究。

马尔科夫链的相关概念:s^{t表示第t时刻的不同状态的概率。P表示转移概率矩阵，其中P_{i,j}表示从第i个状态转移到第j个状态的概率。齐次马尔科夫链的第t+1时刻的状态只和第t时刻有关，可以用公式s}{t+1} = s^{{t}P表示。若存在一个自然数k，使得P}k中的所有元素大于0，则称P为素矩阵。我们还需要引入两个引理。

引理1: 让C、M 和 S 是概率转移矩阵, 其中 M 所有元素大于 0 和 S所有列必有一项大于0，则乘积 CMS 所有元素大于 0。

引理2: 让概率转移矩阵P是一个素矩阵。随着k趋近于无穷，P^k收敛于P{\infty} = \pmb{1}^{T}p{\infty}, 其中p^{\infty}是和初始状态无关的唯一值，并且所有元素大于0。

我们把整个种群的状态看成马尔科夫链的一个状态s，交叉、变异和选择操作则构建了一个概率转移矩阵。我们来分析0<pm<1和1<=pc<=1时概率转移矩阵的性质。让C,M,S分别表示交叉、变异和选择操作带来的概率转移，整体概率转移矩阵P=CMS。1) 经过变异操作，种群状态s_i转化成种群状态s_j的概率(pm)^{h}(1-pm){nL-h} > 0，其中h是两个种群之间不同值的基因位数量。也就是说，M是素矩阵。2) 经过选择操作，种群状态s_i保持不变的概率为

正统的优化算法分析第一个要关心的问题是，优化算法能不能收敛到全局最优点。假设全局最优点的适应度值为maxf，收敛到全局最优点的定义如下

典型遗传算法其实并不收敛。具体的证明我就不列了（感兴趣的同学可以之间看论文 [Rudolph and Günter,1994])，直接说下思路：根据引理2，我们可以知道典型遗传算法会收敛到一个所有种群状态概率都大于0的概率分布上；因此之后，不包含全局最优解的种群一定会不停出现，从而导致上面的公式不成立。实际上，几乎所有遗传算法代码都会将保持已发现最优解。加了这个变化之后的遗传算法是收敛的。思路也是蛮简单的：根据引理2，我们可以知道典型遗传算法会收敛到一个所有种群状态概率都大于0的概率分布上;那么包含全局最优解的种群一定会不停出现，保持已发现最优解的做法会使得上面的公式成立。

看到这部分，我笑出声来。为什么呢？因为这段分析实际用处其实不大。大家想啊，如果我们不考虑之前种群并随机生成新种群（也就是我们说的瞎蒙），构造出来的概率转移矩阵也是素矩阵（P中所有元素的值相等）。也就是说，瞎蒙也是可以收敛哦。因此上面的分析更多地是追求一种结构的美感，对现实实践并没有什么卵用。

模式定理属于脚踏实地型，注重解决人们对遗传算法的疑惑，注重解决实际问题。马尔科夫链属于仰望星空型，注重将遗传算法纳入到一个更广大的理论系统中。其实除了这种两种分析思路之外，还有一种思路。这种思路考察父代和子代种群平均适应度变化。但这种分析思路没有产生太多后续工作，这边就不再介绍了，有兴趣的同学可以直接看论文 [Altenberg and Lee, 1995]。

理论分析的用处

遗传算法理论分析可以指导实际问题。我们用一个分配问题做引子。两位文秘a和b需要处理n件文书；由于两位文秘熟悉领域不一样，两人处理同一件文书所需要的时间不同；怎么分配文书，使得总工作时间最短。遗传算法可以解决这个问题，有两种编码方案：

方案一:我们使用二进制编码。第i位基因是0，则将第i件文书分配给a；第i位基因是1，则将第i件文书分配给b。比如n=3,[1,0,1]表示第1和第3件文书给a文秘，第2件文书给b文秘。

方案二:我们使用排序编码。一个个体代表了文书的排序方案。第i位基因值是j，则将第j件文书排在第i位。两位文秘同时处理文书，其中一位处理手头的文书，则按排序顺序取下一件文书处理。

哪一种编码方式比较好呢？有兴趣的同学可以析下哪种编码方式比较好。先卖个关子，具体答案将在下一篇——遗传算法的变种和多目标遗传算法中介绍。

参考文献

Altenberg, Lee. "The schema theorem and Price’s theorem." Foundations of genetic algorithms 3 (1995): 23-49.
J. Holland, Adaptation in Natural and Artificial Systems, The MIT Press; Reprint edition 1992 (originally published in 1975).
Rudolph, Günter. "Convergence analysis of canonical genetic algorithms." Neural Networks, IEEE Transactions on 5.1 (1994): 96-101.