基于種群熵偏移平均加權的改進量子粒子群算法

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?？梢灶A見，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—），男，漢族，安徽阜陽人，工程師，博士，主要研究方向：星載相控陣系統設計、陣列天線波束賦形算法。