胡建華　熊偉利

摘 要： 粒子群優(yōu)化算法（PSO）是一種群體智能進化計算方法，但在搜索過程中粒子緊跟最優(yōu)粒子運動降低了粒子多樣性和全局搜索能力，從而易陷入局部極值。本文提出一種新的粒子群優(yōu)化算法（PSO-EWD），主要改進體現(xiàn)在2個方面：將慣性權(quán)重與進化因子相關(guān)聯(lián)，根據(jù)種群的進化狀態(tài)而改變權(quán)重大小，以平衡全局搜索能力與局部搜索能力;將時變的分布式時延引入速度更新公式中，以增加粒子的多樣性。本文通過5種算法在9個基準函數(shù)上的實驗對比，證明了新提出的算法相較于另外4種算法具有更優(yōu)的適應(yīng)度值、穩(wěn)定性和收斂速度。

關(guān)鍵詞： 分布式時延; 進化因子; 權(quán)重; 粒子群優(yōu)化

文章編號： 2095-2163（2021）07-0006-07中圖分類號：TP301文獻標志碼： A

An improved Particle Swarm Optimization algorithm

HU Jianhua， XIONG Weili

（College of Science， University of Shanghai for Science and Technology， Shanghai 200093， China）

【Abstract】Particle Swarm Optimization algorithm （PSO） is a kind of evolutionary calculation method with swarm intelligence. In the search process， all particles closely follow the optimal particle's movement， which reduces the particles' diversity and global search ability. So it is easy to fall into local optima. In this paper， a new swarm optimization algorithm （PSO-EWD） has been proposed which is mainly improved in two aspects： the inertia weight is associated with the evolution factor， and the weight is changed according to the evolution state of the population to balance the global search ability and the local search ability; the distributed time-varying delays are introduced into the velocity update formula to increase diversity of the particles. In this paper， the experimental comparison of five algorithms on nine benchmark functions shows that the proposed algorithm has better fitness value， stability and convergence speed than the other four algorithms.

【Key words】distributed time-delay; evolutionary factor; weight; Particle Swarm Optimization （PSO）

0 引 言

粒子群優(yōu)化算法（PSO）[1]是一種種群隨機搜索算法，其靈感來源于鳥類的群集行為。由于PSO算法原理簡單、易實現(xiàn)的特點，在眾多領(lǐng)域中有著廣泛的應(yīng)用。但PSO算法也有收斂速度慢和容易陷入局部最優(yōu)等不足。一方面是由于PSO算法對其控制參數(shù)相當(dāng)敏感，合理的參數(shù)配置才能提高算法的性能， PSO-LDIW（Shi和Eberhart ，1998年、1999年）[2-4]、PSO-CK（Clerc和Kennedy， 2002年）[5]、PSO-TVAC（Ratnaweera，2004年）[6]等算法應(yīng)運而生。另一方面，所有粒子緊跟最優(yōu)粒子運動降低了粒子多樣性和全局搜索的能力。經(jīng)典的PSO算法僅關(guān)注于粒子的當(dāng)前速度、當(dāng)前位置、個體最優(yōu)位置和全局最優(yōu)位置，忽略了粒子的歷史信息和種群的分布狀態(tài)等因素。 2007年，Zhan等人[7]用聚類分析方法，分析了搜索過程中種群分布特性，提出種群進化狀態(tài)這一概念。2009年，Zhan等人[8]提出了一種自適應(yīng)PSO算法（APSO），該算法根據(jù)種群實時進化狀態(tài)來實現(xiàn)慣性權(quán)重的自動控制，用以提高搜索效率和收斂速度。進一步考慮到歷史信息對粒子當(dāng)前速度的影響，時延這一概念被引入PSO算法中，SPSO（Tang等人，2011年）[9]、SDPSO（Zeng等人， 2016年）[10]、MDPSO（Song等人，2017年）[11]等變體相繼被提出來。這些算法有效地平衡了局部搜索和全局搜索能力，提高了粒子的多樣性。2019年，Liu等人[12]引入隨機分布式時延，提出RODDPSO算法，該算法充分考慮了歷史個體最優(yōu)和全局最優(yōu)信息，但卻忽略了不同階段的歷史信息對當(dāng)前狀態(tài)的影響是不同的。

在此基礎(chǔ)上，本文綜合考慮了種群的進化狀態(tài)和不同階段時延的影響效果，提出了一種改進的PSO算法（PSO-EWD）。該次研究的創(chuàng)新點在于：將慣性權(quán)重與進化因子相關(guān)聯(lián)，根據(jù)種群的進化狀態(tài)而改變權(quán)重大小，使全局搜索能力與局部搜索能力得到平衡;將時變的分布式時延引入速度更新公式中，以增加粒子的多樣性。

