基于緊湊度和調度處理的粒子群優化算法*

周　丹，葛洪偉+，蘇樹智，袁運浩

?

基于緊湊度和調度處理的粒子群優化算法*

周丹1,2，葛洪偉1,2+，蘇樹智1，袁運浩1

1.江南大學物聯網工程學院，江蘇無錫214122
2.江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫214122

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(05)-0742-09

http://www.ceaj.org Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 61402203 (國家自然科學基金); the Research Innovation Program for College Graduates of Jiangsu Province under Grant No. KYLX15_1169 (江蘇省普通高校研究生科研創新計劃項目).

Received 2015-06,Accepted 2015-08.

CNKI網絡優先出版: 2015-08-28, http://www.cnki.net/kcms/detail/11.5602.TP.20150828.1622.012.htm l

ZHOU Dan, GE Hongwei, SU Shuzhi, et al. Particle compaction and scheduling based particle swarm optim ization. Journal of Frontiersof Computer Scienceand Technology, 2016, 10(5)：742-750.

摘要：針對標準粒子群優化算法存在收斂速度慢和難以跳出局部最優等問題，提出了一種基于緊湊度和調

度處理的粒子群優化算法。給出了粒子緊湊度和調度處理的概念和方法，通過動態評價粒子群中各粒子間的緊湊程度，從而確定調度的粒子，進而對其進行調度處理，避免粒子陷入局部最優。對11個常見的標準函數進行測試，并與標準粒子群算法和其他改進算法進行對比，實驗結果表明，基于緊湊度和調度處理的粒子群優化算法具有較高的尋優精度和較快的收斂速度。

關鍵詞：粒子群優化算法；局部最優；緊湊度；調度處理；尋優精度；收斂速度

1 引言

粒子群優化算法（particle swarm optim ization，PSO）是Kennedy等人受到飛鳥集群活動的規律性啟發而提出的一種智能優化算法。與其他進化算法相比，它容易實現，參數較少，具有較低的時間和空間復雜度，已在科學和工程領域得到了廣泛的研究和應用。但是，PSO算法在尋優過程中依然存在著收斂速度慢，易陷入局部最優的缺陷。近年來，相關學者對此提出了很多改進方法，如在基本PSO中引入慣性權值[1-3]、壓縮因子[4]以及健康度[5-6]的概念等，這類改進算法雖然能在一定程度上改善PSO的搜索性能，提高算法的收斂速度，但是在處理一些多峰函數時，仍存在易陷入局部最優的問題。為了增強粒子的全局探索能力，在有限規模內保持粒子群的多樣性，避免種群陷入局部最優，學者們在基本PSO中引入了交叉機制[7]、自適應變異機制[8-12]等方法，但卻降低了種群的收斂速度。鑒于單一的智能算法在實際應用中面臨各自的問題，相互之間的促進與補充便成為可行的改進途徑，因此學者們提出混合各種啟發式算法的改進思路，如在PSO中引入蟻群算法的信息素機制[13]、極值優化[14]、爬山策略[15]、人工魚群思想[16]等，但就總體而言，這些算法仍然存在收斂速度慢和易陷入局部最優等缺陷。

通過分析可以看出，粒子群算法存在的主要問題是：（1）對當前全局最優值的追逐力度不夠，導致收斂速度不夠快；（2）算法迭代中后期，粒子的多樣性不夠，導致搜索范圍不夠大，算法全局探索能力較弱，且沒有有效的機制使粒子跳出局部最優，最終導致算法收斂精度不夠高。為了解決此問題，本文引入了緊湊度和調度處理的概念，提出了基于緊湊度和調度處理的粒子群優化算法（particle compaction and scheduling based particle swarm optimization，PCSPSO）。本文算法通過動態計算粒子間的緊湊度來確定調度粒子，進而對調度粒子進行調度處理，擴大粒子的搜索范圍，增強算法的全局探索能力；同時在調度過程中，全局最優值Pg的引導增強了算法的收斂速度。

2 標準粒子群優化算法

標準粒子群優化算法的數學描述為：在D維的搜索空間中，每一個粒子都被看成空間中的一個點，不妨設空間中共有m個粒子，則第i個粒子的空間位置為Xi=[xi1,xi2,…,xiD]，其速度為Vi=[vi1,vi2,…,viD]，其所經歷的最優位置即個體歷史最優位置Pi=[pi1,pi2,…,piD]，其中i=1,2,…,m。所有粒子經歷過的最優位置即全局最優位置Pg=[pg1,pg2,…,pgD]。粒子的位置和速度更新公式分別為：

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

3 相關問題描述

