粒子置换的双种群综合学习PSO 算法

纪 伟，李英梅+，季伟东，张 珑

1.哈尔滨师范大学计算机科学与信息工程学院，哈尔滨 150025

2.天津师范大学计算机与信息工程学院，天津 300387

粒子群算法（particle swarm optimization，PSO）是由Kennedy 和Eberhart[1]于1995 年提出的一种群智能算法。群智能算法、模拟退火算法、遗传算法等构建起智能优化算法的基本体系结构，其中群智能算法，如粒子群算法、人工蜂群算法、萤火虫算法和布谷鸟算法等[2]，通过模拟群体性动物行为，在搜索空间内部利用个体间的信息交流、信息共享达到寻找最优解的目的。然而群智能算法发展至今仍然存在无法有效平衡求解精度和收敛速度的瓶颈，对于基本群智能算法的优化也是众多学者一直以来的研究方向。逐维改进的布谷鸟搜索算法[3]通过逐维更新评价，将维度组合成新的解，进行迭代更新；2018 年王晓静等人[4]提出一种基于均匀局部搜索和可变步长策略的萤火虫优化算法，算法结合局部搜索算子和动态可变步长的策略，有效平衡了算法收敛速度和求解精度；2019 年谢承旺等人[5]提出一种多策略协同的多目标萤火虫算法，均匀随机化初始种群，利用精英个体指导萤火虫移动，通过加扰动和ε-三点最短路径策略增加种群多样性；在萤火虫算法的基础上，文献[6]提出一种变步长萤火虫算法来解决数值优化问题；文献[7]受PSO 算法的启发，将全局最优解Gbest 的信息融合到人工蜂群算法中，提出了一种Gbest指导的人工蜂群算法。

在众多群智能优化算法中，PSO 简单高效，收敛速度快，逐渐在优化算法中脱颖而出[8]。利用PSO 算法的天然优势，在此基础上优化创新，能够取得更为高效的结果。PSO 因在求解连续问题上的优势，使得提出至今广泛应用于参数优化[9]、结果预测[10]、问题诊断[11]等领域。PSO 中每个粒子都视作待优化问题的一个候选解，利用个体历史最优信息和全局最优信息更新粒子速度和位置，在搜索空间迭代搜寻最优解。如同其他群智能算法，PSO 也存在多样性差、易于早熟收敛等问题[12]，因此针对PSO 的改进方法层出不穷，根据众多学者的分析和研究，大致分为如下四方面：

（1）算法参数方面。分析及研究PSO 的参数特性，通过优化算法参数来平衡全局勘探和局部搜索。文献[13]提出一种基于高斯函数实现非线性递减惯性权重的改进算法，从而更好地平衡粒子群搜索性能。2018 年王磊等人[14]将自适应惯性权重和学习因子与二维扰动策略相结合，提高了算法的收敛速度和求解精度。2019 年文献[15]提出一种基于单个粒子最优适应度值的惯性权重调整方法，使得粒子具有不同的惯性权重，该方法增大了惯性权重的多样性，同时有效平衡了全局勘探和局部搜索能力。

（2）拓扑结构方面。根据粒子间的社会关系设计不同的拓扑结构，丰富个体的学习模式，从而达到改善种群多样性的目的。文献[16]中粒子去除全局最优的影响，粒子的学习对象仅为种群中任意两个粒子个体最优中的较优者。文献[17]提出将PSO 中个体视作动态网络拓扑结构下的节点，粒子通过动态变化的网络结构丰富学习模式，平衡全局勘探与局部搜索。文献[18]提出一种改进的链结构粒子群算法，其中粒子只受相邻粒子影响，而不共享整个种群的邻域最优，结果表明算法具有稳定的优化能力。2015 年Liu 等人[19]将“小世界”网络的特性作为邻域拓扑引入PSO，通过概率P逐代改变邻域拓扑结构，丰富了粒子间的学习模式，有效改善了PSO 综合性能。

