陶 乾，阮錦新 ，常會友，顧春琴，陳 強

(1.廣東第二師范學(xué)院計算機科學(xué)系，廣州510310;2.中國科學(xué)院深圳先進技術(shù)研究院，深圳518055;3.中山大學(xué)軟件學(xué)院，廣州510006;4.仲愷農(nóng)業(yè)工程學(xué)院計算機系，廣州510225)

粒子群優(yōu)化(Particle Swarm Optimization，PSO)［1］算法作為基于種群的隨機優(yōu)化技術(shù)，通過人工種群內(nèi)粒子間的合作與競爭實現(xiàn)了多維復(fù)雜空間內(nèi)迭代搜索最優(yōu)解，被成功應(yīng)用于各類科學(xué)問題求解［2－4］;但其缺陷也逐漸顯現(xiàn)，主要體現(xiàn)在以下3個方面:

(1)算法容易陷入局部極值，造成早熟收斂;

(2)算法在多維復(fù)雜空間的迭代進化過程有一定的惰性，解的精度難以持續(xù)提高;

(3)算法通過對自然界生物群體搜索現(xiàn)象的簡化模擬設(shè)計而成，缺乏嚴格理論基礎(chǔ).

粒子作為PSO 算法在多維空間的搜索引擎，其行為特性直接決定了PSO 算法的優(yōu)化性能.為克服局部極值，避免在進化后期收斂速度慢、精度低，各類擾動(又稱為變異或跳轉(zhuǎn))優(yōu)化策略常作為輔助手段來改變pBest、gBest 的引導(dǎo)趨勢、優(yōu)化粒子搜索行為、增強其在多維搜索空間的搜索能力、改進PSO算法的性能. 文獻［5］采用柯西變異來改進粒子搜索性能并提出了一種新的PSO 算法;文獻［6］提出了基于柯西變異的混合PSO 算法并對車輛最大允許載重進行優(yōu)化;文獻［7］采用柯西擾動來提升各類進化算法的優(yōu)化性能;文獻［8］提出了基于柯西和高斯混合變異的PSO 算法并優(yōu)化支持向量機的參數(shù)選擇;文獻［9］提出了基于高斯跳轉(zhuǎn)的高斯PSO 算法;文獻［10］使用高斯擾動來優(yōu)化PSO 算法并應(yīng)用于經(jīng)濟調(diào)度;文獻［11］設(shè)計出了混沌跳轉(zhuǎn)的PSO 算法并對噪音問題進行了優(yōu)化，文獻［12］采用基于混沌時間序列的雙擾動對PSO 算法進行改進并應(yīng)用于網(wǎng)格工作流調(diào)度優(yōu)化.

上述PSO 算法的擾動策略研究主要是實驗驗證，缺乏相關(guān)的理論分析，擾動后粒子在多維空間軌跡特性不明確，收斂性沒有有效的證明，輔助優(yōu)化策略缺乏理論支撐，本文從理論證明和實驗驗證兩方面對擾動后粒子在多維空間的收斂特性進行研究.

1 雙擾動下通用軌跡的收斂性

PSO 算法的pBest 和gBest 擾動的形式化定義如下:

雙擾動下第i個粒子第j 維的通用軌跡公式如下:

設(shè)k=1－c1·r1－c2·r2，經(jīng)遞歸得到

因此，軌跡形成一個序列

就級數(shù)

存在.此時，

總之，只要確保加速系數(shù)c1、c2滿足0 ＜c1+c2＜4，則擾動后粒子軌跡收斂.采用擾動后，粒子跟隨pBest、gBest 跳離局部最優(yōu)解，重新向新的解收斂.

2 結(jié)果與分析

資源約束的項目調(diào)度問題屬于NP-Hard 問題.為驗證理論證明的相關(guān)結(jié)果，我們結(jié)合項目調(diào)度問題在多維空間中對隨機粒子運動軌跡進行了實證分析，選用15個節(jié)點的項目調(diào)度e-Protein［12］來測試PSO 算法并驗證擾動軌跡的收斂性以及pBest、gBest雙擾動策略對軌跡收斂的影響. 為進一步分析隨機性對粒子軌跡的影響，充分考慮了隨機參數(shù)的影響r1，r2?［0，1］.所有實驗的運行環(huán)境都是Pentium D 3.00 GHz，1 024 MB RAM 和Windows XP2 操作系統(tǒng).

從PSO 算法的種群中隨機選取粒子，在15 維優(yōu)化空間繪制其3 種軌跡. 對所有維的粒子軌跡和通用軌跡進行比較，圖1 清晰地給出參數(shù)設(shè)置c1+c2=1.8 +1.8 ＜4 情況下15個維度3 種不同的軌跡波形圖，其中particle 代表粒子軌跡，pBest、gBest 代表pBest 軌跡和gBest 軌跡.

從圖1 可見，不同的維度具有不同的迭代次數(shù)和收斂點.剛開始時，3個軌跡振蕩密集，并且振蕩幅度不等，隨著迭代次數(shù)的增大，gBest 軌跡首先趨于穩(wěn)定并收斂于一點，pBest 和粒子的軌跡隨后也同gBest 軌跡一樣向同一點收斂. 當(dāng)gBestj(t)=，則因此，則粒子在第j 空間停止搜索并且軌跡收斂.

種群中粒子運用自己的搜索經(jīng)驗(pBest)和整個種群的搜索經(jīng)驗(gBest)，通過不斷更新自己每一維的速度，搜索到新的位置，gBest、pBest 引導(dǎo)粒子飛行并收斂于一穩(wěn)定點.其中，2、3、5、7、8、9、11、13 維度屬于間隔性擾動并根據(jù)維度不同間隔時間不同，其他屬于連續(xù)性擾動;連續(xù)擾動和間隔性擾動主要是根據(jù)擾動作用情況不同而不同，對粒子的收斂性影響沒有明顯差異.上述15個維度的整體趨勢是:在擾動后粒子會出現(xiàn)了引導(dǎo)性震蕩，但最后都會收斂.

