基于健康度的自適應過濾粒子群算法*

袁 羅，葛洪偉+，姜道銀

1.輕工過程先進控制教育部重點實驗室（江南大學），江蘇 無錫 214122

2.江南大學 物聯網工程學院，江蘇 無錫 214122

1 引言

粒子群優化（particle swarm optimization，PSO）算法是一種基于迭代的優化方法[1]，它源于對鳥群和魚群群體覓食運動行為的模擬，是一類新興的基于群智能的隨機優化算法，較其他的進化算法相比，易于實現且參數較少，已在科學和工程領域得到了廣泛的應用。然而，基本PSO算法在實現中存在一些不足，如難以跳出局部最優和收斂速度慢等。近些年來，許多學者在優化算法性能上做出的貢獻有：（1）在PSO算法中引入慣性權重[2-3]，增加收斂因子[4]，修正學習因子[5]等，以平衡粒子群的全局探索和局部搜索能力。（2）在PSO混合策略上，如將GA（genetic algoritim）中選擇、變異和交叉的思想融入PSO算法[6-7]，PSO和DE（differential evolution）融合[8]，PSO與其他的一些局部和全局收縮技術都有一定程度的融合，如蟻群算法、單純形算法和模糊邏輯算法等。（3）避免種群陷入局部最優，如引入自適應變異機制[9-13]、交叉機制[14]等方法。但總體而言，這些算法仍然存在易陷入局部最優和收斂速度慢等缺陷。

為彌補PSO算法難以跳出局部最優和收斂速度慢等不足，本文提出了基于健康度[15]的自適應過濾粒子群算法（PSO algorithm with adaptive filter based on health degree，HAFPSO）。該算法通過計算粒子健康度區分粒子狀態，處理并標記異常粒子，當該粒子被處理次數超過一定閾值而仍沒有逼近最優解趨勢時，自適應過濾該粒子位置，重新生成新的位置；同時，利用引導因子更新全局最差粒子值，過濾異常粒子數，避免無效搜索，提高算法的收斂速度。實驗表明，本文算法能夠顯著提高收斂速度和性能。

2 基于健康度的自適應過濾粒子群算法

2.1 標準粒子群算法

標準PSO算法通過模擬鳥群飛行中的覓食行為，把鳥類個體看作隨機的粒子，通過局部和全局最優來引導粒子飛向最優解。粒子根據自己在解空間中的飛行經驗以及粒子群體的飛行狀況動態更新自己的速度和位置。其所經歷的最優位置即個體歷史最優位置記為pi=(pi1,pi2,…,piD)，其中所有粒子經歷過的最優位置即全局最優位置記為pg=[pg1,pg2,…,pgD]。粒子的位置和速度更新公式分別為：

其中，w為慣性權值；c1和c2是加速系數；r1和r2均為[0,1]之間的隨機數。

2.2 HAFPSO算法

2.2.1 健康度

文獻[15]提出健康度概念：在每一次迭代進程中，都會記錄當前的粒子振蕩數NOSC和停滯數NS，如果粒子在每一次迭代中越來越接近最優解，則粒子健康度上升，否則下降。當粒子的健康度低于設定的門限值時，粒子則被判定為異常粒子。粒子健康度計算公式如下：

其中，WS和WOSC分別是粒子的停滯次數和振蕩次數的權值系數。

2.2.2 自適應過濾機制

定義1Limit為一個調節變量，用于衡量異常粒子是否需要自適應過濾處理：

其中，β取值[0,2]；M為最大迭代次數，本文設為2 000；t為當前迭代次數；D為粒子的維度。顯然，隨著迭代次數的增加，Limit值也在增加，能夠更加準確地識別懶惰粒子，從而對懶惰粒子進行救治，避免無效搜索，加快算法收斂速度。

定義2懶惰粒子L定義為：

