張俊溪， 張嘉桐，張玉梅

(1 西安航空學院 車輛工程系， 陜西 西安 710077；

2 西北大學 文化遺產(chǎn)學院， 陜西 西安 710069；

3 陜西師范大學 計算機科學學院， 陜西 西安 710119)

?

一種改進的粒子群優(yōu)化算法

張俊溪1， 張嘉桐2，張玉梅3*

(1 西安航空學院 車輛工程系， 陜西 西安 710077；

2 西北大學 文化遺產(chǎn)學院， 陜西 西安 710069；

3 陜西師范大學 計算機科學學院， 陜西 西安 710119)

摘要：在粒子群優(yōu)化算法的基礎(chǔ)上，將粒子群優(yōu)化算法的速度更新公式中種群最優(yōu)位置用所有個體的平均值與最優(yōu)粒子有限鄰居個體的平均值加權(quán)求和代替；通過將種群平均適應度和整體最優(yōu)位置適應度的比值作為適應度函數(shù)，并引入了加速系數(shù)；得到改進的粒子群優(yōu)化聚類算法既能夠充分參考當前粒子的最優(yōu)信息，也參考了所有個體的最優(yōu)信息和當前最優(yōu)粒子有限鄰居的最優(yōu)信息，在進化過程中可以通過新的適應度函數(shù)自適應地調(diào)整全局搜索和局部搜索的比重對粒子的影響，對算法收斂速度影響較小的前提下較好地提高了收斂精度。最后，選取了4組具有不同分布特征的Benchmark函數(shù)作為驗證函數(shù)，試驗結(jié)果表明,新算法具有較好的收斂特性。

關(guān)鍵詞:粒子群優(yōu)化算法； 適應度； 更新； 收斂速度；收斂精度

MR subject classification: 68Q45

粒子群優(yōu)化算法(particle swarm optimization, PSO) 由Kennedy 和 Eberhart[1-2]于1995年提出。該算法結(jié)構(gòu)簡單、運算過程中參數(shù)調(diào)整較少且實現(xiàn)較為簡便，自誕生以來在學術(shù)界影響廣泛，并取得了大量的研究成果[3-7]。經(jīng)典的粒子群優(yōu)化算法主要關(guān)注2個信息，即位置和速度信息。二者的調(diào)整依賴當前粒子的最優(yōu)位置和種群的最優(yōu)位置信息，對粒子群優(yōu)化算法的改進基本上圍繞這二者展開。Shi和Eberhart通過在基本PSO算法中引入“慣性”和“約束”兩個因子獲得帶有慣性權(quán)重的PSO算法[1]。Clerc提出了收斂因子模型PSO算法的速度遞推方程[2]。Lovbjerg等將進化算法中的交叉操作引入HPSO算法模型[3]。吳曉軍等[4]通過定義PSO粒子搜索中心，并計算局部最優(yōu)解和全局最優(yōu)解的概率密度，使搜索中心在二者之間均勻分布，提出均勻搜索粒子群優(yōu)化算法；胡旺等[5]通過簡化公式消去速度信息，僅依賴位置信息控制進化過程，大大提高了收斂效率；文獻[6]分析了粒子軌跡對算法收斂性的影響，文獻[7]深入分析了慣性權(quán)重的更新和種群拓撲結(jié)構(gòu)的改進。

粒子群算法在進化過程中既參考了種群整體的位置信息又參考了當前粒子的位置信息，如果種群信息采用全體粒子的位置平均值則稱為全局版PSO(GPSO)；如果種群信息采用當前粒子的有限鄰居的位置平均值則稱為局部版PSO(LPSO)[4-5]。采用全局版PSO，則存在著初期收斂速度快但容易陷入局部最優(yōu)的問題，而采用局部版PSO則存在收斂精度高但收斂速度變慢的問題。無論是從參數(shù)進行改進還是從位置信息和速度信息進行改進，都可以不同程度地提高其某些指標，達到改進算法的目的。本文試圖通過將全局版PSO和局部版PSO相結(jié)合，使算法在進化的過程中同時參考種群最優(yōu)信息和當前粒子信息，同時加入當前粒子的有限鄰居信息，使算法在進化的過程中能夠保證收斂速度不會大幅度降低的前提下，提高其搜索精度，避免過早陷入局部最優(yōu)。

1基本粒子群優(yōu)化算法及其

相關(guān)改進

1.1經(jīng)典粒子群優(yōu)化算法

