基于协同进化的动态双重自适应改进PSO算法

宋 美，葛玉辉，刘举胜

上海理工大学 管理学院，上海 200093

1 引言

微粒群算法（Particle SwarmOptimization，PSO）[1]由于其具有实现简单，群体共同进化等优化性能从1995年，被Eberhart 和Kennedy 提出以后，在路径规划、疾病检测、图像分割、电力故障预测等方面产生了巨大的应用价值[2-3]。

虽然PSO算法具有较好的优化性能，然而易陷入局部最优，发生早熟也是其缺陷之一。对此研究人员借鉴自适应和非线性机制对算法参数的取值方式进行了相关改进。借鉴自适应机制，文献[4]针对粒子群算法具有易陷入局部最小值和全局寻优能力差的缺陷，提出了一种自适应惯性权重粒子群算法（AIW_PSO）。研究发现该算法能够有效平衡粒子的位置和速度。文献[5]针对粒子群算法在处理优化问题时缺乏有效的参数控制这一缺陷，采用异步变化策略对学习因子进行更新，采用非线性递减的方式对惯性权重进行更新，改进算法较原算法具有一定的求解优势。文献[6]通过对惯性权重进行自适应取值，将改进的PSO 算法与支持向量机（SVM）进行了结合，利用改进算法对花粉浓度进行了有效的预测。文献[7]将自适应变异应用于PSO 算法中，通过对算法中全局最优值进行扰动，以提高种群多样性，最终形成自适应优化PSO 算法。之后将该算法与小波网络进行结合，形成自适应优化小波网络算法，研究发现该算法预测精度提升率最高。文献[8]根据迭代次数和粒子的位置的变化情况设计了一种新的自适应惯性权重混沌PSO 算法，该算法能够有效避免陷入极值，提高算法性能。

借鉴非线性机制，文献[9]通过引入非线性惯性权重系数，对惯性权重进行非线性取值，形成改进PSO 算法，之后将改进PSO算法与BP算法进行结合，形成了非线性BP 神经网络模型。实验结果表明，改进算法对非线性函数具有良好的拟合效果。文献[10]针对文化算法中的函数优化问题存在过早收敛，不确定等缺陷，基于文化算法框架，将混沌搜索引入算法中，提出了一种混沌文化算法。该算法具在搜索效率、搜索精度及稳定性上有显著表现。文献[11]通过对惯性权重进行非线性取值，形成了一种非线性PSO 算法，该算法在分配网络路由节点和平衡簇结构系统方面具有良好的性能。文献[12]通过引入非线性惯性权重替代传统惯性权重递减，构造了一种改进优化PSO算法的小波支持向量机预警模型，在预测效果上，改进后的算法具有更好的预测性能。

上述研究主要从自适应性和非线性等方面对算法进行设计。设计大多围绕PSO 算法的惯性权重进行了相关改进，且改进算法的求解效果有一定的提升。然而上述改进只是从单个方面对算法的某种参数取值方式进行了改进，鲜有学者将混沌、自适应、非线性和共同演化等特征都考虑到算法中，对粒子群算法中的学习因子、粒子初始值选取以及惯性权重等参数进行协同优化，以提升算法的求解性能。

基于此，本文基于协同进化理论，借鉴协同进化理论中混沌、自适应、非线性和共同演化等诸多特性通过对PSO 进行改进形成动态双重自适应PSO 算法（DDAPSO）。对此算法进行了仿真测试，实验结果表明DDAPSO能够有效避免算法陷入局部极值，具有较好的求解性能。

2 标准PSO算法原理

PSO算法在可行解空间中首先会初始化一群粒子，初始化后的粒子可以看作初始解，用位置、速度、适应度值来表示该粒子或该解的特征。粒子会根据一定的更新法则在解空间中不断运动，在解空间运动的过程中，通过跟踪个体极值pbest和群体极值gbest更新个体位置，粒子每更新一次，计算一次适应度值，通过比较个体极值pbest和群体极值gbest的优劣，从而逐步迭代求得全局最优解。粒子群算法按照式（1）和式（2）进行速度和位置的更新[13]。

