張愛偉，李金新

(杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州 310018)

?

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

張愛偉，李金新

(杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州 310018)

為解決標(biāo)準(zhǔn)粒子群優(yōu)化算法收斂速度慢、容易陷入局部最優(yōu)的問題，提出了一種基于標(biāo)準(zhǔn)粒子群優(yōu)化算法的改進算法.通過對標(biāo)準(zhǔn)粒子群算法的速度和位置更新公式的修改，增強了粒子在搜索后期的多樣性，提高了全局搜索能力，降低了陷入局部最優(yōu)的可能性.用3個基準(zhǔn)函數(shù)對改進算法進行驗證，比較分析表明：NPSO與SPSO比，收斂速度明顯提高，與可能出現(xiàn)不收斂的CFM比，一致收斂.

粒子群算法；收斂速度；搜索能力

0 引 言

粒子群算法(Particle Swarm Optimization，PSO)是James Kennedy和Russell Eberhart于1995年提出的一種群體智能算法.因其易理解、易實現(xiàn)，很多情況下比遺傳算法更有效，近年來受到國內(nèi)外學(xué)者的廣泛關(guān)注，并提出了很多改進算法[1]，如文獻[2]提出了一種自適應(yīng)學(xué)習(xí)粒子群算法，該算法通過4種不同的策略來處理不同類型的搜索空間，文獻[3]提出了雙心擾動量子粒子群優(yōu)化算法，對粒子的勢能中心和粒子群的重心進行自適應(yīng)柯西變異，發(fā)揮兩者在進化后期的協(xié)同引導(dǎo)能力，以提高進化后期粒子群對新空間的開拓能力.這些算法的提出，一定程度上推動了粒子群優(yōu)化算法的發(fā)展，而目前，對PSO算法的改進性研究主要體現(xiàn)在算法的參數(shù)選擇與設(shè)計、領(lǐng)域拓撲結(jié)構(gòu)、群體組織和進化、整合進化計算等混合算法幾個方面[4].同時，因粒子群優(yōu)化算法要設(shè)置的參數(shù)少，編程簡單，被廣泛應(yīng)用于訓(xùn)練神經(jīng)網(wǎng)絡(luò)[5]、最優(yōu)投資組合計算[6]和PID控制器的參數(shù)整定[7]等領(lǐng)域，這種改進算法與應(yīng)用相結(jié)合的模式漸進成為推動PSO算法發(fā)展的趨勢.本文則是從進化變異的角度來思考改進算法，基于前人的算法給出了一種可行的改進方案，即對標(biāo)準(zhǔn)PSO的位置更新公式和速度更新公式進行修改，改善其不足.

1 粒子群算法

1.1 標(biāo)準(zhǔn)粒子群算法

粒子群算法是對鳥群捕食行為的模擬，其基本思想是通過群體間的信息共享和個體之間的相互協(xié)作來尋找最優(yōu)解.將鳥群抽象為粒子群，假設(shè)一個D維空間，存在N個粒子，其中第i個粒子的位置為Xi=(xi1,xi2,xi3,…,xiD)，速度為Vi=(vi1,vi2,vi3,…,viD)，其中i=1,2,3,…,N.把第i個粒子在尋優(yōu)過程中所搜索到的歷史最優(yōu)位置記為Pi=(pi1,pi2,pi3,…,piD)，簡寫為pbest，將整個粒子群搜索到的最優(yōu)位置記為Pg=(pg1,pg2,pg3,…,pgD)，簡稱gbest.James Kennedy和Russell Eberhart早期提出的PSO算法的位置和速度更新公式如下：

(1)

xid(t+1)=xid(t)+vid(t+1).

(2)

其中，i=1,2,3,…,N，d=1,2,3,…,D，r1和r2是分別是兩個獨立的，在[0,1]上均勻分布的隨機數(shù).

為了能更好地控制算法的尋優(yōu)能力，文獻[8]在早期的粒子群算法的速度更新方程中,引入慣性權(quán)重ω，更新后的公式如下：

