基于最优交叉的广泛学习粒子群优化

陈小斌，杨利华，汤可宗

（景德镇陶瓷大学 信息工程学院，江西 景德镇 333403）

0 引言

粒子群优化（Particle Swarm Optimization，PSO）是进化计算的重要分支之一［1］，其是通过模拟自然界生物活动的群体智能行为，同时在借鉴人工生命［2］、鸟群觅食、鱼群学习等群智能行为基础上提出的一种启发式搜索优化算法［3］。相比于其他启发式搜索算法，由于PSO 具有易于实现、操作简单等优点，多年来已成功应用于机器学习、光伏参数识别、资源调度分配等现实世界的诸多优化问题中［4-10］。

然而，PSO 的启发式搜索特性使得该算法存在早熟收敛、收敛速度慢、求解精度低等问题［11］。针对这些问题，不同学者从粒子活动行为、粒子性能评价以及惯性权重自适应调整等方面进行了不少改进工作。文献［12］在基础PSO 算法中提出使用惯性权重调整算法的勘探和开发进度，并提出基于惯性权重ω 的粒子群优化算法（Omega Particle Swarm Optimizer，OPSO），更好地实现了初期勘探与后期开发之间的平衡，有效提升了优化精度；文献［13］通过分析粒子在离散时间运动时的轨迹，并将其发展到连续时间，将勘探与开发任务统一，使用固定参数收缩因子取代惯性权重，提出基于收缩因子的粒子群优化算法（Constriction Faction in Particle Swarm Optimization，CPSO），有效提高了算法优化能力；文献［14］-［17］则分别讨论了PSO 的粒子动态跟踪以及模糊系统，并结合粒子种群个体与集体的信息传递方式，研究了不同种群拓扑结构对PSO优化能力的影响。

此外，粒子种群间的交流学习近年来成为改进的流行方向。文献［18］尝试让粒子个体结合种群历史最优位置的优良信息进行更新，提出一种广泛学习粒子群优化算法（Comprehen-sive Learning Particle Swarm Optimizer，CLPSO）。实验发现广泛学习策略可以较长时间保持种群的多样性，对搜索空间进行更加充分地探索，能够较好地避免种群过早收敛。文献［19］在CLPSO 的基础上，通过在粒子速度更新时增加一个动态扰动项，实现粒子种群在开发与勘探阶段的平衡，从而解决CLPSO 的求解精度问题。文献［20］则利用广泛学习策略生成两个子种群，提出一种增强探索和开发的异构综合学习粒子群优化算法（Heterogeneous Comprehensive Learning Particle Swarm Optimization with Enhanced Exploration and Exploitation，HCLPSO）。其中，开发种群和勘探种群通过异步学习更新各种最优位置信息，在保持算法开发性能充分发挥的同时，也维系了粒子群的多样性。文献［21］利用一种信息共享机制（Information Sharing Mechanism，ISM）来提高PSO 的性能，提出具有信息共享机制的竞争与合作粒子群优化算法（Competitive and Cooperative Particle Swarm Optimization with Information Sharing Mechanism，CCPSO-ISM），通过各粒子之间的信息共享来增强粒子间的沟通，以提高算法的搜索能力。另一方面，通过分析粒子群搜索过程中的运动行为也不失为一种好的改进方式。文献［22］通过动态评估粒子种群分布与适应度等方式对粒子群的惯性权重以及速度更新方式进行自适应调整，以此改进PSO 的收敛速度和全局搜索能力；文献［23］则通过分析粒子运动状态提出双中心粒子群优化算法（Double Center Particle Swarm Optimization，DCPSO），在不额外增加算法实现复杂度的情况下，改善算法的收敛速度和精度。

除分析PSO 自身的启发式优化特性进行改进外，也有不少学者根据其他优化算法获得改进灵感。文献［24］利用高斯预过程拟合方法对当前问题优化空间最优解方向进行预测，并引导粒子群搜索，加快搜索速度，同时增强粒子群的多样性；文献［25］通过一种sigmoid 函数的加权策略来自适应地调整加速系数，提出自适应权重粒子群优化算法（Adaptive Weighting Particle Swarm Optimization，AWPSO），以此提高算法的收敛速度。