其中，ω为惯性权重，d=1,2,…,D表示粒子的维数；i=1,2,…,n表示粒子的个数；k为当前迭代次数；Vid表示粒子的速度；X表示粒子的位置；c1和c2为加速度因子，c1称为个体学习因子，c2称为社会学习因子；r1和r2是分布于[0，1]区间的随机数，Pid为个体极值，Pgd为群体极值。

3 协同进化理论及其特征

关于协同进化的研究，最早始于国外学者对生物学的探索，Ehrlich和Raven最早在研究蝶类与植物之间的作用关系时提出了协同进化这一概念[14]，Jazen[15]随后对协同进化给出了定义：协同进化就是一个物种的特征随着另一个物种的某一特征变化而进行变化，后者的特征同样随着前者特征变化而进化。具体来说协同进化理论具有如下特征：

（1）协同进化中的个体具有多样性[16]。参与协同进化的主体可以是不同形态、不同性质的主体，主体的多样性可以使得整体系统的熵增减小，系统的无序性受到削减，最后在混沌中快速找到最优解。

（2）协同进化中的个体具有自组织、自适应性[17-18]。在复杂系统中，两个或多个个体在协同进化的过程中，个体与个体、个体与环境之间会协同演化，不断地促使整个系统达到最优，同时系统会根据系统的演化结果及时向个体反馈信息，个体会根据反馈信息进行进一步的调整，最终实现个体与系统的协调发展。

（3）协同进化中的个体与环境具有非线性[19]。在个体与整体协同进化过程中，个体与整体将会发生非线性作用，这一作用会促使个体和整体相互演化，进而最终实现协同进化。在协同进化的作用下，个体最优与群体最优将趋于同质，最终促使系统趋于稳定。

基于协同进化理论，结合粒子群算法的进化特点，提出了一种改进的动态双重粒子群算法（Dynamic Dual Adaptive PSO algorithm，DDAPSO）。

4 DDAPSO算法

4.1 算法原理

DDAPSO 算法从PSO 算法的搜索机制和信息传递机制进行了相关设计[20]。其借鉴生物学中的协同进化论对传统粒子群算法进行相关改进，通过对粒子初始值混沌取值，对自我学习因子和社会学习因子非线性取值，对惯性权重进行自适应取值等多种方式，促使算法对目标函数快速求解，具体原理如图1所示。

图1 DDAPSO算法原理

如图1所示，在DDAPSO中，首先，在初始值的选取上，由于混沌算法具有一定的随机性和遍历性，能够以较为随机的搜索方式，对粒子的初值进行取值，因此在算法解解空间一定的情况下，能够使得初值选取更为随机，有效扩展了初值的随机性。

其次，对自我学习因子和社会学习因子进行非线性取值能够使得自我学习因子和社会学习因子借鉴复杂系统中的非线性关系，清楚呈现自我学习因子和社会学习因子的动态变化关系，并根据搜索的迭代次数恰当调整粒子学习能力，进而对局部搜索和全局搜索进行一定平衡。

最后，DDAPSO算法的惯性权重取值区别于传统惯性权重线性递减形式，其根据粒子的适应度值自适应更新惯性权重。当目标函数适应度值较小时，对惯性权重选取一个较小值，粒子在局部位置进行搜索；当目标函数适应度值较大时，对惯性权重选取一个较大值，粒子在全局进行搜索。此时，粒子的惯性权重能够根据适应度值进行自适应进化，从而促使函数值不断向着最优解进行趋近，直到最终找到最优解。

4.2 算法表示

