基于分層自主學習的改進粒子群優(yōu)化算法

袁小平 蔣碩

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

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

中圖分類號： 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 引言

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

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

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

1 基本粒子群算法

基本PSO算法的數(shù)學描述如下。

粒子群的初始種群規(guī)模設定為N，粒子維數(shù)為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]區(qū)間內的兩個隨機數(shù)，粒子在解空間進行搜索的過程中，粒子的速度會被限定在一個最大搜索范圍之內，速度最大值用vmax表示，限定粒子在搜索過程中的范圍，改善算法性能。gbest為全局極值，而pij表示個體極值。

2 HCPSO算法

2.1 HCPSO算法原理

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

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

2.2 HCPSO算法具體實現(xiàn)過程

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

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

3.2 實驗設置

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

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

3.3 算法收斂情況分析

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

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

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

3.4 算法復雜度分析

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

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

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

4 結語

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

參考文獻 （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] 李俊，汪沖，李波，等.基于多策略協(xié)同作用的粒子群優(yōu)化算法[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] 金敏，魯華祥.一種遺傳算法與粒子群優(yōu)化的多子群分層混合算法[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] 郭文忠.離散粒子群優(yōu)化算法及其應用[M].北京：清華大學出版社，2012：46-46.（GUO W Z. Discrete Particle Swarm Optimization Algorithm and Its Application [M]. Beijing：Tsinghua University Press， 2012：46-46.）

[19] 曾輝，王倩，夏學文，等.基于自適應多種群的粒子群優(yōu)化算法[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.）