定義1(σ2)[11]設粒子群的粒子數目為m，f(Xi)為第i個粒子的適應值，favg(X)為粒子群目前的平均適應度，σ2為粒子群當前的適應度方差：

定義2(I(X(t)))[17]設粒子群中粒子數目為m，粒子維數為D，粒子群的位置多樣性I(X(t))定義如下：

4 基于緊湊度和調度處理的粒子群算法

4.1緊湊度

定理1如果粒子群算法陷入早熟收斂或者達到全局收斂，則群體適應度方差σ2等于0。

證明令φ1=c1r1，φ2=c2r2，綜合式（1）、（2）得：

其中，Pi為個體最優值位置；Pg為全局最優值的位置。

如果粒子群算法出現早熟收斂或者達到全局收斂，則個體最優值、全局最優值不再發生變化；此時需考慮當算法出現早熟收斂或者全局收斂時，隨機量φ1、φ2對粒子的影響，由于φ1=c1r1，φ2=c2r2，r1、r2服從均勻分布，為了簡化處理，利用其期望值進行觀察，即：

由定理1可知，當粒子群出現早熟或全局收斂時，群體的適應度方差等于0，此時種群的全局探索能力較弱，為了避免種群陷入局部最優，本文提出了緊湊度的概念，即當兩粒子間的適應度差值在一個門限值范圍內時，就認定此時兩粒子處于緊湊狀態。雖然處于緊湊狀態的粒子能夠加強局部搜索能力，但卻降低了粒子群的全局探索能力，使種群更容易出現早熟收斂。因此，本文根據經驗值設定具體的緊湊度閾值，當相鄰兩粒子間的適應度差值小于此閾值時，就可認定兩粒子已達到了緊湊狀態，否則，兩粒子未達到緊湊狀態。

4.2粒子調度處理的方法

對粒子進行調度處理的主要目標是為了在提高算法尋優精度的同時，加快算法的收斂速度。為了提高算法的尋優精度，本文利用式（9）、（10）對粒子的歷史最優位置Pi、當前位置Xi進行處理，從而改變粒子的運動軌跡，擴大粒子群的搜索范圍；由于有全局最優位置Pg的參與和調度系數c3的控制，調度粒子能夠在Pg周圍進行搜索，提高算法的尋優精度，同時使得粒子搜索到優于已有Pg的概率大大提高，加快算法的收斂速度。

其中，r3,r4∈[0,1]，k,h∈{1,2,…,m}，d∈{1,2,…,D}，且k、h均為隨機值，這些參數的隨機性保證了算法具有很強的探索能力；c3為調度系數，用于控制調度粒子對Pg的跟隨程度，在提高算法尋優精度的同時盡量避免陷入局部最優。

控制種群位置多樣性是提高算法全局探索能力的重要手段之一，因此PCS-PSO算法在處理調度粒子時，通過以一定的小概率p1隨機改變粒子的當前位置而不受Pg的限制，提高算法的全局探索能力。此時雖然會在一定程度上減慢整個種群的收斂速度，但通過小概率p1的控制，可以有效地協調收斂速度與全局探索力度，使種群在快速搜索全局最優值的同時，能夠擴大搜索范圍，增強算法的全局探索能力。具體做法如式（11）所示：

4.3算法描述

針對標準粒子群算法在迭代初期收斂速度慢，而在迭代后期又存在不易跳出局部最優的缺陷，本文提出了基于緊湊度和調度處理的粒子群算法（PCS-PSO）。在PCS-PSO算法中，首先需根據具體問題確定一個合適的緊湊度閾值Hth，然后在種群每一次迭代結束后，根據緊湊度正確選擇調度粒子，并對其進行調度。具體做法為：在粒子群每一次更新結束后，按粒子的適應度值對粒子進行排序，若相鄰兩粒子處于緊湊狀態，則對前一粒子進行調度，直到算法結束。

4.4算法步驟

步驟1隨機初始化粒子群中各粒子的速度和位置：

步驟2更新粒子群中所有粒子的速度和位置：

步驟3將粒子按當前適應度值的大小排序。

步驟4若相鄰兩粒子處于緊湊狀態，則對前一粒子進行如下調度處理：

若產生的隨機數rand

步驟5若粒子的當前適應度值優于目前的全局最優值，則更新粒子群Pg。

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

5 仿真實驗

5.1測試函數

