混合粒子群优化算法及其收敛性分析

董　航，高志强，李姝湲，郭红霞，程　川

（武警工程大学，西安　710086）

混合粒子群优化算法及其收敛性分析

董航，高志强，李姝湲，郭红霞，程川

（武警工程大学，西安710086）

为解决标准粒子群优化算法不能保证全局收敛，寻优精度低，尤其在高维函数优化方面易陷入局部极小值等问题，提出一种融合Kent混沌映射、云模型理论和布谷鸟搜索的混合粒子群优化算法（CPSO）；CPSO算法采用混沌初始化种群位置、全局开发及局部开采的均衡搜索、多子种群协同进化等改进策略，同时从随机优化算法的全局收敛准则角度对CPSO算法的全局收敛性进行证明，并给出了CPSO算法的时间复杂度分析；经典的benchmark测试函数的实验统计结果表明，CPSO算法在收敛性、寻优精度、稳定性等方面均优于经典算法。

混合粒子群优化算法；云模型；混沌映射；布谷鸟搜索；收敛性分析

0　引言

作为群体智能的优秀范例，粒子群优化算法（PSO）［1］具有收敛速度快，调节参数少和寻优能力强等特点，但也存在现代智能优化算法普遍的缺陷，如易陷入局部极小值、寻优精度不高，尤其是在高维函数优化方面尤为明显。目前，混合粒子群优化算法［2］已成为新的研究热点。刘洪波［3］融合了一种非线性反馈的混沌神经元映射算法，提高了种群的多样性和搜索空间的遍历性，在多模态、高维函数优化方面取得良好效果。彭智［4］从广义单调有界数列极限的角度，给出混合优化算法全局收敛的充分条件，为混合算法设计提供基本准则。朱奇光［5］提出了引入人工免疫克隆方法的PSO算法，并成功将其应用到偏振模色散补偿中。方伟［6］用量子空间和量子势能场模型描述PSO算法，证明了融合算法的全局收敛性。

目前，混合算法的研究主要集中在多次重新启动、全局及局部均衡搜索策略、多子种群协同进化等方面［2，4］。本文采用Kent混沌映射引入随机因素，为种群提供具有均匀分布特性的初始位置；在两个子种群的基础上，利用由PSO算法和布谷鸟搜索共享的种群最优资源档案池来记忆和共享种群迭代中的最优历史信息，并指导两个子种群在整个解向量空间协同进化、全面搜索；当种群收敛到一定程度时，启动云模型搜索，引入随机和模糊因素，在种群最优个体周围重新挖掘历史信息，进而得到最终的全局最优解。

1　混合粒子群优化算法的设计与实现

1.1Kent混沌映射

混沌现象存在于非线性动力系统中，具有初值敏感性、规律性、普适性、遍历性等优点。Kent映射［7］是一种典型的离散混沌系统，是二对一型的线性迭代函数，其系统方程如下：

其中：β∈［0，1］，x∈［0，1］。由Perron-Frobenious方程得到Kent映射概率密度函数服从在（0，1）上的均匀分布。另外，在游程、互相关均方根值、平衡性、自相关旁瓣等［8］特征方面，Kent映射均展现出优越的性能。因此，本文采用均匀性更优的Kent映射产生初始随机数序列randi。设种群中粒子位置变量X的取值范围为［xmin，xmax］，采用下式对种群粒子的各维进行初始化。

xid（0）=xmin+randi（xmax-xmin），i=1，2，…，n（2）

1.2布谷鸟搜索

英国学者Yang［9］于2009年模拟布谷鸟寻窝产蛋行为，并结合莱维飞行 （Levy Flights），提出一种元启发式算法——布谷鸟搜索 （Cuckoo Search，CS）。该算法是一种简单、易于实现、且具有全局收敛性［107］的群体智能优化方法。在布谷鸟搜索中，鸟巢代表候选解，利用Levy飞行来更新最好解。然后按发现概率对现有候选解进行舍弃。最后，以随机偏好的方式产生与淘汰等量的解，再次评价解的质量。基于Levy飞行的布谷鸟搜索采用如下方式产生新解：xi（t+1）=xi（t）+α⊕Levy（β）（3）