（1）混沌并不是一片混乱，而是有着精致的内在结构的一类现象，混沌运动能在一定范围内按自身的“规律”不重复地遍历所有状态。在PSO中，初始化种群时，种群的多样性以及初始化粒子时的随机性与粒子的搜索效率有很大的关系，为了使得种群的多样性和随机性得以增强，结合协同进化理论，将混沌这种具有随机性、遍历性及规律性特点的非线性动力系统特有运动形式引入进化计算，利用其具有随机性和遍历性优势，可以有效避免搜索过程陷入局部最优。由于Feigenbaum 迭代与其他产生混沌变量的动力系统相比简单、计算量小、使用方便，所以本文采用Feigenbaum迭代，来构造混沌序列，进行粒子位置和速度的初始化，具体如式（3）所示，其中xn的初始值不能取该混沌迭代方程的不动点。

为了直观展现混沌迭代轨迹，取初值x0=0.007 时，将式（3）的Feigenbaum 迭代轨迹进行了仿真，具体如图2所示（迭代次数取500）。

图2 Feigenbaum迭代轨迹

（2）在PSO 算法中，学习因子体现了粒子的学习能力，其中自我学习因子，体现了粒子的自我学习能力，社会学习因子体现了粒子的社会学习能力。不同的学习因子表明粒子具有不同的寻优能力。在粒子寻优的过程中，初始时期，粒子需要具备较强的个体学习能力，这样其可以在更大的搜索空间中快速寻找到最优解的位置；在搜索后期，粒子需要较大的社会学习能力，可以在周围局部解范围内进一步进行局部搜索。为此，借鉴协同进化理论中非线性优势，引入非线性调整策略来平衡c1、c2的关系，c1、c2通过非线性变化，控制粒子的飞行速度与方向，来提高解的收敛速度与精度，具体调整策略为：

其中，iter为当前迭代次数，itermax为最大迭代次数，c1b、c1e、c2b和c2e分别为c1和c2的初始值和最终值，一般取c1b=2.5，c1e=0.5，c2b=0.5 和c2e=2.5 时算法效果较好，c1、c2的取值如图3所示（学习次数取500）。

（3）为了避免惯性权重线性递减，本文采用自适应惯性权重递减的方法对w进行自适应取值。这样取值可以有效促使w的取值会随着目标函数值得变化而发生相应的调整，及时更新自身信息，不断将自我信息与全局信息进行比较，促使自身信息能够在获取全局信息的基础上进行个体更新和改变，最终实现自身与系统的协同进化。具体自适应惯性权重更新公式如式（6）和（7）所示。

图3 c1、c2 自适应变化图

式中，ωmax表示ω的最大值，ωmin表示ω的最小值，f表示当前目标函数值，favg表示当前平均目标函数值，fmin表示目标函数极小值。

4.3 算法步骤

步骤1 混沌初始化粒子群参数。对初始的粒子按照（3）式进行混沌随机取值，生成初始的粒子速度vi和粒子位置xi。

步骤2 评价粒子群。计算出粒子的适应值，通过fitness 函数将粒子的个体最优值存储到pbest中，群体最优值存储到gbest中。

步骤3 更新自我学习和社会学习因子，按照式（4）和式（5）更新自我学习因子c1和社会学习因子c2。

步骤4 更新惯性权重w，若当前目标函数值f小于平均目标值favg，则按照式（6）更新惯性权重；若当前目标函数值f大于平均目标值favg则按照式（7）更新惯性权重。

步骤5 更新粒子的位置。按照式（1）和式（2）更新粒子的速度和位置。

步骤6 更新个体最优。将粒子的适应度值与上一次迭代的适应度值进行比较，取较好的粒子作为后代粒子。

步骤7 更新全局最优。比较个体最优值pbest和全局最优值gbest，若pbest优于gbest，则将pbest赋值给gbest。

步骤8 当算法满足迭代结束条件，结束算法，否则返回步骤3继续搜索，直到满足停止条件跳出循环。

DDAPSO 算法流程图如图4 所示（其中N为算法最大迭代次数）。

图4 DDAPSO算法流程