遗传算法（Genetic Algorithm，GA）是一种通过借鉴进化生物学遗传中包括突变、自然选择以及杂交等现象发展而来的优化算法［26］。相对于PSO 而言，该算法可通过突变维持染色体的多样性，同时通过交叉操作进行基因重组，以获得更好的结果。因此，许多学者都会借鉴GA 的相关概念对PSO 进行改进。文献［27］借鉴GA 提出另一种具有重组学习和混合变异的动态多种群粒子群优化算法，通过重组学习和混合变异提高算法的优化能力；文献［28］则借鉴GA 个体繁殖的概念，结合PSO 粒子的社会学习操作，提出一种遗传学习粒子群优化算法。

CLPSO 的广泛学习策略能够在搜索过程中较好地勘探整个问题空间，但收敛速度较慢成为算法进一步广泛应用的掣肘。为进一步提高CLPSO 的求解精度，同时加快算法收敛速度，本文借鉴GA 中的染色体交叉概念，提出一种基于最优交叉的广泛学习粒子群优化（Comprehensive Learning Particle Swarm Optimization Based on Optimal Crossover，CLPSO-OC）算法。该算法利用CLPSO 杰出的全局勘探能力，通过粒子历史最优位置与全局最优位置执行交叉操作，产生更优异的结果，以进一步提升算法的综合性能。

1 算法基本理论

1.1 粒子群优化算法

PSO 是一种结合粒子社会学习行为和群体合作交互实现问题求解的启发式优化算法。该算法将种群中每个粒子个体抽象为具有速度Vi和位置Xi的一个质点。伴随着优化过程，各粒子在全局最优位置gbest和个体历史最优位置pbest的引领下按式（1）、式（2）更新粒子速度与位置。

其中，c1、c2分别代表各粒子向pbest和gbest临近区域移动的学习因子，r1、r2则为介于［0，1］之间的随机数。pbest和gbest对粒子的引导使得粒子能够在更广泛的空间内进行探索，同时赋予粒子一定的智能，使粒子能够利用自身历史最优位置与全局最优位置不断地引导自身搜索，让种群得以持续优化。

为进一步平衡粒子群的全局搜索与局部搜索能力，Shi 等［12］在式（1）的基础上引入惯性权重ω，使用式（3）更新速度。此改进大大提高了算法的优化能力，并为之后的研究提供了新方向。

1.2 遗传算法

GA 是受进化启发而提出的一种优化模型，该算法在简单类似染色体的数据结构上对特定问题的潜在方案进行编码，并将重组算法应用于这些结构以保留关键信息。GA 通过随机初始化一定数量的染色体，通过特定方式评估这些结构并进行繁殖，此时那些代表目标问题更好解决方案的染色体比那些解决方案较差的染色体有更多繁殖机会。最优解决方案通常来源于当前染色体集合。在GA中，主要有以下3 种操作：选择、交叉和变异。在选择操作中，可以选择轮盘赌、玻尔兹曼选择等方法；交叉操作中同样具有大量可选的交叉技术，例如循环交叉、多点交叉、均匀交叉等，但主流的操作可分为两种：单点交叉和两点交叉，如图1所示。

Fig.1 Crossover operation图1 交叉操作

交叉操作完成后，GA 对于对应染色体中的每个位会以一些低概率的Pm进行变异。通常，突变率的应用概率小于1%。然而，在实值函数优化中，GA 染色体长度与求解精度紧密相关。此外，优化过程中对优化结果进行评估时需要进行编解码操作，因此大大增加了其实现难度。

2 基于最优交叉的广泛学习粒子群优化

2.1 广泛学习策略

在经典PSO 中，每个粒子的更新同时受到全局极值gbest和个体极值pbest的影响。由于整个种群粒子速度的更新受到全局极值gbest的影响，因此导致经典PSO 算法快速收敛。然而，粒子收敛速度过快在一定程度上会造成粒子种群早熟收敛，无法更加广泛地勘探搜索空间。因此，在这些算法的单峰函数中，往往能够相对快速地得到一个精度较高的解。然而，在多模态函数优化中，过快收敛可能会导致算法陷入局部最优，以至于算法停留在局部最优位置，而无法达到真正的最优区域。广泛学习策略为了给予PSO 在多模态函数中更好的优化能力，使用式（4）进行粒子速度更新。此时粒子的更新不再受全局最优gbest影响，而是由进行引导，其中的计算规则如式（5）所示。通过使用新的速度更新方式控制粒子群对优化空间的搜索，使得各粒子能够更充分地勘探周边区域。

广泛学习策略伪代码如下：

2.2 最优交叉操作