其中，xi（t+1）表示第t+1次迭代产生的第i个候选解，α是用来控制算法在搜索空间中寻优范围的最优步长，⊕是点乘，本文采用Mantegna算法来实现Levy飞行模式，布谷鸟搜索产生新解xi（t+1）的一种具体实现方式为：

其中，α0为常量（通常α0=0.01），xbest（t）表示截至第t次迭代产生的最优解。另外，按发现概率Pa丢弃一定数量的解后，采用如下偏好方式产生等量的新解：

xi（t+1）=xi（t）+rand（xj（t）-xk（t））（5）

其中，rand 为 （0，1）区间的随机数，xj（t）、xk（t）为第t次迭代中的两个随机解。

1.3云模型

中国工程院院士李德毅于1995年首次提出了云模型理论［10］。它是一种用自然语言描述定性概念与定量概念的双向认知转换模型。设U是一个用精确数值表示的定量论域，C是U上的定性概念，若定量值x∈U，且x是定性概念C的一次随机实现，x对C的隶属度μ（x）∈［0，1］是具有稳定倾向的随机数，则x在论域U上的分布称作云，每一个x称作一个云滴。云模型具有3个数字特征，即Ex（Expected value），En（Entropy）和He（Hyper entropy）。

本文采用的一维逆向正态云发生器算法（1-D Backward Normal Cloud Generator，BNCF）［11］充分考虑云模型的雾化特性，对定性概念的数字特征具有更高的矩估计准确性和有效性。采用的一维正向正态云发生器算法（1-D Forward Normal Cloud Generator，FNCG）［12］实现由定性概念向定量数值的转换。

1.4混合粒子群优化算法流程

为克服PSO算法易早熟，不具备全局收敛性等缺点，本文提出一种混合粒子群优化算法（Composite Particle Swarm Optimization，CPSO），混合算法采用“并行加串行”的算法结构，可具体分为以下3个部分，具体算法流程如图1所示。

1）初始化及种群分类：首先，根据式（1）和式（2），利用在遍历过程中均匀性更具优势的Kent混沌映射，产生混沌序列并映射到种群的搜索空间，实现种群初始化。然后，将种群随机等容量地分成种群1和种群2，并行执行以PSO算法为主子群和CS算法为辅助子种群的进化策略。

2）全局开发（explore）：PSO算法和CS算法并行协同演进。其中，为扩大全局搜索范围，提高变异概率，CS算法的发现概率Pa定为黄金分割率（0.618），同时将搜索到的最优解存入种群最优资源档案池，并与PSO算法共同更新种群最优资源档案池中存储的最优个体，优势互补，以扩大PSO算法和CS算法中最优个体的选择范围。当PSO算法达到终止条件，结束以PSO算法为主体，CS算法协同的全局开发过程。

3）局部开采 （exploit）：通过种群密度判定体现种群的进化状态情况。当种群密度小于预设值时，结束算法输出结果；当种群密度大于预设值时，启动云模型深度搜索模式（相当于重启动策略或再次引入随机个体策略）。利用启动逆向云发生器 （BNCG），得到定性概念的数字特征，然后启动正向云发生器（FNCG），生成代表新的搜索粒子的云滴，进行深度开采，直至达到算法结束条件。

图1　CPSO算法流程图

2　混合粒子群优化算法性能分析

本节从随机算法全局收敛性准则［13］的角度出发，对CPSO算法收敛性进行证明和分析。在CPSO算法中，混沌初始化增加种群均匀性，云模型搜索是在已收敛情况下增加开发深度。只有PSO算法和CS算法的子种群协同进化部分影响整个算法的全局收敛性，所以只需证明该部分的收敛性即可。

定理1：假设CPSO算法优化的目标函数f是一个可测函数，其解空间S为Rn上的可测子集，并且CPSO算法同时满足随机搜索算法全局收敛的条件1和条件2，设｛xk｝∞k=0是CPSO算法所产生的解序列，则k→∞

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

