基于种群熵偏移平均加权的改进量子粒子群算法

DOI：10.19850/j.cnki.2096-4706.2024.02.014

收稿日期：2023-05-29

摘  要：量子粒子群算法具有更好的全局搜索能力，被视为对粒子群算法极为有效的改进，然而其运行过程中仍存在种群多样性衰减问题。为进一步提升量子粒子群算法的全局寻优能力，在基于加权平均最优位置的量子粒子群算法的基础上，提出了基于种群熵偏移平均加权的改进量子粒子群算法，将种群熵与加权范围中心偏移值进行动态关联，有效增强了算法搜索空间的遍历性，避免了算法早熟收敛。应用常规测试函数，与传统粒子群算法、量子粒子群算法和加权量子粒子群算法进行了对比分析，证明了文章提出的改进算法的有效性。

关键词：量子粒子群算法；加权量子粒子群算法；种群熵；偏移平均加权；测试函数

中图分类号：TP301；TN95  文献标识码：A  文章编号：2096-4706（2024）02-0060-05

Improved Quantum Particle Swarm Optimization Based on

Population Entropy Offset Mean Weighting

ZHOU Zhiwei

（Huadong Electronic Engineering Research Institute， Hefei  230031， China）

Abstract： The Quantum Particle Swarm Optimization has better global search ability and is considered an extremely effective improvement to the particle swarm optimization. However， there is still a problem of population diversity decay during its operation. In order to further enhance the global optimization ability of Quantum Particle Swarm Optimization， an improved Quantum Particle Swarm Optimization based on population entropy offset mean weighting is proposed， which is based on quantum particle swarm optimization in weighted mean optimal position. Dynamically associating the population entropy with the weighted range center offset value effectively enhances the traversal of the algorithm's search space and avoids premature convergence of the algorithm. By applying conventional test functions， a comparative analysis is conducted with traditional particle swarm optimization， Quantum Particle Swarm Optimization， and weighted quantum particle swarm optimization， demonstrating the effectiveness of the improved algorithm proposed in the paper.

Keywords： QPSO; WQPSO; population entropy; offset mean weighting; test function

0  引  言

粒子群优化算法（Particle Swarm Optimization， PSO）自1995年由Kennedy等[1]提出以来，因其建模简单、收敛速度快且易于实现等得到了广泛的应用，但是PSO算法不能全局收敛[2]，因此很多人提出了PSO的改进措施[3-6]，努力改善其全局搜索性能。2004年，Sun等[7]将量子特性融合到PSO中，提出了量子粒子群优化算法（Quantum-behaved Particle Swarm Optimization， QPSO），增加了迭代过程中的群体多样性，增强了算法的全局寻优能力；然而QPSO仍然存在粒子种群多样性衰减、搜索能力弱化等问题，因此对QPSO算法也出现了许多改进策略，包括自适应调整量子半径策略[8]、团队进化策略[9]、基于Grünwald-Letnikov定义的分数微积分策略[10]、粒子邻域拓扑策略[11]、基于孤子波理论的改进策略[12]等。

Xi等[13]提出了一种加权量子粒子群算法（Weighted Quantum-behaved Particle Swarm Optimization， WQPSO），通過对当前粒子最优位置按照适应度值排序并分别赋予不同加权值的方法，对粒子的平均最优位置进行加权，从而得到新的粒子平均最优位置。

本文受此启发，提出了一种改进策略，即在算法中对平均最优位置加权值的范围中心进行偏移，保证算法在迭代中后期保持较强的搜索能力，并结合种群熵的概念，将种群熵与加权偏移值进行动态关联，实现算法搜索能力的自适应调节。

1  量子粒子群算法

相較于PSO算法，QPSO算法中没有速度矢量，其位置迭代公式为[5]：

（1）

式中pi， j（t）为局部吸引因子，由个体最优位置pi， j（t）和全局最优位置pg， j（t）共同决定，其表达式为：

