PSO算法擾動(dòng)優(yōu)化策略及其收斂性研究

陶 乾，阮錦新 ，常會(huì)友，顧春琴，陳 強(qiáng)

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

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

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

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

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

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

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

1 雙擾動(dòng)下通用軌跡的收斂性

PSO 算法的pBest 和gBest 擾動(dòng)的形式化定義如下:

雙擾動(dòng)下第i個(gè)粒子第j 維的通用軌跡公式如下:

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

因此，軌跡形成一個(gè)序列

就級(jí)數(shù)

存在.此時(shí)，

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

2 結(jié)果與分析

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

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

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

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

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

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

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

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

3 結(jié)論

本文采用遞歸和極限、級(jí)數(shù)收斂等數(shù)學(xué)方法對(duì)pBest 和gBest 雙擾動(dòng)后的軌跡收斂行為進(jìn)行了分析和證明，同時(shí)在高維空間對(duì)擾動(dòng)狀況下粒子的收斂性進(jìn)行了實(shí)驗(yàn)驗(yàn)證. pBest 和gBest 雙擾動(dòng)作為一種優(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.