1 PSO算法

假設(shè)S為種群粒子數(shù)，I={1，2，3，…，S}， D代表搜索空間的維數(shù)，則第i個粒子的速度用Vi表示，位置用Xi表示，其中Xi，Vi∈RD， i∈I。設(shè)第k次迭代后第i個粒子的速度為Vi（k）=（Vi1（k），Vi2（k）， …，ViD（k））位置為Xi（k）=（Xi1（k）， Xi2（k），…，XiD（k））。原始的PSO算法在尋找最優(yōu)解的過程中所有粒子都緊跟個體最優(yōu)粒子和全局最優(yōu)粒子，向著全局最優(yōu)位置移動，記第i個粒子的最優(yōu)位置為Pi=（Pi1，Pi2，…，PiD），全局最優(yōu)粒子的位置為PG=（PG1，PG2，…，PGD。更新迭代公式是：

其中，k是當(dāng)前迭代次數(shù);ri（i=1，2）是D維向量，向量中每一個分量都是[0，1]上的隨機數(shù);ω為慣性權(quán)重;c1是個體認知加速度系數(shù);c2是社會加速度系數(shù)。

其中，ωmax（ωmin）表示在尋優(yōu)過程中慣性權(quán)重的最大（最?。┲? iter（max iter）表示當(dāng)前（最大）的迭代次數(shù)。

2002年，Clerc和Kennedy指出當(dāng)ω=0.729， c1=c2=1.49時算法效果較好[13]（PSO-CK算法）。2004年，受時變慣性權(quán)重的啟發(fā)， Ratnaweera等人提出了PSO-TVAC 算法[14]，將加速度因子改進為：

其中，c1i（c1f）和c2i（c2f）分別是個體認知加速度系數(shù)和社會加速度系數(shù)的初值（終值），這些參數(shù)的取值為：c1i=2.5， c1f=0.5， c2i=0.5， c2f=2.5。

2 改進的PSO算法

2.1 進化狀態(tài)的判斷

2009年，Zhan等人[8]通過分析種群的搜索行為和分布特性提出了進化狀態(tài)，整個搜索過程種群表現(xiàn)出4種狀態(tài)：收斂狀態(tài)、開發(fā)狀態(tài)、勘探狀態(tài)和跳出狀態(tài)，分別用ξ=1，2，3，4表示。用di表示第i個粒子與其他所有粒子的平均距離，即：

記dmin， dmax是集合{di|i∈I}中的最小值和最大值，用G表示全局最優(yōu)粒子，顯然dmin≤dG≤dmax。令：

稱為種群的進化因子，式（6）表明進化因子能恰當(dāng)刻畫種群的分布狀態(tài)，根據(jù)進化因子Ef的大小不同而取不同狀態(tài)[9]：

2.2 新算法的構(gòu)建

經(jīng)典的PSO算法開始搜索時速度很快，但在搜索過程中，所有的粒子都向著當(dāng)前最優(yōu)粒子的方向?qū)ふ遥@使粒子失去了多樣性，在搜索后期收斂速度明顯下降，并且容易陷入局部最優(yōu)。本文通過考慮不同階段的歷史信息對現(xiàn)在的影響，引入具有時變性的分布式時延，以增加粒子的多樣性;同時將慣性權(quán)重與進化因子相關(guān)聯(lián)，來平衡算法的全局搜索和局部搜索的能力。改進后的PSO-EWD算法的迭代公式為：

其中，ω（Ef）是和進化因子Ef相關(guān)的慣性權(quán)重，r3，r4是如同r1，r2的D維隨機向量;α（τ）為隨機數(shù)0或者1;ω1是時延發(fā)生時的自適應(yīng)權(quán)重，決定了每個時延影響的大小; ∑Nτ=1ω1α（τ）（Pi（k-τ）-Xi（k））， ∑Nτ=1ω1α（τ）（PG（k-τ）-Xi（k））分別是關(guān)于自我認知和社會的分布式時延項，這里的τ是時延步數(shù)，N為分布式時延步數(shù)最大值; 約定當(dāng)τ≥k時，Pi（k-τ）=Pi（k）， PG（k-τ）=PG（k）; ξ（k）是第k次迭代時種群的當(dāng)前的狀態(tài);c3和c4是分布式時延項的加速度因子;ml（ξ（k））和mG（ξ（k））是分布式時延項的強度因子，兩者都是根據(jù)進化狀態(tài)ξ（k）所確定的。

2.3 參數(shù)

