简单遗传算法的收敛性分析与马尔可夫链

本节利用马尔可夫链讨论简单遗传算法的收敛性问题。首先介绍一些相关概念。

定义2-6 设{xt：t=0，1，2，…}是一随机变量序列，xt（t=0，1，2，…）在有限状态空间S={a1，a2，…，an}上取值。若对任意k ≥0及正整数i0，i1，…，ik，ik+1 都有：

则称{xt：t=0，1，2，…}为有限马尔可夫链。条件概率P（xt+1=aj|xt=ai）称为该马尔可夫链在时刻t 处于状态ai 的条件下，在时刻t+1 转移到状态aj 的转移概率，记为pij（t）。若转移概率与时间t无关，即对任意ai、aj ∈S 和任意两时刻t1、t2 都有pij（t1）=pij（t2）=pij，则称该马尔可夫链是齐次的，此时称P=（pij）n×n 为该齐次马尔可夫链的转移矩阵。

设{xt：t=0，1，2，…}是一有限齐次马尔可夫链，对任一时刻t（t=0，1，2，…），该马尔可夫链在时刻t的一维分布定义为：

一维分布（2-48）可以表示为向量形式如下：

由

可知：

由式（2-51）知，有限齐次马尔可夫链在任一时刻t 的分布由初始分布p（0）和转移矩阵P 所确定。

定义2-7 设A 是n 阶矩阵：

（1）若对任意i，j ∈{1，2，…，n}，都有aij ≥0，则称A 是非负的，记为A≥0；

（2）若对任意i，j ∈{1，2，…，n}，都有aij ＞0，则称A 是正的，记为A＞0。

定义2-8 设A 是n 阶非负矩阵：

（1）若存在正整数k，使得Ak 是正的，则称A 是本原的；

（2）若存在方阵C，T，使得通过相同的行和列的置换可将矩阵A 变换成形式式：

则称A 是可约的，否则称A 为不可约的；

显然，每个正矩阵都是本原的。

引理2-1 若A，B 是n 阶随机矩阵，则AB 也是n 阶随机矩阵。

证 矩阵AB 第i行元素之和为：

推论2-2 若A1，A2，…，At 是n 阶随机矩阵，则A1A2…At 也是n 阶随机矩阵。

定义2-9 设A 是一个n 阶随机矩阵：

（1）若A 具有相同的行，则称A 是稳定的；

（2）若A 的每一列至少有一个正元素，则称A 是列可允许的。

引理2-2 设C，M，S 是随机矩阵，且M 是正的，S 是列可允许的，则乘积矩阵CMS 是正的。

证 设A=CM，B=AS。由于C 是随机的，于是C 的每一行都存在正元素，从而有：

即A＞0。又因为S 是列可允许的，所以C 的每一列都存在正元素，从而有：

这就证明了B=AS=CMS＞0。

引理2-3 设P 是一个n 阶本原随机矩阵，则当k→∞时，Pk 收敛到一个正的稳定随机矩阵：

其中（p1，p2，…，pn）是满足下列方程的唯一解：

例2-11 给定下列随机矩阵：

证明该随机矩阵是本原的。

解 为简单起见，以×表示矩阵中的正元素，由

知P 是本原的。

是一个稳定的随机矩阵，且有：

其中（p1，p2，…，pn）是满足下列方程的唯一解：

并且有pi ＞0（i=1，2，…，m），pi=0（i=m+1，…，n）。

下面研究简单遗传算法的马尔可夫链表示。

由于SGA 所处的状态只与群体中的个体有关，故可将SGA 的一个群体看作是一个状态。若群体中每个个体是一个长度为l的二进制位串，而群体的规模为N，则每一个状态可用一个长度为l·N 的二进制位串来表示。所以简单遗传算法的状态空间为Ω={0，1}l·N。

例如，若N=4，当前群体为{（1，0，1，1），（0，1，1，0），（0，0，1，1），（0，0，0，1）}，则表示当前群体的状态为（1，0，1，1，0，1，1，0，0，0，1，1，0，0，0，1）。

由于SGA 的状态是有限的，且SGA 中的杂交、变异和选择算子与演化代数无关，因而第t+1代群体所处的状态只与第t代群体所处的状态有关，而与第t 代群体之前群体所处的状态无关，故若用X（t）表示SGA 第t代群体所处的状态，则{X（t），t=0，1，2，…}是一个有限齐次马尔可夫链。

下面讨论该有限齐次马尔可夫链的转移矩阵。为了证明简单起见，假定遗传算法中的选择、杂交和变异算子的应用次序为：杂交，变异，选择。即使用下列遗传算法的基本结构：

SGA 的一个状态通过杂交、变异和选择算子的作用转移到下一个状态，故转移矩阵可以表示为3个随机矩阵C，M，S 的乘积，其中C，M，S 分别表示由杂交、变异和选择算子所引起的随机矩阵。