5 算法复杂度及收敛性分析

5.1 算法复杂度分析

在经典粒子群算法中，粒子群的规模为N，每个粒子的维数为D，粒子每进行一次迭代，其计算复杂度为O(N)[21]；在DDAPSO 算法中，主要的执行运算的复杂度包括：

（1）粒子的初始值混沌取值，其算法的复杂度为O(DN)。

（2）计算适应度的均值，其算法复杂度为O(N+1)。

因此，DDAPSO 算法整体复杂度为O(DN)。该算法理论复杂度理论上高于经典PSO算法，并且算法的复杂度会随着粒子个数的增加和维数的增加而进一步增大。但在求解时间和求解效率上，由于DDAPSO 算法借鉴了复杂协同进化理论的协同进化，自适应和非线性等诸多特性却具有较好求解性能。

5.2 算法收敛性分析

在算法的收敛性方面，相关研究已经对PSO 算法收敛性进行了相关分析[22-24]，结合前人研究，本文依据文献[22-23]对DDAPSO 算法的收敛性进行相关分析，具体如下。

假设1 目标函数f的解空间为Rn到R，Q为Rn的一个子集，算法的最终目的是在Q的范围内找到一个最优解z，使得目标函数最小化。当存在f(D(z,δ))≤f(z)时，若δ∈Q，则f(D(z,δ))≤f(δ)。其中，D为迭代函数。

假设2 对于Q的任意Borel子集B，如果测度u(B)>0 ，则有，其中vi[B]是由测度vi所得到B的概率。

定理1 若目标函数f为可测函数，Q为可测子集，满足假设1 和假设2，同时假设为算法生成的解序列，则

证明DDAPSO 算法的收敛性，需要证明其符合假设1、假设2和定理1。

引理1 DDAPSO满足假设1。

由步骤7 可知，比较个体最优值pbest和全局最优值gbest，若pbest优于gbest，则将pbest赋值给gbest。

在DDAPSO算法中，假设D为算法的迭代函数，则D函数的描述可以根据步骤7定义为：

若f(gbest)≤f(pbest) ，则D(gbest,pbest)= gbest，因此f(D(gbest,pbest))= f(gbest)≤f(pbest) 。若f(gbest)≥f(pbest) ，则D(gbest,pbest)=pbest，因此，f(D(gbest,pbest))=f(pbest)≤f(pbest) 。因此，DDAPSO 算法满足假设1。

引理2 DDAPSO算法满足假设2。

定义Q的任意 Borel 子集B=Mi,k，在 DDAPSO 算法中，令φ1=c1×r1，φ2=c2×r2，由式（1）和式（2）可得：

其中，w按照式（6）和式（7）自适应取值，c1和c2按照式（4）和式（5）非线性取值。随着迭代次数的增加，c1、c2的非线性取值以及w的自适应取值使得Borel 子集中的元素更加随机。因此，种群中粒子测度u(Mi,k)不断增大，其并集也不断增大。此时，假设种群中粒子支持集的并集为β，则DDAPSO 算法搜索停止时，。因此，DDAPSO算法的样本空间的并集包含Q，此时u(B)>0，存在

综上，DDAPSO算法满足假设2。

引理3 DDAPSO算法是一个全局收敛算法。

证明因DDAPSO算法满足假设1和假设2，由定理1知，则DDAPSO是一个全局收敛算法。

6 测试仿真

6.1 测试函数

为了检验DDAPSO 算法的性能，本文选取了6 个经典Benchmark 函数进行测试。在6 个测试函数中，De Jong、Quadric、Rosenbrock valley为单模态函数；Rastrigin、Schaffers、Ackley 为多模态函数。其中 De Jong 为复杂的非线性对称单模函数，Rosenbrock valley为很难极小化的典型病态单模函数；在6 个函数中，函数的全局最优位置均为[0，0]，各个函数对应的极小值均为0，具体的函数轨迹如图3所示。