在PSO 中，寻优粒子个体是独立且自主的，在行为上会受到全局最优粒子的影响，但粒子间无法将可能存在的最优信息进行共享，因此优化效率和优化精度都会在一定程度上受到影响。而GA 中通过染色体交叉的方式可以对两个染色体上的对应位置进行交换，以此让优化个体间进行直接的信息交流。据此，本文为进一步改善粒子群的收敛速度和优化精度，从粒子群的社会学习方式出发，提出一种最优交叉操作，该操作只发生在优化过程后期的全局最优位置与个体历史最优位置之间。由于这两个位置都包含了各粒子的优良信息，因此通过交叉操作可以更好地进行优良信息的学习，从而有可能得到更好的最优位置。交叉操作执行公式如式（6）所示，其中tempcross是最优位置besti和随机个体最优位置对应的交叉结果。

在交叉操作中，通过一个随机概率r选择交叉操作类型。当随机概率r大于0.5 时执行单点交叉操作，小于等于0.5时执行双点交叉操作，最优交叉伪代码如下：

2.3 CLPSO-OC算法

CLPSO-OC 借助广泛学习策略优良的广域勘探能力，提高算法在多模态问题模型中的优化能力，减少算法落入局部最优的风险。同时结合遗传算法中的染色体交叉概念，提出一种最优交叉方法，通过全局最优位置随机与种群中任意粒子历史最优位置的交叉操作来交换彼此的优良信息，以促进粒子间的学习交流，加快算法收敛速度，并有效提高求解精度。算法总体流程如下：

Step 1：初始化参数设定，给每个粒子赋予随机的初始位置和速度。

Step 2：将粒子个体的历史最优位置初始化为粒子的初始位置，同时根据适应度函数评价出全局最优位置。

Step 3：执行广泛学习策略并更新粒子位置。

Step 4：从Xt时刻的粒子位置和pbestt-1时刻的粒子个体历史最优位置中评价出pbestt时刻的粒子个体历史最优位置。

Step 5：从pbestt时刻的粒子个体历史最优位置和gbestt-1时刻的全局最优位置中更新gbestt。

Step 6：执行最优交叉操作。

Step 7：判断是否满足结束操作，若是，则执行Step 10，否则执行Step 3。

Step 8：输出当前全局最优位置以及相对应的适应度值。

CLPSO-OC 相对于原算法而言，并未增加算法的实现难度，也没有额外增加时间复杂度。算法流程如图2所示。

Fig.2 Flow of CLPSO-OC图2 CLPSO-OC执行流程

3 实验结果与分析

3.1 平台搭建与测试前的准备

本次测试采用的软件环境和硬件环境配置为：Windows11 操作系统，Matlab2020b 运行环境，处理器为Intel（R）Core（TM）i7-9700 CPU，主频 3.00GHz，内存为8GB。

为了突出对比，本文选取国外较为流行的典型改进PSO 进行对比，分别是OPSO［12］、CPSO［13］、CLPSO［18］、HCLPSO［20］、CCPSO-ISM［20］、DCPSO［23］、AWPSO［25］。其中，OPSO 和CPSO 是PSO 算法的经典之作，两者从粒子种群空间与时间角度对算法进行改进；CLPSO、HCLPSO 以及CCPSO-ISM 则从粒子群学习方式出发对算法进行改进；AWPSO 使用Sigmoid 函数对惯性权重进行自适应调整；DCPSO 则从粒子种群搜索在空间上的分布角度出发，使用双中心方法提升算法的优化效率。以上算法都涵盖了PSO 较为代表性的改进方向，也被大部分学者所认可，因此本文选择以上算法进行对比实验。各算法参数、粒子种群大小及最大迭代次数设置如表1 所示。从CEC2017 中选取部分函数，如Sphere、Rosenbrock等经典优化问题模型作为基准测试函数，具体如表2 所示。其中，f1～f6和f7～f12分别是无模态和多模态函数，表中D代表问题的求解维度，X代表搜索区间，且满足X∈RD。f*指对应优化问题模型在D维度下的理论最优值。

Table 1 Parameter setting of algorithms表1 算法参数设置

Table 2 Information of benchmark test function表2 基准测试函数信息

3.2 评价指标

本节选取各算法在基准测试函数独立重复实验中的最小值min、平均值mean以及标准差std作为基本评价指标，三者分别能够代表算法的最佳优化能力、平均优化效果和算法的优化稳定性，能够较为直观地反映出各算法在对应基准函数中的性能。

