一種改進(jìn)的粒子群優(yōu)化算法

胡建華　熊偉利

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

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

文章編號(hào)： 2095-2163（2021）07-0006-07中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)志碼： 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]是一種種群隨機(jī)搜索算法，其靈感來(lái)源于鳥(niǎo)類(lèi)的群集行為。由于PSO算法原理簡(jiǎn)單、易實(shí)現(xiàn)的特點(diǎn)，在眾多領(lǐng)域中有著廣泛的應(yīng)用。但PSO算法也有收斂速度慢和容易陷入局部最優(yōu)等不足。一方面是由于PSO算法對(duì)其控制參數(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ùn)而生。另一方面，所有粒子緊跟最優(yōu)粒子運(yùn)動(dòng)降低了粒子多樣性和全局搜索的能力。經(jīng)典的PSO算法僅關(guān)注于粒子的當(dāng)前速度、當(dāng)前位置、個(gè)體最優(yōu)位置和全局最優(yōu)位置，忽略了粒子的歷史信息和種群的分布狀態(tài)等因素。 2007年，Zhan等人[7]用聚類(lèi)分析方法，分析了搜索過(guò)程中種群分布特性，提出種群進(jìn)化狀態(tài)這一概念。2009年，Zhan等人[8]提出了一種自適應(yīng)PSO算法（APSO），該算法根據(jù)種群實(shí)時(shí)進(jìn)化狀態(tài)來(lái)實(shí)現(xiàn)慣性權(quán)重的自動(dòng)控制，用以提高搜索效率和收斂速度。進(jìn)一步考慮到歷史信息對(duì)粒子當(dāng)前速度的影響，時(shí)延這一概念被引入PSO算法中，SPSO（Tang等人，2011年）[9]、SDPSO（Zeng等人， 2016年）[10]、MDPSO（Song等人，2017年）[11]等變體相繼被提出來(lái)。這些算法有效地平衡了局部搜索和全局搜索能力，提高了粒子的多樣性。2019年，Liu等人[12]引入隨機(jī)分布式時(shí)延，提出RODDPSO算法，該算法充分考慮了歷史個(gè)體最優(yōu)和全局最優(yōu)信息，但卻忽略了不同階段的歷史信息對(duì)當(dāng)前狀態(tài)的影響是不同的。

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

1 PSO算法

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

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

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

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

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

2 改進(jìn)的PSO算法

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

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

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

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

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

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

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

2.3 參數(shù)

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

權(quán)重ω1用來(lái)控制時(shí)延項(xiàng)對(duì)速度的影響， 因?yàn)殡x當(dāng)前狀態(tài)越近的歷史信息對(duì)當(dāng)前狀態(tài)的影響較大，而越遠(yuǎn)的歷史信息對(duì)當(dāng)前狀態(tài)的影響相對(duì)較小，因此ω1為關(guān)于τ的遞減函數(shù)，本文?。?/p>

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

3 仿真實(shí)驗(yàn)

3.1 基準(zhǔn)函數(shù)

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

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

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

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

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

3.3 5種算法的對(duì)比

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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.

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

收稿日期： 2021-03-08