（3）多种群方面。相比单一的粒子种群，多个种群间利用有效的信息交流机制，不但可以丰富种群资源，还可以合理利用其他种群信息指导当前种群进化。文献[20]中Liang 等人把粒子种群分为具有小邻域结构的小群，采用随机重组算法实现种群间信息交流，增加了种群多样性，在复杂的多峰函数上具有较快收敛速度。2017 年Chengkhuntod 等人[21]利用多个PSO 种群迭代更新，如果陷入局部最优且局部最优不同，则种群的局部最优进行复制操作；如果陷入局部最优且局部最优相同，则局部最优进行重置操作，从而脱离局部最优位置。2018 年邓先礼等人[22]提出一种基于多种群的自适应迁移PSO 算法，为三个种群分配不同的加速度因子使其具有不同的搜索特性，周期性评价种群优劣程度，进行粒子迁移操作，实现不同搜索特性的种群协作寻优以及合理分配资源。

（4）算法（策略）混合方面。不同的优化算法（策略）在性能上具有不同的优势，巧妙融合不同优化算法（策略）思想，提出优劣互补的创新算法，同样也能提升算法的综合性能。文献[23]中Kayhan 等人将粒子群算法和电子表格求解器相结合，提出一种新的混合全局和局部优化算法，将PSO 用作全局优化算法，求解器用作局部优化算法，二者通过解的相互补充，来产生良好初始解，避免陷入局部最优。夏学文等人[24]提出一种具备反向学习和局部学习能力的粒子群算法，当陷入局部最优时对大部分粒子应用反向学习策略，对小部分较优粒子应用局部学习策略，提高了种群多样性的同时避免了陷入局部最优。2018 年Wang 等人[25]结合自学习的候选生成策略和竞争性学习策略，提出一种自适应学习策略的混合PSO 算法，能够较好地平衡全局勘探和局部搜索。

另外还有一些新颖的PSO 改进算法，如文献[26]提出一种基于Logistic 映射的自适应变尺度混沌粒子群算法，对部分较优粒子进行变尺度混沌局部优化，从而提高算法求解精度。文献[27]采用最坏粒子替换策略进行种群更新，结合短期记忆和长期记忆存储粒子信息。2019 年徐利锋等人[28]提出一种多级扰动的混合粒子群优化算法，避免陷入局部最优位置，在多目标优化问题上取得较好效果。

上述所有的PSO 算法的改进，其目的都是为了解决种群多样性差，求解精度低，收敛速度慢等问题。针对这些问题，本文结合拓扑结构优化，多种群协同寻优和混合策略等思想，提出一种粒子置换的双种群综合学习PSO 算法（comprehensive learning PSO algorithm based on particle permutation，PP-CLPSO），根据粒子群算法搜索过程的快速性和收敛性，以及Logistic 混沌思想对搜索空间的随机性和遍历性，设置具有不同搜索特性的双种群系统：自适应惯性权重的PSO 种群和基于Logistic 映射的混沌化种群。然后利用粒子编号机制，建立双种群间粒子一一对应的同号结构和种群内粒子两两一对的同位结构，赋予粒子新型社会关系；当自适应惯性权重PSO 种群搜索过程陷入局部最优时，PSO 种群同位结构下适应度值较差的粒子与混沌化种群中具有相同编号的粒子进行同号粒子置换操作，实现双种群间的信息交流，增加了种群多样性；对粒子置换操作后的双种群系统，综合同位粒子学习策略和局部学习策略，既保证了全局勘探能力，又提高了局部搜索精度。

1 PSO 算法

其中，w为惯性权重，表示当前代的速度对下一代速度的影响，通常采用线性递减的惯性权重选择技术，公式为w=wmax-t⋅(wmax-wmin)/T，其中wmax=0.9，wmin=0.4，T为最大迭代次数，t为当前迭代次数；c1和c2为学习因子，表示粒子对个体历史最优和全局最优的学习能力，取值一般为c1=c2=2.0；r1和r2为[0,1]之内的随机数。

2 PP-CLPSO 算法的主要思想

2.1 双种群系统

2.1.1 自适应惯性权重的PSO 种群（Pop1）

