一種改進的粒子群優化算法

胡建華　熊偉利

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

關鍵詞： 分布式時延; 進化因子; 權重; 粒子群優化

文章編號： 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 引 言

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

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

1 PSO算法

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

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

其中，ωmax（ωmin）表示在尋優過程中慣性權重的最大（最小）值; iter（max iter）表示當前（最大）的迭代次數。

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

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

2 改進的PSO算法

2.1 進化狀態的判斷

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

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

稱為種群的進化因子，式（6）表明進化因子能恰當刻畫種群的分布狀態，根據進化因子Ef的大小不同而取不同狀態[9]：

2.2 新算法的構建

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

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

2.3 參數

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

權重ω1用來控制時延項對速度的影響， 因為離當前狀態越近的歷史信息對當前狀態的影響較大，而越遠的歷史信息對當前狀態的影響相對較小，因此ω1為關于τ的遞減函數，本文取：

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

3 仿真實驗

3.1 基準函數

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

3.2 參數N的訓練

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

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

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

3.3 5種算法的對比

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

4 結束語

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

參考文獻

[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-），女，博士，講師，主要研究方向：大數據;? 熊偉利（1994-），女，碩士研究生，主要研究方向：大數據。

收稿日期： 2021-03-08