基于分層自主學習的改進粒子群優化算法

袁小平 蔣碩

摘 要：針對粒子群優化（PSO）算法容易陷入局部最優、收斂精度不高、收斂速度較慢的問題，提出一種基于分層自主學習的改進粒子群優化（HCPSO）算法。首先，根據粒子適應度值和迭代次數將種群動態地劃分為三個不同階層;然后，根據不同階層粒子特性，分別采用局部學習模型、標準學習模型以及全局學習模型，增加粒子多樣性，反映出個體差異的認知對算法性能的影響，提高算法的收斂速度和收斂精度;最后，將HCPSO算法與PSO算法、自適應多子群粒子群優化（PSO-SMS）算法以及動態多子群粒子群優化（DMS-PSO）算法分別在6個典型的測試函數上進行對比仿真實驗。仿真結果表明，HCPSO算法的收斂速度和收斂精度相對給出的對比算法均有明顯提升，并且算法執行時間和基本PSO算法執行時間差距在0.001量級內，在不增加算法復雜度的情況下算法性能更高。

關鍵詞：群體智能;粒子群優化算法;粒子差異性;種群多樣性;自主學習

中圖分類號： TP301.6; TP18

文獻標志碼：A

Abstract： Focusing on the shortages of easily falling into local optimal， low convergence accuracy and slow convergence speed in Particle Swarm Optimization （PSO） algorithm， an improved Particle Swarm Optimization based on HierarChical autonomous learning （HCPSO） algorithm was proposed. Firstly， according to the particle fitness value and the number of iterations， the population was dynamically divided into three different classes. Then， according to characteristics of different classes of particles， local learning model， standard learning model and global learning model were respectively adopted to increase particle diversity and reflect the effect of individual difference cognition on performance of algorithm and improve the convergence speed and convergence precision of algorithm. Finally， HCPSO algorithm was compared with PSO algorithm， Self-adaptive Multi-Swarm PSO algorithm （PSO-SMS） and Dynamic Multi-Swarm PSO （DMS-PSO） algorithm on 6 typical test functions respectively. The simulation results show that the convergence speed and convergence accuracy of HCPSO algorithm are obviously higher than these of the given algorithms， and the execution time difference of the proposed algorithm and basic PSO algorithm is within 0.001 orders of magnitude. The performance of the proposed algorithm is improved without increasing complexity.

Key words： group intelligence; Particle Swarm Optimization （PSO） algorithm; particle difference; population diversity; autonomous learning

0 引言

群體智能算法是通過觀察動物群體的捕食、遷徙等活動，進行仿真模擬而產生的智能算法，粒子群優化（Particle Swarm Optimization， PSO）算法是Kennedy等[1]在1995年提出的一種基于種群的智能算法。PSO算法是定義于連續空間的群智能算法，具有參數較少、原理簡單、并行搜索和全局收斂等優點，已經廣泛應用于永磁電機關鍵參數調整[2-3]、人臉識別[4]、分配優化問題[5]等相關領域;但是，PSO算法也存在收斂精度不足、搜索速度較慢以及容易早熟收斂等缺點。針對這些問題，研究人員通過引入相關理論改進學習模型、改變參數調整方式、引入學習算子、算法融合以及多子群等方法對基本算法進行改進研究。文獻[6]引入混沌量子理論改進PSO算法理論模型，結合高效局部搜索機制和自適應動態懲罰方法進行約束處理，提高求解精度，并用之于優化問題中。文獻[7]使用策略協同機制，引入反向學習、高斯變異和柯西分布等概念，改進PSO算法理論模型，提高算法收斂精度。文獻[8]采用自適應慣性權重調整方式，平衡算法的全局和局部搜索能力，提高算法的優化性能，但是慣性權重調整方式對算法的性能提高有限。文獻[9]中提出多慣性權重的調整方式調整慣性權重提高算法的性能，但是算法穩定性較差。文獻[10]改進PSO算法中的學習因子，變化學習因子的取值，提高速度更新和學習過程，并通過實驗驗證取得一定的效果。文獻[11]通過動態速度修改和引入免疫學習算子對算法進行改進，并將改進算法應用于電機參數估計，優化系統參數估計模型取得較好效果。文獻[12]通過模糊高斯學習策略構建精英粒子群進化融合機制，提高種群多樣性與收斂性，增強算法逃離局部最優位置的能力。文獻[13]通過將PSO算法和混合教學算法進行融合互補，彌補算法全局搜索能力不足的問題，取得一定效果，但是將算法復雜化。文獻[14]首次提出多子群策略優化算法性能，為算法改進提供了新思路。文獻[14]首次提出多子群策略優化算法性能，為算法改進提供了新思路。文獻[15]進一步對多子群策略進行研究，提出動態多子群粒子群優化（Dynamic Multi-Swarm Particle Swarm Optimization， DMS-PSO）算法，優化效果較為突出。文獻[16]以自主學習和精英群策略對多子群PSO算法進行改進，提高算法收斂精度，縮短尋優時間。文獻[17]將遺傳算法和多子群算法進行融合，變換子群的更新方式，加強算法在全局搜索和局部搜索之間的平衡能力，提升算法性能，取得一定的效果。文獻[18]將種群分為精英亞群和幾個正常亞群并通過一組基準函數進行測試驗證了算法的收斂速度和全局收斂能力，并應用于永磁同步電機參數估計，取得較好效果。

