基于距離代價的自適應慣性權重粒子群優化算法

黃欣 丘剛瑋 唐偉萍

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

關鍵詞：粒子群優化算法;自適應慣性權重;粒子距離代價;DCAPSO;擾動因子

中圖分類號：TP391 ? ? ? ?文獻標識碼：A

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

1 引言

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

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

2 標準的粒子群優化算法

標準的PSO算法是根據以下公式更新粒子的速度和位置：

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為慣性權重;t為當前的迭代次數;r1和r2是在隨機數，隨機范圍為[0，1];c1和c2是學習因子;vi（t）為粒子i在t時刻的速度;xi（t）為粒子i在t時刻的位置。

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

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

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

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

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

3 基于距離代價的PSO算法

3.1 距離代價

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

根據粒子群優化算法的特點，本文重新構造如下的距離代價函數：

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

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

定義2：令avg（pbest（t））為所有粒子在t時刻個體最優的平均位置。定義此時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）

本文確定了距離代價最小準則作為衡量粒子的優劣性，即：當距離代價最小時，粒子所處的位置最優。

3.2 自適應慣性權重

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

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

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

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

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

3.3 DCAPSO算法

均值粒子群優化算法（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）

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

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

DCAPSO的主要技術要點和操作步驟如下：

Step 1：初始化粒子種群，即初始化gbest0、pbest0、速度v0、位置x0、學習因子c、慣性權重w0;

Step 2：評價每個粒子xi的是適應度值f（xi），即計算對應的目標函數值;

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

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

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

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

4 仿真實驗

4.1 測試函數

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

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

4.2 實驗測試和結果

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

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

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

5 結束語

本文提出了DCAPSO算法，該算法采用粒子的距離代價Fi（L，D）與兩個平均距離代價F_avg1、F_avg2的差值作將種群劃分為三個不同的等級，并針對等級不同的粒子采取相應的慣性權值策略來更新粒子當前的速度和位置，并在每次迭代的過程中對全局最優加入一個服從正態分布的擾動因子，加入的擾動因子既有利于增加全局最優活性，又保持了種群的多樣性，同時融入了MeanPSO的思想。仿真實驗使用5個基準函數對比了5種算法，對比證明了本文提出的算法，在優化性能上更有優勢。具體體現在更少的迭代次數找到最優解，并且擁有更快的收斂速度以及更好的收斂精度。原因在于其在原PSO基礎上加強了全局搜索能力以及后期收斂的微調能力。總而言之，本文提出的改進算法是一種兼具效果和速度的粒子群優化算法。研究標準粒子群優化算法其他參數的距離代價對算法的影響是今后的研究內容。今后進一步的研究方向將集中于把本文提出的優化算法實踐于應用中，以期進一步驗證算法的有效性，并發掘其實際應用價值。

參考文獻：

[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].同濟大學學報（自然科學版），2016，44（9）：1450-1457.

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

[5] 范成禮，付強，邢清華.基于改進PSO的臨空高速飛行器協同跟蹤優化[J].系統工程與電子技術，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] 周俊，陳璟華，劉國祥，等.粒子群優化算法中慣性權重綜述[J].廣東電力，2013，26（7）：6-12.

[10] 楊善林，李永森，胡笑旋，等.K-MEANS算法中的K值優化問題研究[J].系統工程理論與實踐，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.

【通聯編輯：代影】

收稿日期：2021-12-24

基金項目：教育新一代信息技術創新項目（2020ITA03027）;廣西2020年度中青年教師基礎能力提升項目（2020KY41016）;廣西農業科技自籌經費項目（Z2019102）;廣西農業職業技術大學2021年科學研究與技術開發計劃課題（YKJ2124）

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