（2）

mj为粒子群平均最优位置：

（3）

（4）

M为种群规模，D为粒子维数；φ、u均为（0，1）之间的随机数；β为QPSO算法的收缩扩张系数，用来控制算法收敛速度，是算法中唯一的控制参数，一般取1到0.5随迭代次数线性递减。

2  加权量子粒子群算法

Xi等[13]认为精英粒子在群体演化中应该起主导作用，因此在WQPSO中提出根据当前粒子最优位置的适应度值排序对其分别赋予不同的权重值，赋予精英粒子较大的权值，赋予弱质粒子较小的权值，然后对粒子群平均最优位置进行加权平均。

WQPSO算法中的平均最优位置m（t）的表达式为：

（5）

其中αi为加权因子，并且每个粒子加权值根据其适应度值升序排序从1.5到0.5线性递减取值。

3  本文提出的改进量子粒子群算法

3.1  种群熵及其量化测度

Zhang等[14]将种群熵用于对差分进化算法的改进，刘洪达等[15]将种群熵用于对布谷鸟算法改进。种群熵可作为种群内个体多样性的度量方法，对于D维的M个粒子的种群，设解集为xi， j ∈ [xmin， xmax]，其种群熵可按照如下方式进行计算：

1）将[xmin， xmax]划分为N个间隔相等的子区间，Ai = [xmin + （i -1）δ， xmin + iδ]，Nδ = xmax - xmin，i = 1， 2， …， N。

2）统计个体元素属于子区间Ai的个数为Ni，i = 1， 2， …， N。

3）计算个体元素属于子区间Ai的概率估计值为 = Ni / N，i = 1， 2， …， N。

4）把概率的估计值  代入式（6）计算种群熵估计值：

（6）

3.2  偏移中心加权

尽管WQSO加权机制的出发点是加速算法收敛，然而这种加权的加速收敛作用可能使得粒子种群在飞过局部最优点时，加速向局部最优点收敛，因此无法从根本上克服快速收敛和全局寻优的矛盾。

考虑式（1）中| mj - xi， j（t） |项（记为搜索因子Fsq；类似地，WQPSO中的搜索因子记为Fsw）。搜索因子所产生的差分值是保障算法搜索遍历能力的重要因素，其中包含了当前种群粒子与所有当前局部最优粒子的信息交互。

假设粒子种群趋近于局部最优点，当前种群的多样性迅速衰减，粒子种群平均最优与当前局部最优以及当前种群都将非常接近，搜索因子将趋近于0，算法的搜索将因此陷入停滞。

WQPSO算法中由于对平均最优位置做了加权，在粒子多样性没有大幅降低的情况下，相对于QPSO算法，其搜索因子Fsw的遍历性会更大，而随着迭代进行，当粒子多样性大幅降低的情况下，其搜索因子Fsw逐渐趋近于Fsq。可以预见，WQPSO从性能上将比QPSO有一定的提升，但在种群多样性降低的情况下仍无法避免陷入早熟收敛。WQPSO在应对局部最优点较多的多模函数时，其性能提升并不显著，且未能找到全局最优。

基于以上讨论，本文提出改进策略为：

1）动态偏移加权值变化范围的中心点，使搜索因子在整个搜索过程中不会快速趋于0。在进化过程中当粒子逐渐趋于同化时，由于偏移加权的作用，搜索因子不会趋于0值，即使粒子种群飞过局部最优点附近时，也不会被局部最优点所“捕获”。

2）偏移加权值范围中心的幅度大小与当前种群熵值相关联。当粒子多样性水平较高、种群还未形成过度聚集时，采用较小的加权偏移值；当粒子多样性水平较低、种群开始形成聚集，采用较大的加权偏移值，驱动种群扩大搜索范围，使优化搜索不至过早陷入停滞。

3.3  基于种群熵的动态权重偏移

种群熵的理论最大值为ln（D · M），理论最小值为0。将其归一化处理为：