上述研究中對PSO算法的理論模型、重要參數設置以及算法融合方面的改進都能在一定程度上提高PSO算法的性能，但本質上依然未解決提升PSO算法的收斂精度和搜索速度之間的矛盾問題，多子群策略雖然能夠取得較好的效果，但是依然存在分群過程中粒子數量過多、計算量巨大以及粒子學習過程中學習模式固定、缺乏自主獨立性等問題。

基于此，以分級策略作為切入點，通過類似多子群的方式，提出基于分層自主學習的改進粒子群優化（Particle Swarm Optimization based on HierarChical autonomous learning， HCPSO）算法，對種群進行動態分層，在不增加種群粒子數量的情況下，根據不同階層粒子特性采用不同的學習模型，提高粒子學習的自主性，反映出個體差異和認知對其進化的影響，以中間層實現粒子間的信息交流，隨著算法迭代動態調整粒子學習模型，提高算法性能。

1 基本粒子群算法

基本PSO算法的數學描述如下。

粒子群的初始種群規模設定為N，粒子維數為n維，在t時刻粒子i在解空間的坐標定義為Xti=（xti1，xti2，…，xtin），i=1，2，…，N，其速度大小決定了粒子每次在解空間飛行距離大小，用Vti=（vti1，vti2，…，vtin）表示，則粒子i在時刻t的第j（j=1，2，…，n）維空間中的速度以及位置更新公式如式（1）～（3）所示：

其中：ω為慣性權值;c1和c2為加速因子;r1和r2是在[0，1]區間內的兩個隨機數，粒子在解空間進行搜索的過程中，粒子的速度會被限定在一個最大搜索范圍之內，速度最大值用vmax表示，限定粒子在搜索過程中的范圍，改善算法性能。gbest為全局極值，而pij表示個體極值。

2 HCPSO算法

2.1 HCPSO算法原理

在基本PSO算法中，種群中所有粒子都是單純地按照式（1）和（3）更新，使得種群在收斂時，降低了多樣性，導致算法容易陷入局部最優。有研究表明，在尋優過程中較優粒子會有更大概率靠近最優位置，而較差粒子更偏離最優位置[18]，因此，本文根據粒子適應度值和函數評價次數將種群動態劃分為三個不同階層，對不同階層的粒子采用不同的學習方式。這種分級策略在增加種群多樣性的同時，一定程度上提高了粒子的搜索速度。上層粒子較優，其鄰域內存在更好解的可能性更大，因此對其采用局部學習模型，加強局部范圍搜索能力;中層粒子處于優劣之間，作為整個群體信息交流的橋梁，兼顧全局與局部搜索能力，保留基本學習模型;下層粒子較差，因此讓其以一定概率隨機游走，并采用全局學習模型，增強種群多樣性。

