改進型耗散粒子群優化算法

姜長元，趙曙光，郭力爭，冀 川

（1.東華大學 信息科學與技術學院，上海 201620；2.湖州師范學院 理學院，浙江 湖州 313000）

改進型耗散粒子群優化算法

姜長元1，2，趙曙光1，郭力爭1，冀 川1

（1.東華大學 信息科學與技術學院，上海 201620；2.湖州師范學院 理學院，浙江 湖州 313000）

通過對標準粒子群優化算法中慣性權重的分析和對耗散理論的研究，提出了一種慣性權重正弦調整的耗散粒子群優化算法（S－DPSO），并對該算法進行了深入的分析和研究.通過對4個典型函數的仿真測試，試驗結果表明S－DPSO在收斂速度和全局收斂性方面都比標準粒子群優化算法、隨機慣性權重粒子群優化算法、慣性權重正弦調整粒子群優化算法、耗散粒子群優化算法和隨機慣性權重耗散粒子群優化算法有明顯改進.理論分析和仿真試驗驗證了S－DPSO的正確性和有效性.

粒子群優化算法；慣性權重；正弦調整；耗散；跳變因子

粒子群優化（particle swarm optimization，PSO）算法是1995年由美國社會心理學家KENNEDY和電氣工程師EBERHART基于鳥群覓食行為而提出的群體智能進化算法［1－2］.該算法由于具有概念簡明、參數簡單、收斂速度快、實現方便等特點，受到了很大的關注.加入慣性權重的PSO算法現已成為常用的標準PSO算法.目前，PSO算法已成為一個研究熱點，通常用于多目標優化、神經網絡參數訓練、智能系統控制等方面［3－5］.

由于標準PSO算法更像粒子的聚類，粒子向當前最好位置的方向飛行，導致多樣性缺失，適應值停滯，尤其在進化后期缺乏改進解的能力［3］.國內外學者提出了多種改進算法［2－8］.標準PSO算法在前期具有較好的全局搜索能力，后期收斂性也較好，但收斂速度比較慢；隨機慣性權重粒子群優化（R－PSO）算法［4］雖然前期收斂速度很快，但后期的局部搜索能力較差.本文研究慣性權重ω對算法性能的影響以及耗散理論對解的多樣性貢獻，提出一種慣性權重正弦調整的耗散粒子群優化（S－DPSO）算法.通過仿真測試，S－DPSO算法在收斂速度和全局收斂性方面均優于標準PSO算法、R－PSO算法、慣性權重正弦調整粒子群優化（S－PSO）算法、耗散粒子群優化（DPSO）算法和隨機慣性權重耗散粒子群優化（R－DPSO）算法.

1 標準PSO算法

PSO算法采用進化算法中群體和進化的概念.隨機初始化一群沒有體積、沒有質量的粒子，將每個粒子視為優化問題的一個可行解，粒子的好壞由一個事先設定的適應度函數來確定.每個粒子在可行解空間中運動，由一個速度變量決定其方向和距離.粒子根據自身的最優位置和整個粒子群全體的最優位置，調節自身的飛行方向和速度，一直朝目前的最優粒子飛行［2－4］.

粒子群進化過程可用下面兩個方程描述.

其中：r1，r2為均勻分布在（0，1）區間的隨機數；c1，c2稱為學習因子，通常取c1＝c2＝2，在式（1）中，為簡化，常常記φ1＝c1r1，φ2＝c2r2；ω稱為慣性權重.根據式（1）和（2）對粒子的速度、位置不斷更新進化，直到滿足最大迭代次數或者滿足所要求的精度才停止迭代.

式（1）右側第一項為粒子先前速度的繼承，依據自身的速度進行慣性運動；第二項為“認知”部分，結合自身以往的經歷實現下一步行為決策；第三項為“社會”部分，表示粒子間的信息共享與合作.

2 改進型耗散粒子群優化算法

2.1 S－PSO算法

通過對各種改進的粒子群優化算法的分析研究、仿真［2－8］可知，慣性權重ω對算法性能有以下影響：較大的ω值有利于跳出局部最優，進行全局尋優；較小的ω值有利于局部尋優，加速算法收斂.

本文提出一種慣性權重正弦調整的粒子群優化算法：

取φ1＝ （ω（t）＋1）r1，φ2＝ （ω（t）＋1）（2－r1）r2，文獻［9－11］中提到的所有條件均能得到滿足，從理論上說明了S－PSO算法在收斂性能上有一定的保障.

由ω值的變化可知，在算法開始時，讓粒子在其自身附近作局部尋優，在一段時間后加大互相協作程度，進行全局尋優，最后讓最優粒子進行局部搜索.

2.2 耗散粒子群結構

