黃欣 丘剛瑋 唐偉萍

摘要：由于不同等級種群的學(xué)習(xí)能力不一樣，其步長大小也會不一樣，該文提出了一種新的基于距離代價的自適應(yīng)慣性權(quán)重粒子群優(yōu)化算法。該算法在運行過程中根據(jù)粒子位置的距離代價，將種群分為三個等級，對不同等級的種群采用不同的慣性權(quán)重策略更新粒子的速度和位置，并在每次迭代的過程中對全局最優(yōu)加入一個擾動因子來增加粒子的多樣性。通過仿真實驗，將該文提出的PSO算法與其他幾種粒子群優(yōu)化算法進行對比，實驗結(jié)果表明：在相同條件下該算法能以較少的迭代次數(shù)得到最優(yōu)解，同時兼具好的收斂速度和高的收斂精度。

關(guān)鍵詞：粒子群優(yōu)化算法;自適應(yīng)慣性權(quán)重;粒子距離代價;DCAPSO;擾動因子

中圖分類號：TP391 ? ? ? ?文獻標(biāo)識碼：A

文章編號：1009-3044（2022）05-0052-04

1 引言

粒子群優(yōu)化算法[1]（Particle Swarm optimization，PSO）是一經(jīng)典的群智能演化算法，在1995年由Eberhart和Kennedy提出。PSO算法因其快速收斂、易于實現(xiàn)、魯棒性好等優(yōu)勢優(yōu)點，被廣泛研究以及改進。改進的領(lǐng)域有故障檢測[2]、醫(yī)療診斷[3]、科學(xué)管理[4]、飛行器協(xié)調(diào)跟蹤優(yōu)化[5]等。盡管PSO的優(yōu)勢突出，在實際應(yīng)用中逐漸暴露其后期迭代收斂差、容易陷入局部最優(yōu)值且難以跳出、收斂精度低的缺點。越來越多的學(xué)者致力于對PSO進行優(yōu)化改進。Shi等人提出w是極其重要的一項參數(shù)，先后提出隨機權(quán)重（Random Weight，RW）[6]、線性遞減權(quán)重（Linear Decrease Weight，LDW）[7]和模糊慣性權(quán)重[8]這三種策略。以上三種慣性權(quán)重的改進策略，實際上通過自適應(yīng)調(diào)節(jié)慣性權(quán)重的大小，進而控制粒子的局部和全局搜索能力，即慣性權(quán)重越大，該粒子的全局搜索能力越強;慣性權(quán)重越小，粒子的局部搜索能力越大。上述三種策略提高了粒子群的整體性能和收斂速度。文獻[9]分析了對慣性權(quán)重改進的幾種典型策略，如：非線性型函數(shù)、高斯分布型函數(shù)、正弦分布型函數(shù)等。

以上的改進策略在一定程度上提高了PSO算法的性能，但是等級不同的種群學(xué)習(xí)能力不一樣，因此步長大小也會不一樣。上述的改進算法未能解決在不同等級的種群自動調(diào)節(jié)步長大小的問題。為了解決該問題，本文提出了新的PSO算法。該算法采用粒子的距離代價將種群劃分為三個不同的等級，并針對等級不同的粒子采取相應(yīng)的慣性權(quán)值策略來更新粒子當(dāng)前的速度和位置，在每次迭代的過程中對全局最優(yōu)加入一個擾動因子，并融入了“pbest和gbest線性組合”思想使算法在很大程度上克服了收斂慢、易陷入局部等缺點，且獲得了較好的優(yōu)化效果。

2 標(biāo)準(zhǔn)的粒子群優(yōu)化算法

標(biāo)準(zhǔn)的PSO算法是根據(jù)以下公式更新粒子的速度和位置：

vi（t+1）=wvi（t）+c1r1（pbesti（t）-xi（t））+c2r2（gbesti（t）-xi（t）） ? ? ? ? （1）

xi（t+1）=xi（t）+vi（t+1） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

其中，w為慣性權(quán)重;t為當(dāng)前的迭代次數(shù);r1和r2是在隨機數(shù)，隨機范圍為[0，1];c1和c2是學(xué)習(xí)因子;vi（t）為粒子i在t時刻的速度;xi（t）為粒子i在t時刻的位置。

針對基本PSO算法收斂速度緩慢、極易陷入局部最優(yōu)這些缺點，Shi等人分別在文獻[6-7]提出RW、LDW策略，還有研究者提出“非線性型函數(shù)”策略。這三種策略的更新公式分別為：