算法迭代初期，種群中大部分粒子距離最優位置較遠，因此使上層粒子較少、下層粒子較多，增強算法全局搜索能力;算法迭代后期，粒子逐漸向最優位置靠攏，需對解空間進行細致搜索，因此增加上級階層粒子，同時減少下級階層粒子，加強算法局部搜索能力，提高收斂速度。隨著算法迭代，各階層粒子的數量變化如圖1所示。

2.2 HCPSO算法具體實現過程

PSO算法優化過程中，設當代全體粒子適應度值大小用集合F={f1， f2，…， fN}表示，其中：N代表粒子總數， fi代表的是第i個粒子適應度值大小。根據適應度值大小對全體粒子進行升序排列（此處適應度值越小代表粒子位置越優），形成新的粒子序列集合X={x1，x2，…，xN}，重新排序后粒子的序號唯一標識粒子的優劣程度，如圖2所示。

由圖2可知，重新排序后，粒子序號越大，表示粒子適應度值越差，因此，將重新排序后的粒子序號作為劃分粒子為不同階層的依據。設定全局最優粒子重新排序后的序號為NXl，low和up分別表示分層的下界和上界，具體更新方式如式（4）和（5）所示：

3.2 實驗設置

實驗硬件環境為Intel Core i5-4258U CPU @ 2.40GHz，內存為8GB，在Matlab 2017a下完成。

為增強可比性，選擇多子群方面的改進算法來進行對比仿真實驗，選取基本PSO算法、DMS-PSO算法、PSO-SMS（Self-adaptive Multi-Swarm PSO）[19]算法與HCPSO算法進行仿真對比實驗，統計適應度誤差均值與標準差，算法各自獨立運行50此處為50次，而3.4節中卻是30次，不一致，是寫錯了，還是我們理解錯了？請明確。回復：那個實驗是兩次實驗，分開的，也可以理解成我重復了兩次實驗，但是第二次實驗獨立運行次數只進行了30次。第一次實驗獨立運行了50次，這個沒有寫錯。次。不同的PSO設置了統一參數。算法參數設置為：ω=0.7296，最大迭代次數T=2000，學習因子c1=c2=2，粒子維數分別取10維和30維，其他對比算法的特定參數選取如參考文獻所述，此處不再贅述。

3.3 算法收斂情況分析

表2給出了4種算法在6個標準測試函數上的粒子平均適應度（Mean）和標準差（Std）的統計對比數據，粒子分別取10維和30維。

由表2中數據可以看出，不管對單峰函數、多峰函數、噪聲函數還是旋轉多峰函數，HCPSO算法相對于基本PSO算法和其他兩種對比算法在收斂精度和穩定性上都有較為明顯的優勢。函數1～3均為單峰函數，由統計數據可以看出，對于函數1～2幾種算法都能取得一定的優化效果，但是HCPSO算法的優化精度明顯更高，穩定性也更好，函數3是相對更為復雜的單峰函數，由表中可以看出其他對比算法優化效果較差，而HCPSO算法依然可以保持較好的優化效果;函數4～6均為多峰函數，由表2中統計數據可以看出，針對多峰函數，HCPSO算法依然有較高的收斂精度，PSO算法很快就陷入局部最優，PSO-SMS算法以及DMS-PSO算法在10維的時候能夠取得一定的優化效果，但是隨著維數增加，其優化效果變得較差，而HCPSO算法隨著維度的增加，收斂精度波動較小，證明HCSPO算法對于高維多峰問題有較好的適應性，對于多峰函數，HCPSO算法收斂精度較高，證明下層粒子按照全局學習模型以及擾動方式更新可以增加粒子多樣性，提高算法前期的全局搜索能力，讓粒子在搜索過程中更容易跳出局部最優位置，找到更好的解;函數7為噪聲函數，由表2中的統計數據可以看出，在10維的時候HCPSO算法的優化效果較好，基本PSO算法的優化效果次之，而PSO-SMS算法和DMS-PSO算法優化效果較差，可以看出HCPSO算法抗干擾能力較好，隨著維度的增加，PSO-SMS算法和DMS-PSO算法的抗干擾能力相對有所提升，但是和HCPSO算法相比依然有較大差距;函數8～9為典型的旋轉多峰函數，由表2中的數據可以看出，不管實在10維還是30維的情況下HCPSO算法相對其他對比算法都有明顯的優勢，特別是對函數9優勢較大。