单模态函数：

函数1 De Jong函数

De Jong 函数实际上是一个Sphere 函数，此函数存在极小值，其全局最优解在一个狭窄的椎体底端，在x1=x2=0 时存在全局最小值，具体如图5（a）所示。

函数2 Quadric函数

Quadric 函数是一个典型的单模态测试函数，其全局最优解在一个狭长的山谷中，是一个很难极小化的测试函数，当x1=x2=0 时其存在全局极小值，具体如图5（b）所示。

函数3 Rosenbrock’s valley函数

Rosenbrock’s valley 是一个非常经典的优化测试函数，其全局最优值位于一个带有抛物面的卷状的峡谷中。虽然山谷的坡度不是很大，但全局收敛很难，当x1=x2=1 时，此函数存在全局极小值点，具体如图5（c）所示。

多模态函数：

函数4 Rastrigin函数

Rastrigin函数是一个基于De Jong函数的局部最小值规则分布的多模态函数，是一个典型的多模态函数，该函数在求解最优解过程中，极易陷入局部最优解中，当x1=x2=0 时，全局最小值，具体如图5（d）所示。

函数5 Schaefer’sf7 函数

Schaefer’sf7 函数是一个典型的病态多模态函数，该函数在自变量取值范围内存在很多局部最优点，在寻求最优解过程中很难找到全局极值点，是一个典型的多模测试函数。当x1=x2=0 时，存在全局最小值，具体如图5（e）所示。

函数6 Ackly函数

Ackley是一个使用广泛的多模测试函数，其全局最优解在一个狭小的椎体底部，在寻求最优解的过程中，算法极易停滞不前陷入局部最优，从而找不到全局最优解。当x1=x2=0 时，其全局最小值，具体如图5（f）所示。

6.2 测试环境与参数设置

测试环境如下：计算机的CPU 为Intel®Core™ i7-8700 CPU @3.20 GHz 3.19 GHz，运行内存为8.0 GB；软件为Windows10操作系统下的Matlab2018A中文版。

在实验中，本文将与PSO（算法1），文献[25]中的指数型函数递减惯性权重的PSO 算法（算法2），文献[26]中的高阶指数型函数的递减惯性权重PSO 算法（算法3），文献[27]中的二阶振荡微粒群算法（算法4），文献[28]中的带收缩因子的PSO 算法（算法5）进行了对比。其中PSO算法中的惯性权重采用线性递减的形式，惯性权重w在区间[0.4，0.9]之间线性取值；文献[25]中指数型函数递减惯性权重中的α为控制因子，控制w与迭代次数变化曲线的平滑度，通常取3；文献[26]中高阶指数型函数的递减惯性权重中的β一般取20。其余参数具体设置：自我学习因子和社会学系因子的初始值和最终值分别为c1b=2.2，c1e=0.5，c2b=0.5，c2e=2.2，粒子数目为30，迭代次数为500 次，混沌初始化中的u取4，测试算法参数设置具体取值如表1所示。

6.3 测试结果及分析

对每种算法分别独立运行10 次，将其运行结果进行统计，其中Function 表示最优化目标函数，Algorithm表示算法，Goal表示目标值，◢best表示最优值，◢worst表示最差值，◢avg 表示平均值，◢std 表示标准差，◢num表示寻优次数，◢%表示寻优率，t表示运行时间（单位s），本文以10−6为误差容忍度，测试结果如表2、表3所示，函数迭代轨迹如图6、图7所示（图中为了使曲线变化对比明显，纵轴表示种群平均适应度自然对数值，横轴表示进化代数）。

表1 相关参数设置

