基于高斯擾動的量子粒子群優化算法

摘 要:針對量子粒子群優化(QPSO)算法在優化過程中面臨早熟問題，提出了在粒子的平均位置或全局最優位置上加入高斯擾動的QPSO算法，可以有效地阻止粒子的停滯，因此較容易地使粒子避免陷入局部最優。為了評估算法的性能，利用標準測試函數對標準PSO算法、QPSO算法以及基于高斯擾動的QPSO算法進行了比較測試。其結果表明，該算法具有較強的全局搜索能力和較快的收斂速度。

關鍵詞:量子粒子群優化算法; 平均位置; 全局最優位置; 高斯擾動

中圖分類號:TP18;TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2093-04

doi:10.3969/j.issn.1001-3695.2010.06.028

Quantum-behaved particle swarm optimization based on Gaussian disturbance

WANG Xiao-gena， LONG Hai-xiaa， SUN Junb

(a.School of Education， b.School of Information Engineering， Jiangnan University， Wuxi Jiangsu 214122， China)

Abstract:Due to shortcoming of quantum-behaved particle swarm optimization (QPSO) algorithm that it was often premature convergence， this paper proposed a revised QPSO with Gaussian disturbance on the mean best position or global best position of the swarm. The disturbance could effectively prevent the stagnation of the particles and therefore made them escape the local optima more easily. To evaluate the performance of the new method， tested the QPSO with Gaussian disturbance， along with QPSO and standard PSO on several well-known benchmark functions. Experiment simulations show that the proposed algorithm has powerful optimizing ability and more quickly convergence speed.

Key words:quantum-behaved particle swarm optimization algorithm; mean position; global best position; Gaussian distur-bance

0 引言

美國社會心理學家Kennedy和電氣工程師Eberhart于1995年提出了PSO算法[1]，其主要思想來源于對鳥類群體行為的研究，已經在很多領域得到了成功的應用。但是在算法收斂性方面，Burgh證明了標準PSO算法不能收斂于全局最優解，甚至于局部最優解[2]。

在PSO算法的改進方面，Kennedy[3]引入了鄰域拓撲的概念來調整鄰域的動態選擇，增加鄰域間的信息交流，提高種群的多樣性;Lovbjerg等人[4]于2001年將遺傳算法中的子群體概念引入PSO算法中，同時引入繁殖算子以進行子群體的信息交流;Kennedy于2004年從概率統計的角度，將粒子的運動改為正態擾動的隨機擾動，并采用鄰域環拓撲結構來改進PSO算法的性能[5];Riget等人[6]利用種群的多樣性出發，在PSO算法中增加了發散能力，較好地提高了算法的全局搜索能力; Sun Jun等人[7]提出了基于量子行為的粒子群算法(QPSO)，提高了粒子群的全局收斂能力。

QPSO算法的思想來源于量子力學和PSO模型，每個粒子類似于量子空間中的基本粒子，問題可行解的整個空間都是每個粒子的搜索范圍，因而其全局搜索性能大大優于經典PSO算法。但QPSO算法在運行過程中也存在粒子群體多樣性衰減的現象，即隨著算法的運行，部分粒子由于速度的減小而失去活力，導致后續的搜索中失去局部搜索能力和全局搜索能力，因此出現了許多改進的QPSO算法。Sun Jun等人[8]提出了概率分布機制使種群在全局搜索中更加有效;而且Sun Jun等人[9]提出了基于多樣性的QPSO來防止種群的聚集，使粒子更容易避開局部最優點;在QPSO算法中加入模擬退火(SA)不僅能跳出局部最優而且能夠提高QPSO算法的全局搜索能力[10];Coelho[11]介紹了基于Gaussian 概率分布的QPSO算法，在此算法中引入了變異算子;在QPSO算法中利用免疫記憶和接種技術的特征引導算法的搜索過程，以提高算法的收斂速度[12]。本文在QPSO算法的基礎上引入高斯擾動來提高QPSO算法的全局收斂能力。

1 QPSO算法