PSO算法通過模擬鳥群和魚群群體覓食的運動行為，將鳥或魚定義為種群的粒子，每個粒子的基本信息用其幾何位置和速度向量表示，粒子在覓食的過程中既參考自己的運動方向，同時也參考整個種群所經(jīng)歷的最優(yōu)方向來調(diào)整自己的覓食行為。粒子的覓食行為可以用公式(1)、(2)來表示，其中pbest和gbest稱為個體極值和全局極值，分別是第i個粒子曾經(jīng)達到的最優(yōu)位置和種群所經(jīng)歷過的最優(yōu)位置。粒子通過這2個極值來更新自己。

(1)

xid=xid+vid,

(2)

其中：d為搜索空間的維度；r1和r2是服從U(0,1)分布的隨機數(shù)；學習因子c1和c2為非負常數(shù); vid∈[-vmax,vmax]，vmax是由用戶設定的速度約束常數(shù)。如果取xgd為整個種群的最優(yōu)位置，則上述算法被稱為全局版PSO(GPSO)，如果令x0d為第i個粒子的有限鄰居搜索到的最優(yōu)位置，并取xgd=x0d，則算法被稱為局部版PSO(LPSO)[5]。

1.2粒子群優(yōu)化算法的相關(guān)改進

自PSO算法提出以來，在改善PSO性能方面展開了大量的研究工作[10-17]?；綪SO算法經(jīng)過Shi[1，9]等人的改進，引入了慣性權(quán)重w，形成了目前應用最為廣泛的一種形式：

vi(t+1)=wvi(t)+c1r1(t)[pi(t)-xi(t)]+c2r2(t)[pg(t)-xi(t)],

(3)

xi(t+1)=xi(t)+vi(t+1),

(4)

其中:w為慣性系數(shù)，典型取值為w=0.4或w=0.9,該算法側(cè)重先全局后局部的搜索方式，很大程度上改善了算法的搜索能力和收斂精度;隨機變量r1和r2以及學習因子c1和c2與經(jīng)典粒子群算法中的取值相同;pi(t)為當前粒子的最優(yōu)位置信息；pg(t)為整個種群的最優(yōu)位置信息；vi∈[-vmax,vmax],vmax是由用戶設定的約束速度的常數(shù)[10]。Clerc建議采用收縮因子來保證PSO算法收斂[6,11]：

(5)

其中，“收縮因子”的計算按照(6)式進行，即

(6)

使用Clerc的收縮因子方法時,通常取φ=4.1,從而使收縮因子χ=0.729。該算法不再需要限制最大速度vmax。

此外，對PSO的改進主要集中于與其他進化算法的結(jié)合，如遺傳算法(GA)、遺傳規(guī)劃(GP)和免疫算法等，目標是提高算法收斂的速度以及收斂的精度。Angeline[1]將GA的選擇算子引入PSO中，通過選擇每一代中的較優(yōu)粒子進行迭代，可以提高算法的優(yōu)化性能；李寧[13]、呂振肅[14]等人提出帶變異算子的PSO算法，通過變異算子處理部分極值點問題來增強全局搜索能力，同時又不降低收斂速度和收斂精度。高鷹等[15]則將免疫算法引入到PSO中，改善了算法的收斂速度。以上算法都有各自的優(yōu)缺點，而且都通過引入其他算子來優(yōu)化算法性能，且往往增加了算法的時間復雜度[12，16]。

2改進的粒子群優(yōu)化算法

2.1粒子群的位置更新優(yōu)化

從粒子群優(yōu)化算法的標準公式(3)和(4)中可以看出，粒子根據(jù)pi(t)(i=1、2、…、N)和pg(t)來更新自己的速度和位置，在進化的過程中如果選擇pg(t)為有限鄰居的平均值，則算法搜索效率低；如果選擇pg(t)為種群所有粒子的平均值，則算法容易陷入局部最優(yōu)，因此應該充分利用當前最優(yōu)粒子的鄰居信息以及整個種群所有粒子的最優(yōu)位置信息來更新算法，就可以兼顧搜索過程中對信息的充分利用。可以對(3)式作如下變化，如(7)式所示：

vi(t+1)=ωxi(t)+c1r1(pi(t)-xi(t))+

c2r2(α(p0(t)-xi(t))+

(1-α)(pg(t)-xi(t)))，

(7)

xi(t+1)=vi(t)+xi(t+1),

(8)