耗散結構是指處在遠離平衡態的開放系統，通過與外界交換物質和能量，在一定的條件下通過自組織形成一種新的穩定的有序結構.文獻［12］首先實現了將耗散結構引入粒子群算法中，提出了耗散粒子群算法.在耗散粒子群算法中，通過對粒子速度、位置的跳變來完成對系統的耗散過程［13－14］.具體實現如式（3）和（4）所示.

其中：cv和cl為跳變因子，其值在［0，1］內；random（Ld，Ud）為Ld與Ud之間的隨機數.在隨機數小于這兩個跳變因子的情況下，速度和位置進行跳變，這樣可以防止系統達到暫時平衡態，也就是算法陷入局部最優的情況.

式（3）和（4）的兩步跳變在速度與位置更新之后.

2.3 算法分析

本文提出的慣性權重正弦調整的耗散粒子群優化算法，在速度迭代過程中，當粒子逐漸接近最好位置的過程中，式（1）的后兩項逐漸趨近于0，如果，速度的變化將完全依靠式（1）的即如果粒子到達全局最佳位置之后，還要繼續移動，必須保持原速度和權值ω都不為0.如果先前的速度已非常接近于0，那么粒子一旦達到全局最佳位置，它們的運動將趨向停滯狀態，粒子將一直在一個位置周圍運動，稱這樣的算法是不完全收斂的［13－14］.

標準PSO算法之所以搜索精度不高，是因為粒子速度下降至0時，所搜索到的解尚未達到全局最優.耗散粒子群優化算法為了解決這個問題，用隨機數與一個適當的跳變因子進行比較，在滿足比較條件的情況下，加入負熵對速度進行耗散，保持系統處于遠離平衡的狀態.耗散粒子群優化算法并沒有改變標準PSO算法的基本結構，主要更新機制與標準PSO算法相似，只是通過對粒子的不斷耗散來增加種群的多樣性，從而提高算法的搜索性能.因此，耗散粒子群優化算法會收斂于個體歷史最優和群體最優中的某個權平衡點.

耗散粒子群優化算法每一次迭代更新產生的結果值是否需要進行耗散與隨機數和跳變因子比較結果有關，目前跳變因子的選擇主要依據經驗值.

3 仿真實例

3.1 仿真設置

為了能進一步比較，選取一種隨機變化慣性權重粒子群優化算法［4］，即ω＝0.4＋rand（）/2，在整個迭代過程中，ω值的變化范圍均為［0.4，0.9］.

待測試算法有PSO，R－PSO，S－PSO，將其分別加入耗散結構后又得3種：DPSO，R－DPSO，SDPSO，共計6種算法.

為驗證新算法的性能，采用文獻［2］中所提及的Benchmark的4個常用測試函數，如式（5）～（8）所示，用6種算法進行測試，統計收斂率、收斂代數與平均最優適應度.

f1是Sphere函數：

f2是Rosenbrock函數：

f3是Rastrigrin函數：

f4是Griewank函數：

其中：f1是單峰函數，全局最小值為0，收斂于（0，0，…，0）；其余3個函數均是經典的多峰函數，全局最小值為0，f2收斂于 （1，1，…，1），f3和f4收斂于 （0，0，…，0）.

在對4個測試函數仿真試驗的各PSO算法中，取c1＝c2＝2；最大進化代數取為1 500；群體規模為40；跳變因子cv＝cl＝0.1；各個函數的vmax取為變量范圍的上限.對每個算法，各運行20次，取平均適應度、平均最優結果，收斂率、收斂代數為評價數據.其他測試參數如表1所示.測試機器為Pentium Dual 1.8G，2G內存，采用 Matlab 7.0編程.

表1 4個函數的測試參數Table 1 Test parameters for four functions

3.2 結果分析

4個測試函數20次試驗平均最優解隨迭代次數的變化歷程如圖1～4所示.從圖1～4可以看出，若不加入耗散結構，S－PSO算法收斂性優于PSO算法和R－PSO算法.本文提出的S－DPSO算法在迭代前期有很強的收斂性，在1/5迭代時期即已獲得理想值，尤其是圖2（b），3（b），4（b），其強收斂性更具說服力，且在后續迭代過程中始終能保持優勢.在圖3（a）中，PSO 算法、R－PSO 算法、S－PSO 算法不能很好收斂到最優解附近，而加入耗散結構后，算法收斂性立即得到較大改善，且以S－DPSO算法收斂性最好，見圖3（b）.若針對某一函數，將6種算法的仿真測試結果放在一起，也有很好的表現效果.當然，若增加迭代次數，算法還將進一步收斂.表2是仿真結果，從平均最優迭代結果和收斂代數來看，S－DPSO算法均比其他5種算法要好.在仿真試驗中，通過改變維數、迭代次數、群體規模、跳變因子等，S－DPSO算法在相同條件下多次測試均取得較理想結果，這說明在針對4個測試函數方面，本文提出的S－DPSO算法能夠加快收斂速度，使收斂精度變高.