（7）

则归一化种群熵的范围为 。

在算法迭代开始时，粒子种群熵一般较大，采用较小的加权偏移值；随着迭代进行，粒子种群熵不断减小，采用较大的加权值偏移值；种群熵值与加权值偏移幅度采用线性递减关系相关联，以实现上文所述的改进策略。

设加权值的变化范围R，偏移加权范围中心为b，大小与归一化种群熵由式（9）确定：

（8）

从而得到每次迭代过程中的加权范围为：

（9）

为下文讨论方便，本文提出的算法记为PEW-QPSO（Population Entropy Weighted QPSO），算法实现伪代码如下：

Initialize population：

random X[i] and set P[i]=X[i];

Calculate pop fitness f[i]， set fP[i] = f[i]; set gbest = arg min（fP[i]）;

Calculate pop entropy S（1）; Set alpha_max， alpha_min using Eq. （9）;

Sort fP in descending order and set alpha linearly from alpha_max to alpha min;

While iteration number Iter below MaxIter

Do

Iter = Iter +1;

Calculate mbest using Eq. （5）;

fori= 1 to pop size M

If f[i]

g = arg min（fP[i]）;

endif

for j=1 to dimensionality D

φ=rand（0，1）;

p[i][j]=φ*P[i][j]+（1-φ）*P[g][j];

u=rand（0，1）

ifrand（0，1）>0.5

X[i][j]=p[i][j]-β*abs（m[j]-X[i][j]）*ln（1/u）;

else

X[i][j]=p[i][j]+ β*abs（m[j]-X[i][j]）*ln（1/u）；

endif

endfor

endfor

Calculate pop entropy S（Iter）； Set alpha_max， alpha_min using Eq. （9）；

Sort fP in descending order and set alpha linearly from alpha_max to alpha min；

Until iteration number exceed MaxIter

4  測试分析

4.1  测试函数

为了测试改进算法的性能，本文采用表1所示的4种常用的标准测试函数[3]。

4.2  算法设置及测试结果

为了分析算法性能，每个测试函数均在PSO、QPSO、WQPSO和本文提出改进算法作对比。每种函数在问题维度D = 10、D = 20、D = 30的情况下，针对每种算法均运行20次，记录每次的最优适应度值后得到其适应度均值和方差，种群数量取为函数维度的5倍即M = 5D。最大迭代次数设为1 000次。算法基本参数设置，如表2所示。

4.3  结果分析

表3是对4种函数采用4种算法运行20次的最优适应度值的均值和方差统计值，图1、图4是对4种函数分部采用4种算法运行20次相应的平均适应度收敛曲线和归一化种群熵曲线。下面分别进行分析：

1）Quadric函数：Quadric函数是一个受随机噪声影响的单峰函数，从表3和图1结果可知，4种算法均很难收敛，但本文提出的算法搜索速度最快，统计数据比其他3种算法基本优一个数量级以上。

2）Griewank函数：从表3和图2可知，PSO过早陷入局部极小点，QPSO和WQPSO在迭代500次左右时陷入局部极小点，种群熵值趋于也稳定；本文算法虽未找到全局极小点但搜索仍未停滞，所得适应度值优于QPSO和WQPSO一个数量级以上，而且随着问题维度的增加，本文算法的搜索能力并未退化。

3）Rastrigin函数：从表3和图3可知，PSO过早陷入局部极小点，QPSO和WQPSO虽未陷入局部极小点，但收敛速度很慢，本文算法虽基本都能找到全局极小点，显著优于其他3种算法。

4）Alpine函数：从表3和图4可知，QPSO和WQPSO搜索虽未停滞但收敛很慢，PSO在中后期反而优于QPSO和WQPSO，本文算法无论在收敛速度和全局寻优能力方面均表现最好，显著优于其他3种算法。