(3)

xid(t+1)=xid(t)+vid(t+1).

(4)

ω的值一般為非負值，當(dāng)ω較大時，后一速度對前一速度影響較大，全局搜索能力強，局部搜索能力弱，當(dāng)較小時，局部搜索能力強，但是全局搜索能力會較弱，為此文獻[8]提出了線性遞減策略，即將ω的值設(shè)置為如下：

ω(t)=(ωini-ωend)(Tmax-t)/Tmax+ωend.

(5)其中，Tmax為最大迭代次數(shù)，ωini為初始慣性權(quán)重，ωend為到最大迭代次數(shù)時的慣性權(quán)重，典型的取值為ωini=0.9，ωend=0.4.式(3)、式(4)稱之為標(biāo)準(zhǔn)粒子群算法(Standard Particle Swarm Optimization，SPSO)[9].

1.2 帶收縮因子的粒子群算法

1999年，Maurice Clerc采用數(shù)學(xué)證明，建議在速度更新公式上采用收縮因子η來使得PSO算法收斂，更新公式如下：

(6)

xid(t+1)=xid(t)+vid(t+1).

(7)

2 改進粒子群算法

粒子群算法提出以來，已有許多改進的算法，如采用優(yōu)化約束粒子群算法、向量評價微分遺傳算法、GA-EO算法、Pareto存檔進化策略[10]、并行單前沿遺傳算法等[11].本文在SPSO的速度和位置更新公式的基礎(chǔ)上，試圖引入復(fù)合校正修改來提高算法的收斂速度，即保證前期的全局搜索能力，又提高后期跳出局部最優(yōu)值的可能性.速度更新公式的修正如下：

(8)

其中，T為(0,1)之間的常數(shù)，r3為服從[0,1]上的隨機數(shù)，其他參數(shù)采用標(biāo)準(zhǔn)算法.

要提高算法的收斂速度，即要求vid(t+1)越快的收斂到0越好，為此在式(3)的前面乘以T-r3來增強收斂速度，同時通過T的適當(dāng)取值來提高粒子群算法在前期的局部搜索能力，保證其處于最優(yōu)值序列中.此外，為了不過分的影響前期的全局搜索能，給速度公式加上r3vid(t),保證速度公式能夠在提高收斂速度的同時，又擁有著合理的局部和全局搜索能力.

當(dāng)算法進入后期搜索時，粒子可能會被局部最優(yōu)值限制，失去多樣性，這樣當(dāng)大多數(shù)粒子被限制在局部最優(yōu)時可能導(dǎo)致算法整體上陷入局部最值，為此將位置更新公式添加擾動因子，在后期搜索是能夠提高粒子多樣性，為跳出局部最優(yōu)值提供可能，更新后的公式如下：

xid(t+1)=ωxid(t)+vid(t+1)(r4-ω)+c3(r5-0.5).

(9)

這樣，將式(8)、式(9)結(jié)合起來就是本文改進的新粒子群算法(New Particle Swarm Optimization，NPSO).NPSO的算法流程如下：

1)初始化種群規(guī)模N，在一定范圍內(nèi)隨機產(chǎn)生N個位置和速度；

2)將每個粒子的初始化值帶入到適應(yīng)函數(shù)中計算適應(yīng)值；

3)找出每個粒子的最好位置和找出整個種群的最好值；

4)根據(jù)新算法的位置更新公式和速度更新公式進行更新；

5)計算個體最優(yōu)和全局最優(yōu)值，判斷是否達到允許誤差范圍或最大迭代次數(shù)，如果沒有則跳到步驟2，否則跳出迭代，輸出結(jié)果，算法結(jié)束.

3 算法驗證

本文通過3個基準(zhǔn)函數(shù)來驗證新算法的可行性，并通過與SPSO算法、CFM算法比較來說明算法改進的合理性.

3.1 基準(zhǔn)函數(shù)

這3個函數(shù)的各個分量的隨機初始化值的區(qū)間如表1所示.