（1）杂交矩阵C。

设C=（cij）为由杂交算子引起的|Ω|×|Ω|矩阵，其中cij 表示状态i经杂交算子的作用后变为状态j 的概率。因为一个状态经杂交算子的作用后，总要变为另一个状态，所以有：(www.xing528.com)

即C=（cij）是一个随机矩阵。

（2）变异矩阵M。

设M=（mij）为由变异算子引起的|Ω|×|Ω|矩阵，其中mij 表示状态i经变异算子的作用后变为状态j 的概率。

因为变异算子是独立地作用在群体中个体的每一个基因位上的，若变异概率pm 满足0＜pm ＜1，那么有：

式中，Hij 表示状态i与状态j 的Hamming距离。

即M=（mij）是一个正的随机矩阵。

（3）选择矩阵S。

设S=（sij）为由选择算子引起的|Ω|×|Ω|矩阵，其中sij 表示状态i经选择算子的作用后变为状态j 的概率。因为一个状态经选择算子的作用后，总要变为另一个状态，所以有：

即S=（sij）是一个随机矩阵。

设状态i所表示的群体为{a1，a2，…，aN}，用轮盘赌选择策略，则个体ai 被选择的概率为：

于是状态i经选择后仍为状态i的概率为：

由此可知S=（sij）是列可允许的。

定义2-10 设P（t）={x1（t），x2（t），…，xN（t）}是遗传算法当代数为t 时的群体，Zt=max{f（xk（t））|t=1，2，…，N}表示群体P（t）的最优适应值，f*=max{f（x）|x ∈{0，1}l}表示全局最优适应值。

若

则称遗传算法依概率收敛于全局最优解。

定理2-2 若杂交概率pc 和变异概率pm 满足0≤pc ≤1，0＜pm ＜1，则简单遗传算法不能依概率收敛于全局最优解。

证 设状态i所表示的群体{a1，a2，…，aN}满足：

定理2-2说明了简单遗传算法不能依概率收敛到全局最优解，但只要对简单遗传算法做一点改动，每次将当前找到的最优解保留下来，则可证明改进后的遗传算法依概率收敛到全局最优解。

改进后的简单遗传算法描述如下：

改进后的简单遗传算法在当前代保留了以前各代所得到的最优解。为确定起见，将当前最优的解存放在群体的开始，并假定保留的最优解不参加遗传运算。这样改进后的简单遗传算法第t 代所处的状态可以用一个长度为l· （N +1）的二进制位串来表示—— （abest（t），a1（t），…，aN（t）），其中abest（t）表示遗传算法到第t 代为止所得到的最优解，而a1（t），a2（t），…，aN（t）分别表示第t代群体中的N 个个体，所以修改后的简单遗传算法的状态空间为Ω+={0，1}l·（N+1）。

例如，若N=4，当前群体为{（1，0，1，1），（0，1，1，0），（0，0，1，1），（0，0，0，1）}，若直到当前群体之前的最好个体为（1，0，1，0），则表示当前群体的状态为：

(1,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,0,0,0,1)

利用上述改进后遗传算法状态的表示，将Ω+的状态按其最优解的适应值从大到小排序，若最优解的适应值相同，则按原状态空间的顺序排序。由于最优解不参加遗传运算，若记改进后的遗传算法的杂交矩阵、变异矩阵和选择矩阵分别用|Ω+|×Ω+|阶矩阵C+、M+、S+表示，易知C+，M+，S+可以表示为：

式中，C，M，S 分别为简单遗传算法的|Ω|×|Ω|阶杂交矩阵、变异矩阵和选择矩阵。

在进行选择后，要将当前群体的最优解与保留的最优解进行比较，以获得到目前为止的最优解。这一操作可以用一转移矩阵U=（uij）来表示。

对任一状态i∈Ω+，设状态i 所表示的群体为[abest（t），a1（t），…，aN（t）]，并设b=argmax{f（ai（t））|i=1，2，…，N}∈{0，1}l，即b 为适应值最大的个体，则当f[abest（t）]＜f（b）时，uij=1，这里状态j 表示的群体为[b，a1（t），…，aN（t）]；否则uii=1。于是矩阵U的每一行有且仅有一个元素为1，其他元素为0。

又根据状态空间Ω+中状态的排列顺序可知，对任意i，j∈Ω+，当i＜j 时，Uij=0，所以矩阵U 是一个下三角矩阵，即：

式中，Uij 均为|Ω|×|Ω|阶矩阵，而且U11 为单位矩阵。

定理2-3 改进后的简单遗传算法依概率收敛到全局最优解。

证 由上面的讨论知，改进后的简单遗传算法的转移矩阵为：

其中CMSU11=CMS=P 是正的随机矩阵，而：

由引理2-4知：

于是，若（p1（0），p2（0），…，pn（0））为SGA 的任一初始分布，则存在极限分布：

因此算法依概率收敛到全局最优解。