準確地確定懶惰粒子是關鍵。根據定義1，調節變量Limit用于確定是否對異常粒子進行自適應過濾處理。當異常粒子被處理次數超過Limit值而仍沒有逼近最優解的趨勢時，即被視為懶惰粒子。在鎖定懶惰粒子后，立刻重新生成一個新的位置，更新公式如下：

其中，pg為第i個粒子的全局最優位置；xi為第i個粒子的位置。

定義3引導因子q為每輪迭代中最接近最優解的粒子，q滿足條件：

其中，xi代表粒子的位置；cosθ計算方式為：

粒子運動軌跡如圖1所示，粒子在運動過程中，如果連續兩代都朝著同一方向，則可以判斷為粒子的運動軌跡存在朝著最優解方向運動的趨勢。隨著迭代次數的增加，如果粒子運動軌跡重復這種狀態，即可以判斷該粒子在朝著最優解方向運動。如果迭代后期出現粒子當前迭代與上一次迭代運行方向相異時，則在當前迭代中該粒子不滿足引導因子的條件，直接利用傳統方法更新該粒子速度和位置。

Fig.1 Particle trajectory圖1 粒子軌跡圖

在收斂的情況下，因為所有的粒子都向最優解的方向運動，所以粒子趨向同一化，失去了多樣性，使得后期收斂速度明顯變慢，以致算法收斂到一定精度時無法繼續優化。粒子群在尋優過程中，無論是找到最優解還是陷于局部最優，整個過程中pg的變化率會越來越小，最終趨于靜止。隨著迭代次數的增加，所有粒子的位置會逐步靠近并停止在pg處。一旦粒子趕上種群最優，粒子會聚集到相應位置并停止移動，種群的多樣性會慢慢喪失，從而導致算法過早收斂而出現早熟現象。

而引導因子q為每輪迭代中最接近最優解的粒子，隨著迭代次數的增加，通過記錄每個粒子當前迭代與上一次迭代運行的方向是否相異來判斷粒子的飛行狀態，在當前迭代中選擇最接近最優解的粒子作為引導因子。引導因子是由粒子的飛行狀態決定的，可以指引最差粒子徑直地朝最優解方向飛行，提高種群多樣性的同時加快收斂速度。因此利用引導因子來更新最差全局粒子值，可以有效地平衡搜索過程的多樣性和方向性，避免算法陷入局部最優。

因此，利用引導因子q引導更新全局最差粒子值，從而在每一次迭代中降低異常粒子數，提高整體粒子的健康度。其計算公式如下：

其中，xw是種群中適應度最差的粒子位置。

在粒子實際運行過程中，大部分的粒子運行狀態并不盡如人意，存在一些粒子始終無法逼近最優位置。文獻[15]提出的HPSO（particle swarm optimization based on health degree）算法通過計算粒子健康度區分正常粒子和異常粒子，將異常粒子的歷史最優位置進行更新，但是隨著迭代次數的增加，粒子速度下降導致很難跳出局部最優；另外，每一次迭代要對每一個粒子進行判斷處理，而存在一些粒子始終無法逼近最優位置，這就延長了尋優時間。

自適應過濾機制通過對異常粒子進行標記，利用調節變量Limit識別懶惰粒子，重新生成一個新的位置；同時，用引導因子q引導全局最差粒子，過濾異常粒子數，提高整體粒子的健康度。利用這種自適應的過濾機制，一方面可以增加粒子的多樣性，有助于算法在迭代后期跳出局部最優，加大算法跳出局部最優的幾率，提升粒子的全局尋優能力；另一方面避免無效搜索，加快算法收斂速度。

2.2.3 算法步驟

輸入：粒子個數N，粒子維數D，迭代次數Iterations，運行次數number。

步驟2計算粒子的適應度值。

步驟3更新每個粒子的速度和位置。

步驟4計算每一個粒子的健康度，若判斷是異常粒子，更新異常粒子歷史最優值位置pi=rand(0,1)×(pg-xi)，識別懶惰粒子，重新生成新的位置xi=xi+rand(0,1)×(pg-xi)。