表1 3個測試函數(shù)的最優(yōu)解、最優(yōu)值和搜索區(qū)間

3.2 參數(shù)設(shè)置

涉及到的參數(shù)是搜索空間維度設(shè)為10，種群規(guī)模設(shè)置為30，最大迭代次數(shù)設(shè)置為30 000，對每個函數(shù)獨立運行20次.設(shè)置c1=c2=2，c3=10-5,ω由0.9到0.4線性減少，T=0.5,對于CFM算法取η=0.729.

設(shè)置函數(shù)允許的誤差如表2所示.

表2 函數(shù)允許的誤差

3.3 仿真結(jié)果

為了從收斂性和準(zhǔn)確性兩個方面來驗證新算法的正確性，通過設(shè)置允許誤差，使用3種算法進行對比驗證，在達到精度后停止運行，來驗證新算法的收斂速度.按每個函數(shù)每個算法獨立運行20次，記錄每次的迭代次數(shù)，結(jié)果如表3所示.

表3 3種算法對3個基準(zhǔn)函數(shù)在允許誤差范圍迭代次數(shù)的平均值及最優(yōu)值

從表3中可以很明顯的看出，在收斂速度上，算法CFM對3個函數(shù)的收斂速度都是最快的，而算法SPSO則是最慢的，平均在6 000次以上才能收斂到誤差范圍內(nèi).相比于這2種算法，新算法NPSO對3個函數(shù)的收斂雖然比CFM慢，但是從平均收斂次數(shù)上來看，差距不是很大，而且比SPSO小很多.從最優(yōu)值上來看，NPSO的最優(yōu)值除Griewanks函數(shù)外，都是最小的.因此，從總體上來說，新算法NPSO在收斂數(shù)度和最優(yōu)值上的改善還是比較明顯的，特別是與CFM算法對于Ackley函數(shù)的作用相比，一定是收斂的.為了能夠更清楚的顯示比較結(jié)果，將20次實驗結(jié)果繪制成的曲線如圖1所示.

圖1 3種算法對3個函數(shù)20次內(nèi)完成收斂的迭代次數(shù)曲線圖

從圖1中能直觀地看出，3種算法對函數(shù)的收斂能力的優(yōu)劣.對于3個基準(zhǔn)函數(shù)，SPSO算法的收斂速度最慢，而且收斂也不穩(wěn)定，最低要4 000多次，而最高要達到近9 000次才會收斂，并且從表3中的最優(yōu)值也可以看出，SPSO算法的最優(yōu)值基本上都是最大的.相比于SPSO算法，CFM算法則是收斂最快也是最穩(wěn)定的，但是在實驗中，CFM算法對Ackley函數(shù)出現(xiàn)過收斂失敗的情況，在20次的實驗中出現(xiàn)了3次收斂失敗，失敗率有15%，這也說明了，CFM算法雖然收斂快但是犧牲了準(zhǔn)確度，這會導(dǎo)致算法性能比較差.而相比于這2種算法，NPSO算法在收斂速度上較SPSO算法有了顯著的提高，雖然略慢于CFM算法的收斂速度，但在最優(yōu)值這個準(zhǔn)確度上，NPSO算法基本上是最小的，而且，相比于CFM算法，NPSO沒有出現(xiàn)不收斂的情況，這也可以說明在一定程度上NPSO算法的性能要好于CFM算法.算法在不設(shè)置誤差范圍時對3個函數(shù)收斂曲線如圖2所示，迭代總次數(shù)為30 000次.

圖2 不設(shè)置誤差范圍時，3個函數(shù)收斂曲線圖

從圖3中可以發(fā)現(xiàn)，在不設(shè)置允許誤差范圍時，3種算法對3個函數(shù)的最終收斂結(jié)果是一樣的，都能基本上達到理論值，但是在收斂速度上SPSO是不如其他2種算法的，而且從圖3中也能看出，SPSO算法會出現(xiàn)收斂最優(yōu)值在一定時期內(nèi)基本不變的情況，這說明可能陷入了局部最優(yōu)值，而NPSO算法，基本上都是快速的收斂到最優(yōu)值，這也說明了NPSO算法有著很好的跳出局部最優(yōu)值的能力.