下面進一步通過實驗驗證c1+c2＞4 情況下粒子的發(fā)散情況.通常情況下，當(dāng)粒子速度vji(t+1)=0 時，粒子軌跡收斂于一穩(wěn)定點.因此可通過監(jiān)測迭代后期粒子速度是否接近0 來判斷粒子軌跡是否發(fā)散.為更好體現(xiàn)粒子軌跡的動態(tài)特性，測試進行了3 000 次迭代，在同樣的運行環(huán)境下獨立運行20 次.同時，c1、c2每次迭代的增量定義為0.02，且c1，c2［0.1，5.8］.成功運行20 次后，從15 維中隨機選取第3、11 維進行分析，如圖2 所示.圖中左下角深藍色三角形表明粒子軌跡接近收斂(此時的20 次平均速度接近0). 由于粒子在20 次運行中只要一次速度不為0 則平均速度即不為0，所以我們認為只要平均速度接近0(深藍區(qū)域)即可認為粒子在該維的軌跡收斂，否則軌跡發(fā)散.從圖2 可以發(fā)現(xiàn)三角形區(qū)域的邊弧的斜率約為－1，邊界為c1+c2=4，黑色區(qū)域表明平均速度為0，粒子在擾動后經(jīng)過一段時間會停止搜索、軌跡在20 次實驗中完全收斂;當(dāng)c1+c2＞4 時，粒子在擾動后一直高速搜索，粒子軌跡發(fā)散.因此，通過實驗可以發(fā)現(xiàn)當(dāng)參數(shù)c1+c2＞4時，粒子在受到擾動后軌跡發(fā)散.

綜上分析，在gBest、pBest 雙擾動下，粒子在各個維度出現(xiàn)了引導(dǎo)性震蕩，維度不同振幅不同，在確保加速系數(shù)c1、c2滿足0 ＜c1+c2＜4 情況下所有維度都在震蕩后收斂.作為PSO 算法搜索引擎的粒子在多維空間中擾動后仍然收斂，擾動作為一種優(yōu)化策略能有效提升粒子的搜索性能但不影響粒子的收斂性.總之，pBest 和gBest 雙擾動作為一種優(yōu)化策略能防止算法早熟收斂但不影響粒子收斂.

圖1 擾動后粒子軌跡、pBest 軌跡和gBest 軌跡的比較Figure 1 The trajectories comparison of the particle，pBest and gBest

圖2 參數(shù)c1、c2 不同取值對粒子軌跡發(fā)散和收斂影響Figure 2 The convergence of the particle trajectories under c1、c2

3 結(jié)論

本文采用遞歸和極限、級數(shù)收斂等數(shù)學(xué)方法對pBest 和gBest 雙擾動后的軌跡收斂行為進行了分析和證明，同時在高維空間對擾動狀況下粒子的收斂性進行了實驗驗證. pBest 和gBest 雙擾動作為一種優(yōu)化策略能防止算法早熟收斂但不影響粒子的收斂性.

［1］Kennedy J，Eberhart R. Particle swarm optimization［C］∥IEEE proceedings of the international conference on neural networks (ICNN). Perth，WA，1995:1942－1948.

［2］Selakov A，Cvijetinovi D，Milovi L，et al. Hybrid PSO-SVM method for short-term load forecasting during periods with significant temperature variations in city of Burbank［J］. Applied Soft Computing，2014，16:80－88.

［3］Khan S A，Nadeem A. Automated test data generation for coupling based integration testing of object oriented programs using particle swarm optimization［M］.New York:Springer International Publishing，2014:115－124.

［4］Gaing Z L，Lin C H，Tsai M H，et al. Rigorous design and optimization of brushless pm motor using response surface methodology with quantum-behaved pso operator［J］. IEEE Transactions on Magnetics，2014，50(1):1－4.

［5］Wang H，Li H，Liu Y，et al. Opposition-based particle swarm algorithm with Cauchy mutation［C］∥IEEE proceedings of the international conference on evolutionary computation. Singapore，2007:4750－4756.

［6］Venkatesan S，Kamaraj N，Chellam S. Optimal wheeling transaction based on maximum allowable load of the buyer bus using HPSO with Cauchy mutation［J］. International Review of Electrical Engineering，2011，6(5):2440－2447.

［7］Ali M，Pant M. Improving the performance of differential evolution algorithm using Cauchy mutation ［J］. Soft Computing，2011，15(5):991－1007.

［8］Wu Q，Law R. Cauchy mutation based on objective variable of Gaussian particle swarm optimization for parameters selection of SVM［J］. Expert Systems with Applications，2011，38(6):6405－6411.

［9］Wang X，Wang H B，Liu H T. An improved Gaussian mixture model based on least-squares cross-validation and Gaussian PSO with Gaussian jump［C］∥IEEE proceedings of the international conference on machine learning and cybernetics (ICMLC). Xi'an，China，2012，2:714－719.

［10］Varma S C，Murthy K S L，SriChandan K. Gaussian particle swarm optimization for combined economic emission dispatch［C］∥IEEE proceedings of the international conference on energy efficient technologies for sustainability(ICEETS). Nagercoil，India，2013:1336－1340.

［11］Mendel E，Krohling R A，Campos M. Swarm algorithms with chaotic jumps applied to noisy optimization problems［J］. Information Sciences，2011，181(20):4494－4514.

［12］Tao Q，Chang H，Yi Y，et al. A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow［J］.Computers ＆ Operations Research，2011，38(5):824－836.