其中:隨機變量r1和r2以及學習因子c1和c2與經(jīng)典粒子群算法中的取值相同;pi(t)為當前粒子的最優(yōu)位置信息；pg(t)為整個種群的最優(yōu)位置信息；P0為粒子Pi的有限鄰居位置信息，Pg為全局粒子的位置信息，基本粒子群算法中的Pg(t)分量被P0(t)和Pg(t)的加權(quán)平均取代。這樣粒子的搜索中心從Pi和Pg之間變成Pi和P0與Pg之間的某個中心值之間，如圖1所示，pi′為P0和Pg的加權(quán)平均位置信息。

圖1　改進后粒子的搜索路徑與搜索中心

則(7)和(8)式就構(gòu)成了新的自適應PSO算法模型，定義

其中:N為種群中個體的總數(shù);m為當前粒子的有限個鄰居粒子的個數(shù)。

2.2粒子搜索中心的概率密度分布

在粒子群優(yōu)化算法中，加速系數(shù)c1和c2分別控制個體粒子的位置信息和種群的位置信息對粒子速度的影響。根據(jù)PSO算法的特點，進化初期個體粒子的更新應起主導作用，這樣可以使搜索空間增加，不易陷入局部極值；而在進化后期，種群的位置信息應起主導作用，這樣可以提高搜索的速度和精度。文獻[17]對加速系數(shù)做了如下改進：

令

c1(t)=1-exp(-β|Fa(t)-Fg(t)|)，

(9)

c2(t)=1-c1(t)，

(10)

其中:Fa(t)為粒子群的平均適應度;Fg(t)為整體最優(yōu)位置pg(t)的適應度。二者在進化初期有較大的差，而后期差別越來越小， 為控制系數(shù)。因此,該模型中，c1(t)非線性減小，c2(t)則非線性增大。

假定r1、r2為常數(shù)，則粒子搜索中心位于pi和pg之間[4]；假定r1和r2為隨機數(shù)，則令c=c1/c2，pi=0，pg=1，X、Y代表隨機變量r1和r2，則令

(11)

計算公式(11)的聯(lián)合概率密度函數(shù)[4]，如公式(12)所示，從中可以看出，z′并不服從均勻分布，且在1/(1+c)處取得極大值，圖2為c取不同值時的概率密度函數(shù)圖形，其中h為c取不同值對應的概率密度，縱坐標為概率密度，橫坐標為p0-pg的歸一化參數(shù)。

(12)

圖2　概率密度函數(shù)圖形

(7)式可以擴展為

vi(t+1)=wxi(t)+c1(t)r1(pi(t)-xi(t))+

c2(t)v2(α(p0(t)-xi(t))+

(1-α)(pg(t)-xi(t)))。

(13)

(13)式和(8)式構(gòu)成了新的自適應粒子群優(yōu)化算法的模型(new adaptive PSO,NAPSO)。

根據(jù)文獻[12]，分別對粒子群的位置信息進行分析，可以得到(14)式，該式中對于種群的最優(yōu)位置信息pg只能取全體種群粒子的平均值或者當前粒子的有限鄰居粒子的平均值，根據(jù)本文提出的新的自適應PSO算法(NAPSO)，可以擴展為式(15)，同時參考2個全局位置信息。

(14)

(15)

通過大量實驗證明，當α=0.3,w=0.5,β=10時，算法具有較好的收斂性能。

從式(15)中可以得出：當p0=pg時，即種群的最優(yōu)位置信息選擇相同的種群粒子，則(13)式又還原為(7)式，同全局版或局部版PSO。

3實驗結(jié)果與分析

通過選取4組Benchmark函數(shù)，測試新的自適應粒子群優(yōu)化算法(NAPSO)的搜索性能。Benchmark函數(shù)可以有效考察新型算法對不同類型問題的優(yōu)化性能，本文選取的4組基準測試函數(shù)涵蓋單峰函數(shù)和多峰函數(shù)，可以考察算法的收斂速度和收斂精度。分別用全局版PSO(GPSO)、局部版PSO(LPSO)和NAPSO做驗證試驗，慣性因子w按照慣例取0.8，全局版PSO和局部版PSO的加速系數(shù)c1和c2都取1，進化次數(shù)設為2 000，運行50次所得函數(shù)最優(yōu)值點的平均值和最優(yōu)值的平均值作為算法的衡量指標。

所用的Benchmark函數(shù)及其參數(shù)選擇如表1所示，由于維度增大，自變量取值范圍增大會增加算法的復雜度，本文對部分函數(shù)的參數(shù)做了微調(diào)，便于簡化運算過程。

表1　用于測試的基準函數(shù)及其參數(shù)