步驟5更新全局最差粒子值，提高整體粒子的健康度xw=xw+rand(0,1)×(qi-xw)。

步驟6判斷是否滿足結束條件，若不滿足，跳轉至步驟2，否則，算法結束。

3 HAFPSO算法分析

3.1 粒子移動進程模擬

改進前后的兩種算法的粒子移動進程模擬如圖2、圖3所示，在引導因子的作用下，每次迭代后，異常粒子數降低，整體粒子健康度上升，收斂速度明顯加快。

Fig.2 Particle trajectory by HPSO圖2 改進前粒子移動進程圖

Fig.3 Particle trajectory by HAFPSO圖3 改進后粒子移動進程圖

3.2 時間復雜度分析

衡量算法優劣的另一標準就是算法的復雜程度。假設粒子個數N，粒子維數D，考慮到最壞的情況，HAFPSO算法進行一次迭代的時間復雜度分析如下：

（1）初始化粒子參數，時間復雜度為O(ND)。

（80）瓦氏皺指苔Telaranea wallichiana（Gottsche）R.M.Schust.

（2）判斷停止迭代，時間復雜度為O(1)。

（3）計算粒子健康度，如果判斷為異常粒子，進行處理的同時標記該粒子，被搜索次數加1；再判斷無效搜索次數是否大于設定閾值，若是，則重新更新位置，時間復雜度為O(ND)。

（4）引導因子更新最差粒子值，時間復雜度為O(ND)。

（5）更新歷史最優位置表和全局最優位置表，時間復雜度為O(N)。

因此，HAFPSO算法的時間復雜度為O(ND)。

3.3 算法收斂性分析

一個算法是否收斂必須滿足兩個條件：（1）在搜索空間中，產生的解都是獨立的。（2）能夠保存最優解。HAFPSO算法收斂性分析如下。

定義4設X?為算法的最優解，則X?須滿足：

其中，X為搜索變量，f為目標函數。θ(R)=|R?X?|解空間R中最優解的個數。

定義5若，則HAFPSO算法收斂。其中，R0代表初始化的解，t表示迭代次數。

定理1 HAFPSO算法收斂。

證明令P0(t)=P{θ(R(t))=0}，則：

在HAFPSO算法中，如果存儲的最優解中不為空的話，那下一次迭代中最優解的個數肯定不為0，即P{θ(R(t+1))=0|θ(R(t))≠0}=0 。因此，P0(t+1)=P{θ(R(t+1))=0|θ(R(t))=0}×P{θ(R(t))=0}。由算法描述可知，P{θ(R(t+1))=1|θ(R(t))=0}＞0，令,… 然后：

因此，當t→∞時，P{θ(R(t))≥1}→1，即HAFPSO算法是收斂的。 □

4 仿真實驗及結果分析

4.1 測試函數

為了測試HAFPSO算法的效果，對11個標準測試函數進行仿真實驗。表1給出了11個測試函數的名稱、搜索空間范圍、屬性和最優值。

Table 1 Test functions表1 測試函數

4.2 調節變量Limit中β值選擇實驗

為了確定HAFPSO算法Limit變量中β的最佳值，設定粒子維數D=50，粒子數目N=30，最大迭代次數為2 000，對β分別取值為0.2、0.4、0.6、0.9、1.1、1.3、1.6、1.8進行了測試，實驗結果如表2所示。其中Mean代表20次實驗中解的平均值，反應了解的質量；Std表示解的方差，反映了算法的穩定性。

從表2中可以看出，當β的取值為1.1時，算法的尋優精度最高，性能最好。這一點充分體現了算法在對異常粒子處理過程中的自適應過濾機制對提高算法收斂精度有一定的貢獻。從表2中數據分析可知，當β值較大的話，會出現對懶惰粒子的更新速度不夠而尋優精度不高的現象；β取值較小的話，算法的自適應過濾能力過度，這在F2、F3、F5中體現得較為明顯；當β小于1.1時，算法在給定迭代次數內的尋優精度隨著β的增加而有所提高。

