基于粒子群的混合智能优化算法收敛性分析

武警工程大学 高见文 葛卫丽

武警杭州士官学校 郭 程

基于粒子群的混合智能优化算法收敛性分析

武警工程大学 高见文 葛卫丽

武警杭州士官学校 郭 程

本文针对粒子群算法（PSO）存在的不能以概率1全局收敛以及易陷入早熟收敛等问题，提出将PSO算法和遗传算法（GA）相结合的混合算法，采用并联模式实现了两种算法的协同进化，并证明了算法能够以概率1全局收敛。

粒子群算法；遗传算法；混合算法

1.引言

PSO算法是一种得到广泛应用的智能优化算法，因其算法简单、收敛性快等优点，在复杂优化问题、人工智能以及聚类分析等领域都有广泛的应用。但是PSO算法也存在着易陷入早熟收敛、不能以概率1全局收敛的问题［1］。而采用最优保留策略的遗传算法虽然存在着收敛速度慢等问题，但是其具有全局收敛性，能够以概率1全局收敛。因此将两种算法结合起来组成混合算法，能够有效利用两者的优点，优势互补，弥补不足。

2.PSO算法和GA算法的混合模式

PSO算法和GA算法的混合算法流程图如下：

图1　混合算法流程图

在初始化后，PSO算法和遗传算法并行进化，并将各自最优解存储于全局最有数据库，当满足结束条件时，算法终止，在种群全局最优数据库中选取全局最优粒子输出。

3.混合算法收敛性分析

Solis和Wets［2］给出了一般随机搜索算法收敛性判定准则及相关定理，一般最优化问题可记为〈A，f〉，对于随机搜索算法D，其第k次寻优结果为Xk，下一次迭代寻优结果为Xk+1=D（Xk，ζk）。其中，A为Rn上某个子集的σ-域，f为适应度函数，ζk为算法D寻优过程中找到的解。

准则1：算法D满足f（D（x，ζ））≤f（x），若ζ∈A，则f（D（x，ζ））≤f（ζ）。

准则1要求随机搜索算法D是广义单调非递增的，从而保证适应度值f（x）是非递增的。

准则2：对于A的任意Borel子集P，若满足v（P）〉0，则有：

其中，μk（P）为算法D在第k次迭代中搜索到的解在集合P上的概率测度。准则2说明，只要是可行解空间A中概率测度大于零的子集P，算法D连续无穷次搜索不到集合P中解的概率为0。

引理：若函数f可测，可测空间A是Rn上可测子集，且算法D满足条件1和条件2，是算法D产生的解序列，则：

其中，P（xk∈Rε，M）是算法D第k步搜索到的解xk在最优区域Rε，M中的概率测度。

文献［1］指出PSO算法不能以概率1收敛于全局最优解，利用K-means算法原理计算适应度的过程不影响混合算法的收敛性，文献［3］证明种群初始化不会直接影响算法收敛性，因此证明混合算法的全局收敛性，仅需证明PSO算法和云遗传算法的协同过程的全局收敛性。

文献［4］应用齐次有限马尔科夫链分析并证明了保留最优个体的遗传算法以概率1全局收敛。

定理：设混合算法优化的目标函数f是一个可测函数，其解空间S为Rn上可测子集，并且混合算法满足随机搜索算法全局收敛的准则1和准则2，设是混合算法所产生的解序列，则：

其中，P（xk∈Rε，M）是混合算法第k步搜索到的解xk在最优区域Rε，M中的概率测度。

证明：

依据混合算法协同部分的流程，迭代函数F可定义为：

因为混合算法利用全局最优数据库保留种群最优解，即采用适应度值非递增的精英保留策略，可知算法满足准则1。

如果混合算法满足准则件2，则规模为n的混合种群样本采样空间的并集一定包含目标函数f的解向量空间S，即：

其中，Mi，k为第k次迭代种群中粒子i的样本空间支撑，即概率测度为1的最小闭子集。

令Yk为遗传算法在第k次迭代时搜索到的解。因为单独执行云遗传算法得到的解序列｛Yk｝以概率l全局收敛于最优区域Rε，M。因此，在混合算法中，对于有限个满足f（Yk）〉f（Pg，k）的解Yk，可令其下一状态为Pg，k，并将其存储于全局最优数据库中，而且该机制对云遗传算法全局收敛性没有影响，即在混合算法中恒有公式（6）成立，也就是说，当f（Yk）〈f（Pg，k）时，存在一个粒子i0，其支撑集Mi0，k=S。

而对于其它粒子i，

其中，0≤φ1≤c1，0≤φ2≤c2，可知Mi，k为一个顶点为（φ1，φ2）=（0，0），另一个顶（φ1，φ2）=（c1，c2）的超矩形。

当max｛c1|Pi-X（t-1）|，c2|Pg-X（t-1）|｝〈0.5diameterj（S）时，有：v（Mi，k∩S）〈v（S），其中，diameterj（S）表示解向量空间S在第j维分量的长度。因xi收敛到平衡点（φ1Pi+φ2Pg）/（φ1+φ2），所以Mi，k长度趋于0。随着迭代次数k增加，逐渐减少，从而存在整数k1，当k〉k1时，，但是因为有支撑集Mi0，k=S，所以。令S的Borel子集A=Mi，k，则v（A）〉0，且（18）式成立，从而混合算法满足准则2。

综上所述，混合算法的PSO算法和遗传算法的协同部分，满足随机搜索算法全局收敛的判定准则1和判定准则2。因此混合算法的搜索序列以概率1收敛于全局最优解，即混合算法具有全局收敛性。

4.结论

本文首先对PSO算法和GA算法的优缺点进行了介绍，在此基础上介绍了二者混合协同进化的模型，并对混合算法的收敛性进行了分析，证明了混合算法能够以概率1收敛到全局最优解。

［1］张慧斌，王鸿斌，胡志军.PSO算法全局收敛性分析［J］.计算机工程与应用，2011，47（34）：61-63.

［2］Solis F，Wets R.Minimization by Random Search Techniques［J］.Mathematics of Operations Research，1981（6）：19-30.

［3］梁旭，黄明，宁涛，等.现代智能优化混合算法及其应用［M］.北京：电子工业出版社，2014：70-72.

［4］恽为民，席裕庚.遗传算法的全局收敛性和计算效率分析［J］.控制理论与应用，1996，13（4）：455-459.

高见文（1991—），山东临沂人，硕士研究生，现就读于武警工程大学。