证明：依据CPSO算法流程（只针对两个子种群协作部分），迭代函数F可定义为

因为CPSO算法利用种群最优资源档案池保留种群最优解，即采用适应度值非递增的精英保留策略，可知算法满足文献［13］中条件1。

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

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

令Yk为CS算法在第k次迭代时搜索到的解。因为，单独执行CS算法得到的解序列｛Yk｝以概率l全局收敛于最优区域Rε，M［14］。因此，在CPSO算法中，对于有限个满足f（Yk）＞f（Pg，k）的解Yk，可令其下一状态为Pg，k，并将其存储于种群最优资源档案池中，而且该机制对CS算法的全局收敛性没有影响，即在CPSO算法中恒有li mP（Yk∈Rε，M）=

k→∞1，也就是说，当f（Yk）＜f（Pg，k）时，存在一个粒子i0，其支撑集Mi0，k=S，而对于其它的粒子i，由文献［15］中推导得到的二阶非齐次递归公式有

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

综上所述，CSPO算法的两个子种群协作部分，满足随机搜索算法全局收敛的条件1和条件2，并结合初始化和云模型深度搜索两个策略，CPSO算法的搜索序列依概率1收敛于全局最优解，即CSPO算法具有全局收敛性。

另外，本文提出的混合粒子群算法（CPSO）的时间复杂度和空间复杂度都是多项式时间阶，且与PSO算法的复杂度在同一数量级上，因此，无论是从算法的执行效率还是数据的存储结构等方面均简单方便，易于计算机编程实现。

3　混合粒子群优化算法的benchmark测试函数实验

实验相关参数设置如下：初始化种群规模为40，两个子种群规模各为20，惯性权重ω从0.9线性递减至0.4，学习因子c1=c2=1.494，最大迭代次数为1 000。对比算法PSO［16］和CSPSO［17］参数设置均与参考文献相同。

为便于验证分析，实验结果中，均以“平均误差+标准差”形式表示每个解，同时，给出了0.05显著水平下的双侧t -检验结果。“≈”表示对比算法与本章算法解的质量相似；“++”表示对比算法解的质量比本章算法性能差；“+|”表示对比算法解的质量比本章算法性能好。对维数为30的测试函数（f1～f4）分别独立进行20次实验，算法性能测试的最终结果如表1所示。

从表1可以看出，就单峰函数（f1、f2）而言，CPSO算法与标准PSO算法、CSPSO算法相比，在具有更高精度的同时，解的稳定性显著提高，而且可以很轻易的找到全局最优解；其中，标准PSO算法和CSPSO算法也均可收敛到相应容忍度下限，且CSPSO算法优于标准PSO算法。在有众多局部极值点的多峰函数（f3、f4）中，CPSO算法同样显著提高了解的质量，并且在f3函数上获得全局最优解；对多峰函数f4而言，子种群并行协作和基于种群最优资源档案池深度搜索策略能够有效提高算法解的质量，得到了精度较好的解。CPSO算法之所以能在大多数的函数上改善解的质量，是因为采用子种群并行策略使算法避免了算法陷入局部最优，扩大全局寻优空间；云模型的深度搜索充分利用历史信息加强算法局部搜索性能。

表1　算法性能测试结果

上述结果表明，通过布谷鸟群、共享种群最优资源档案池、云模型等机制的引入，提高了全局开发和局部开采的性能。粒子群和布谷鸟共享寻优信息，提高了开发范围；云模型更加精确的完善了局部开采机制。总之，新机制的引入解决了粒子群算法在高维复杂函数寻优中，容易早熟收敛、寻优精度不高的问题。通过实验与分析，为达到更优的算法效能，推荐布谷鸟种群大小适宜设置为30，此时寻优效果和算法复杂度都可满足实际应用的要求。

4　结论