[ w=0.5+rand（）2] ? ? ? ? ? ? ? ? ? ? ? ?（3）

[w=wmax-t*（wmax-wmin）tMax] ? ? ? ? ? ? ? ? ? ?（4）

[w=wmin+（wmax-wmin）*exp（-25*（ttMax）6）] ? ? ? ? ? ? ? ? ? （5）

以上算法均是從算法本身的收斂特點來對慣性權(quán)重的大小進行調(diào)整，即在算法迭代初期時，粒子群需要較強的全局搜索能力，進行更加全面的全局搜索;在算法搜索后期時，粒子群需要更強的搜索能力，以便使得算法加快收斂。但是，并沒有根據(jù)種群實際搜索情況對種群分等級，并采取不同的搜索策略。

3 基于距離代價的PSO算法

3.1 距離代價

由于不同等級的種群學(xué)習(xí)能力是不一樣的，其步長也是不一樣的。通過對不同等級的種群采用不同的搜索策略，使得等級不同的種群自適應(yīng)調(diào)整步長的大小，更好地適應(yīng)實際的搜索情況，能夠在局部搜索與全局搜索之間進行有效的平衡。我們通過采用“距離代價來”將粒子群劃分成三個不同的種群?！熬嚯x代價”這一概念在2006年提出[10]，它作為最佳聚類數(shù)的有效性檢驗函數(shù)去解決K-means 算法的k值優(yōu)化問題。

根據(jù)粒子群優(yōu)化算法的特點，本文重新構(gòu)造如下的距離代價函數(shù)：

定義1：令avg（xi（t））為粒子i在t時刻所有維度上的平均位置，avg（gbesti（t））為此時全局最優(yōu)在所有維度上的平均位置。定義此時兩者的位置距離為：

L（t）=| avg（xi（t））- avg（gbesti（t）） | ? ? ? ? ? ? ? ? （6）

定義2：令avg（pbest（t））為所有粒子在t時刻個體最優(yōu)的平均位置。定義此時avg（xi（t））與avg（pbest（t））的位置距離為：

D（t）=| avg（xi（t））- avg（pbesti（t）） | ? ? ? ? ? ? （7）

定義3：定義粒子的“距離代價”為L（t）與D（t）相加之和：

F（L，D）= L（t）+D（t） ? ? ? ? ? ? ? ? ?（8）

本文確定了距離代價最小準(zhǔn)則作為衡量粒子的優(yōu)劣性，即：當(dāng)距離代價最小時，粒子所處的位置最優(yōu)。

3.2 自適應(yīng)慣性權(quán)重

慣性權(quán)重w是平衡該算法全局探索能力與局部開發(fā)能力的關(guān)鍵因素。取較大的w時，粒子具有較強的全局搜索能力;反之，具有較強的局部搜索能力。

本文的改進策略如下：在第t次迭代中，用公式（6）（7）（8）計算每個粒子的距離代價Fi（L，D），將距離代價進行升序排序，然后將它們分成兩半分別計算平均值F_avg1和F_avg2，最后將每個粒子的距離代價Fi（L，D）與F_avg1、F_avg2進行比較，從而將粒子群分成三個等級的子群，對不同等級的子群采用以下三種不同的慣性權(quán)重w策略：

Fi（L，D）<F_avg1：此時是較好的粒子，并處于距離gbest或pbest相對較近的位置，此時應(yīng)取較小的慣性權(quán)重wmin。

Fi（L，D）>F_avg2。說明此時該粒子是較差的粒子，并處于距離gbest或pbest相對較遠的位置，此時應(yīng)取較大的wmax。

Fi（L，D）>F_avg1且Fi（L，D）<F_avg2。此時，w在[0.4，0.6]范圍內(nèi)隨機取值。

3.3 DCAPSO算法

均值粒子群優(yōu)化算法（Mean Particle Swarm Optimization，MeanPSO）最初是由Kusum Deep等[11]在2009年提出，使用pbest和gbest的線性組合來修正pbest、gbest，該算法的速度更新公式為：

vi（t+1）=wvi（t）+c1r1（（pbesti（t）+gbesti（t））/2- xi（t）） +c2r2（（pbesti（t）-gbesti（t））/2-xi（t）） ?（9）