表2 显示的是DDAPSO 算法与其余算法在单模态函数上测试所得的结果。从表2中的最优解，标准差和寻优率上可以发现，DDAPSO 算法较算法4、算法5 而言，首先在求解精度上具有极大的优势，这一点在Rosenbrock’s valley 函数上，表现尤为明显；在稳定性方面，从De Jong、Quadric 这两个单模态函数上可以发现DDAPSO 的求解性能较为稳定，较其他算法具有明显的优势；其次，从算法的运行时间上来看，DDAPSO在寻求最优解的过程中所花费的时间最少，在求解效率上具有一定的优势。此外，将DDAPSO 算法与算法1、算法2、算法3进行对比，发现DDAPSO算法在求解精度和寻优效率上也具有相当大的优势，由于DDAPSO 中的自适应惯性权重较线性惯性权重递减具有较强的适应环境的能力，这样在寻求最优解的过程中，可以不断与外界环境进行交互，协同进化，从而快速找到最优解。

图 6 显示的是 De Jong、Quadric 和 Rosenbrock’svalley 函数在求解最优解的过程中的迭代轨迹，从上述优化结果中可以看出，DDAPSO算法在求解单模态函数时，较其他算法具有明显的优势。在寻优性能上，最差的是PSO 算法，在寻优的过程中容易陷入局部最优解，从而使得算法停滞不前，发生早熟现象。DDAPSO由于借鉴了协同进化理论中的个体的多样性以及主动性，利用混沌搜索克服前期所选粒子的单一性，使得种群的多样性得以增加，从而使得进化能够跳出局部最优，快速找到全局最优解。

表2 单模态函数测试对比

表3 多模态函数测试对比

表3显示的是动态双重自适应PSO算法（DDAPSO）与其他算法在多模态函数上测试所得的结果。从表3中的最优解，标准差和寻优率上可以发现，DDAPSO 算法较其他算法具有一定的寻优优势。在求解精度上，对比各算法在Rastrigin，Schaefer’sf7 函数上的求解性能，可以发现DDAPSO算法在求解精度上，具有很好的寻优性能，尤其在多模态Rastrigin 函数上表现尤为明显；从运行时间来看，DDAPSO 算法在寻优过程中所花费时间最短。此外，在运行时间上，对比表3和表2可以发现，多模态函数在寻优的过程中所花费的时间较单模态函数花费的多；从稳定性和寻优率来看，DDAPSO 较其他算法具有较为稳定的寻优性能，在寻优率上，较其他算法而言，具有一定的优势，在一定的迭代次数内能够较多次逃脱局部最优解，找到全局最优解，具有极好的寻优性能。

图 7 显示的是 Rastrigin，Schaefer’sf7 和 Ackly 函数在求解最优解的过程中的迭代轨迹，从上述优化结果中可以看出，DDAPSO 算法在求解多模态函数时，较其他算法具有明显的优势。从函数迭代轨迹可以发现，DDAPSO算法在求解多模态函数时，由于借鉴了协同进化理论中的协同进化的优势，粒子个体在寻优的过程中，在个体与外界环境协同作用下，不断进化，从而在短时间找到全局最优解。这一性能在在Rastrigin和Ackly函数上表现非常明显，DDAPSO算法可以在大约150代之内找到最优解，较其他算法具有极高的寻优效率。

7 结束语

图6 单模态测试函数迭代轨迹图

针对PSO算法易陷入局部最优，发生早熟这一先天缺陷，本文利用生物学中的协同进化理论，借鉴其进化主体的多样性，对基本PSO 算法进行了改进，形成了动态双重自适应PSO算法。首先在初始化种群时，将混沌搜索引入PSO 算法中，增加了种群的多样性，其次引入非线性动态调整策略对个体学习因子和社会学信息因子进行非线性取值，最后借鉴协同进化过程中与环境的主动适应性这些优点，对惯性权重进行自适应取值，从而形成了动态双重自适应PSO 算法。最后经仿真发现，该算法无论在单模态测试函数上还是在多模态测试函数上，在求解精度、稳定性、寻优率及运行时间上较其他5种算法均具有较好的求解性能，具有广泛的应用前景。

图7 多模态测试函数迭代轨迹图