實驗結(jié)果如圖3所示，橫坐標為迭代次數(shù)，縱坐標為適應度的對數(shù)值，標號Ⅰ、Ⅱ、Ⅲ分別表示LPSO、GPSO和NAPSO對表1中4個函數(shù)的優(yōu)化曲線。本實驗所選的4個函數(shù)最優(yōu)值均為零，從圖3a可以看出，對于Rastrigr函數(shù)的仿真結(jié)果中，NAPSO算法的收斂效率最高，在第800步就已經(jīng)收斂到極小值，且最終收斂的結(jié)果更趨近于零值。而LPSO的收斂效率較差，在1 800步時收斂到極小值。圖3b是對Griewank函數(shù)的仿真結(jié)果，該函數(shù)為多峰函數(shù)，且極值分布具有不均勻性，故3種算法對該函數(shù)的仿真結(jié)果均比第一個函數(shù)的仿真結(jié)果差，從收斂曲線可以看出，收斂的最終結(jié)果誤差較大，且最終收斂的步數(shù)均在1 600步之后，整體上收斂的效率為NAPSO高于GPSO，GPSO高于LPSO。圖3c為SchwefelProblem函數(shù)，該函數(shù)與Griewank函數(shù)相比，極值點分布更加不均勻，因此仿真的結(jié)果次于Rastrigr函數(shù)和SchwefelProblem函數(shù)。收斂的極值距零點差別較大，接近于1。圖3d為Rosenrock函數(shù)的仿真結(jié)果，該函數(shù)為較為復雜的單峰函數(shù)，3種算法對該函數(shù)的仿真結(jié)果收斂效率差別較小，總體上NAPSO的收斂效率略高于LPSO，LPSO略高于GPSO。

從4個函數(shù)的仿真結(jié)果來看，NAPSO的收斂效率總體上高于經(jīng)典PSO算法，且更適合于極值點均勻分布的函數(shù)。對于極值點非均勻分布的函數(shù)，由于粒子在搜索的過程中較多地參考了“社會”信息，而使得收斂速度相對下降，而導致部分粒子收斂于局部極值點。但總體上本文提出的NAPSO算法在綜合考慮了當前最優(yōu)粒子位置信息、種群最優(yōu)位置信息以及當前粒子鄰居位置信息的情況下，能夠更好地全面利用進化過程中的位置信息，使算法盡量在“認知”和“社會”信息之前取得折中值。所得結(jié)果可以看出，NAPSO算法的穩(wěn)定性是最優(yōu)的。

圖3GPSO、LPSO和NAPSO算法在4個函數(shù)下的收斂性分析

Fig.3Convergence analysis of GPSO、LPSO and NAPSO in the 4 function

4結(jié)論

本文在經(jīng)典粒子群優(yōu)化算法的基礎(chǔ)上提出了一種新的自適應粒子群優(yōu)化算法，通過將粒子群算法的速度更新公式進行改進，在種群最優(yōu)位置信息的基礎(chǔ)上增加了當前最優(yōu)粒子的鄰居位置信息，并將二者的加權(quán)平均值作為位置信息的進化依據(jù)；同時將種群平均適應度和整體最優(yōu)位置適應度的比值作為適應度函數(shù)，引入加速系數(shù)，得到新的自適應粒子群算法模型。該模型在進化的過程中，可以自適應地調(diào)整“認知”部分和“社會”部分對粒子的影響，在進化前期以“認知”部分為主導，加快收斂速度，進化后期以“社會”部分為主導，提高收斂的精度。

4組標準Benchmark函數(shù)涵蓋了不同分布特點的單峰和多峰函數(shù)，仿真結(jié)果表明本文提出的算法在收斂效率和收斂精度方面有一定的優(yōu)勢，尤其對于極值點均勻分布的函數(shù)具有較好的優(yōu)越性。但是該算法增加了權(quán)重因子和控制系數(shù)，這兩個參數(shù)需要通過多次試驗獲得，因此對于極值點分布特點差別較大的優(yōu)化問題處理結(jié)果表現(xiàn)不一致。

參考文獻：

[1] SHI Y H, EBERHART R C. A modified particle swarm optimizer[C]∥IEEE International Conference of Evolutionary Computation, Anchorage:IEEE, 1998: 69-73.

[2] CLERC M. The swarm and queen towards a deterministic and adaptive particle swarm optimization[C]∥Proceedings of Congress on Evolutionary Computation, Washinton D C:IEEE, 1999: 782-786.

