基于種群熵偏移平均加權(quán)的改進(jìn)量子粒子群算法

DOI：10.19850/j.cnki.2096-4706.2024.02.014

收稿日期：2023-05-29

摘? 要：量子粒子群算法具有更好的全局搜索能力，被視為對(duì)粒子群算法極為有效的改進(jìn)，然而其運(yùn)行過程中仍存在種群多樣性衰減問題。為進(jìn)一步提升量子粒子群算法的全局尋優(yōu)能力，在基于加權(quán)平均最優(yōu)位置的量子粒子群算法的基礎(chǔ)上，提出了基于種群熵偏移平均加權(quán)的改進(jìn)量子粒子群算法，將種群熵與加權(quán)范圍中心偏移值進(jìn)行動(dòng)態(tài)關(guān)聯(lián)，有效增強(qiáng)了算法搜索空間的遍歷性，避免了算法早熟收斂。應(yīng)用常規(guī)測(cè)試函數(shù)，與傳統(tǒng)粒子群算法、量子粒子群算法和加權(quán)量子粒子群算法進(jìn)行了對(duì)比分析，證明了文章提出的改進(jìn)算法的有效性。

關(guān)鍵詞：量子粒子群算法；加權(quán)量子粒子群算法；種群熵；偏移平均加權(quán)；測(cè)試函數(shù)

中圖分類號(hào)：TP301；TN95? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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? 引? 言

粒子群優(yōu)化算法（Particle Swarm Optimization， PSO）自1995年由Kennedy等[1]提出以來(lái)，因其建模簡(jiǎn)單、收斂速度快且易于實(shí)現(xiàn)等得到了廣泛的應(yīng)用，但是PSO算法不能全局收斂[2]，因此很多人提出了PSO的改進(jìn)措施[3-6]，努力改善其全局搜索性能。2004年，Sun等[7]將量子特性融合到PSO中，提出了量子粒子群優(yōu)化算法（Quantum-behaved Particle Swarm Optimization， QPSO），增加了迭代過程中的群體多樣性，增強(qiáng)了算法的全局尋優(yōu)能力；然而QPSO仍然存在粒子種群多樣性衰減、搜索能力弱化等問題，因此對(duì)QPSO算法也出現(xiàn)了許多改進(jìn)策略，包括自適應(yīng)調(diào)整量子半徑策略[8]、團(tuán)隊(duì)進(jìn)化策略[9]、基于Grünwald-Letnikov定義的分?jǐn)?shù)微積分策略[10]、粒子鄰域拓?fù)洳呗訹11]、基于孤子波理論的改進(jìn)策略[12]等。

Xi等[13]提出了一種加權(quán)量子粒子群算法（Weighted Quantum-behaved Particle Swarm Optimization， WQPSO），通過對(duì)當(dāng)前粒子最優(yōu)位置按照適應(yīng)度值排序并分別賦予不同加權(quán)值的方法，對(duì)粒子的平均最優(yōu)位置進(jìn)行加權(quán)，從而得到新的粒子平均最優(yōu)位置。

本文受此啟發(fā)，提出了一種改進(jìn)策略，即在算法中對(duì)平均最優(yōu)位置加權(quán)值的范圍中心進(jìn)行偏移，保證算法在迭代中后期保持較強(qiáng)的搜索能力，并結(jié)合種群熵的概念，將種群熵與加權(quán)偏移值進(jìn)行動(dòng)態(tài)關(guān)聯(lián)，實(shí)現(xiàn)算法搜索能力的自適應(yīng)調(diào)節(jié)。

1? 量子粒子群算法

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

（1）

式中pi， j（t）為局部吸引因子，由個(gè)體最優(yōu)位置pi， j（t）和全局最優(yōu)位置pg， j（t）共同決定，其表達(dá)式為：

（2）

mj為粒子群平均最優(yōu)位置：

（3）

（4）

M為種群規(guī)模，D為粒子維數(shù)；φ、u均為（0，1）之間的隨機(jī)數(shù)；β為QPSO算法的收縮擴(kuò)張系數(shù)，用來(lái)控制算法收斂速度，是算法中唯一的控制參數(shù)，一般取1到0.5隨迭代次數(shù)線性遞減。

2? 加權(quán)量子粒子群算法

Xi等[13]認(rèn)為精英粒子在群體演化中應(yīng)該起主導(dǎo)作用，因此在WQPSO中提出根據(jù)當(dāng)前粒子最優(yōu)位置的適應(yīng)度值排序?qū)ζ浞謩e賦予不同的權(quán)重值，賦予精英粒子較大的權(quán)值，賦予弱質(zhì)粒子較小的權(quán)值，然后對(duì)粒子群平均最優(yōu)位置進(jìn)行加權(quán)平均。

WQPSO算法中的平均最優(yōu)位置m（t）的表達(dá)式為：

（5）

其中αi為加權(quán)因子，并且每個(gè)粒子加權(quán)值根據(jù)其適應(yīng)度值升序排序從1.5到0.5線性遞減取值。