表2 4個函數6種算法的平均測試結果Table 2 Testing average results for four functions with six algorithms

續 表

4 結 語

粒子群優化算法是一種新型的進化算法，在算法收斂速度以及慣性權重調整方面還有很多值得研究的問題.本文通過分析慣性權重調整方法對收斂速度的影響以及耗散理論對解的影響，提出了一種慣性權重正弦調整的耗散粒子群優化（S－DPSO）算法，并且利用 PSO，R－PSO，S－PSO，DPSO，R－DPSO，S－DPSO算法對4種典型測試函數進行仿真試驗，試驗結果表明，S－DPSO算法比其他5種PSO算法收斂速度更快、收斂精度更高.

［1］KENNEDY J，EBERHART R C.Particle swarm optimization［C］//Proceedings IEEE International Conference on Neural Networks.Piscataway NJ：IEEE Service Center，1995：1942－1948.

［2］SHI Y，EBERHART R C.Empirical study of particle swarm optimization［C］//Proceedings of Congress on Evolutionary Computation.Washing DC，1999：1945－1950.

［3］EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory ［C ］//Proceedings of the 6th International Symposium on Micro Machine and Human Science.Piscataway NJ：IEEE Service Center，1995：39－43.

［4］李麗，牛奔.粒子群優化算法［M］.北京：冶金工業出版社，2009.

［5］韓江洪，李正榮，魏振春.一種自適應粒子群優化算法及其仿真研究［J］.系統仿真學報，2006，18（10）：2969－2971.

［6］胡建秀，曾建潮.微粒群算法中慣性權重的調整策略［J］.計算機工程，2007，33（11）：193－195.

［7］TRELEA I C.The particle swarm optimization algorithm：Convergence analysis and parameter selection［J］.Information Processing Letters，2003，85（6）：317－325.

［8］SHI Y，EBERHART R C.Parameter selection in particle swarm optimization ［C］//Proceeding of Seventh Annual Conference on Evolutionary Computation.Washing DC，1998：591－600.

［9］李寧，孫德寶，鄒彤，等.基于差分方程的PSO算法粒子運動軌跡分析［J］.計算機學報，2006，29（11）：2052－2061.

［10］CLERC M，KENNEDY J.The particle swarm－explosion，stability，and convergence in a multidimensional complex space［J］.IEEE Transactions on Evolutionary Computation，2002，6（1）：58－73.

［11］XIE X F，ZHANG W J，YANG Z L.A issipative article warm optimization ［C］//The IEEE Congress on Evolutionary Computation，Hawaii，2002：1456－1461.

［12］任小波，楊忠秀.耗散粒子群算法的性能分析［J］.計算機仿真，2010，27（2）：204－207.

［13］孟凡輝，王秀坤，赫然，等.一種改進的耗散粒子群算法［J］.計算機工程與應用，2005（12）：34－36，69.

［14］SHEN X F，WEI K P，WU D M，et al.A dynamic adaptive dissipative particle swarm optimization with mutation operation［C］//2007IEEE International Conference on Control and Automation.Guangzhou，2007：586－589.

An Improved Dissipative Particle Swarm Optimization Algorithm

JIANG Chang－yuan1，2，ZHAO Shu－guang1，GUO Li－zheng1，JI Chuan1
（1.College of Information Science and Technology，Donghua University，Shanghai 201620，China；2.School of Science，Huzhou Teachers College，Huzhou Zhejiang 313000，China）

Based on the analyzing inertia weight of the standard particle swarm optimization（PSO）algorithm and studying the dissipative structure theory，a new dissipative PSO（DPSO）algorithm with sinusoidal changing inertia weight（S－DPSO）is presented.S－DPSO algorithm is conducted in－depth analysis and research.By the experiments of four benchmark function，the results show the performance of S－DPSO improve more clearly than the standard PSO，random inertia weight PSO（R－PSO），S－PSO，DPSO and R－DPSO.Theoretical analysis and simulation experiments show that the S－DPSO is efficient and feasible.

particle swarm optimization algorithm；inertia weight；sinusoidal changing；dissipative；chaotic factors

TP 301.6

A

2011－05－27

浙江省教育廳基金資助項目（Y201016350）；湖州市自然科學基金資助項目（2010YZ05）；浙江省自然科學基金資助項目（Y6110043）

姜長元（1975—），男，安徽安慶人，講師，博士研究生，研究方向為控制理論與控制工程.E－mail：jcy＠hutc.zj.cn

趙曙光（聯系人），男，教授，E－mail：sgzhao＠dhu.edu.cn

1671－0444（2012）03－0312－06