[3] LOVBJERG M, RASMUSSEN T K, KRINK T. Hybrid particle swarm optimization with breeding and subpopulations[C]∥IEEE International Conference on Evolutionary Computation, San Diego:IEEE, 2000: 1217-1222.

[4] 吳曉軍, 楊戰(zhàn)中, 趙明. 均勻搜索粒子群算法[J]. 電子學報,2011,39(6)：1261-1266.

[5] 胡旺, 李志蜀. 一種更簡化而高效的粒子群優(yōu)化算法[J]. 軟件學報,2007,18(4)：861-868.

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

[7] MAHFOUF M, CHEN M Y, LINKENS D A. Adaptive weighted swarm optimization for multi-objective optimal design of alloy steels[C]∥Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 2004: 762-771.

[8] KENNEDY J, EBERHART R C. Particle swarm optimization[C].∥Proceeding of the IEEE Conference on Neural Networks,New York:Institute of Electrical and Electronics Engineers,1995:1942-1948.

[9] SHI Y H, EBERHART, R.C. Empirical study of particle swarm optimization[C]∥Proceeding of the IEEE Congress on Evolutionary Computation,Washinton D C:IEEE,1999:1945-1950.

[10] SHI Y H, EBERHART R C. Parameter selection in particle swarm optimization[C]∥Proceeding of 7th Annual Conference on Evolutionary Programming.Washington D C:IEEE,1998:591 -600.

[11] CLERC M. The swarm and queen: towards a deterministic and adaptive particle swarm optimization[C]∥Proceedings of the IEEE Congress on Evolutionary Computation,Washinton D C:IEEE, 1999:1951-1957.

[12] HIGASHI N, IBA H. Particle Swarm Optimization with Gaussian Mutation[C]∥The 2003 Congress on Evolutionary Computation. Piscataway, New Jersey: IEEE, 2003: 72-79.

[13] 李寧，劉飛，孫德寶. 基于帶變異算子粒子群優(yōu)化算法的約束布局優(yōu)化研究[J]. 計算機學報, 2004,27(7)：897-903.

[14] 呂振肅, 侯志榮.自適應變異的粒子群優(yōu)化算法[J].電子學報,2004, 32(3):416-420.

[15] 高鷹, 謝勝利.免疫粒子群優(yōu)化算法[J].計算機工程與應用,2004, 40(6):4-6.

[16] 鄒彤, 李寧, 孫德寶, 等. 帶陰性選擇的粒子群優(yōu)化算法[J]. 華中科技大學學報(自然科學版), 2006，34(2):87-90.

[17] 高鷹. 一種自適應擴展粒子群優(yōu)化算法[J]. 計算機工程與應用, 2006(15)：12-15.

〔責任編輯宋軼文〕

An improved particle swarm optimization algorithm

ZHANG Junxi1, ZHANG Jiatong2， ZHANG Yumei3*

(1 Department of Vehicle Engineering, Xi′an Aeronautical University,Xi′an 710077, Shaanxi, China;2 College of Cultural Heritage, Northwest University, Xi′an 710069, Shaanxi, China;3 School of Computer Science, Shaanxi Normal University, Xi′an 710119, Shaanxi, China)

Abstract:Based on the basic particle swarm optimization algorithm, the average of best particles is replaced by the weighted sum of the average of best particles and the average of the neighbor particles in the speed update formula. Using the ratio of average fitness of the whole particles and the average fitness of best particle as the fitness function, and the acceleration factor is introduced, a new adaptive PSO algorithm is obtained. The new algorithm used both the information of present particle and the information of the whole particles and the neighbors of present particle. In the process of evolution, it can adjust the global search and the local search component by the new model adaptively. So the convergence speed and precision can be improved. Experiments on 4 benchmark functions demonstrate that the new algorithm is more efficient.

Keywords:particle swarm optimization algorithm; fitness; update; convergence speed; convergence precision

中圖分類號：TP18

文獻標志碼：A

*通信作者：張玉梅，女，副教授，博士。E-mail:zym0910@tom.com

基金項目：陜西省重點科技創(chuàng)新團隊項目(2014KTC-18)；陜西省自然科學基金重點項目(2014JZ021)；陜西省自然科學基金(2014JM8353)

收稿日期：2015-06-16

doi:10.15983/j.cnki.jsnu.2016.02.124

文章編號：1672-4291(2016)02-0015-07

第一作者： 張俊溪，女，講師，主要研究方向為模式識別與智能系統(tǒng)。E-mail:zhang_junxi@126.com