3? 本文提出的改進(jìn)量子粒子群算法

3.1? 種群熵及其量化測(cè)度

Zhang等[14]將種群熵用于對(duì)差分進(jìn)化算法的改進(jìn)，劉洪達(dá)等[15]將種群熵用于對(duì)布谷鳥算法改進(jìn)。種群熵可作為種群內(nèi)個(gè)體多樣性的度量方法，對(duì)于D維的M個(gè)粒子的種群，設(shè)解集為xi， j ∈ [xmin， xmax]，其種群熵可按照如下方式進(jìn)行計(jì)算：

1）將[xmin， xmax]劃分為N個(gè)間隔相等的子區(qū)間，Ai = [xmin + （i -1）δ， xmin + iδ]，Nδ = xmax - xmin，i = 1， 2， …， N。

2）統(tǒng)計(jì)個(gè)體元素屬于子區(qū)間Ai的個(gè)數(shù)為Ni，i = 1， 2， …， N。

3）計(jì)算個(gè)體元素屬于子區(qū)間Ai的概率估計(jì)值為 = Ni / N，i = 1， 2， …， N。

4）把概率的估計(jì)值? 代入式（6）計(jì)算種群熵估計(jì)值：

（6）

3.2? 偏移中心加權(quán)

盡管WQSO加權(quán)機(jī)制的出發(fā)點(diǎn)是加速算法收斂，然而這種加權(quán)的加速收斂作用可能使得粒子種群在飛過局部最優(yōu)點(diǎn)時(shí)，加速向局部最優(yōu)點(diǎn)收斂，因此無(wú)法從根本上克服快速收斂和全局尋優(yōu)的矛盾。

考慮式（1）中| mj - xi， j（t） |項(xiàng)（記為搜索因子Fsq；類似地，WQPSO中的搜索因子記為Fsw）。搜索因子所產(chǎn)生的差分值是保障算法搜索遍歷能力的重要因素，其中包含了當(dāng)前種群粒子與所有當(dāng)前局部最優(yōu)粒子的信息交互。

假設(shè)粒子種群趨近于局部最優(yōu)點(diǎn)，當(dāng)前種群的多樣性迅速衰減，粒子種群平均最優(yōu)與當(dāng)前局部最優(yōu)以及當(dāng)前種群都將非常接近，搜索因子將趨近于0，算法的搜索將因此陷入停滯。

WQPSO算法中由于對(duì)平均最優(yōu)位置做了加權(quán)，在粒子多樣性沒有大幅降低的情況下，相對(duì)于QPSO算法，其搜索因子Fsw的遍歷性會(huì)更大，而隨著迭代進(jìn)行，當(dāng)粒子多樣性大幅降低的情況下，其搜索因子Fsw逐漸趨近于Fsq。可以預(yù)見，WQPSO從性能上將比QPSO有一定的提升，但在種群多樣性降低的情況下仍無(wú)法避免陷入早熟收斂。WQPSO在應(yīng)對(duì)局部最優(yōu)點(diǎn)較多的多模函數(shù)時(shí)，其性能提升并不顯著，且未能找到全局最優(yōu)。

基于以上討論，本文提出改進(jìn)策略為：

1）動(dòng)態(tài)偏移加權(quán)值變化范圍的中心點(diǎn)，使搜索因子在整個(gè)搜索過程中不會(huì)快速趨于0。在進(jìn)化過程中當(dāng)粒子逐漸趨于同化時(shí)，由于偏移加權(quán)的作用，搜索因子不會(huì)趨于0值，即使粒子種群飛過局部最優(yōu)點(diǎn)附近時(shí)，也不會(huì)被局部最優(yōu)點(diǎn)所“捕獲”。

2）偏移加權(quán)值范圍中心的幅度大小與當(dāng)前種群熵值相關(guān)聯(lián)。當(dāng)粒子多樣性水平較高、種群還未形成過度聚集時(shí)，采用較小的加權(quán)偏移值；當(dāng)粒子多樣性水平較低、種群開始形成聚集，采用較大的加權(quán)偏移值，驅(qū)動(dòng)種群擴(kuò)大搜索范圍，使優(yōu)化搜索不至過早陷入停滯。

3.3? 基于種群熵的動(dòng)態(tài)權(quán)重偏移

種群熵的理論最大值為ln（D · M），理論最小值為0。將其歸一化處理為：

（7）

則歸一化種群熵的范圍為 。

在算法迭代開始時(shí)，粒子種群熵一般較大，采用較小的加權(quán)偏移值；隨著迭代進(jìn)行，粒子種群熵不斷減小，采用較大的加權(quán)值偏移值；種群熵值與加權(quán)值偏移幅度采用線性遞減關(guān)系相關(guān)聯(lián)，以實(shí)現(xiàn)上文所述的改進(jìn)策略。

設(shè)加權(quán)值的變化范圍R，偏移加權(quán)范圍中心為b，大小與歸一化種群熵由式（9）確定：

（8）

