第三章 经典遗传算法的收敛性

3.1 相关概念

确定性过程：在每个固定的时刻t，变化过程的结果是确定的，这个结果可用t的某个确定函数描述，如sint等。

随机过程：过程变化的结果是随机的，即以某种可能性出现多个（有限或无限个）结果之一，这个结果可用于t有关的某个随机变量描述（对于每个固定的时刻$t_j(j=1,2,3...),X(t_j)$tj​(j=1,2,3...),X(tj​)都是随机变量，则称X(t)为随机过程）。（设随机试验E的样本空间S={e}，对其每个元素e，依照某个规则确定出一个样本函数X(e,t)，由全部元素e所确定的一簇样本函数X(e,t)称为随机过程。）

马尔科夫链 设状态空间的基数是可列（可数）的，过去各时刻状态分别为$A_1,A_2,...,A_{m-1}$A1​,A2​,...,Am−1​，若目前状态为$A_m$Am​的概率满足$P(A_m\mid A_{m-1},...,A_1)=P(A_m\mid A_{m-1})$P(Am​∣Am−1​,...,A1​)=P(Am​∣Am−1​)（无后效性），则称这样的概率转移过程为马尔科夫链。

有限的马尔科夫链 状态数为有限的马尔科夫链。

状态转移矩阵 对有限的马尔科夫链，设其状态空间E的基数为$\vert E \vert=N$∣E∣=N，给它们依次编号为1,2,3,…,N，记为E={1,2,…,N}，在某个时刻t，从状态i转移到状态j的概率记为$p_{ij}(i,j\in E)$pij​(i,j∈E)，则称矩阵
$P=\begin{bmatrix} p_{11} & p_{12} & {...}&p_{1N} \\ p_{21} & p_{22} & {...}&p_{2N} \\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ p_{N1} & p_{N2} & {...}&p_{NN} \\ \end{bmatrix}$P=⎣⎢⎢⎢⎡​p11​p21​⋮pN1​​p12​p22​⋮pN2​​......⋱...​p1N​p2N​⋮pNN​​⎦⎥⎥⎥⎤​
为马尔科夫链的状态转移矩阵。注意：P中元素非负，且每一行元素之和为1。

齐次马尔科夫链：状态转移矩阵与时刻t无关的马尔科夫链。

3.2 经典遗传算法的马尔科夫链分析

群体长字符串 设经典遗传算法群体规模为n，每个个体串长为l，群体看成n个个体字符串依次排列所得到的一串长为nl的字符串。

状态空间 将每一个群体看成一个状态，将所有可能群体集合看成状态空间E，则E的基数$\vert E\vert=2^{n\times l} $，依次给状态编号为1,2,…,$2^{n\times l}$2n×l。

状态的表示 对状态$i \in E$i∈E，令$\pi_k(i)(k=1,2,...,n)$πk​(i)(k=1,2,...,n)表示状态i中第k个个体对应的长为l的字符串，则状态可表示为$i=\pi_1(i)\pi_2(i)...\pi_n(i)$i=π1​(i)π2​(i)...πn​(i)。

状态转移矩阵 经典遗传算法从一代群体（一个状态）进化到下一代群体（另一个状态）的过程只是和当前群体有关，和以前群体无关，故此过程可以看做一个马尔科夫链。因为经典遗传算法中，交叉、变异和选择的方式均与代数无关，所以，此马尔科夫链是齐次的，又因为$\vert E \vert$∣E∣有限，故此马尔科夫链为有限齐次的马尔科夫链。因为交叉、变异和选择方式均与时间无关，所以其状态转移矩阵为常矩阵。设交叉引起的状态转移矩阵为C，变异引起的状态转移矩阵为M，选择引起的状态转移矩阵为S，则经典遗传算法中的状态转移矩阵为P=CMS。

引理 设C,M,S均为N阶随机矩阵，且M为正矩阵，S为列允许的，则P为正随机矩阵。

定理 在经典遗传算法中，若取$P_c\in (0,1),p_m\in (0,1)$Pc​∈(0,1),pm​∈(0,1)，选择为比例选择，则P=CMS>0

定理 经典遗传算法是一个遍历的马尔科夫链，即不论初始分布如何取，都有正的极限分布$p^\infty=(p^\infty_1,p^\infty_2,...,p^\infty_N)$p∞=(p1∞​,p2∞​,...,pN∞​)。其中，$p^{\infty}_i>0(i=1,2,3,...,N),\sum_i^Np^\infty_i=1,N=2^{nl}$pi∞​>0(i=1,2,3,...,N),∑iN​pi∞​=1,N=2nl，且在任一代t，马尔科夫链处于每一状态的概率大于0（$p^t=p^0P^t>0$pt=p0Pt>0）。

定义 设$Z_t=\max{F(\pi_k^t(i))\mid k=1,2,...,n}$Zt​=maxF(πkt​(i))∣k=1,2,...,n，F*为最优解的适应度函数值，若

$\lim_{t\to \infty}P\{Z_t=F^*\}=1$limt→∞​P{Zt​=F∗}=1，则称遗传算法依概率收敛于全局最优解。

定理 经典遗传算法不依概率收敛于全局最优解。

定理 在一个遍历的马尔科夫链中，对任一初始状态i及一个其他状态j，从状态i转移到状态j的转移次数的平均值是有限的。·