慣性權(quán)重ω用來平衡算法的全局搜索能力和局部搜索能力，PSO-EWD算法將ω與進化因子Ef相聯(lián)系，以適應(yīng)于搜索環(huán)境。因為相對較小的ω有利于種群收斂和開發(fā)，相對較大的ω有利于種群勘探和跳出，而進化因子在跳出狀態(tài)時相對較大而收斂狀態(tài)時相對較小，本文取ω（Ef）的初值為0.9，計算公式為：

權(quán)重ω1用來控制時延項對速度的影響， 因為離當(dāng)前狀態(tài)越近的歷史信息對當(dāng)前狀態(tài)的影響較大，而越遠的歷史信息對當(dāng)前狀態(tài)的影響相對較小，因此ω1為關(guān)于τ的遞減函數(shù)，本文取：

取分布式時延項的加速度因子c3=c1， c4=c2;強度因子ml（ξ）、mG（ξ）根據(jù)進化狀態(tài)ξ 來確定（見表1），其初始值ml（ξ）、mG（ξ）都取為0，在k次迭代后，若種群的進化狀態(tài)為收斂時，粒子將緊跟當(dāng)前找到的全局最優(yōu)粒子快速聚集，忽略時延項的影響而取ml（1）=mG（1）=0;在開發(fā)狀態(tài)時，粒子將利用個體最優(yōu)歷史信息在潛在區(qū)域仔細搜索，而忽略全局最優(yōu)信息的影響，取ml（2）=-0.01， mG（2）=0。在勘探狀態(tài)時，探索全局最優(yōu)解是重要任務(wù)，鼓勵粒子在全局歷史最優(yōu)信息的指導(dǎo)下探索整個搜索空間，取ml（3）=0， mG（3）=0.01;在跳出狀態(tài)時，粒子群將跟隨全局最優(yōu)粒子飛離局部極值周圍區(qū)域，去尋求一個更好的解，個體和全局的歷史最優(yōu)位置都需要綜合考慮，取ml（4）=0.01， mG（4）=0.01。

3 仿真實驗

3.1 基準函數(shù)

本文選取9個常見的基準函數(shù)來驗證算法的性能，其中包括單峰函數(shù)、多峰函數(shù)。研究中選擇的函數(shù)、名字、搜索空間等具體信息見表2。

3.2 參數(shù)N的訓(xùn)練

在搜索空間隨機選取20個種群，所有粒子均具有隨機的初始速度Vi（i∈I）和位置Xi（i∈I），計算出每個粒子的適應(yīng)度值，選出初始個體最優(yōu)粒子位置Pi和全局最優(yōu)粒子位置PG。為驗證PSO-EWD算法在處理復(fù)雜問題時的優(yōu)越性，本文選定搜索空間的維數(shù)為100維，最大迭代次數(shù)為20 000次，同時為消除隨機因素的影響，每個實驗重復(fù)40次，最后取平均值。

在PSO-EWD算法的速度更新公式中，分布式時延步數(shù)的最大值N是個訓(xùn)練參數(shù)，由實驗訓(xùn)練所確定。過大的N會增加計算負擔(dān)，過小的N不能充分發(fā)揮時延的作用，本文將在75、100、125、150、175五個數(shù)中選取一個使PSO-EWD算法性能較好的N。實驗結(jié)果如圖1所示，縱坐標表示平均適應(yīng)度值的對數(shù)，橫坐標表示迭代次數(shù)。

由圖1可看出，在5個不同N的取值中，當(dāng)N=125時函數(shù)f2（x），f3（x），f4（x），f6（x）以及f7（x）有最優(yōu)的適應(yīng)度值和相對快的收斂速度;雖然函數(shù)f1（x），f5（x），f8（x），f9（x）沒有最優(yōu)適應(yīng)度值，但有更早的收斂趨勢。因此本文選取最大時延步數(shù)N=125。

3.3 5種算法的對比

本文選取PSO-CK、PSO-LDIW、MDPSO、RODDPSO四種算法來對比驗證PSO-EWD算法的優(yōu)越性。仿真實驗結(jié)果如圖2所示。圖2表現(xiàn)了5種算法在100維搜索空間中的收斂性能，對于9個基準函數(shù)來說，PSO-EWD算法以更快速度收斂于最優(yōu)的適應(yīng)度值。5種算法在100D的搜索空間中的性能比較見表3。由表3可知，從最小值、均值、方差三個評價指標來對比5種算法。從表3中可以看出，PSO-EWD算法在9個基準函數(shù)上都有最小的適應(yīng)度均值，這說明PSO-EWD算法有較好的尋優(yōu)質(zhì)量和收斂精度。從方差來看，PSO-EWD算法僅在f5（x）上次于RODDPSO算法，這說明PSO-EWD算法具有較好的穩(wěn)定性。就最小值而言，PSO-EWD算法僅在f6（x）、f7（x）上次于RODDPSO算法，這說明PSO-EWD有較好的跳出局部極值、尋找全局最優(yōu)解的能力。進一步仔細比較，算法性能表現(xiàn)次優(yōu)的是RODDPSO算法，這說明引入了分布式時延的2種算法由于充分考慮了歷史個體最優(yōu)信息和全局最優(yōu)信息而更能增加粒子的多樣性，增強跳出局部最優(yōu)的能力。而采用與進化狀態(tài)關(guān)聯(lián)的慣性權(quán)重和具有時變性的時延的PSO-EWD算法更能平衡全局搜索能力和局部搜索能力，從而提升了收斂精度。

