姜長(zhǎng)元，趙曙光，郭力爭(zhēng)，冀 川

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

改進(jìn)型耗散粒子群優(yōu)化算法

姜長(zhǎng)元1，2，趙曙光1，郭力爭(zhēng)1，冀 川1

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

通過(guò)對(duì)標(biāo)準(zhǔn)粒子群優(yōu)化算法中慣性權(quán)重的分析和對(duì)耗散理論的研究，提出了一種慣性權(quán)重正弦調(diào)整的耗散粒子群優(yōu)化算法（S－DPSO），并對(duì)該算法進(jìn)行了深入的分析和研究.通過(guò)對(duì)4個(gè)典型函數(shù)的仿真測(cè)試，試驗(yàn)結(jié)果表明S－DPSO在收斂速度和全局收斂性方面都比標(biāo)準(zhǔn)粒子群優(yōu)化算法、隨機(jī)慣性權(quán)重粒子群優(yōu)化算法、慣性權(quán)重正弦調(diào)整粒子群優(yōu)化算法、耗散粒子群優(yōu)化算法和隨機(jī)慣性權(quán)重耗散粒子群優(yōu)化算法有明顯改進(jìn).理論分析和仿真試驗(yàn)驗(yàn)證了S－DPSO的正確性和有效性.

粒子群優(yōu)化算法；慣性權(quán)重；正弦調(diào)整；耗散；跳變因子

粒子群優(yōu)化（particle swarm optimization，PSO）算法是1995年由美國(guó)社會(huì)心理學(xué)家KENNEDY和電氣工程師EBERHART基于鳥(niǎo)群覓食行為而提出的群體智能進(jìn)化算法［1－2］.該算法由于具有概念簡(jiǎn)明、參數(shù)簡(jiǎn)單、收斂速度快、實(shí)現(xiàn)方便等特點(diǎn)，受到了很大的關(guān)注.加入慣性權(quán)重的PSO算法現(xiàn)已成為常用的標(biāo)準(zhǔn)PSO算法.目前，PSO算法已成為一個(gè)研究熱點(diǎn)，通常用于多目標(biāo)優(yōu)化、神經(jīng)網(wǎng)絡(luò)參數(shù)訓(xùn)練、智能系統(tǒng)控制等方面［3－5］.

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

1 標(biāo)準(zhǔn)PSO算法

PSO算法采用進(jìn)化算法中群體和進(jìn)化的概念.隨機(jī)初始化一群沒(méi)有體積、沒(méi)有質(zhì)量的粒子，將每個(gè)粒子視為優(yōu)化問(wèn)題的一個(gè)可行解，粒子的好壞由一個(gè)事先設(shè)定的適應(yīng)度函數(shù)來(lái)確定.每個(gè)粒子在可行解空間中運(yùn)動(dòng)，由一個(gè)速度變量決定其方向和距離.粒子根據(jù)自身的最優(yōu)位置和整個(gè)粒子群全體的最優(yōu)位置，調(diào)節(jié)自身的飛行方向和速度，一直朝目前的最優(yōu)粒子飛行［2－4］.

粒子群進(jìn)化過(guò)程可用下面兩個(gè)方程描述.

其中：r1，r2為均勻分布在（0，1）區(qū)間的隨機(jī)數(shù)；c1，c2稱(chēng)為學(xué)習(xí)因子，通常取c1＝c2＝2，在式（1）中，為簡(jiǎn)化，常常記φ1＝c1r1，φ2＝c2r2；ω稱(chēng)為慣性權(quán)重.根據(jù)式（1）和（2）對(duì)粒子的速度、位置不斷更新進(jìn)化，直到滿(mǎn)足最大迭代次數(shù)或者滿(mǎn)足所要求的精度才停止迭代.

式（1）右側(cè)第一項(xiàng)為粒子先前速度的繼承，依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng)；第二項(xiàng)為“認(rèn)知”部分，結(jié)合自身以往的經(jīng)歷實(shí)現(xiàn)下一步行為決策；第三項(xiàng)為“社會(huì)”部分，表示粒子間的信息共享與合作.

2 改進(jìn)型耗散粒子群優(yōu)化算法

2.1 S－PSO算法

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

本文提出一種慣性權(quán)重正弦調(diào)整的粒子群優(yōu)化算法：

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

由ω值的變化可知，在算法開(kāi)始時(shí)，讓粒子在其自身附近作局部尋優(yōu)，在一段時(shí)間后加大互相協(xié)作程度，進(jìn)行全局尋優(yōu)，最后讓最優(yōu)粒子進(jìn)行局部搜索.

2.2 耗散粒子群結(jié)構(gòu)

耗散結(jié)構(gòu)是指處在遠(yuǎn)離平衡態(tài)的開(kāi)放系統(tǒng)，通過(guò)與外界交換物質(zhì)和能量，在一定的條件下通過(guò)自組織形成一種新的穩(wěn)定的有序結(jié)構(gòu).文獻(xiàn)［12］首先實(shí)現(xiàn)了將耗散結(jié)構(gòu)引入粒子群算法中，提出了耗散粒子群算法.在耗散粒子群算法中，通過(guò)對(duì)粒子速度、位置的跳變來(lái)完成對(duì)系統(tǒng)的耗散過(guò)程［13－14］.具體實(shí)現(xiàn)如式（3）和（4）所示.

其中：cv和cl為跳變因子，其值在［0，1］內(nèi)；random（Ld，Ud）為L(zhǎng)d與Ud之間的隨機(jī)數(shù).在隨機(jī)數(shù)小于這兩個(gè)跳變因子的情況下，速度和位置進(jìn)行跳變，這樣可以防止系統(tǒng)達(dá)到暫時(shí)平衡態(tài)，也就是算法陷入局部最優(yōu)的情況.

