2.5 差分进化算法的收敛性分析

2.5.1 差分进化算法的随机过程描述

作为一种基于种群的随机优化算法，标准DE算法的进化过程可以用一个随机过程来描述，若将每一代种群看成随机过程的一个状态，那么所有可能的种群便构成状态空间。对于形如的全局优化问题，假定f在有界闭集上存在有限的全局最优值f*，相应最优解为X*。在有限精度下，搜索区域Ω可以看作n维欧氏空间中有限个离散的点的集合，其中每一个点的坐标对应于种群中的一个个体X。假设种群规模为NP，则每一代种群对应于Ω中的NP个点，如果将这些点看成一个NP点集，则等同于每一代种群对应于一个NP点集，同时也对应于随机过程的一个状态S。Ω中所有的NP点集对应所有可能的种群集合。

在标准DE算法中，生成新个体的父代个体Xi(t)、Xr 1(t)、Xr2(t)和Xr 3(t)都来源于当前种群且所有进化算子，包括变异算子、交叉算子都只与当前种群有关，同时选择操作也只在新生成个体和当前种群个体之间进行，因此新种群只与当前种群有关，即而与其父代种群之前的各代种群（τ<t）无关。这一事实说明，标准DE算法的进化算子都不具有记忆性，因此由其生成的种群序列也就构成了马尔科夫链。由于进化算子与时刻t无关，且在有限计算精度下差分进化对应的随机过程的状态空间是有限的，因此，在有限精度下标准DE算法所生成的种群序列构成的是有限、齐次的马尔科夫链。

对于标准DE算法生成种群所构成的马尔科夫序列，有以下结论成立。

① 标准DE算法具有保存最优个体的精英保留性质。标准DE算法生成种群所构成的马尔科夫序列中，最优状态集Γ*是闭的，即一旦种群中产生了最优JJG个体X*，相应的状态为最优状态S*，那么后续各代种群（τ<t）都将包含最优个体X*。

② 标准DE算法生成种群所构成的马尔科夫序列中，所有的齐次种群所对应的状态子集都是闭的。如果标准DE算法的种群是齐次种群，即每个个体都相同，那么由变异表达式（2-3）和交叉表达式（2-4）可知，变异算子和交叉算子都不可能产生不同于当前个体的新个体，因而即使进化过程无限发展，种群将永远停留在当前的齐次种群。因此标准DE算法不能保证算法收敛于问题的全局最优解。

2.5.2 差分进化算法的收敛性定义

优化算法一般都存在算法收敛性和计算效率的问题，即算法都不能保证针对所有问题以1概率收敛于最优解，在这一点上 DE 算法也不例外。若搜索区域Ω包含L个点，那么状态空间Γ={S1,S2,…,SM}的状态数为 Γ=M。DE算法中每一代种群可能的取值情况，或者说随机过程的状态分布情况都可以用一个M维概率向量（称为状态分布向量）来表示，如式（2-15）所示。

其中，qi表示状态Si出现的概率，满足式（2-16）。

假设存在状态转移矩阵P，那么状态分布向量满足式（2-17）。

如果当迭代次数t→∞时，存在极限状态分布向量q∞，即q(t)→q∞，则称此种群马尔科夫链是收敛的。

DE算法生成种群所构成的马尔科夫链序列的收敛性与DE算法本身的收敛性并不等价。种群马尔科夫链序列的收敛只是算法收敛的必要条件，因为如果极限分布向量q∞中存在某个分量qi∞ >0，但它所对应的状态Si并不对应最优种群，那么即使算法无限迭代下去，也无法确保收敛于问题的全局最优解。因而要使算法收敛，必须保证极限分布向量q∞中对应于最优状态的分量之和为1，如式（2-18）所示。

同时必须保证对应于其他非最优状态的分量均为0。因而得到DE算法收敛的定义，即如果由DE算法生成种群所构成的马尔科夫链序列是收敛的，并且其状态分布向量的极限q∞满足，则称DE算法是收敛的。