綜合上文，本文提出了基于距離代價的自適應(yīng)慣性權(quán)重粒子群優(yōu)化算法（an Adaptive inertial weight Particle Swarm Optimization algorithm based on Distance Cost，DCAPSO）。

算法設(shè)計思路是：通過設(shè)計代價距離函數(shù)，將粒子種群劃分為三個不同等級的子種群，然后子種群根據(jù)他們距離食物不同的位置，采取不同的搜索策略，使其自適應(yīng)選擇不同的慣性權(quán)重，進而自動調(diào)整搜索步長，以達到平衡局部搜索和全局搜索的效果。

DCAPSO的主要技術(shù)要點和操作步驟如下：

Step 1：初始化粒子種群，即初始化gbest0、pbest0、速度v0、位置x0、學(xué)習(xí)因子c、慣性權(quán)重w0;

Step 2：評價每個粒子xi的是適應(yīng)度值f（xi），即計算對應(yīng)的目標(biāo)函數(shù)值;

Step 3：更新pbest——將歷史中的個體位置記錄為{p0，p1，...，pn}，其中適應(yīng)度值最優(yōu)的粒子個體即為pbest;更新gbest——將每一代的個體最優(yōu)記錄為{pbest0，pbest1，...，pbestn}，假設(shè)第i個個體最優(yōu)的適應(yīng)度函數(shù)值最優(yōu)，則pbesti即為gbest;

Step 4：不同的粒子采用3.2不同的w更新策略，粒子根據(jù)三種不用的更新策略，劃分成三個子種群，每個子種群具有不同的功能：第一個子種群處于個體最優(yōu)或者全局最優(yōu)個體的附近，需要對此處進行更加詳細的局部挖掘，因此采用較小的慣性權(quán)重;第二個子種群距離最優(yōu)個體較遠，說明該處有食物的概率較小，需要對該處進行更加詳細的全局搜索，因此使用較大的慣性權(quán)重;第三個子種群處于前兩者之間的位置，需要平衡局部和全局搜索，因此需要適中的慣性權(quán)重;并使用公式（2）（9）更新粒子的速度和位置;

Step 5：對全局最優(yōu)gbest施加一個服從正態(tài)分布的擾動因子gbest=gbest*μ，其中μ=0.5*normrnd（0，1）;

Step 6：判斷是否終止迭代，如果滿足終止條件，則終止迭代，否則返回Step 2。

4 仿真實驗

4.1 測試函數(shù)

為了論證DCAPSO算法的有效性，我們通過五個經(jīng)典的測試函數(shù)對本文的算法進行驗證，并與文獻[6]的隨機慣性權(quán)重（RIW）、文獻[7]線性遞減權(quán)重（LDW）、非線性型函數(shù)權(quán)重策略（EW）、文獻[11] MeanPSO算法進行實驗對比，以觀察它們在相同環(huán)境下性能差異。

實驗環(huán)境如下：Intel（R） Core（TM） i7-10510U CPU @ 1.80GHz ?2.30 GHz，RAM 16.0 GB，64位操作系統(tǒng)，MATLAB 2018a。五種經(jīng)典的測試函數(shù)如表1所示。

4.2 實驗測試和結(jié)果

在本文的實驗中，五種算法的c1和c2 均設(shè)為2;wmin取0.1，wmax取0.9;種群數(shù)取40;最大迭代次數(shù)tMax=300。對于給定的五個測試函數(shù)，每個算法各運行100次，找出在迭代過程中的最差值、最優(yōu)值、平均值。五種算法的實驗數(shù)據(jù)對比結(jié)果如表2～表6所示。

圖1～圖5分別為算法五種算法優(yōu)化測試函數(shù)f1～f5在維數(shù)取30的尋優(yōu)進化曲線，圖中的橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示適應(yīng)度，即每次迭代得到的全局最優(yōu)值（取常用對數(shù)log10）。

從表2～表6和圖1～圖5可得：本文提出的DCAPSO算法在大部分性能上明顯優(yōu)于其他四種算法;而且在維數(shù)增加時，該算法依然比其他四種算法具有更快的收斂速度和收斂精度，魯棒性更好。

5 結(jié)束語