本文在實驗中選取了Sphere、Rosenbrock、Penalized、Levy、Griewank、Rastrigin、NC- Rastrigin、Ackley、Cigar、Ellipse、Quadric這11個變量維數可變的常用測試函數（見表1）。在進行參數選擇實驗時，僅用了F1～F4；在與其他算法（PSO、HPSO[5]、APSO[12]）進行對比時，所有函數均會被測試。此外，為了保證實驗數據的公平有效，本文具體做法如下：（1）在每次運行各種算法之前，生成一組初始值并初始化粒子，從而消除因初始值不同而導致的差異；（2）每次實驗均將各算法反復運行20次，最后對其進行統計，從而消除因算法隨機性導致的差異。

Table 1 Test functions表1 測試函數

5.2參數的選擇實驗

在實驗中適應度閾值根據經驗值取Hth=100，下面對PCS-PSO算法中的參數c3、p1進行實驗和分析。為了確定調度處理時調度系數c3的最佳值，設定粒子維度D=30，小概率p1=0.05，粒子數目m=30，最大迭代次數itmax=3 000，對c3取值分別為0.1、0.3、0.4、0.5、0.6、0.7、0.9、1.1時進行了測試，實驗結果如表2所示。其中Mean表示20次實驗中最優解的平均值，反應了解的質量；Std表示解的方差，反應了算法的穩定性和魯棒性。

從表2中可以看出，當調度系數c3的取值為0.5時，算法的尋優精度最高，性能最優。調度系數c3體現了調度粒子對全局最優值Pg的依賴程度。從表中數據分析可知，當c3較大時，會導致調度粒子過度依賴Pg而出現尋優精度不高的現象；當c3較小時，會出現粒子對最優位置Pg的利用力度不夠，在3 000次迭代內尋優精度不夠高，這在F2、F3、F4中體現得較為明顯，即當c3≤0.5時，算法在給定迭代次數內的尋優精度隨著c3的增加而提高。

下面繼續研究小概率p1對算法的影響。對p1分別取0、0.01、0.03、0.05、0.07、0.10、0.20進行測試，此時調度系數取最佳值，即c3=0.5，其他參數的設置同上，實驗結果見表3。

Table 2 Influence of different c3on PCS-PSO表2 不同c3對PCS-PSO算法的影響

Table 3 Influence of different p1on PCS-PSO表3 不同小概率對PCS-PSO算法的影響

從表3中可以看出，當小概率p1=0.05時，算法的尋優精度最高，性能最優。這一點充分體現了粒子群在尋優過程中，小概率擾動對提高算法收斂精度有一定的貢獻，而以較大概率進行擾動又會導致對當前全局最優值的追逐力度不夠，降低算法的收斂速度。這一點在函數F2、F3、F4中表現得較為明顯，即當p1≤0.05，尋優精度隨著p1的增加而提高；而當p1>0.50時，尋優精度卻隨著p1的增加而降低。

5.3性能測試實驗與分析

為了驗證本文算法（PCS-PSO）的性能，將PCSPSO算法與標準PSO、收斂速度快且尋優能力相對較好的HPSO[5]、尋優能力強且不易陷入局部的APSO[12]進行了對比。各算法的詳細參數（HPSO、APSO的參數設置方案分別源自文獻[5，12]）如表4所示，其中粒子維數D=30，粒子個數m=30。實驗結果統計表如表5所示，其中Best、Worst、Mean、Std、S.R.分別表示各算法在20次獨立實驗過程中的最好值、最壞值、平均值、適應度方差和達到指定精度（1.00E-04）的百分比。

Table 4 Setting parameters for algorithms表4 各算法參數設置

從表5可以看出，PCS-PSO算法較其他對比算法表現出了良好的收斂速度和收斂精度，在F2、F3和F4中表現得尤為突出。F2（Rosenbrock）是非凸的病態函數，常用于考察算法的執行效率；F3（Penalized）、F4（Levy）均為多峰函數，用于考察算法跳出局部最優的能力。APSO算法在多峰函數F4、F5、F6、F7、F8中尋優精度不夠高；HPSO算法在多峰函數F3、F4中尋優能力較弱；PCS-PSO算法在上述所有多峰函數上的尋優精度較高，從而表明了本文算法PCS-PSO減輕了局部極值現象。為了進一步展現PCS-PSO算法在尋優速度上的優勢，表6給出了各算法達到指定精度（1.00E-04）所花費的時間。運行環境為：CPU Intel i5-3470，主頻3.2 GHz，內存4.0 GB，64位Win7系統；實驗在Matlab 2010 b軟件上運行。統計結果為20次重復實驗的平均值，若200 000次迭代后還未達到該精度，則用“—”表示。此外，圖1、圖2分別給出了粒子的收斂曲線和位置多樣性變化圖，由于篇幅有限，本文列舉了具有代表性的6個測試函數的收斂曲線圖和3個測試函數的位置多樣性變化圖，在其他測試函數上也有相似的性能。