式（3）和（4）的兩步跳變?cè)谒俣扰c位置更新之后.

2.3 算法分析

本文提出的慣性權(quán)重正弦調(diào)整的耗散粒子群優(yōu)化算法，在速度迭代過(guò)程中，當(dāng)粒子逐漸接近最好位置的過(guò)程中，式（1）的后兩項(xiàng)逐漸趨近于0，如果，速度的變化將完全依靠式（1）的即如果粒子到達(dá)全局最佳位置之后，還要繼續(xù)移動(dòng)，必須保持原速度和權(quán)值ω都不為0.如果先前的速度已非常接近于0，那么粒子一旦達(dá)到全局最佳位置，它們的運(yùn)動(dòng)將趨向停滯狀態(tài)，粒子將一直在一個(gè)位置周?chē)\(yùn)動(dòng)，稱(chēng)這樣的算法是不完全收斂的［13－14］.

標(biāo)準(zhǔn)PSO算法之所以搜索精度不高，是因?yàn)榱Ｗ铀俣认陆抵?時(shí)，所搜索到的解尚未達(dá)到全局最優(yōu).耗散粒子群優(yōu)化算法為了解決這個(gè)問(wèn)題，用隨機(jī)數(shù)與一個(gè)適當(dāng)?shù)奶円蜃舆M(jìn)行比較，在滿(mǎn)足比較條件的情況下，加入負(fù)熵對(duì)速度進(jìn)行耗散，保持系統(tǒng)處于遠(yuǎn)離平衡的狀態(tài).耗散粒子群優(yōu)化算法并沒(méi)有改變標(biāo)準(zhǔn)PSO算法的基本結(jié)構(gòu)，主要更新機(jī)制與標(biāo)準(zhǔn)PSO算法相似，只是通過(guò)對(duì)粒子的不斷耗散來(lái)增加種群的多樣性，從而提高算法的搜索性能.因此，耗散粒子群優(yōu)化算法會(huì)收斂于個(gè)體歷史最優(yōu)和群體最優(yōu)中的某個(gè)權(quán)平衡點(diǎn).

耗散粒子群優(yōu)化算法每一次迭代更新產(chǎn)生的結(jié)果值是否需要進(jìn)行耗散與隨機(jī)數(shù)和跳變因子比較結(jié)果有關(guān)，目前跳變因子的選擇主要依據(jù)經(jīng)驗(yàn)值.

3 仿真實(shí)例

3.1 仿真設(shè)置

為了能進(jìn)一步比較，選取一種隨機(jī)變化慣性權(quán)重粒子群優(yōu)化算法［4］，即ω＝0.4＋rand（）/2，在整個(gè)迭代過(guò)程中，ω值的變化范圍均為［0.4，0.9］.

待測(cè)試算法有PSO，R－PSO，S－PSO，將其分別加入耗散結(jié)構(gòu)后又得3種：DPSO，R－DPSO，SDPSO，共計(jì)6種算法.

為驗(yàn)證新算法的性能，采用文獻(xiàn)［2］中所提及的Benchmark的4個(gè)常用測(cè)試函數(shù)，如式（5）～（8）所示，用6種算法進(jìn)行測(cè)試，統(tǒng)計(jì)收斂率、收斂代數(shù)與平均最優(yōu)適應(yīng)度.

f1是Sphere函數(shù)：

f2是Rosenbrock函數(shù)：

f3是Rastrigrin函數(shù)：

f4是Griewank函數(shù)：

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

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

表1 4個(gè)函數(shù)的測(cè)試參數(shù)Table 1 Test parameters for four functions

3.2 結(jié)果分析

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

表2 4個(gè)函數(shù)6種算法的平均測(cè)試結(jié)果Table 2 Testing average results for four functions with six algorithms

續(xù) 表

4 結(jié) 語(yǔ)

粒子群優(yōu)化算法是一種新型的進(jìn)化算法，在算法收斂速度以及慣性權(quán)重調(diào)整方面還有很多值得研究的問(wèn)題.本文通過(guò)分析慣性權(quán)重調(diào)整方法對(duì)收斂速度的影響以及耗散理論對(duì)解的影響，提出了一種慣性權(quán)重正弦調(diào)整的耗散粒子群優(yōu)化（S－DPSO）算法，并且利用 PSO，R－PSO，S－PSO，DPSO，R－DPSO，S－DPSO算法對(duì)4種典型測(cè)試函數(shù)進(jìn)行仿真試驗(yàn)，試驗(yàn)結(jié)果表明，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］李麗，牛奔.粒子群優(yōu)化算法［M］.北京：冶金工業(yè)出版社，2009.

［5］韓江洪，李正榮，魏振春.一種自適應(yīng)粒子群優(yōu)化算法及其仿真研究［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18（10）：2969－2971.

［6］胡建秀，曾建潮.微粒群算法中慣性權(quán)重的調(diào)整策略［J］.計(jì)算機(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算法粒子運(yùn)動(dòng)軌跡分析［J］.計(jì)算機(jī)學(xué)報(bào)，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］.計(jì)算機(jī)仿真，2010，27（2）：204－207.

［13］孟凡輝，王秀坤，赫然，等.一種改進(jìn)的耗散粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，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

浙江省教育廳基金資助項(xiàng)目（Y201016350）；湖州市自然科學(xué)基金資助項(xiàng)目（2010YZ05）；浙江省自然科學(xué)基金資助項(xiàng)目（Y6110043）

姜長(zhǎng)元（1975—），男，安徽安慶人，講師，博士研究生，研究方向?yàn)榭刂评碚撆c控制工程.E－mail：jcy＠hutc.zj.cn

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

1671－0444（2012）03－0312－06