PSO 算法的搜索方式是利用个体历史最优信息和种群最优位置信息，指导粒子动态更新速度和位置，惯性权重w作为PSO 算法中的一个重要参数，在搜索过程中起到调整粒子下一次迭代飞行速度，平衡全局勘探和局部搜索的作用。常用的线性递减的惯性权重，在迭代后期惯性权重较小，粒子飞行速度较慢，而PP-CLPSO 的一个核心思想是每当Pop1 陷入局部最优就执行粒子置换策略，而置换操作往往发生在迭代后期，此时粒子需要较大的飞行速度向有利位置飞行，显然线性递减的惯性权重选择技术不适用于PP-CLPSO。本文惯性权重选择技术不再依赖粒子的迭代次数，而是根据粒子的适应度值进行自适应调节。自适应惯性权重选择技术见算法1。

算法1自适应惯性权重算法

步骤1计算Pop1 粒子适应度值fi的平均适应度值favg。

步骤2取适应度值大于favg的粒子，计算平均适应度值fworseavg；取适应度值小于favg的粒子，计算平均适应度值fbetteravg。

步骤3如果fi＞fworseavg，则第i个粒子的惯性权重赋值为wmax。

步骤4如果fi＜fbetteravg，则第i个粒子的惯性权重赋值为wmin。

步骤5如果fbetteravg≤fi≤fworseavg，则第i个粒子的惯性权重按照式（3）、式（4）赋值。

其中，wmax=0.9，wmin=0.4，ε表示位于fbetteravg和fworseavg之间的粒子适应度值归一化到Sigmoid 函数自变量[a,b]之间的取值，根据w取值范围得到a=-0.405 47，b=2.197 22。这样就建立了适应度值与惯性权重之间的非线性关系，较大适应度值的粒子具有较大的惯性权重，使其加速向最优位置飞行；较小适应度值的粒子，避免飞行速度过大而跳过最优位置，因此赋予较小惯性权重；粒子随着适应度值的降低，惯性权重非线性下降。解决了迭代后期置换操作后的粒子惯性权重太小的问题，改善了Pop1 的收敛特性。

2.1.2 基于Logistic映射的混沌化种群（Pop2）

Logistic 映射是混沌系统中常见的一维混沌映射，处于混沌态Logistic 映射系统中的变量具有随机性和遍历性。Logistic 映射具有多种形式，式（5）是一常见的Logistic映射形式，其中混沌域为(0,1)，Logistic参数μ=[0,4]，当3.569 945 6…≤μ≤4 时，系统处于混沌状态。

本文根据混沌思想生成基于Logistic 映射的混沌化种群（Pop2），种群内的每个粒子随迭代次数增加，不改变其遍历种群搜索范围的方式，与Pop1 的搜索过程并行进行，为整个双种群系统提供了丰富的粒子资源，极大地增加了种群多样性。Pop2 搜索步骤见算法2。

算法2Pop2 搜索

步骤1t=1；

步骤2生成N个混沌域(0,1)内的初始向量，其中第i个粒子的D维初始向量为

步骤3利用式（5）迭代生成混沌序列

步骤4按照将产生的混沌序列映射到粒子原始解空间，得到，更新适应度值；

步骤5更新最优信息，t=t+1，返回步骤2。

2.2 同号结构和同位结构

对于种群规模大小均为N的Pop1 和Pop2，利用粒子编号机制明确种群粒子信息，通过粒子编号机制使得种群间粒子形成一一对应的同号结构，并且生成种群内部的两两一对的同位结构，如图1。同号结构是基于粒子编号机制赋予粒子间的一种虚拟结构，指导双种群粒子的信息交流，当满足粒子置换操作条件时，依据同号结构进行粒子置换操作。同位结构提供了一种新的社会学习模式，当粒子置换操作后，Pop1 内处于同位结构下的粒子相互学习，指导粒子进行对自身有利的飞行。

2.3 粒子置换策略

Fig.1 Same sign structure and same position structure图1 同号结构和同位结构