Table 2 Influence of different βon HAFPSO表2 不同β對HAFPSO算法的影響

4.3 性能測試實驗與分析

將本文算法HAFPSO與標準粒子群PSO、APSO（adaptive particle swarm optimization）[10]、HPSO[15]進行對比，從而驗證算法的性能。本文中實驗種群個數為30，測試函數的維數為50維，迭代次數為2 000；APSO和HPSO算法的參數設置分別見文獻[10,15]，實驗結果如表3所示。

從表3數據對比可以看出，在標準測試函數中，HAFPSO算法相較于HPSO算法在解的質量、算法的穩定性上都有了很大的提高。特別地，在F8、F11的尋優精度和穩定性上表現得尤為突出：F8是非凸的病態函數，常用于考察算法的執行效率；F11為多峰函數，用于測試算法跳出局部最優的能力。顯然，HPSO算法在單峰函數F2、F3、F9以及多峰函數F8、F11中尋優精度較弱。而HAFPSO算法在上述所有的測試函數中都有著很好的表現。

為了更直觀地反映算法的尋優效果，4種算法對相關測試函數的收斂曲線如圖4所示。圖中的橫坐標表示迭代次數，因篇幅有限，圖中只列出其中6幅，其他效果類似。從圖4中可以看出，HAFPSO算法具有較快的收斂速度，無論是單峰函數還是多峰函數都只需較少的迭代次數就能找到全局最優。

為了進一步展示各種算法種群的位置多樣性[16]隨迭代次數的變化情況，圖5給出了4種算法的位置多樣性在迭代過程中的變化曲線，由于篇幅有限，本文僅列舉3幅，其他效果類似。圖中橫縱坐標分別表示種群的迭代次數和當前的位置多樣性I(X(t))，表達式如下：

從圖5中可以看出，HAFPSO算法在迭代初期粒子多樣性相對偏低，種群搜索范圍相對較小，從而使算法具有相對較強的局部搜索能力，加快算法收斂速度；在迭代后期，粒子多樣性相對較高，粒子能夠在較大范圍內進行搜索，增強了粒子群的全局搜索能力，提高算法收斂速度。縱觀整個迭代過程，HAFPSO算法中粒子群的位置多樣性I(X(t))較為穩定，有利于平衡種群的局部探索和全局探索能力。因此，通過對表3、圖4、圖5的分析可知，HAFPSO算法在尋優精度和收斂速度方面明顯優于其他算法。

4.4 算法尋優時間對比

為了進一步表現HAFPSO算法在尋優速度上的優勢，將各算法獨立運行20次，比較相同仿真環境，粒子維數皆為50的情況下，達到指定收斂精度（1.00E-04）所需要的運行時間，如果200 000次迭代后仍然沒有達到該精度，則用“—”表示，結果如表4所示。

Table 3 Comparison for 50-dimension problems表3 各算法在50維下的計算結果比較

Fig.4 Convergence curves圖4 收斂曲線

Fig.5 Position variety圖5 位置多樣性

由表4中數據分析可知，在仿真環境和參數設置相同的情況下，本文提出的HAFPSO算法達到給定的尋優精度所需的運行時間優于HPSO算法，這也從另一方面再次驗證了HAFPSO算法的有效性。

5 結束語

針對標準粒子群算法在尋優時存在收斂速度慢以及難以跳出局部最優等問題，本文提出了基于健康度的自適應過濾粒子群算法（HAFPSO）。通過計算粒子健康度區分粒子狀態，標記異常粒子，當該粒子被處理次數超過一定閾值而仍沒有逼近最優解的趨勢時，重新生成新的位置；同時，利用引導因子引導更新最差粒子值，避免無效搜索，加快算法收斂速度。仿真實驗結果表明，HAFPSO算法尋優精度高，收斂速度快，在性能上比文中給出的其他改進算法更優。

Table 4 Comparison of time for achieveing optimization表4 算法尋優時間比較