4 結(jié)束語

本文考慮到所有粒子緊跟最優(yōu)粒子運動降低了粒子多樣性和全局搜索能力，提出了一種新的分布式權(quán)重粒子群優(yōu)化算法（PSO-EWD）。通過考慮不同階段的歷史信息對當(dāng)前速度的影響，引入具有時變性的分布式時延，以增加粒子的多樣性;同時，將慣性權(quán)重與進化因子相關(guān)聯(lián)，來平衡算法的全局搜索和局部搜索的能力。實驗在100維的搜索空間中迭代20 000次，并且為了減少隨機因素的影響實驗重復(fù)40次而取平均值。新算法在9個基準函數(shù)上與4種經(jīng)典的PSO算法對比，實驗結(jié)果證明PSO-EWD算法具有更優(yōu)的穩(wěn)定性、收斂速度與適應(yīng)度值。

參考文獻

[1]EBERHART R， KENNEDY J. A new optimizer using particle swarm theory [C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science.Nagoya， Japan：IEEE， 1995： 39-43.

[2]SHI Y， EBERHART R C. Parameter selection in particle swarm optimization [C]//Proceedings of the 7th International. Conference on Evolutionary Programming. San Diego， CA， USA：IEEE， 1998： 591-600.

[3]SHI Y， EBERHART R C. A modified particle swarm optimizer [C]//Proceedings of IEEE International Conference on Evolutionary Computation. Anchorage， AK：IEEE， 1998： 69-73.

[4]SHI Yuhui， EBERHART R C. Empirical study of particle swarm optimization [C]// Proceedings of the 1999 Congress on Evolutionary Computation.Washington DC， USA：IEEE， 1999， 3：1945-1950.

[5]CLERC M， KENNEDY J. The particle swarm：Explosion，stability，and convergence in a multidimensional complex space [J].IEEE Transactions on Evolutionary Computation， 2002， 6（1）： 58-73.

[6]RATNAWEERA A， HALAAMUGE S， WATSON H C. Self organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J]. IEEE Transactions on Evolutionary Computation， 2004，8（3）： 240-255.

[7]ZHAN Zhihui， XIAO Jing， ZHANG Jun， et al. Adaptive control of acceleration coefficients for particle swarm optimization based on clustering analysis [C]//2007 IEEE Congress on Evolutionary Computation. Singapore：IEEE， 2007：3276-3282.

[8]ZHAN Zhihui， ZHANG Jun， LI Yun， et al. Adaptive particle swarm optimization [J]. IEEE Transactions on systems， Man， and Cybernetics，Part B（Cybernetics）， 2009， 39（6）： 1362-1381.

[9]TANG Y， WANG Z， FANG J. Parameters identification of unknow delayed genetic regulatory networks by a switching particle swarm optimization algorithm [J]. Expert Systems with Applications， 2011， 38（3）： 2523-2535.

[10]ZENG Nianyin， WANG Zidong， ZHANG Hong， et al. A novel switching delayed PSO algorithm for estimating unknown parameters of lateral flow immunoassay [J]. Cognitive Computation， 2016， 8（2）： 143-152.

[11]SONG Baoye， WANG Zidong， ZOU Lei. On global smooth path planning for mobile robots using a novel multimodal delayed PSO algorithm [J]. Cognitive Computation，2017， 9（1）： 5-17.

[12]LIU Weibo， WANG Zidong， LIU Xiaohui. A novel particle swarm optimization approach for patient clustering from emergency departments [J]. IEEE Transactions on Evolutionary Computation， 2019， 23（4）： 632-644.

[13]CLERK M， KENNEDY J.The particle swarm：explosion，stability，and convergence in a multidimensional complex space [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（1）： 58-73.

[14]RATNAWEERA A， HALAAMUGE S， WATSON HC. Self organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J]. IEEE Transactions on Evolutionary Computation， 2004，8（3）： 240-255.

作者簡介： 胡建華（1978-），女，博士，講師，主要研究方向：大數(shù)據(jù);? 熊偉利（1994-），女，碩士研究生，主要研究方向：大數(shù)據(jù)。

收稿日期： 2021-03-08