遗传算法系列之三:数学摆摆手，“很惭愧，只做了一点微小的工作”

遗传算法是一个模拟生物进化的算法，并不是从数学推导出来的。但还是有人探究遗传算法的数学基础呢？在介绍遗传算法数学基础之前，先定义一些符号:

因为有各种各样的编码方式、变异操作、交叉操作和选择操作，遗传算法的形态呈现多样性。这里只介绍针对典型遗传算法的分析。那么什么是典型遗传算法呢？典型遗传算法： 1. 编码方式是二进制编码：基因的取值只能是0或者1。 2. 变异操作将所有染色体所有基因位以pm的概率翻转。 3. 交叉操作选择选择相邻的个体，以pc的概率决定是否需要交叉。如果需要交叉，随机选择一个基因位，并交换这个基因位以及之后的所有基因。 4. 选择操作采用轮盘赌算法。轮盘赌算法有放回地采样出原种群大小的新一代种群，个体

I_i

的采样概率如下所示。

(1)

\begin{eqnarray*} p(I_i) = \frac{f(I_i)}{\sum_{i=1}^{m} f(I_i)} \nonumber \\ \end{eqnarray*}

模式定理

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

有了这些符号，我们就可以引入模式定理了。

模式定理:在典型的遗传算法中，下面公式成立。 (2)

\begin{eqnarray*} p(H)^{t+1} >= p(H)^{t}\frac{\overline{f}(H)}{\overline{f}}(1-pm*O(H))(1-pc*\frac{L(H)}{L-1}) \end{eqnarray*}

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

(3)

\begin{eqnarray*} p(H)^{t+1} &=& \frac{\sum_{\{I^j|H \in I^j\}}f(I^j)p(I^j)^t}{\sum_{j=1}^{m}f(I^j)p(I^j)^t} \nonumber \\ &=& p(H)^{t} \frac{(\sum_{\{I^j|H \in I^j\}}f(I^j)p(I^j)^t) / p(H)^{t} }{\overline{f}} \nonumber \\ &=& p(H)^{t} \frac{\overline{f}(H)}{\overline{f}} \nonumber \\ \end{eqnarray*}

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

(1-pm)^{O(H)}

。当

0 <= x <= 1

和n=1,…时，不等式

(1-pm)^{O(H)} >= 1-O(H)*pm

成立，从而经过变异操作，模式H的出现概率。

(4)

\begin{eqnarray*} p(H)^{t+1} >= p(H)^{t}\frac{\overline{f}(H)}{\overline{f}}(1-pm*O(H)) \nonumber \\ \end{eqnarray*}

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

(1-pc)(1-\frac{L(H)}{L-1}) >= 1-pc*\frac{L(H)}{L-1}

。经过交叉操作，模式H的出现概率。

(5)

\begin{eqnarray*} p(H)^{t+1} >= p(H)^{t}\frac{\overline{f}(H)}{\overline{f}}(1-pm*O(H)) (1-pc*\frac{L(H)}{L-1}) \nonumber \\ \end{eqnarray*}

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

\frac{\overline{f}(H)}{\overline{f}}(1-pm*O(H)) (1-pc*\frac{L(H)}{L-1}) >= 1

，此时

(6)

\begin{eqnarray*} p(H)^{t+p} >= p(H)^{t}(\frac{\overline{f}(H)}{\overline{f}}(1-pm*O(H)) (1-pc*\frac{L(H)}{L-1}))^p \end{eqnarray*}

即模式H呈现指数增长。

马尔科夫链分析

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

马尔科夫链的相关概念:

\pmb{p}^t

表示第t时刻的不同状态的概率。

\pmb{P}

表示转移概率矩阵，其中

\pmb{P}_{i,j}

表示从第i个状态转移到第j个状态的概率。齐次马尔科夫链的第t+1时刻的状态只和第t时刻有关，可以用公式

\pmb{p}^{t+1} = \pmb{p}^{t}\pmb{P}

表示。若存在一个自然数k，使得

\pmb{P}^{k}

中的所有元素大于0，则称

\pmb{P}

为素矩阵。我们还需要引入两个引理。

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

\pmb{P}

是一个素矩阵。随着k趋近于无穷，

\pmb{P}^{k}

收敛于

\pmb{P}^{\infty} = \pmb{1}^{T}\pmb{p}^{\infty}

, 其中

\pmb{p}^{\infty}= \pmb{p}^{0}lim_{k \rightarrow \infty} \pmb{P}^{k} = \pmb{p}^{0}

是和初始状态无关的唯一值，并且所有元素大于0。

我们把整个种群的状态看成马尔科夫链的一个状态

\pmb{s}

，交叉、变异和选择操作则构建了一个概率转移矩阵。我们来分析

0 < pm < 1

和

0 <= pc <= 1

时概率转移矩阵的性质。让

\pmb{C}, \pmb{M}, \pmb{S}

分别表示交叉、变异和选择操作带来的概率转移，整体概率转移矩阵

\pmb{P} = \pmb{C}\pmb{M}\pmb{S}

。1) 经过变异操作，种群状态

\pmb{s}_i

转化成种群状态

\pmb{s}_j

的概率

\pmb{M}_{i,j} = (pm)^{h}(1-pm)^{n*l - h} > 0

，其中h是两个种群之间不同值的基因位数量。也就是说，

\pmb{M}

是素矩阵。2) 经过选择操作，种群状态

\pmb{s}_i

保持不变的概率

\pmb{S}_{i,i} = \frac{\prod_{i=1}^{n}f(I_i)}{(\prod_{i=1}^{n}f(I_i))^n} > 0

。也就是说,

\pmb{S}

的所有列必定有一元素大于0。根据引理1，我们可以知道概率转移矩阵

\pmb{P}

是素矩阵。

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

(7)

\begin{eqnarray*} lim_{k \rightarrow \infty} P( max_{I \in \pmb{s}^k} (fitness(I)) = maxf) = 1 \nonumber \\ \end{eqnarray*}

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

看到这部分，我笑出声来。为什么呢？因为这段分析实际用处其实不大。大家想啊，如果我们不考虑当前种群而是随机生成新种群（也就是瞎蒙），构造出来的概率转移矩阵也是素矩阵，

P_{i,j} = \frac{1}{2^{nL}}

。也就是说，瞎蒙也是可以收敛哦。因此上面的分析更多地是追求一种结构的美感，对现实实践并没有什么卵用。

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

参考文献

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.