Table 6 Running time of algorithms表6 各算法達到指定精度的運行時間

Fig.1 Convergence curve圖1 收斂曲線

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

從圖1中可以看出，PCS-PSO算法具有較快的收斂速度，特別是在Sphere和Cigar函數中表現得尤為明顯，只需較少的迭代次數就能找到全局最優解。從圖2中可以看出，在迭代初期，PCS-PSO算法中粒子多樣性相對較低，使得種群的搜索范圍相對較小，從而使算法具有相對較強的局部搜索能力，加快種群的收斂速度；在迭代后期，PCS-PSO算法中粒子多樣性相對較高，有利于粒子在較大范圍內進行搜索，增強粒子群的全局探索能力，提高算法收斂精度。縱觀整個迭代過程，PCS-PSO算法中粒子群的位置多樣性I(X(t))較為穩定，有利于平衡種群的局部搜索和全局探索能力。通過對表5和圖1的數據進行分析易知，PCS-PSO算法在收斂速度和尋優精度上明顯優于其他對比算法。

6 結束語

由于標準粒子群優化算法在尋優時存在收斂速度慢和易陷入局部最優等問題，本文給出了緊湊度的概念和相應的調度處理方法，提出了基于緊湊度和調度處理的粒子群算法，在種群每一次迭代更新結束后，通過統計粒子間的緊湊程度，選擇合適的粒子對其進行調度，保證了種群的搜索范圍，避免種群多樣性的缺失，具體的調度策略使算法在整個尋優過程中能夠有效地平衡種群的局部搜索能力和全局探索能力。仿真實驗結果表明，本文提出的基于緊湊度和調度處理的粒子群算法在收斂速度和尋優精度上具有良好的性能。

References：

[1] Shi Yuhui, Eberhart R. A modified particle swarm optimizer [C]//Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, Anchorage, USA, May 4-9, 1998. Piscataway, USA: IEEE, 1998: 69-73.

[2] Shi Yuhui, Eberhart R C. Parameter selection in particle swarm optimization[C]//LNCS 1447: Proceedings of the 7th International Conference on Evolutionary Programm ing, San Diego, USA, Mar 25- 27, 1998. Berlin, Heidelberg: Springer, 1998: 591-600.

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

[4] Clerc M, Kennedy J. The particle swarm-explosion, stability and convergence in a multi-dimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (1): 58-73.

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

[6] Jin Qibing, Zhao Zhenxing, Su Xiaojing, et al. PSO algorithm with high speed convergence based on particle health[J]. CIESC Journal, 2011, 62(8): 2328-2333.

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

[8] Zhang Dingxue, Liao Ruiquan. Adaptive particle swarm optimization algorithm based on population velocity[J]. Control and Decision, 2009, 24(8):1257-1260.

[9] Zhu Haimei, Wu Yongping. A PSO algorithm w ith high speed convergence[J]. Control and Decision, 2010, 25(1): 20-24.

[10] Ren Zihui, Wang Jian. Accelerate convergence particle swarm optimization algorithm[J]. Control and Decision, 2011, 26(2): 201-206.

[11] Lv Zhensu, Hou Zhirong. Particle swarm optimization w ith adaptive mutation[J]. ACTA Electronica Sinica, 2004, 32(3): 416-420.