為了更直觀地表現出算法在迭代過程中的收斂情況，圖4給出了粒子維數取30維的情況下，各算法在不同測試函數上的優化對比曲線，縱坐標是以10為底取對數后的結果。在算法迭代初期，保持下層粒子較多，粒子更容易跳出局部最優位置，找到更好的解，由圖4中（a）、（c）、（e）、（g）和（h）可以看出，算法在迭代過程中有明顯跳出局部最優的過程，證明下層粒子的擾動和更新策略的有效性。上層粒子隨著算法迭代的進行，粒子數逐漸增加，由圖中曲線的變化趨勢可以看出，HCPSO算法的收斂速度對比其他算法有明顯提高，證明上層粒子進行局部搜索能夠在一定程度上加快算法后期收斂，驗證了改進策略的有效性。

3.4 算法復雜度分析

如表3所示，給出了4種算法在6個測試函數上獨立運行30次，平均每次所需的時間（計算機性能對時間影響較大），粒子維數為30維，最大迭代次數為2000。

由表3可以看出，在相同的迭代次數下，基本PSO算法迭代所用時間最短，DMS-PSO算法由于分群原因，其粒子數較多，運行時間相對增加，而PSO-SMS算法雖然分群過程中各子群的粒子較少，但是需要對粒子進行多次重組增加了運行時間，HCSPO算法所需時間對比基本PSO算法差別并不明顯，由此可以看出所提出的改進策略并沒有以消耗運行時間為代價來提高算法的性能。

由基本PSO算法的執行流程可以看出，算法的時間復雜度主要來自于粒子位置初始化以及粒子速度和位置更新部分，其時間復雜度均可以表示為O（N·D）。對2.3節中HCPSO算法偽代碼的描述進行分析，得出算法在運行過程中增加了對粒子所在層級的判斷，需要按照適應度值的大小對粒子進行排序，排序部分時間復雜度表示為O（N2），在粒子維數較小時，維度大小近似和種群規模相同，而實際情況中，粒子維度取值一般比較適中，所以HCPSO算法的時間復雜度近似記為O（N·D），并未在數量級上改變算法的復雜度。

4 結語

本文對PSO算法的原理進行了深入分析研究，針對基本PSO算法易陷入局部最優、收斂精度不高、收斂速度較慢的問題，提出一種基于分層自主學習的改進PSO算法。首次提出類似多子群方式的分層方式，通過對種群進行動態分層，根據不同層級粒子特性采用不同的學習模型，增加粒子多樣性和自主學習能力，讓算法更容易跳出局部最優位置。動態分層方式可以在不增加粒子數的情況下實現類似分群的效果，并且中間層作為通信橋梁避免了粒子信息交流過程中通信周期難以確定的問題。最后通過仿真實驗驗證了改進策略的有效性。然而本文算法存在有待改進之處，例如中級階層粒子數較多，對算法的影響較大，基本學習模型還有進一步改進優化空間，并且將算法在實際問題中進行驗證，將理論應用于實際有待深入討論，這將是下一步需要研究的問題。

參考文獻 （References）

[1] KENNEDY J， EBERHART R. Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway， NJ： IEEE， 1995：1942-1948.

[2] LIU Z H， WEI H L， LI X H， et al. Global identification of electrical and mechanical parameters in PMSM drive based on dynamic self-learning PSO [J]. IEEE Transactions on Power Electronics， 2018， 33（12）： 10858-10871.

[3] LIU Z H， WEI H L， ZHONG Q C， et al. Parameter estimation for VSI-Fed PMSM based on a dynamic PSO with learning strategies [J]. IEEE Transactions on Power Electronics， 2017， 32（4）： 3154-3165.

[4] MISTRY K， ZHANG L， NEOH S C， et al. A micro-GA embedded PSO feature selection approach to intelligent facial emotion recognition [J]. IEEE Transactions on Cybernetics， 2017， 47（6）： 1496-1509.