本文提出了DCAPSO算法，該算法采用粒子的距離代價Fi（L，D）與兩個平均距離代價F_avg1、F_avg2的差值作將種群劃分為三個不同的等級，并針對等級不同的粒子采取相應(yīng)的慣性權(quán)值策略來更新粒子當(dāng)前的速度和位置，并在每次迭代的過程中對全局最優(yōu)加入一個服從正態(tài)分布的擾動因子，加入的擾動因子既有利于增加全局最優(yōu)活性，又保持了種群的多樣性，同時融入了MeanPSO的思想。仿真實驗使用5個基準(zhǔn)函數(shù)對比了5種算法，對比證明了本文提出的算法，在優(yōu)化性能上更有優(yōu)勢。具體體現(xiàn)在更少的迭代次數(shù)找到最優(yōu)解，并且擁有更快的收斂速度以及更好的收斂精度。原因在于其在原PSO基礎(chǔ)上加強了全局搜索能力以及后期收斂的微調(diào)能力?？偠灾疚奶岢龅母倪M算法是一種兼具效果和速度的粒子群優(yōu)化算法。研究標(biāo)準(zhǔn)粒子群優(yōu)化算法其他參數(shù)的距離代價對算法的影響是今后的研究內(nèi)容。今后進一步的研究方向?qū)⒓杏诎驯疚奶岢龅膬?yōu)化算法實踐于應(yīng)用中，以期進一步驗證算法的有效性，并發(fā)掘其實際應(yīng)用價值。

參考文獻：

[1] Kennedy J， Eberhart R. Particle swarm optimization[C]//IEEE International Conference on Neural Networks， 1995. Proceedings. IEEE， 2002：1942-1948.

[2] Liu Weixin，Wang Yujia，Liu Xing，et al. Weak thruster fault detection for AUV based on stochastic resonance and wavelet reconstruction[J].Journal of Central South University2016，23（11）：2883-2895.

[3] 張濤，張明輝，李清偉，等.基于粒子群-支持向量機的時間序列分類診斷模型[J].同濟大學(xué)學(xué)報（自然科學(xué)版），2016，44（9）：1450-1457.

[4] 羅淑娟，白思俊，郭云濤.決策者偏好交互項目組合選擇模型及算法優(yōu)化研究[J].西北工業(yè)大學(xué)學(xué)報，2016，34（4）：724-730.

[5] 范成禮，付強，邢清華.基于改進PSO的臨空高速飛行器協(xié)同跟蹤優(yōu)化[J].系統(tǒng)工程與電子技術(shù)，2017，39（3）：476-481.

[6] Eberhart R C， Shi Y. Tracking and optimizing dynamic systems with particle swarms[C]// Evolutionary Computation， 2001.Proceedings of the 2001 Congress on. IEEE， 2002：94-100.

[7] Shi Y， Eberhart R. A modified particle swarm optimizer[C]//IEEE International Conference on Evolutionary Computation Proceedings， 1998. IEEE World Congress on Computational Intelligence. IEEE Xplore， 1999：69-73.

[8] Shi Y， Eberhart R C. Particle swarm optimization with fuzzy adaptive inertia weight[J].Nature， 2001， 212（5061）：511-512.

[9] 周俊，陳璟華，劉國祥，等.粒子群優(yōu)化算法中慣性權(quán)重綜述[J].廣東電力，2013，26（7）：6-12.

[10] 楊善林，李永森，胡笑旋，等.K-MEANS算法中的K值優(yōu)化問題研究[J].系統(tǒng)工程理論與實踐，2006，26（2）：97-101.

[11] Deep K，Bansal J C.Mean particle swarm optimisation for function optimisation[J].International Journal of Computational Intelligence Studies，2009，1（1）：72.

【通聯(lián)編輯：代影】

收稿日期：2021-12-24

基金項目：教育新一代信息技術(shù)創(chuàng)新項目（2020ITA03027）;廣西2020年度中青年教師基礎(chǔ)能力提升項目（2020KY41016）;廣西農(nóng)業(yè)科技自籌經(jīng)費項目（Z2019102）;廣西農(nóng)業(yè)職業(yè)技術(shù)大學(xué)2021年科學(xué)研究與技術(shù)開發(fā)計劃課題（YKJ2124）

作者簡介：黃欣（1983—），男，廣西平南人，副教授，碩士研究生，主要研究方向為計算機網(wǎng)絡(luò)技術(shù);丘剛瑋（1985—），男，廣西賀州人，工程師，學(xué)士，主要研究方向為計算機技術(shù);唐偉萍（1983—），女，廣西玉林人，通信作者，副教授，學(xué)士，主要研究方向為計算機技術(shù)應(yīng)用。