另外，观察图3、图4中收敛曲线，本文算法在收敛速度下降时有明显的“重启”现象，而且有多个“重启”点，体现了算法能够根据当前种群熵的变化进行了搜索因子的动态调整，印证了本文改进策略设计思想。

5  结  论

本文提的改进算法利用种群熵值作为动态加权反馈参数，结合对平均最优位置的加权中心偏移，能够根据种群熵值变化动态补偿搜索因子的退化，平衡了算法收敛速度和全局寻优的矛盾，在整个搜索迭代过程中保持较强的搜索能力，大大提升了算法的全局寻优能力。针对常用测试函数给出了数值仿真结果，表明该方法能在很大程度上避免了早熟收敛，能够跳出局部最优，极大提高了计算精度和全局寻优能力，优于对比参考的PSO、QPSO和WQPSO等算法。

参考文献：

[1] KENNEDY J，EBERHART R. Particle swarm optimization [C]//Proceedings of ICNN'95 - International Conference on Neural Networks.Perth：IEEE，1995：1942-1948.

[2] VAN DEN BERGH F. An Analysis of Particle Swarm Optimizers [D].Ph.D. Thesis，University of Pretoria，2001.

[3] EBRAHIMI A，DEHDELEH V，BROUMANDNIA A，et al. Improved Particle Swarm Optimization through Orthogonal Experimental Design [C]//2017 2nd Conference on Swarm Intelligence and Evolutionary Computation （CSIEC）.Kerman：IEEE，2017：153-158.

[4] BHAMBU P，KUMAR S，SHARMA K. Self balanced particle swarm optimization [J].International journal of systems assurance engineering and management，2018，9（4）：774-783.

[5] AL-BAHRANI L T，PATRA J C. A novel orthogonal PSO algorithm based on orthogonal diagonalization [J].Swarm and Evolutionary Computation，2018，40：1-23.

[6] KARIM A A，ISA N A M，WEI H L. Hovering Swarm Particle Swarm Optimization [J].IEEE Access，2021，9：115719-115749.

[7] SUN J，FENG B，XU W B. Particle swarm optimization with particles having quantum behavior [C]//Proceedings of the 2004 Congress on Evolutionary Computation .Portland：IEEE，2004：325-331.

[8] PAMPAR? G，ENGELBRECHT A P. Self-adaptive Quantum Particle Swarm Optimization for Dynamic Environments [J].Swarm Intelligence，2018：163–175.

[9] LIU G Q，CHEN W Y，CHEN H D，et al. A Quantum Particle Swarm Optimization Algorithm with Teamwork Evolutionary Strategy [J].Mathematical Problems in Engineering，2019，2019：1-12.

[10] XU L，MUHAMMAD A，PU Y F，et al. Fractional-order quantum particle swarm optimization [J].PLOS ONE，2019，14（6），e0218285.

[11] FLORI A，OULHADJ H，SIARRY P. A new neighborhood topology for quantum particle swarm optimization （QUAPSO） [C]//the Genetic and Evolutionary Computation Conference Companion.2019：255-256.

[12] FALLAHI S，TAGHADOSI M. Quantum-behaved particle swarm optimization based on solitons [J].Scientific Reports，2022，12（1）：13977-13977.

[13] XI M L，SUN J，XU W B. An improved quantum-behaved particle swarm optimization algorithm with weighted mean best position [J].Applied Mathematics and Computation，2008，205（2）：751–759.

[14] ZHANG Y Y，DAI G M，ZUO M C，et al. A population entropy based adaptation strategy for differential evolution [C]//the Genetic and Evolutionary Computation Conference Companion.2019：330-331.

[15] 劉洪达，李德全，王栋.基于种群熵的变步长布谷鸟搜索算法 [J].计算机仿真，2022，39（9）：370-376.

作者简介：周治伟（1979—），男，汉族，安徽阜阳人，工程师，博士，主要研究方向：星载相控阵系统设计、阵列天线波束赋形算法。