張媛媛， 高興寶

(陜西師范大學數(shù)學與信息科學學院， 陜西 西安 710062)

0 引 言

作為進化算法之一的粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是一種模擬自然界的生物活動以及群體智能的全局隨機搜索算法. 由于粒子群優(yōu)化算法的模型和計算比較簡單，全局優(yōu)化能力強， 且能夠解決高維多目標優(yōu)化問題，因此已成功應用于函數(shù)優(yōu)化、模糊系統(tǒng)控制、神經(jīng)網(wǎng)絡訓練等.

自從1995年PSO被提出后，國內外專家在其理論、算法改進及應用方面的研究都取得了很大的進展.關于PSO的數(shù)學基礎、收斂性和穩(wěn)定性的研究，2002年法國數(shù)學家Clerc與Kennedy[1]在基本粒子群的基礎上設計了壓縮因子的參數(shù)，大大提高了收斂速度；Kadirkamanathan對PSO的研究和數(shù)學分析由靜態(tài)分析深入到了動態(tài)分析[2].關于PSO拓撲結構的研究，Kennedy提出了如星型結構、環(huán)型結構、齒形結構、金字塔結構、馮．諾曼結構等，并比較了它們在PSO中的性能[3]，2006年Kennedy和Mendes將這些拓撲結構在Fully Informed的PSO上進行了測試[4].在這些靜態(tài)的拓撲結構的基礎上，研究者們在不同的迭代階段用不同的拓撲結構動態(tài)地改變算法的探索和開發(fā)能力，在保持種群多樣性和算法收斂性上取得了動態(tài)的變化和平衡，提高了算法的整體性能[5].另外，研究者還通過將其他搜索算法與PSO算法相結合，得到了許多不同性能的PSO混合算法，如Chen等人將遺傳算法中的變異算子和交叉算子引入到PSO算法中[6，7]，增加種群的多樣性以提高種群的搜索能力；Zhang和Xie將PSO算法與差分進化算法進行了混合[8].以上對PSO的改進僅限于結構和與其他算法的混合，本文從粒子群的個體出發(fā)，不但對迭代后粒子與上一代粒子的適應值進行評價，還評價了它們的位置，根據(jù)評價結果對每個粒子進行不同的操作，從而提高了整個粒子群的搜索速度和求解最優(yōu)解的精度.

1 粒子群優(yōu)化算法

在粒子群優(yōu)化算法中，通過隨機產(chǎn)生一定數(shù)目的粒子作為問題搜索空間的可行解，然后進行迭代搜索， 直到找到最優(yōu)粒子.每個粒子都有自己的位置和速度，其優(yōu)劣依據(jù)適應值來評價，即根據(jù)問題定義的適應度函數(shù)的值來評價；粒子根據(jù)自己的歷史最優(yōu)和群體的全局最優(yōu)解決定下一次的位置和速度，進行不斷的更新，使其在問題搜索空間進行探索和開發(fā)， 最終找到全局最優(yōu)解.

設在一個D維目標搜索空間中，有N個粒子組成一個群體，第i個粒子的位置、速度和個體最優(yōu)可用向量分別表示為：

群體探索到的最優(yōu)位置為：gbest=(gbest1,gbest2,…,gbestD)，則其速度和位置的更新公式如下：

(1)

(2)

其中w是慣性權值，c1和c2是加速系數(shù)，r1和r2是兩個[0.1]區(qū)間的隨機數(shù)，t是迭代次數(shù).

根據(jù)文獻[9]，公式(1)中除第1項為粒子前一次迭代的速度外，其余兩項為“認知項(cognition)”和“社會項(social)”，分別表示粒子自身的思考和對社會的認識.前一次迭代速度起到平衡全局和局部搜索的能力，“認知項(cognition)”使粒子有足夠強的全局搜索能力，避免陷入局部極小，而“社會項(social)”體現(xiàn)了粒子間的信息共享.三項的共同作用使粒子在搜索空間有較好的飛行速度. 此外當w=1時， 算法稱為基本粒子群算法.基本粒子群算法中，由于速度更新后的值變得很大，從而使粒子的位置變化也很大而偏離搜索空間. 針對此缺點，Shi等引入了如下線性遞減權值w來平衡探索和開發(fā)能力：

w=wmax-i·(wmax-wmin)/Gmax

(3)

其中wmax、wmin分別為最大和最小慣性權值，Gmax是最大迭代次數(shù).稱此算法為標準粒子群算法.

2 雙評價粒子群算法

2.1 雙評價粒子群優(yōu)化算法的思想

基于標準粒子群優(yōu)化算法， 對迭代后的每個粒子的位置和適應值與上一代粒子的位置和適應值進行比較， 然后根據(jù)比較結果對粒子進行變異.

2.2 具體操作

在分析標準粒子群的迭代軌跡后，將迭代過程首先分為探索階段和開發(fā)階段， 即根據(jù)經(jīng)驗0～0.2 為探索階段，0.2 ～1為開發(fā)階段；其次在不同階段根據(jù)評價結果對性質劣的粒子進行不同的變異.