在执行粒子置换策略之前需要明确两个问题，即何时进行粒子置换操作和置换种群中哪些粒子。在PP-CLPSO 算法中，Pop1 搜索后期种群多样性差，陷入局部最优位置时粒子收敛速度减慢，最终导致算法停滞，若在此时双种群系统资源进行调度，配合粒子学习模式的改变，可使算法重新激活。因此本文以Pop1 的收敛程度作为粒子置换策略的指标，当检测到Pop1 种群最优信息cycle代未更新，则认为Pop1 陷入局部最优位置，触发粒子置换策略。对于第二个问题，由于此时Pop1 的粒子已经陷入局部最优，无法找到更优的解，此时选择当前同位结构下个体适应度值较差的个粒子与Pop2 进行同号粒子置换操作。粒子置换策略不但激活了停滞状态的Pop1，改善了种群的多样性，而且建立了双种群系统之间的关联性，实现双种群间信息交流。

2.4 综合学习策略

粒子置换操作后的双种群系统引入了新的粒子信息，就需要新的学习模式指导粒子学习，来平衡全局勘探和局部搜索的能力。本文结合同位粒子学习和局部学习两种方式，进行S代的综合学习策略，来达到双种群协同寻优的目的。

2.4.1 同位粒子学习

对于置换操作后的Pop1 来说，新置换进来的粒子位置信息具有混沌化特性，可以很好地用来指导其同位结构下陷入局部最优位置的粒子跳出局部最优位置，本文把这部分粒子的学习模式称为同位粒子反向学习，如Part1。而新置换进来的粒子也可以利用其同位粒子所具备的较优位置信息进行正向搜索，本文把这部分粒子学习模式称为同位粒子正向学习，如Part2。

Part1：Pop1 保留下的N/2 个粒子反向学习的对象是其历史最差位置和当前代同位结构下新置换进来的Pop2 混沌态的粒子位置，其中第i个粒子的速度信息和位置信息更新公式如式（6）、式（2）所示。

2.4.2 局部学习

对于置换操作后的Pop2 来说，其目的是为了进行局部细致搜索。首先取全局最优位置：

通过计算其个体最优位置与全局最优位置的绝对距离差值，以此距离为最大搜索步长，在个体历史最优位置采取线性递减搜索步长的方式向全局最优靠近，即完成Pop2 内N个粒子在个体历史最优位置的局部搜索。具体操作如Part3，局部学习采用贪心策略更新其位置信息。

Part3：此时Pop2 内的N个粒子，分别计算其历史最优位置与全局最优位置的差值距离di=Gbest′-，以di作为第i个粒子的最大搜索步长，然后分别在其历史最优位置采用线性递减的搜索步长向全局最优位置正向搜索，其中第i个粒子的位置更新公式如式（8），r为[0,1]之间的随机数，s、S分别为当前综合学习代数和最大综合学习代数。

需要说明的是，综合学习期间的Pop1，其目的是为了使粒子能够通过同位粒子学习策略分布在搜索空间，此时需要调整自适应选择惯性权重技术，即将fi＜fbetteravg的粒子惯性权重赋值为wmax，使适应度较小的粒子以更大的飞行速度跳出局部最优；将fi＞fworseavg的粒子惯性权重赋值为wmin，使适应度较大的粒子以较小的速度缓慢向较优信息靠近，其他粒子以式（3）、式（4）选择其惯性权重。经过S代综合学习后会出现两种情况：一是全局最优信息发生更新，则令Gbest1=Gbest′，指导种群再次按照原搜索方式进行迭代寻优；二是全局最优信息未发生更新，此时Pop1 经过S代的同位粒子学习也已经跳出局部最优位置，粒子较好地分布于搜索空间，综合学习完成后，重新启动原搜索方式继续迭代寻优。

2.5 PP-CLPSO 算法流程

根据上述改进算法策略介绍，PP-CLPSO 的算法流程如图2。

Fig.2 Flowchart of PP-CLPSO algorithm图2 PP-CLPSO 算法流程图

3 实验结果与分析

3.1 测试函数

本文选取9 个经典测试函数来检验PP-CLPSO算法的综合性能，根据函数特点分为：F1～F5单峰函数，F6～F9多峰函数。测试函数详细信息见表1。