從而得到每次迭代過程中的加權(quán)范圍為：

（9）

為下文討論方便，本文提出的算法記為PEW-QPSO（Population Entropy Weighted QPSO），算法實(shí)現(xiàn)偽代碼如下：

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? 測(cè)試分析

4.1? 測(cè)試函數(shù)

為了測(cè)試改進(jìn)算法的性能，本文采用表1所示的4種常用的標(biāo)準(zhǔn)測(cè)試函數(shù)[3]。

4.2? 算法設(shè)置及測(cè)試結(jié)果

為了分析算法性能，每個(gè)測(cè)試函數(shù)均在PSO、QPSO、WQPSO和本文提出改進(jìn)算法作對(duì)比。每種函數(shù)在問題維度D = 10、D = 20、D = 30的情況下，針對(duì)每種算法均運(yùn)行20次，記錄每次的最優(yōu)適應(yīng)度值后得到其適應(yīng)度均值和方差，種群數(shù)量取為函數(shù)維度的5倍即M = 5D。最大迭代次數(shù)設(shè)為1 000次。算法基本參數(shù)設(shè)置，如表2所示。

4.3? 結(jié)果分析

表3是對(duì)4種函數(shù)采用4種算法運(yùn)行20次的最優(yōu)適應(yīng)度值的均值和方差統(tǒng)計(jì)值，圖1、圖4是對(duì)4種函數(shù)分部采用4種算法運(yùn)行20次相應(yīng)的平均適應(yīng)度收斂曲線和歸一化種群熵曲線。下面分別進(jìn)行分析：

1）Quadric函數(shù)：Quadric函數(shù)是一個(gè)受隨機(jī)噪聲影響的單峰函數(shù)，從表3和圖1結(jié)果可知，4種算法均很難收斂，但本文提出的算法搜索速度最快，統(tǒng)計(jì)數(shù)據(jù)比其他3種算法基本優(yōu)一個(gè)數(shù)量級(jí)以上。

2）Griewank函數(shù)：從表3和圖2可知，PSO過早陷入局部極小點(diǎn)，QPSO和WQPSO在迭代500次左右時(shí)陷入局部極小點(diǎn)，種群熵值趨于也穩(wěn)定；本文算法雖未找到全局極小點(diǎn)但搜索仍未停滯，所得適應(yīng)度值優(yōu)于QPSO和WQPSO一個(gè)數(shù)量級(jí)以上，而且隨著問題維度的增加，本文算法的搜索能力并未退化。

3）Rastrigin函數(shù)：從表3和圖3可知，PSO過早陷入局部極小點(diǎn)，QPSO和WQPSO雖未陷入局部極小點(diǎn)，但收斂速度很慢，本文算法雖基本都能找到全局極小點(diǎn)，顯著優(yōu)于其他3種算法。

4）Alpine函數(shù)：從表3和圖4可知，QPSO和WQPSO搜索雖未停滯但收斂很慢，PSO在中后期反而優(yōu)于QPSO和WQPSO，本文算法無(wú)論在收斂速度和全局尋優(yōu)能力方面均表現(xiàn)最好，顯著優(yōu)于其他3種算法。

另外，觀察圖3、圖4中收斂曲線，本文算法在收斂速度下降時(shí)有明顯的“重啟”現(xiàn)象，而且有多個(gè)“重啟”點(diǎn)，體現(xiàn)了算法能夠根據(jù)當(dāng)前種群熵的變化進(jìn)行了搜索因子的動(dòng)態(tài)調(diào)整，印證了本文改進(jìn)策略設(shè)計(jì)思想。

5? 結(jié)? 論

本文提的改進(jìn)算法利用種群熵值作為動(dòng)態(tài)加權(quán)反饋參數(shù)，結(jié)合對(duì)平均最優(yōu)位置的加權(quán)中心偏移，能夠根據(jù)種群熵值變化動(dòng)態(tài)補(bǔ)償搜索因子的退化，平衡了算法收斂速度和全局尋優(yōu)的矛盾，在整個(gè)搜索迭代過程中保持較強(qiáng)的搜索能力，大大提升了算法的全局尋優(yōu)能力。針對(duì)常用測(cè)試函數(shù)給出了數(shù)值仿真結(jié)果，表明該方法能在很大程度上避免了早熟收斂，能夠跳出局部最優(yōu)，極大提高了計(jì)算精度和全局尋優(yōu)能力，優(yōu)于對(duì)比參考的PSO、QPSO和WQPSO等算法。

參考文獻(xiàn)：

[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，F(xiàn)ENG 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] 劉洪達(dá)，李德全，王棟.基于種群熵的變步長(zhǎng)布谷鳥搜索算法 [J].計(jì)算機(jī)仿真，2022，39（9）：370-376.

作者簡(jiǎn)介：周治偉（1979—），男，漢族，安徽阜陽(yáng)人，工程師，博士，主要研究方向：星載相控陣系統(tǒng)設(shè)計(jì)、陣列天線波束賦形算法。