[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,Oct 4-6,1995.Piscataway:IEEE,1995:39-43.

[2]Chatterjee A,Siarry P.Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J].Computers&Operations Research,2006,33(3):859-871.

[3]Pi Qianying,Ye Hongtao.A dynamic adjusting inertia weight particle swarm optimization[J].Journal of Guangxi University of Science and Technology,2016,27(3):26-32.

[4]Clerc M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation,Washington,Jul 6-9,1999.Piscataway:IEEE,1999:1951-1957.

[5]Zhang Shuiping,Zhong Weibiao.Hybrid particle swarm optimization algorithm of new learning factors and constraint factor[J].Application Research of Computers,2015,32(12):3626-3628.

[6]Khamsawang S,Wannakarn P,Jiriwibhakorn S.Hybrid PSODE for solving the economic dispatch problem with generator constraints[C]//Proceedings of the 2nd International Conference on Computer and Automation Engineering,Singapore,Feb 26-28,2010.Piscataway:IEEE,2010,5:135-139.

[7]Premalatha K,Natarajan A M.Discrete PSO with GA operators for document custering[J].International Journal of Recent Trends in Engineering,2009,1:20-24.

[8]Qin Quande,Cheng Shi,Zhang Qingyu,et al.Particle swarm optimization with interswarm interactive learning strategy[J].IEEE Transactions on Cybernetics,2015,46(10):2238-2251.

[9]Ao Yongcai,Shi Yibing,Zhang Wei,et al.Improved particle swarm optimization with Adaptive inertia weight[J].Journal of the University of Electronic Science and Technology of China,2014,43(6):874-880.

[10]Zhan Zhihui,Zhang Jun,Li Yun,et al.Adaptive particle swarm optimization[J].IEEE Transactions on Systems,Man&Cybernetics:Part B,2009,39(6):1362-1381.

[11]Das S,Goswami D,Chatterjee S,et al.Stability and chaos analysis of a novel swarm dynamics with applications to multi-agent systems[J].Engineering Applications of Artificial Intelligence,2014,30(3):189-198.

[12]Gong Yuejiao,Li Jingjing,Zhou Yicong,et al.Genetic learning particle swarm optimization[J].Journal of Power&Energy Engineering,2016,46(10):2277-2290.

[13]Angeline P J.Evolutionary optimization versus particle swarm optimization:philosophy and performance differences[C]//LNCS 1447:Proceedings of the 7th International Conference on Evolutionary Programming VII,San Diego,Mar 25-27,1998.Berlin,Heidelberg:Springer,1998:601-610.

[14]Zhang Chengxing.Comprehensive informed particle swarm optimizer based on constrict factor[J].Journal of Frontiers of Computer Science and Technology,2014,8(4):506-512.

[15]Jin Qibing,Wang Kewen,Zhao Zhenxing,et al.HPSO algorithm with high speed convergent based on particle health degree[J].Applied Mathematics&Information Sciences,2014,8(4):1809-1821.

[16]Shen Yuanxia,Wang Guoyin,Zeng Chuanhua.Study on the relationship between population diversity and learning parameters in particle swarm optimization[J].Acta Electronica Sinica,2011,39(6):1238-1244.

附中文參考文獻：

[3]皮倩瑛,葉洪濤.一種動態調節慣性權重的粒子群算法[J].廣西科技大學學報,2016,27(3):26-32.

[5]張水平,仲偉彪.改進學習因子和約束因子的混合粒子群算法[J].計算機應用研究,2015,32(12):3626-3628.

[9]敖永才,師奕兵,張偉,等.自適應慣性權重的改進粒子群算法[J].電子科技大學學報,2014,43(6):874-880.

[14]張成興.壓縮因子綜合信息粒子群算法[J].計算機科學與探索,2014,8(4):506-512.

[16]申元霞,王國胤,曾傳華.PSO模型種群多樣性與學習參數的關系研究[J].電子學報,2011,39(6):1238-1244.