本文提出的混合粒子群优化算法（CPSO），解决了标准PSO算法易陷入局部最优解、不能保证全局收敛的问题。采用Kent混沌初始化，并结合CS算法和PSO算法的特性，在云模型的基础上，提出了在函数优化方面具有全局收敛性的CPSO算法。实验证明，CPSO比其他算在搜索精度、解的质量及收敛性能上都更具优势，尤其在求解多维函数优化问题上是具有竞争力的，因此，将CPSO算法应用到工程优化、智能调度、信息融合、态势感知、聚类分析等诸多领域是具有广阔前景的。

［1］李洪明.多域光网络中基于博弈论的智能优化生存性算法设计与仿真实现［D］.沈阳：东北大学，2010.

［2］李宝磊，施心陵，苟常兴，等.多元优化算法及其收敛性分析［J］.自动化学报，2015，41（5）：949-959.

［3］刘洪波，王秀坤，谭国真.粒子群优化算法的收敛性分析及其混沌改进算法［J］.控制与决策，2006，21（6）：636-645.

［4］彭智，谢玲.混合优化算法的全局收敛性分析［J］.北京理工大学学报，2012，32（4）：435-440.

［5］朱奇光，王洪瑞.IC-PSO算法的收敛性分析及应用研究［J］.光电工程，2010，37（4）：108-112.

［6］方伟，孙俊，谢振平，等.量子粒子群优化算法的收敛性分析及控制参数研究 ［J］.物理学报，2010，59（6）：3686-3694.

［7］梁瑞鑫，郑德玲.基于区间套混沌搜索的混合优化方法［J］.北京科技大学学报，2002，24（3）：342-344.

［8］张勇，单承赣.Kent混沌伪随机码的性能研究［J］.合肥工业大学（自然科学版），2003，26（2）：227-231.

［9］Yang X S，Deb S.Cuckoo search via Lévy flights［C］.In：Proc.of the World Congress on Nature and Biologically Inspired Computing. 2009：210214.

［10］李德毅.不确定性人工智能［M］.北京：国防工业出版社，2005.

［11］高溥，王寅杰，李宗刚，等.无确定度逆向云模型新算法［J］.计算机应用研究，2013，30（8）：2262-2265.

［12］代劲，宋娟，胡娟，等.云模型与文本挖掘［M］.北京：人民邮电出版社，2013.

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

［14］王凡，贺兴时，王燕，等.基于CS算法的Markov模型及收敛性证明［J］.计算机工程，2012，38（11）：180-185.

［15］王丽芳，曾建潮.基于微粒群算法与模拟退火算法的协同进化方法 ［J］.自动化学报，2006，32（4）：630-635.

［16］Kennedy J，Eberhart R.Particle swarm optimization［A］.Proc. of the IEEE Int'l Conf.on Neural Networks［C］.1995：1942 1948.

［17］Wang F，He X S，Luo L G，et al.Hybrid optimization algorithm of PSO and cuckoo search［A］.Proc.of the 2nd Int'l Conf.on Artificial Intelligence，Management Science and Electronic Commerce（AIMSEC）［C］.2011.1172-1175.

Composite Particle Swarm Optimization and Analysis of Convergence

Dong Hang，Gao Zhiqiang，Li Shuyuan，Guo Hongxia，Cheng Chuan
（University of CAPF，Xi'an710086，China）

In order to cope with low accuracy and disability in convergence of PSO，a composite PSO algorithm is proposed，combined with Kent mapping，cloud model and cuckoo search.Furthermore，chaotic initialization，exploration and exploitation as well as multi-swarm strategies are adopted.In addition，convergence analysis and time complexity of CPSO are conducted.Finally，experiment results of standard benchmark function show that compared with traditional methods，our proposed algorithm is excellent in both convergence，accuracy and robustness.

composite particle swarm optimization；cloud model；chaos mapping；cuckoo search；convergence analysis

1671-4598（2016）05-0146-04

10.16526/j.cnki.11-4762/tp.2016.05.042

TP393

A

2015-09-08；

2015-12-15。

国家自然科学基金项目（61309008）。

董航（1992-），男，黑龙江哈尔滨人，硕士研究生，主要从事统计学和智能优化算法方向的研究。

高志强（1989-），男，黑龙江齐齐哈尔人，硕士研究生，主要从事智能优化算法方向的研究。