此外，统计检验方法是检验优化算法性能的关键方法之一，通过检验测试可以得出更可靠的结论。本文采用Friedman 检验各算法之间的差异，同时进一步使用Wilcoxon 符号秩检验来验证CLPSO-OC 与其他比较算法之间的差异显著性水平。通过以上两个统计检验方法验证CLPSO-OC 在求解经典优化问题上的普遍有效性。

3.3 算法测试结果分析

根据上文实验环境的设置，各算法在所有测试函数中完成了独立重复优化实验，详细实验结果如表3 所示。从表3 可以看出，CLPSO-OC 在f3、f9、f10、f124 个基准函数测试结果中的3 项指标都优于其他7 种改进PSO 算法；在f1、f2两个基准函数中，CLPSO 具有更好的优化性能；CCPSOISM 则在f8和f11中表现出比其他改进PSO 算法更优异的性能；在基准函数f5中，所有算法都能够得到最优结果，但OPSO、CLPSO、DCPSO、CCPSO-ISM 以及CLPSO-OC 表现更加稳定。

Table 3 Comparison of benchmark function test performance表3 基准函数测试性能比较

为了观察各优化算法的收敛状态，本文将收敛结果按照一定比例进行等比缩放，最终结果如图3所示。

Fig.3 Convergence state diagram of each improved algorithm under a fixed number of iterations图3 各改进算法在固定迭代次数下的收敛状态图

从图3 中各算法在对应函数中的收敛状态可以看出，在指定的迭代次数内，CLPSO-OC 在函数f3、f9中收敛速度和收敛精度的表现最为优异；在函数f1中，HCLPSO 表现较好，在后期能较为快速地达到更高精度；CPSO 在函数f4中展现出来的优化能力最强。综合来说，CLPSO-OC 相对于CLPSO 具有更快的收敛速度和更高的求解精度，同时与其他改进PSO 算法相比具有较好的优化能力。

3.4 基于Friedman 检验与Wilcoxon 符号秩检验的可靠性对比分析

各算法的Friedman 检验结果如表4 所示，其中CLPSO-OC 在对比优化算法中的基准问题优化性能排名第一。Friedman 检验中的统计数据p 值强烈表明8 种算法优化结果之间存在显著差异。此外，CLPSO-OC 与其他参考算法的Wilcoxon 符号秩检验结果如表5 所示。检验结果表明，CLPSO-OC 与OPSO、CPSO、CLPSO 以及AWPSO 4 个改进PSO算法相比，显示出显著性水平α=0.05的明显改善，其与DCPSO、HCLPSO 和CCPSO-ISM 之间的差异在统计学上并不显著，但从基准函数测试结果可以看出，CLPSO-OC 在大部分基准测试函数上的优化效果与DCPSO、HCLPSO 和CCPSO-ISM 相比有一定的领先优势。此外，从与原算法CLPSO 的对比可以看出，CLPSO-OC 的优化精度和收敛速度有较为明显的改善。因此，Friedman 检验和Wilcoxon 符号秩检验验证了CLPSO-OC在基准问题上的一般有效性。

Table 4 Friedman statistical test results of various algorithms in benchmark function test表4 各算法在基准函数测试中的Friedman统计检验结果

Table 5 Statistical test results of Wilcoxon symbols for various algorithms in benchmark function test表5 各算法在基准函数测试中的Wilcoxon符号秩统计检验结果

4 结论

针对CLPSO 算法收敛速度慢、优化精度低等问题，本文提出一种基于最优交叉的广泛学习粒子群优化算法，实现在改善算法优化效率、提升求解精度的同时加快粒子群收敛。本文从GA 中的染色体交叉获得灵感，提出一种粒子群历史个体最优位置交叉操作，用于改善粒子群收敛速度慢的问题，同时提供各粒子之间优良信息传递的一个可行方法，既能保持CLPSO 卓越的多模态开发能力以及较高的算法优化稳定性，又能提升算法的优化效率。

实验结果表明，本文提出的CLPSO-OC 针对测试的基准函数相较于CLPSO 有更好的优化表现。其在各基准测试函数中的搜索精度更高，平均优化效果和稳定性更好。相对于其他改进PSO 算法，CLPSO-OC 在综合性能上也有较大提升。最优交叉方法给当前PSO 改进提供了一种新思路，同时给神经网络训练、大规模复杂网络等现实优化问题模型提供了一种新的解决方案。未来将进一步研究最优交叉的改进操作，以期再次提高算法优化效率。