在一個n維的目標搜索空間中，QPSO算法有m個代表潛在問題解的粒子組成群體X={x1，x2，…，xm}，在t時刻第i個粒子的位置為xi(t)=(xi1(t)，xi2(t)，…，xin(t))，粒子沒有速度向量。個體最好的位置表示為Pi(t)=(Pi1(t)，Pi2(t)，…，Pin(t));群體全局最好的位置為Pg(t)=(Pg1(t)，Pg2(t)，…，Pgn(t))，其中g為處于全局最好位置粒子的下標。

Clerc等人[13]在對粒子軌道的分析中證明了這樣一個事實:假如每一個粒子收斂到它的局部吸引點Ai=(Ai1，Ai2，…，Aim)并且滿足下面的條件式(1)，那么PSO算法是收斂的。

Aij(t)=(c1r1Pij(t)+c2r2Pgj(t))/(c1r1+c2r2)or Aij(t)=φ×Pij(t)+(1-φ)×Pgj(t)(1)

其中:φ=c1r1/(c1r1+c2r2)。從式(1)中可以看出局部吸引點Ai是一個位于超矩形中的隨機點。下面介紹QPSO算法。

假如粒子在以吸引點為中心的一維δ勢阱中運動，解一維δ勢阱的Schrdinger方程，得到概率擾動函數D(x)=e-2|A-x|/L。使用Monte Carlo方法可以得到:

x=A±L2ln(1/u)，u~U(0，1)(2)

Sun Jun等人在QPSO算法中引入了平均最好位置[7]。它定義為所有粒子個體最好位置的平均，即

C(t)=(C1(t)，C2(t)，…，Cm(t))=(1M∑ni=1Pi，1(t)，1M∑ni=1Pi，2(t)，…，1M∑ni=1Pi，n(t))(3)

L的值用下面的公式計算:L=2α×|Cj(t)-xij(t)|，粒子位置更新方程為

xij(t+1)=Aij(t)±α×|Cj(t)-xij(t)|×ln(1/u)(4)

其中，參數α為收縮—擴張系數，可以通過調節α的值來控制算法的收斂速度，α必須滿足α<1.782來保證粒子的收斂[14]。通常α從α0到α1線性減小(α0>α1)。

2 基于高斯擾動的QPSO算法

在經典PSO算法中，隨著粒子群的集體性不斷提高、多樣性的快速下降，粒子間信息的快速流動導致算法很難逃離局部最優位置，因此粒子的群集性導致多樣性的降低和適應值變化的停滯。在QPSO算法中，盡管每次迭代中單個粒子的搜索空間為問題可行解的所有空間，由于粒子的群集性，算法執行過程中多樣性的損失也不可避免。

從經典PSO和QPSO算法的更新方程可以推導得出，經典PSO和QPSO算法中的所有粒子將收斂到一個公共的點，使得種群的多樣性非常低，并且粒子在下一次迭代之前沒有進一步的搜索。為了克服這個問題，對QPSO算法進行了改進研究，以期提高QPSO算法后期階段粒子的多樣性和算法的性能。改進的方法是在QPSO算法中加入高斯擾動(Gaussian distur-bance)， 采用下面三種策略:

a)在平均最好位置上加入高斯擾動

Cj(t)=Cj(t)+ε×Rn; j=1，2，…，N(5)

b)在全局最好位置上加入高斯擾動

Pg(t)=Pg(t)+ε×Rn; j=1，2，…，N(6)

c)在平均最好位置和全局最好位置上均加入高斯擾動，利用式(5)(6)。

在式(5)(6)中，ε是一個預先設定的參數;Rn是均值為0和標準方差為1的滿足高斯擾動的隨機數。

在QPSO算法中加入高斯擾動可以有效地避免多樣性的下降和早熟收斂的產生，這是因為算法運行過程中粒子群體不斷進化時，時刻對平均最好位置和全局最好位置進行擾動，保持粒子的活動性，幫助粒子逃離局部最優位置，使得算法得到更好的性能。具有高斯擾動的QPSO算法能夠保持粒子的活力，在算法的后續階段能夠有效地幫助粒子逃離局部最優，從而提高算法的性能。

改進后的QPSO算法的執行過程如下:

a)在問題空間中初始化粒子群中粒子的位置，并設置初始個體最優值。

b)利用式(3)計算平均最優位置C。

c)利用式(5)或式(6)得到擾動點。