[5] GHAMRY K A， KAMEL M A， ZHANG Y. Multiple UAVs in forest fire fighting mission using particle swarm optimization[C]// Proceedings of the 2017 International Conference on Unmanned Aircraft Systems. Piscataway， NJ： IEEE， 2017： 1404-1409.

[6] TURGUT O E. Hybrid chaotic quantum behaved particle swarm optimization algorithm for thermal design of plate fin heat exchangers [J]. Applied Mathematical Modelling， 2016， 40（1）：50-69.

[7] 李俊，汪沖，李波，等.基于多策略協同作用的粒子群優化算法[J].計算機應用，2016，36（3）：681-686.（LI J， WANG C， LI B， et al. Particle swarm optimization algorithm based on multi-strategy cooperation [J]. Journal of Computer Applications， 2016， 36（3）：681-686.）

[8] ZHANG L， TANG Y， HUA C， et al. A new particle swarm optimization algorithm with adaptive inertia weight based on Bayesian techniques [J]. Applied Soft Computing， 2015， 28（C）：138-149.

[9] GUPTA I K， CHOUBEY A， CHOUBEY S. Particle swarm optimization with selective multiple inertia weights[C]// Proceedings of the 2017 International Conference on Computing， Communication and Networking Technologies. Washington， DC： IEEE Computer Society， 2017：1-6.

[10] ZHOU Z， JIAO B. The improvement of particle swarm optimization[C]// Proceedings of the 2017 International Conference on Systems and Informatics. Piscataway， NJ： IEEE， 2017： 373-377.

[11] LIU J， MEI Y， LI X. An analysis of the inertia weight parameter for binary particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation， 2016， 20（5）：666-681.

[12] 周偉，羅建軍，靳鍇，等.基于模糊高斯學習策略的粒子群進化融合算法[J].計算機應用，2017，37（9）：2536-2540.（ZHOU W， LUO J J， JIN K， et al. Evolutionary algorithm for particle swarm optimization based on fuzzy Gauss learning strategy [J]. Journal of Computer Applications， 2017， 37（9）：2536-2540.）

[13] WANG H， LI Y. Hybrid teaching-learning-based PSO for trajectory optimization [J]. Electronics Letters， 2017， 53（12）：777-779.

[14] LOVBJERG M， RASMUSSEN T K， KRINK T. Hybrid particle swarm optimiser with breeding and subpopulations[C]// GECCO01： Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. San Francisco： Morgan Kaufmann， 2001：469-476.

[15] LIANG J J， SUGANTHAN P N. Dynamic multi-swarm particle swarm optimizer [C]// Proceedings of the 2005 IEEE International Swarm Intelligence Symposium. Piscataway， NJ： IEEE， 2005：124-129.

[16] 姜海燕，王芳芳，郭小清，等.基于自主學習和精英群的多子群粒子群算法[J].控制與決策，2014，29（11）：2034-2040.（JIANG H Y， WANG F F， GUO X Q， et al. Multi-swarm particle swarm optimization based on autonomic learning and elite swarm [J]. Control and Decision， 2014，29（11）：2034-2040.）

[17] 金敏，魯華祥.一種遺傳算法與粒子群優化的多子群分層混合算法[J].控制理論與應用，2013，30（10）：1231-1238. （JIN M， LU H X. A multi-subgroup hierarchical hybrid of genetic algorithm and particle swarm optimization [J]. Control Theory and Applications， 2013，30（10）：1231-1238.）

[18] 郭文忠.離散粒子群優化算法及其應用[M].北京：清華大學出版社，2012：46-46.（GUO W Z. Discrete Particle Swarm Optimization Algorithm and Its Application [M]. Beijing：Tsinghua University Press， 2012：46-46.）

[19] 曾輝，王倩，夏學文，等.基于自適應多種群的粒子群優化算法[J].計算機工程與應用，2018，54（10）：59-65.（ZENG H， WANG Q， XIA X W， et al. Particle swarm optimization algorithm based on self-adaptive multi-swarm [J]. Computer Engineering and Applications， 2018，54（10）：59-65.）