Table 1 Test function表1 测试函数

3.2 对比算法

PP-CLPSO 算法结合了拓扑结构优化、算法参数改进、混合策略结合和多种群协同寻优的思想，为验证PP-CLPSO 算法具有高效的求解精度和收敛速度，本文选取了4 个涉及上述优化思想的算法进行对比，分别为：用于多峰函数优化的综合学习粒子群优化算法（comprehensive learning particle swarm optimizer，CLPSO）[16]、高斯分布衰减惯性权重粒子群优化算法（particle swarm optimization algorithm with decreasing inertia weight based on Gaussian function，GDIWPSO）[13]、具备反向学习和局部学习能力的粒子群优化算法（reverse-learning and local-learning PSO，RLPSO）[24]、基于多种群的自适应迁移粒子的粒子群算法（multipopulation based self-adaptive migration PSO，MSMPSO）[22]。上述对比算法的详细参数设置如表2。

Table 2 Contrast algorithm表2 对比算法

Table 3 Influence of cycle on algorithm表3 cycle对算法的影响

3.3 参数设置

PP-CLPSO 算法是以Pop1 的收敛情况作为执行粒子置换策略和综合学习策略的标准，因此如何判断Pop1 陷入局部最优显得格外重要，本文采取cycle代Gbest1未发生更新的方式来判断种群是否收敛于局部最优位置。为了更好地确定cycle的值，在种群规模Popn=20(n=1,2)，粒子维度D=30，最大迭代次数T=2×104时，分别将cycle的值设为5、15、20、25、30 进行实验测试，实验结果如表3 所示，其中Mean、St分别表示独立运行20 次实验结果的平均值、标准差。

分析F9函数在相同参数和仿真环境下cycle对算法时间的影响，实验结果如图3，其中T1和T2为算法运行时间和达到指定精度（1.00E-04）所用时间，单位秒（s）。

Fig.3 Influence of cycle on algorithm time图3 cycle对算法时间的影响

从上述分析结果可以看出，当cycle取值较小，种群中粒子在当前收敛状态下仍然具有找到更优解的趋势，若在此状态下执行粒子置换操作，不但会增加置换操作的次数，导致算法整体时间大大增加，而且粒子收敛不彻底，也降低了求解结果的精确度；当cycle取值较大，粒子收敛于局部最优位置且没有找到更优解的趋势，此时过多的迭代也会增加达到指定求解精度的时间。根据实验测试和结果分析表明，cycle设置为20 代，实验的结果最佳。

此外综合学习的代数也直接影响算法的整体性能，根据表2 结果取cycle=20，其他实验参数同上，对综合学习代数S分别设为10、20、30、40、50 的情况下进行实验测试，根据表3 选择结果具有明显区别的测试函数F3、F9进行分析，实验结果如表4 所示。

Table 4 Influence of comprehensive learning times S on algorithm表4 综合学习代数S对算法的影响

从表4 可以看出，若综合学习的代数太大，Part2同位粒子正向学习粒子再次收敛到局部最优位置，并且将增加算法整体时间，若综合学习的代数太小，Part1 同位粒子反向学习粒子跳出局部最优位置的能力不足，并且全局勘探和局部搜索找到更优解的几率较小，重新采用标准PSO 搜索方式容易再次陷入局部最优，根据实验测试取综合学习代数S=20。

3.4 实验结果

3.4.1 求解结果分析

将PP-CLPSO 与4 个对比算法分别在30 维的测试函数上独立运行20 次，将实验结果的平均值和标准差用来评价算法的求解精度。算法在9 个测试函数上的求解结果见表5。其中加粗数据为对应测试函数的最优求解结果。从表5 可以看出，PP-CLPSO在9 个测试函数中有7 个取得最优求解结果。通过对求解结果的进一步分析可以看出，PP-CLPSO 在5个单峰函数中3 次找到全局最优解，说明相比其他对比算法，PP-CLPSO 在单峰函数上能够较为精准地找到最优解。而在4 个多峰函数上，PP-CLPSO 有4 次找到最优结果，说明对于多峰问题，PP-CLPSO 能够展现出更为优越的性能。

