袁 羅，葛洪偉+，姜道銀

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

2.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

1 引言

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

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

2 基于健康度的自適應(yīng)過濾粒子群算法

2.1 標準粒子群算法

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

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

2.2 HAFPSO算法

2.2.1 健康度

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

其中，WS和WOSC分別是粒子的停滯次數(shù)和振蕩次數(shù)的權(quán)值系數(shù)。

2.2.2 自適應(yīng)過濾機制

定義1Limit為一個調(diào)節(jié)變量，用于衡量異常粒子是否需要自適應(yīng)過濾處理：

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

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

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

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

定義3引導(dǎo)因子q為每輪迭代中最接近最優(yōu)解的粒子，q滿足條件：

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

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

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

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

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

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

其中，xw是種群中適應(yīng)度最差的粒子位置。

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

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

2.2.3 算法步驟

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

步驟2計算粒子的適應(yīng)度值。

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

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

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

步驟6判斷是否滿足結(jié)束條件，若不滿足，跳轉(zhuǎn)至步驟2，否則，算法結(jié)束。

3 HAFPSO算法分析

3.1 粒子移動進程模擬

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

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

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

3.2 時間復(fù)雜度分析

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

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

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

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

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

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

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

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

3.3 算法收斂性分析

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

定義4設(shè)X?為算法的最優(yōu)解，則X?須滿足：

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

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

定理1 HAFPSO算法收斂。

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

在HAFPSO算法中，如果存儲的最優(yōu)解中不為空的話，那下一次迭代中最優(yōu)解的個數(shù)肯定不為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 仿真實驗及結(jié)果分析

4.1 測試函數(shù)

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

Table 1 Test functions表1 測試函數(shù)

4.2 調(diào)節(jié)變量Limit中β值選擇實驗

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

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

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

4.3 性能測試實驗與分析

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

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

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

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

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

4.4 算法尋優(yōu)時間對比

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

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

Fig.4 Convergence curves圖4 收斂曲線

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

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

5 結(jié)束語

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

Table 4 Comparison of time for achieveing optimization表4 算法尋優(yōu)時間比較

[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]皮倩瑛,葉洪濤.一種動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法[J].廣西科技大學(xué)學(xué)報,2016,27(3):26-32.

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

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

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

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