d)對于粒子群體中的每一個粒子，計算粒子的當前適應值并與前一次迭代的適應值進行比較，更新粒子的個體最優位置Pi，即如果f[xi(t+1)]

e)計算粒子群體的群體最優位置Pg(t+1)=arg min1≤i≤M{f[Pi(t)]}。

f)更新粒子群體的全局最優位置。

g)根據Aij(t)=φj(t)×Pij(t)+[1-φj(t)]×Pgj(t)，φj(t)~U(0，1)計算得到一個隨機點的位置。

h)根據式(4)計算粒子的新位置。

i)重復步驟b)~h)，直到滿足結束循環條件。

3 仿真實驗

3.1 實驗設置

本文實驗中引入了五個標準函數來測試具有高斯擾動的QPSO算法的總體性能，對測試函數的函數形式、搜索范圍、初始化范圍的設置如表1[15]所示，所有函數的理論最小值均為0。本文設計了四類測試實驗:a)SPSO優化實驗;b)QPSO優化實驗;c)平均最好位置上加入高斯擾動的QPSO算法(MQPSO);d)全局最好位置上加入高斯擾動的QPSO算法(BQPSO);e)平均和全局最好位置上均加入高斯擾動的QPSO算法(MBQPSO)。

表1 標準測試函數及其參數

functionfunction expressionsearch domaininitial range

Spheref1(x)=∑ni=1x2i[-100，100][50，100]

Rosenbrockf2(x)=∑n-1i=1(100×(xi+1-x2i)2+(xi-1)2)[-100，100][15， 30]

Rastriginf3(x)=∑ni=1(x2i-10×cos(2πxi)+10)[-5.12，5.12][2.56，5.12]

Griewankf4(x)=14000∑ni=1x2i-∏ni=1cosxii+1[-600，600][300，600]