[12] Zhan Zhihui, Zhang Jun, Li Yun, et al. Adaptive particle swarm optim ization[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2009, 39(6): 1362-1381.

[13] Shelokar P S, Siarry P, Jayaraman V K, et al. Particle swarm and ant colony algorithms hybridized for improved continuous optim ization[J]. Applied Mathematics and Computation, 2007, 188(1): 129-142.

[14] Chen M inrong, Li Xia, Zhang Xi, et al. A novel particle swarm optimizer hybridized w ith extremal optimization[J]. Applied Soft Computing, 2010, 10(2): 367-373.

[15] Wu Yonghua, Peng Yong, Wang Gang. Hybrid particle swarm optimization algorithm based on colony mountainclimbing strategy[J]. Computer Engineering and Applications, 2014, 50(1): 45-48.

[16] Yao Xiangguang, Zhou Yongquan, Li Yongmei. Hybrid algorithm w ith artificial fish swarm algorithm and PSO[J]. Application Research of Computer, 2010, 27(6): 2084-2086. [17] Shen Yuanxia, Wang Guoyin, Zeng Chuanhua. Study on the relationship between population diversity and learning parameters in particle swarm optim ization[J]. ACTA Electronica Sinica, 2011, 39(6):1238-1244.

[18] Li Ning, Sun Debao, Zou Tong, et al.An analysis for a particle?s trajectory of PSO based on difference equation[J]. Chinese Journal of Computers, 2006, 29(11): 2052-2061.

附中文參考文獻：

[6]靳其兵,趙振興,蘇曉靜,等.基于粒子健康度的快速收斂粒子群優化算法[J].化工學報, 2011, 62(8): 2328-2333.

[8]張頂學,廖銳全.一種基于種群速度的自適應粒子群算法[J].控制與決策, 2009, 24(8): 1257-1260.

[9]朱海梅,吳永萍.一種高速收斂粒子群優化算法[J].控制與決策, 2010, 25(1): 20-24.

[10]任子暉,王堅.加速收斂的粒子群優化算法[J].控制與決策, 2011, 26(2): 201-206.

[11]呂振肅,侯志榮.自適應變異的粒子群優化算法[J].電子學報, 2004, 32(3): 416-420.

[15]吳永華,彭勇,汪剛.基于群體爬山策略的混合粒子群優化算法[J].計算機工程與應用, 2014, 50(1): 45-48.

[16]姚祥光,周永權,李詠梅.人工魚群與微粒群混合優化算法[J].計算機應用研究, 2010, 27(6): 2084-2086.

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

[18]李寧,孫德寶,鄒彤,等.基于差分方程的PSO算法粒子運動軌跡分析[J].計算機學報, 2006, 29(11): 2052-2061.

ZHOU Dan was born in 1989. She is an M.S. candidate at Jiangnan University, and the member of CCF. Her research interests include artificial intelligence and pattern recognition.

周丹（1989—），女，湖北荊州人，江南大學碩士研究生，CCF會員，主要研究領域為人工智能，模式識別。

GE Hongwei was born in 1967. He received the M.S. degree in computer science from Nanjing University of Aeronautics and Astronautics in 1992 and the Ph.D. degree in control engineering from Jiangnan University in 2008. Now he is a professor and Ph.D. supervisor at School of Internet of Things Engineering, Jiangnan University. His research interests include artificial intelligence and pattern recognition, machine learning, image processing and analysis, etc.

葛洪偉（1967—），男，江蘇無錫人，1992年于南京航空航天大學計算機系獲得碩士學位，2008年于江南大學信息學院獲得博士學位，現為江南大學物聯網工程學院教授、博士生導師，主要研究領域為人工智能與模式識別，機器學習，圖像處理與分析等。在國際權威期刊、會議和國內核心期刊上發表論文70多篇，主持和承擔了國家自然科學基金等國家級項目和省部級項目近20項，獲省部級科技進步獎多項。

SU Shuzhi was born in 1987. He is a Ph.D. candidate at Jiangnan University. His research interests include pattern recognition and machine learning.

蘇樹智（1987—），男，山東泰安人，江南大學博士研究生，主要研究領域為模式識別，機器學習。

YUAN Yunhao was born in 1983. He received the Ph.D. degree from Nanjing University of Science and Technology in 2013. Now he is an associate professor at Jiangnan University. His research interests include pattern recognition and machine learning.

袁運浩（1983—），男，江蘇徐州人，2013年于南京理工大學獲得博士學位，現為江南大學物聯網工程學院副教授，主要研究領域為模式識別，機器學習。

Particle Com paction and Scheduling Based Particle Swarm Optim ization?

ZHOU Dan1,2, GE Hongwei1,2+, SU Shuzhi1, YUAN Yunhao1
1. School of Internet of Things Engineering, Jiangnan University, Wuxi, Jiangsu 214122, China
2. Key Laboratory of Advanced Process Control for Light Industry, M inistry of Education, Jiangnan University, Wuxi, Jiangsu 214122, China
+ Corresponding author: E-mail: ghw8601@163.com

Key words:particle swarm optim ization; local optim ization; compaction; scheduling; accuracy of convergence; speed of convergence

Abstract:To the problems of slow convergence and easy to fall into local optim ization appeared in standard particle swarm optimization, this paper proposes a particle compaction and scheduling based particle swarm optimization (PCS-PSO). Firstly, this paper presents the regulations of particles’compaction and scheduling. In order to avoid particles to stay in local optim ization, PCS-PSO evaluates dynam ically particle’s compaction and schedules the particle when the value of the particle’s compaction is beyond the threshold. Compared w ith standard particle swarm optim ization and other optimization algorithms using 11 benchmark functions, the experimental results show that PCS-PSO has better behaviors in convergence accuracy and speed.

doi:10.3778/j.issn.1673-9418.1507025 E-mail: fcst@vip.163.com

文獻標志碼：A

中圖分類號：TP18