3.4.2 收敛曲线分析

为了更为直观地看出与4 个对比算法在求解精度和收敛速度上的差异性，图4 给出了对比算法在9个测试函数上的收敛曲线，其中每次运行的最大评价次数（maximum number of fitness evaluations）为FEs=10 000D，从图4（a）、（b）、（d）可以看出PPCLPSO 在单峰函数上具有较快的收敛速度，并且能够迅速找到全局最优值，对于图4（c）、（e）其表现仅稍逊于MSMPSO，对于单峰函数能够迅速收敛于全局最优位置。从图4（g）、（h）这两个多峰函数的收敛过程可以看出PP-CLPSO 搜索前期收敛速度和求解精度并不是最好的，但是通过粒子置换和综合学习策略能够使得算法在迭代后期也能够有发现更优解的机会。从图4（f）、（g）、（h）、（i）中能够看出PPCLPSO 对于多峰函数具有较为准确的收敛特性。综合来说，PP-CLPSO 不管是在解决单峰问题上还是多峰问题上，随着迭代过程中的粒子置换和综合学习，能够使粒子在求解精度和收敛速度上呈现出较为优越的性能。

3.4.3 算法时间分析

根据PP-CLPSO 的算法流程可知，算法单次迭代所需要的时间为Ta+Tb+Tc，其中Ta为双种群系统中所有粒子的进化一次所用的时间，Tb为粒子执行过程所占用的时间，Tc为粒子置换策略和综合学习策略时间，当算法没有陷入局部最优时Tc则为0。其中Ta的时间复杂度为O(N)，Tb的时间复杂度为O(1)，Tc的时间复杂度为O(S×N)，因此算法的时间复杂度为O(S×N)。

Table 5 Solution result表5 求解结果

Fig.4 Convergence curve图4 收敛曲线

在仿真环境相同的情况下，为了更有效分析算法时间上的优势，表6 给出了PP-CLPSO 与4 个对比算法在3 个单峰函数和3 个多峰函数达到指定求解精度（1.00E-04）所利用的时间，单位秒（s），其中“—”表示最大迭代次数后仍未达到该精度。

Table 6 Running time of algorithms表6 算法运行时间 s

从表6 中可以看出相比4 个对比算法来说能够在更短的时间达到指定的求解精度，通过对算法流程分析可以得出，虽然陷入局部最优时候增加了S代的综合学习，增加了算法单次迭代的时间，但是S代的综合学习更快地找到全局最优解，供下次种群1 中利用，结合自适应惯性权重算法所赋予的不同权重系数，使得有利粒子能够以更大的飞行速度，更快地收敛于全局最优位置。

3.4.4 算法综合性能分析

为检验PP-CLPSO 算法的综合性能，将其与其他群智能优化算法进行对比，在维度D=30，种群规模N=100，最大迭代次数T=D×10 000 的参数设定下，独立运行50 次，取测试结果的平均误差与文献[4]的数据进行对比，其中DDICS[3]、GABC[7]、VSSFA[6]、UGCS[4]这4 个群智能算法的其他参数设置与其原文一致，实验结果如表7 所示。由表7 可以看出PPCLPSO 在6 个测试函数上的求解结果均优于其他4个群智能算法。

Table 7 Mean error value of PP-CLPSO and other swarm intelligence algorithms表7 PP-CLPSO 与其他群智能算法的平均误差值

4 结束语

本文提出的PP-CLPSO 算法旨在解决群智能优化算法难以跳出局部最优这一难题。利用标准粒子群算法和Logistic 混沌思想建立双种群系统，种群间粒子形成独特的同位结构和同号结构，通过动态置换粒子策略来增加种群多样性，综合同位粒子学习和局部学习两种粒子学习策略，帮助算法跳出局部最优的同时提高收敛速度和求解精度。利用9 个测试函数和4 个粒子群改进算法、4 个群智能算法进行实验对比，实验结果表明PP-CLPSO 算法具有较为优异的综合性能。进一步检验算法在实际应用问题中的有效性将是下一步研究的主要内容。