Schafferf5(x)=0.5+(sin(x2+y2)2-0.5(1.0+0.001(x2+y2))2[-100，100][30，100]

在MQPSO、BQPSO和MBQPSO三種算法中，參數ε設置為常數0.000 5。

實驗測試過程中，將測試函數的函數值設置為粒子的適應值并對每個函數進行50次測試，記錄平均最優適應值和標準偏差。為了研究算法的可擴展性，每個函數的測試過程中采用了不同的種群尺寸M和不同的維度D。種群大小設置為20、40和80，除了Schaffer函數外，其他所有函數的維度分別設置為10、20和30，對應的算法最大迭代次數設置為1 000、1 500和2 000;Shaffer函數的最大迭代次數設置為2 000，維度設置為2。對于標準SPSO算法，其加速度系數設置為c1=c2=2，慣性權重因子線性地從0.9 減少到0.4。對于QPSO、MQPSO、BQPSO、MBQPSO算法，參數α隨算法的運行從1.0 線性地降低到 0.5。算法50次運行后最小適應值的均值和標準方差如表2～6所示。

表2 Sphere function的仿真結果

MdimgmaxSPSOmean best(St.Dev.)QPSOmean best(St.Dev.)MQPSOMean Best(St.Dev.)BQPSOMean Best(St.Dev.)MBQPSOMean Best(St.Dev.)

1010004.6636e-021(1.0816e-020)9.9733e-044(4.8708e-043)5.0300e-008(1.3118e-008)5.0497e-006(3.4412e-006)5.3813e-006(3.1992e-006)

202015009.0397e-012(3.6044e-011)1.3330e-023(3.8578e-023)4.7465e-007(9.9433e-008)3.5660e-005(2.1636e-005)4.7677e-005(2.3478e-005)

3020005.4652e-008(1.2866e-007)7.3807e-014(3.9980e-013)1.4537e-006(2.4669e-007)9.3845e-005(5.4052e-005)1.1948e-004(5.4181e-005)

1010006.0519e-025(1.3454e-024)3.7703e-075(2.2257e-074)3.9535e-008(9.5266e-009)3.2510e-006(2.2243e-006)5.0716e-006(3.0487e-006)

402015008.8091e-015(2.7541e-014)6.2598e-043(3.9131e-042)3.7711e-007(8.2315e-008)3.5805e-005(2.4493e-005)4.0116e-005(2.3457e-005)

3020005.7175e-011(9.2317e-011)5.8240e-029(2.7907e-028)1.2868e-006(1.7584e-007)8.4143e-005(3.8269e-005)1.0903e-004(5.3538e-005)

1010001.0585e-028(3.2288e-028)1.2629e-101(7.5408e-101)2.9073e-008(9.0087e-009)3.5302e-006(2.4952e-006)4.2719e-006(1.8701e-006)

802015007.7687e-018(1.8497e-017)5.3031e-069(2.4450e-068)3.4336e-007(7.2103e-008)3.0502e-005(1.4564e-005)3.5635e-005(1.7060e-005)

3020009.7939e-013(4.2925e-012)4.5013e-050(2.1861e-049)1.0576e-006(1.5789e-007)7.5891e-005(3.7680e-005)1.1553e-004(6.9752e-005)

表3 Rosenbrock function的仿真結果

Mdim gmaxSPSOmean best(St. Dev.)QPSOmean best(St. Dev.)MQPSOmean best(St. Dev.)BQPSOmean best(St. Dev.)MBQPSOmean best(St. Dev.)

10100027.1159(46.8982)34.0254(63.4626)25.8956(46.9880)25.2115(56.3068)26.2399(51.3287)

2020200094.5540(184.6187)71.9134(117.2893)68.2976(74.2750)82.7217(135.8673)68.9907(102.4339)

302000146.0952(160.1071)122.8972(142.4230)117.2070(182.7348)152.8106(231.8329)121.8970(176.2897)

10100027.8007(63.0610)18.1606(25.5968)10.4080(14.5591)16.7396(36.5529)14.1402(16.3845)

4020150052.0378(55.7566)49.8761(46.4435)37.4891(41.7028)41.5129(44.5833)41.2398(37.4944)

101000107.3789(166.7348)69.0404(58.9664)54.0157(44.7894)51.0299(44.3111)71.5374(69.0916)

10100012.6281(24.4214)12.2803(23.4514)11.6420(15.8026)5.5796(7.8057)9.3444(12.5441)

8020150053.2359(125.5355)37.0901(38.3374)31.7689(33.3099)37.9613(44.7665)32.3365(37.8422)

302000108.0814(150.4659)56.1391(37.6330)51.6486(35.0710)

53.1795(41.3760)48.3516(35.7636)

表4 Rastrigin function的仿真結果

MdimgmaxSPSOmean best(St. Dev.)QPSOmean best(St. Dev.)MQPSOmean best(St. Dev.)BQPSOmean best(St. Dev.)MBQPSOmean best(St. Dev.)

1010005.0041(2.6778)4.6331(2.1420)4.7510(3.1345)4.5472(2.6457)4.2412(2.1028)

2020150022.5019(7.1447)13.9361(4.1434)14.2945(4.0683)15.0436(6.9150)13.9171(5.6081)

30200051.9810(13.9263)28.8876(8.6535)27.6005(7.2470)28.5434(6.8237)29.8254(12.6546)

1010003.7436(1.6012)2.6205(1.6433)2.8383(1.4988)2.9309(1.5199)3.0445(1.6246)

4020150016.4207(5.73480)11.0822(3.9558)10.7361(3.5389)11.4977(3.8580)11.0816(3.5947)

30200039.9508(9.7971)21.2964(5.2381)20.1047(5.3041)19.3349(6.2123)21.0376(4.9071)

101002.3688(1.2046)2.3989(2.0275)1.8728(1.3937)2.1618(1.1852)1.8095(1.2067)

8020150012.5326(4.3126)9.1060(3.7092)7.8344(2.1418)8.4864(2.7149)7.9112(2.5657)

30200032.1621(8.1184)15.9700(4.3547)15.8483(4.0925)16.5147(4.1843)16.0957(3.8550)

表5 Griewank function的仿真結果

MdimgmaxSPSOmean best(St. Dev.)QPSOmean best(St. Dev.)MQPSOmean best(St. Dev.)BQPSOmean best(St. Dev.)MBQPSOmean best(St. Dev.)

1010000.0990(0.0494)0.0631(0.0453)0.0597(0.0360)0.0609(0.0432)0.0569(0.0384)

202015000.0327(0.0287)0.0249(0.0261)0.0247(0.0197)0.0195(0.0194)0.0226(0.0236)

3020000.0186(0.0248)0.0105(0.0128)0.0113(0.0117)0.0093(0.0123)0.0094(0.0133)

1010000.0770(0.0304)0.0475(0.0391)0.0473(0.0355)0.0401(0.0226)0.0456(0.0338)

402015000.0325(0.0292)0.0265(0.0360)0.0202(0.0173)0.0180(0.0178)0.0179(0.0190)

3020000.0135(0.0130)0.0093(0.0145)0.0074(0.0096)0.0086(0.0112)0.0115(0.0143)

1010000.0726(0.0321)0.0421(0.0415)0.0375(0.0324)0.0357(0.0229)0.0406(0.0389)

802015000.0264(0.0228)0.0139(0.0140)0.0104(0.0115)0.0102(0.0152)0.0154(0.0162)

3020000.0104(0.0143)0.0084(0.0118)0.0077(0.0103)0.0077(0.0105)0.0073(0.0117)

表6 Schaffer function的仿真結果

MdimgmaxSPSOmean best(St.Dev.)QPSOmean best(St.Dev.)MQPSOmean best(St.Dev.)BQPSOmean best(St.Dev.)MBQPSOmean best(St.Dev.)

20220000.0012(0.0032)0.0016(0.0036)0.0011(0.0030)7.7769e-004(0.0027)0.0011(0.0030)

40220000(0)3.8865e-004(0.0019)7.5145e-005(5.2839e-004)1.3470e-008(1.7547e-008)8.7229e-008(1.7562e-007)

80220000(0)2.2252e-009(4.8635e-009)1.0159e-007(7.0668e-007)7.4479e-009(1.0750e-008)7.6312e-009(1.6788e-008)

3.2 實驗結果

從表2~6的實驗結果中可以看出，三種具有高斯擾動的QPSO算法，其中MQPSO算法的性能總體上優于BQPSO和MBQPSO算法。對于函數Sphere 來說，QPSO效果最好，SPSO次之，MQPSO優于BQPSO和MBQPSO，BQPSO和MBQPSO的性能相當。對于Rosenbrock函數來說，MQPSO和MBQPSO的性能在各種情況下都優于SPSO和QPSO;BQPSO除了在粒子數為20、維數為20和30，粒子數為80、維數為20的三種情況下，其他所有的情況下都優于SPSO和QPSO算法。除MQPSO、BQPSO、MBQPSO每種情況下的最小值都小于SPSO和QPSO算法得到的結果，如對粒子數20、維數為10的情況，MQPSO的最小值為25.895 6，BQPSO的最小值為25.211 5，MBQPSO的最小值為26.239 9，都小于SPSO和QPSO的函數平均值。對于Rastrigin 函數，MQPSO、BQPSO、MBQPSO大多數情況下取得的函數平均值都小于SPSO和QPSO算法，QPSO算法的性能優于SPSO算法。對于Griewank 函數，MQPSO、BQPSO、MBQPSO在所有情況下取得的函數平均值都小于SPSO，80%的情況都優于QPSO算法，并且QPSO算法的性能優于SPSO算法。對于Schaffer函數來說，除了粒子數80、維數為2的情況下，QPSO算法的性能優于MQPSO、BQPSO、MBQPSO算法，其他情況下MQPSO、BQPSO、MBQPSO算法的性能優于QPSO算法。

圖1給出了粒子數為40、維數為20的情況下前四個函數對應的SPSO、 QPSO和GQPSO三種算法的收斂過程;對于Shaffer函數，維數為2的情況下SPSO、 QPSO和基于高斯擾動的QPSOC(GQPSO)三種算法的收斂過程。其中GQPSO描繪的是三種擾動下取得最小值的算法的收斂過程。對于函數Sphere來說，GQPSO描述的是MQPSO的收斂過程;對于函數Rosenbrock來說，GQPSO描述的是MQPSO的收斂過程;對于函數Rastrigin來說， GQPSO描述的是MQPSO的收斂過程;對于函數Griewank來說，GQPSO描述的是MBQPSO的收斂過程;對于函數Shaffer來說，在粒子數為40、維數為2的情況下，GQPSO描述的是BQPSO的收斂過程。

從圖1的收斂過程可以看出，QPSO和GQPSO的收斂速度大于SPSO的收斂速度，QPSO與GQPSO的收斂速度相似。總體上，GQPSO的性能優于QPSO的性能。

圖2給出了粒子數為20、維數為10的情況下QPSO算法和高斯擾動的QPSO算法對應的四個函數的多樣性變化曲線，多樣性的計算參考文獻[16]。從圖中可以看出，加入高斯擾動的QPSO算法提高了種群的多樣性。

4 結束語

所有的實驗結果顯示，QPSO算法和基于高斯擾動的QPSO算法在絕大多數測試函數上都優于SPSO算法。基于高斯擾動的QPSO算法優于QPSO算法，并且在平均最好位置上加入的擾動取得的結果最好，基于高斯擾動的QPSO算法的收斂速度最快，提高了種群的多樣性。

參考文獻:

[1]KENNEDY J，EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks.Piscata-way:IEEE Press，1995:1942-1948.

[2]Van den BERGH F. An analysis of particle swarm optimizers[D].Pretoria: University of Pretoria，2001.

[3]KENNEDY J. Small worlds and mega-minds:effects of neighborhood topology on particle swarm performance[C]//Proc of Congress on Evo-lutionary Computation.Washington DC:IEEE Press，1999:1931-1938.

[4]LOVBJERG M， RASUSSEN T K， KRINK T. Hybrid particle swarm optimizer with breeding and subpopulation[C]//Proc of the 3rd Genetic and Evolutionary Computation Conferences.Berlin:Springer，2001:469-476.

[5]KENNEDY J. Probability and dynamics in the particle swarm[C]//Proc of Congress on Evolutionary Computation.Washington DC:IEEE Press，2004:340-347.

[6]RIGET J， VESTERSTROM J S. A diversity-guided particle swarm optimizer:the ARPSO [R].Arhus，Denmark:Department of Computer Science，University of Aarhus:2002.

[7]SUN Jun， XU Wen-bo， FENG Bin. A global dearch dtrategy of guantum-behaved particle swarm optimization[C]//Proc of IEEE Confe-rence on Cybernetics and Intelligent Systems.[S.l.]:IEEE Press，2004:291-294.

[8]SUN Jun， XU Wen-bo， FANG Wei. Quantum-behaved particle swarm optimization with a hybrid probability distribution[C]//Proc of the 9th Pacific Rim International Conference on Artificial Intelligence.Berlin:Springer，2006:737-746.

[9]SUN Jun，XU Wen-bo，FANG Wei.A diversity-guided quantum-behaved particle swarm optimization algorithm[C]//Proc of IEEE International Conference on Simulated Evolution and Learning.Washington DC:IEEE Press，2006:497-504.

[10]LIU Jing， SUN Jun， XU Wen-bo. Improving quantum-behaved particle swarm optimization by simulated annealing[C]//Proc of International Conference on Intelligent Computing.Berlin:Springer，2006:130-136.

[11]COELHO L S. Novel Gaussian quantum-behaved particle swarm optimizer applied to electromagnetic design [J].Science， Measurement Technology.2007，11(5):290-294.

[12]LIU Jing，SUN Jun，XU Wen-bo， et al. Quantum-behaved particle swarm optimization with immune memory and vaccination[C]//Proc of IEEE International Conference on Granular Computing.Piscataway:IEEE Press，2006:453-456.

[13]CLERC M， KENNEDY J. The particle swarm:explosion，stability，and convergence in a multi-dimensional complex space [J].IEEE Trans on Evolutionary Computation，2002，6(1):58-73.

[14]SUN Jun， XU Wen-bo， FENG Bin. Adaptive parameter control for quantum-behaved particle swarm optimization on individual level[C]//Proc of IEEE International Conference on Systems， Man and Cybernetics.Piscataway:IEEE Press，2005:3049-3054.

[15]YAO Xin， LIU Yong， LIN Guang-ming. Evolutionary programming made faster [J]. IEEE Trans on Evolutionary Computation，1999，3(2):82-88.

[16]SUN Jun， XU Wen-bo， FANG Wei. A diversity-guided quantum-behaved particle swarm optimization algorithm[C]//Proc of IEEE International Conference on Simulated Evolution and Learning.Washington DC:IEEE Press，2006:497-504.