在此，分如下3種情形對粒子進行相應的處理.

在探索階段, 首先計算當前每個粒子的適應值(f(xi(t)))和到個體最優(yōu)粒子的距離d1以及上一代粒子的適應值(f(xi(t-1)))和到個體最優(yōu)粒子的距離d2.

(1) 若f(xi(t))d2，則認為當前第i個粒子有好的探索能力， 讓它繼續(xù)迭代.

(2) 若f(xi(t))>f(xi(t-1))且d1

(3)若f(xi(t))f(xi(t-1))且d1>d2,則認為當前第i個粒子和上一代第i個粒子各自占有優(yōu)勢，線性組合它們，即xi(t)=q·xi(t)+(1-q)·xi(t-1)，q=0.5,然后繼續(xù)迭代.

類似于探索階段，在開發(fā)階段，首先迭代后計算當前每個粒子的適應值(f(xi(t)))和到全局最優(yōu)粒子的距離d3以及與上一代粒子的適應值(f(xi(t-1)))和到全局最優(yōu)粒子的距離d4.

(1) 若f(xi(t))

(3) 若f(xi(t))d4，或f(xi(t))>f(xi(t-1))且d3

3 算法的測試

為比較兩個優(yōu)化算法進化的效果.本文對6個函數(shù)進行了測試，其中函數(shù)f1、f2、f3為單峰函數(shù)，函數(shù)f4、f5、f6為多峰函數(shù)，且都有一個極值點. 測試函數(shù)如下：

根據(jù)實驗，算法參數(shù)設置如下：種群規(guī)模為N=30， 粒子的維數(shù)為D=30， 最大迭代步數(shù)相應為Gmax=1 000，加速因子c1=2，c2=2.6，線性下降的慣性權重w的變化范圍為[0. 2, 0. 4]. 兩種算法對測試函數(shù)的進化軌跡如圖1至圖6所示.

圖1 Sphere model function 圖2 Quadric function

圖3 Rosenbrock function 圖4 Schwefel function

圖5 Rastrigin function 圖6 Griewank function

表1測試結果中SPSO代表標準粒子群優(yōu)化算法， IPSO代表雙評價粒子群優(yōu)化算法.表中數(shù)據(jù)顯示了SPSO和IPSO兩種算法對函數(shù)f1(x)、f2(x)、f3(x)、f4(x)、f5(x)、f6(x)數(shù)值仿真的測試結果與精確解的比較.從實驗結果看到，對函數(shù)f1(x)、f2(x)、f3(x)、f4(x)、f5(x)、f6(x)，雙評價粒子群優(yōu)化算法在標準粒子群優(yōu)化算法的基礎上，它的探索速度和開發(fā)精度都有一定的提高.

表1 測試結果

4 結束語

針對標準粒子群算法對迭代后粒子的優(yōu)劣并不進行評價的缺陷，本文提出了雙評價粒子群優(yōu)化算法. 從實驗結果可以看出雙評價粒子群優(yōu)化算法不僅加快了粒子群的探索速度， 還提高了開發(fā)精度.然而如何依據(jù)問題的特點來劃分探索和開發(fā)階段，以提高算法的性能仍是有待實驗及研究的問題.

參考文獻

[1] M Clerc, J Kennedy. The particle swarm-explosion, stability and convergence in a multidimensional complex space[J]. IEEE Trans. Evol. Comput.,2002,6(2):58-73.

[2] V Kadirkamanathan, K Selvarajah, P J Fleming. Stability analysis of the particle dynamics in particle swarm optimizer[J].IEEE Trans. Evol. Comput., 2006, 10(3):245-255.

[3] J Kennedy, R Mendes. Population structure and particle swarm performance[J]. Proc. IEEE Congr. Evol. Comput., 2002，(1):1 671-1 676.

[4] J Kennedy, R Mendes. Neighborhood topologies in fully informed and best-of-neighborhood particle swarms[J]. IEEE Trans. on Syst. Man, Cybern., C, 2006,36(4):515-519.

[5] J J Liang, P N Suganthan. Dynamic multi-swarm particle swarm optimizer[J]. Swarm Intelligence Symp., 2005,(6):124-129.

[6] Y P Chen, W C Peng, M C Jian. Particle swarm optimization with recombination and dynamic linkage discovery[J]. IEEE Trans. on Syst., Man,Cybern., B, 2007,37(6):1 460-1 470.

[7] P S Andrews. An investigation into mutation operators for particle swarm optimization[J]. Proc. IEEE Congr. Evol. Comput., 2006，(5):1 044-1 051.

[8] W J Zhang, X F Xie. DEPSO: hybrid particle swarm with differential evolution operator[J]. Proc. IEEE Congr.Sys., Man,Cybern., 2003, (10): 3 816-3 821.

[9] Shi Y, Eberhart R C. A Modified Particle Swarm Optimizer[C]. Proceedings of the IEEE . Congress on Evolutionary Computation, 1998:69-73.