4 結(jié)束語

本文在標(biāo)準(zhǔn)粒子群算法的基礎(chǔ)上提出了一種新的改進算法NPSO，通過對標(biāo)準(zhǔn)粒子群算法的速度和位置更新公式的修正，來改進算法的收斂速度.與SPSO比收斂速度明顯提高，與可能出現(xiàn)不收斂的CFM比，NPSO一定收斂，只是收斂速度略慢.總的來說，NPSO算法在收斂速度、最優(yōu)值以及跳出局部最優(yōu)值的能力方面有著很大的改善和提高，因此，本文的這種改進是可行的.下一步工作就是如何在改進收斂速度的同時，提高最優(yōu)值和跳出局部最優(yōu)能力，進一步的完善算法的性能.

[1]張建科,劉三陽,張曉清.改進的粒子群算法[J].計算機工程與設(shè)計,2007,28(17):4215-4116.

[2]LI C,YANG S,NGUYEN T T. A self learning particle swarm optimizer for global optimization problems[J]. Systems,Man,and Cybernetics,Part B:Cybernetics, IEEE transactions on, 2012,42(3):627-646.

[3]王安龍,何建華,陳松,等.雙心擾動量子粒子群優(yōu)化算法研究[J].計算機工程,2014,40(7):193-196.

[4]覃大勝.粒子群優(yōu)化算法的改進及其應(yīng)用研究[D].廣州：暨南大學(xué),2015.

[5]ZHAO Y, ZU W, ZENG H. A modified particle swarm optimization via particle visual modeling analysis[J]. Computers & Mathematics with Applications, 2009, 57(11): 2022-2029.

[6]王雪峰,葉中行.基于PSO的最優(yōu)投資組合計算方法[J].工程數(shù)學(xué)學(xué)報,2007,24(1):31-36.

[7]周陽花,魏敏,孫偉.基于權(quán)重QPSO算法的PID控制器參數(shù)優(yōu)化[J].計算機工程與應(yīng)用,2010,46(5):224-228.

[8]李鵬.一種改進的粒子群優(yōu)化算法[D].長沙：湖南師范大學(xué),2008.

[9]白艷敏.一種改進的粒子群算法[J].科技信息,2012(5):40-41.

[10]OLTEAN M, GROSAN C, ABRAHAM A, et al. Multiobjective optimization using adaptive Pareto archived evolution strategy[C]//5th International Conference on Intelligent Systems Design and Applications (ISDA’05). IEEE, 2005: 558-563.

[11]馮金芝，陳興，鄭松林.一種改進的多目標(biāo)粒子群優(yōu)化算法及其應(yīng)用[J].計算機應(yīng)用研究,2014,31(3):675-678.

An Improved Particle Swarm Optimization Algorithm

ZHANG Aiwei, LI Jinxin

(SchoolofElectronicInformation,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

In order to solve the problem of slow convergence and easy to fall into local optimum, an improved algorithm based on the standard particle swarm optimization algorithm is proposed. By modifying the velocity update formula and the position update formula of the standard particle swarm optimization algorithm, the diversity of the particle in the late period of search is improved, and the global searching ability is improved, and the possibility of falling into local optimum is reduced. 3 benchmark functions are used to validate the improved algorithm, and the results are compared with the other two particle swarm optimization algorithms. The experimental results show that the new algorithm has some improvement in the convergence rate and the local optimum.

particle swarm algorithm; convergence rate; search ability

10.13954/j.cnki.hdu.2016.06.003

2016-04-25

張愛偉(1989-)，男，江蘇淮安人，碩士研究生，電路與系統(tǒng).通信作者：李金新副教授，E-mail：ljx@hdu.edu.cn.

TP301.6

A

1001-9146(2016)06-0010-05