一種加權(quán)變異的粒子群算法

徐 燈，傅 晶，王文豐，2，章 香，韓龍哲，2，方宗華，董健華

(南昌工程學(xué)院 1.信息工程學(xué)院;2.江西省水信息協(xié)同感知與智能處理重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330099)

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是由Eberhart[1]等根據(jù)鳥群覓食行為所提出。PSO具有很好的生物社會(huì)背景，易于理解、參數(shù)少且易實(shí)現(xiàn)，在科學(xué)研究與工程實(shí)踐中備受關(guān)注，譬如在路徑規(guī)劃[2]、圖像處理[3]和洪水預(yù)報(bào)[4]等眾多領(lǐng)域中都得到了廣泛應(yīng)用。然而，PSO算法卻也存在著一些不足之處，例如容易陷入早熟現(xiàn)象、后期收斂速度較慢以及收斂精度不高等問題。

為此，國內(nèi)外專家學(xué)者提出了許多不同改進(jìn)策略的粒子群算法。Yan[5]等將隨機(jī)學(xué)習(xí)機(jī)制與Levy飛行策略的特點(diǎn)相結(jié)合，在粒子的位置更新過程中，讓粒子頻繁短距離變換和偶爾長距離跳躍來提高種群的多樣性。Chen[6]等引入正余弦加速度系數(shù)有效加強(qiáng)局部搜索能力，再對(duì)粒子進(jìn)行反向?qū)W習(xí)，加入服從正余弦變化的慣性權(quán)重加速因子，提高了收斂的速度。文獻(xiàn)[7]在速度更新方式中加入了局部最優(yōu)位置，動(dòng)態(tài)調(diào)整個(gè)體最優(yōu)、局部最優(yōu)以及群體最優(yōu)在速度更新公式中的權(quán)重，改進(jìn)了PSO算法的優(yōu)化性能。Hao[8]等在改進(jìn)粒子群算法時(shí)采用了算術(shù)交叉，共享粒子之間的信息來幫助早熟粒子跳出局部最優(yōu)，提高了算法的精度。Zhao[9]等提出將種群分為正常和早熟兩種狀態(tài)，當(dāng)種群處于正常狀態(tài)按標(biāo)準(zhǔn)PSO公式進(jìn)化，在早熟狀態(tài)則引入矢量高斯學(xué)習(xí)策略以增強(qiáng)種群多樣性。張強(qiáng)[10]等對(duì)種群的進(jìn)化方式做了細(xì)分，結(jié)合了4種不同的方式使粒子進(jìn)化具有自主性，提高了算法的精度和收斂速度。上述算法分別在粒子的位置更新、加速度因子、動(dòng)態(tài)調(diào)整權(quán)重、種群的優(yōu)劣劃分等單方面策略對(duì)標(biāo)準(zhǔn)PSO算法進(jìn)行改進(jìn)，雖然都在一定程度上改善了粒子多樣性、時(shí)間復(fù)雜度、易陷于早熟等問題，但是，大部分算法缺乏整體維度的考慮，在解決了粒子多樣性等問題的同時(shí)可能增加了時(shí)間復(fù)雜度等問題，且均存在不同程度易于陷入早熟、收斂速度較慢以及收斂精度低的問題，特別是在高維函數(shù)優(yōu)化問題上較為明顯。

有鑒于此，本文提出了一種加權(quán)變異的粒子群算法(Weighted Variation Particle Swarm Optimization，WVPSO)。該算法引入自適應(yīng)權(quán)重、自適應(yīng)學(xué)習(xí)因子以及自然選擇三種加速粒子收斂，算術(shù)交叉加權(quán)策略提高粒子的多樣性以及高斯擾動(dòng)增大粒子跳出局部最優(yōu)的能力，并通過仿真實(shí)驗(yàn)對(duì)其性能進(jìn)行了驗(yàn)證分析。

1 基本粒子群算法

PSO初始化為一群隨機(jī)粒子，種群中的每個(gè)粒子都代表一個(gè)給定問題的潛在解。這些粒子通過調(diào)整飛行方向來引導(dǎo)自己，利用自身和其它群體成員的最優(yōu)值來找到問題的最佳答案。

假設(shè)在一個(gè)D維的搜索空間中，有N個(gè)粒子組成一個(gè)群落，其中第i個(gè)粒子表示為Xi=(xi1，xi2，…，xiD)，第i個(gè)粒子的“飛行”速度記為vid，第i個(gè)粒子目前為止搜索到的最優(yōu)位置稱為個(gè)體最優(yōu)值，記為：Pbest=(pi1，pi2，…，piD)，i=1，2，…，N；整個(gè)粒子種群目前為止搜索到的最優(yōu)位置稱為群體最優(yōu)值，記為：gbest=(pg1，pg2，…，pgD)。得到個(gè)體最優(yōu)值和群體最優(yōu)值后，粒子便根據(jù)如下公式更新自己的速度和位置：

vid=ω×vid+c1r1(pid-xid)+c2r2(pgd-xid)，

(1)

xid=xid+vid，

(2)

式中的c1，c2為學(xué)習(xí)因子，也稱加速常數(shù)；r1，r2為0～1之間的隨機(jī)數(shù)。

2 WVPSO算法

針對(duì)PSO算法易于陷入早熟、收斂速度較慢和收斂精度不高等問題，本文提出了WVPSO算法，主要從以下三個(gè)方面進(jìn)行改進(jìn)：

(1)為保證算法尋優(yōu)策略的全局搜索能力的同時(shí)平衡其局部搜索能力，本文提出一種自適應(yīng)權(quán)重和自適應(yīng)學(xué)習(xí)因子的方法，對(duì)式(1)中的權(quán)重w和學(xué)習(xí)因子c1，c2自動(dòng)調(diào)整；

(2)為增加粒子種群的多樣性、提高算法的搜索精度，本文提出一種加權(quán)變異的方法，在每次評(píng)估適應(yīng)值后加入算術(shù)交叉和自然選擇機(jī)制來改變粒子的位置和速度；

(3)對(duì)于算法易于陷入早熟的問題，在陷入早熟時(shí)加入高斯擾動(dòng)，讓粒子能夠盡量地跳出局部最優(yōu)值。

2.1 自適應(yīng)權(quán)重和自適應(yīng)學(xué)習(xí)因子

在PSO算法迭代的過程中，權(quán)重在算法迭代前期需要讓粒子的步長變化更快，從而讓粒子盡可能早地達(dá)到全局最優(yōu)值所在的區(qū)域，而在算法迭代后期則應(yīng)該減少步長的變化，讓粒子在該區(qū)域內(nèi)作精準(zhǔn)的搜索使之找到全局最優(yōu)解。對(duì)于學(xué)習(xí)因子，在算法迭代前期應(yīng)該自我學(xué)習(xí)率占比高，群體學(xué)習(xí)率占比低；隨著迭代不斷進(jìn)行，自我學(xué)習(xí)比率要逐步降低，而群體學(xué)習(xí)比率則逐漸提高。這樣既可以加快算法的收斂速度，又可以提高算法的收斂精度。基于上述思想，本文提出了一種自適應(yīng)權(quán)重和自適應(yīng)學(xué)習(xí)因子的方法：

(3)

(4)

(5)

式(3)～(5)中，it和MaxIt分別為算法當(dāng)前的迭代次數(shù)和最大的迭代次數(shù)；rand為0～1之間的隨機(jī)數(shù)；c1up，c1low為自我學(xué)習(xí)因子的上下界；c2up，c2low為群體學(xué)習(xí)因子的上下界。式(3)中，權(quán)重w在算法迭代前期盡可能取最大值，從而使算法步長得到更快的變化；隨著算法的不斷迭代，權(quán)重則逐漸減小，以滿足算法的自適應(yīng)權(quán)重需求；式(4)在算法進(jìn)行的過程中是一個(gè)遞減的函數(shù)，式(5)則是一個(gè)遞增的函數(shù)，符合自適應(yīng)學(xué)習(xí)因子的思想要求。

2.2 加權(quán)變異

由于標(biāo)準(zhǔn)PSO算法收斂速度比較慢、迭代后期種群多樣性降低，使得算法最后難以搜索到全局最優(yōu)值。對(duì)此，本文加入算術(shù)交叉和自然選擇策略來提高粒子多樣性、增強(qiáng)收斂速度與精度。對(duì)于變異粒子的比例，通過以下方式選擇：

[|P1|，|P2|，…，|PN|].

(6)

將所有粒子適應(yīng)值的絕對(duì)值從小到大按照式(6)方式排列，并按照式(7)進(jìn)行分割，式(7)如下：

(7)

將式(6)中的適應(yīng)值分成ξ1，ξ2，ξ3，ξ4四個(gè)部分，由于粒子群算法存在的隨機(jī)性，因此將粒子的適應(yīng)值分為好(ξ1，ξ2)與不好(ξ3，ξ4)兩個(gè)群體。其中ξ1，ξ4各占總體的20%；ξ2，ξ3各占總體的30%。這里使用交叉操作作用于ξ2，ξ3，融合好粒子與差粒子，不僅能夠產(chǎn)生具有多樣性的后代，而且促使差粒子向好粒子移動(dòng)；使用自然選擇作用于ξ1，ξ4，直接將差粒子ξ4的速度與位置直接替換為好粒子ξ1的速度與位置，類似于將整個(gè)種群縮小20%，從而大大加快粒子的收斂速度。具體策略如下：

(1)算術(shù)交叉：根據(jù)文獻(xiàn)[11]的交叉公式，本文改進(jìn)算術(shù)交叉公式如下所示：

xξ3=rand×xξ2+(1-rand)×xξ3，

(8)

vξ3=rand×vξ2+(1-rand)×vξ3.

(9)

xξ2，xξ3為式(7)中ξ2，ξ3處的粒子位置；vξ2，vξ3為式(7)中ξ2，ξ3處的粒子速度；rand為0～1之間的隨機(jī)數(shù)。

(2)自然選擇：通過選擇好的粒子來替換差的粒子，增加粒子的收斂速度，具體方式如下：

(10)

xξ1，xξ4為式(7)中ξ1，ξ4處的粒子位置；vξ1，vξ4為式(7)中ξ1，ξ4處的粒子速度。

2.3 高斯擾動(dòng)

隨著算法的迭代，當(dāng)全局最優(yōu)值所在的區(qū)域遠(yuǎn)離當(dāng)前種群的最優(yōu)值時(shí)，粒子容易向錯(cuò)誤的方向?qū)W習(xí)，此時(shí)粒子將極易陷入早熟。為了讓算法跳出局部最優(yōu)，在后期迭代時(shí)加入高斯擾動(dòng)。如果當(dāng)前適應(yīng)值經(jīng)過幾次迭代后不再發(fā)生變化，則判斷算法陷入早熟，這時(shí)加入高斯擾動(dòng)，讓粒子震蕩，使其擺脫局部最優(yōu)，因此在迭代初期加入高斯擾動(dòng)策略。

2.4 算法流程

WVPSO算法流程如下所示：

Step1 隨機(jī)初始化粒子的位置和速度，設(shè)定相關(guān)參數(shù)；

Step2 根據(jù)式(3)～(5)計(jì)算慣性權(quán)重w，學(xué)習(xí)因子c1和c2；

Step3 計(jì)算粒子群的適應(yīng)值，根據(jù)適應(yīng)值的絕對(duì)值從小到大按照式(6)方式排列，并使用式(7)分割；

Step4 使用算術(shù)交叉式(8)～(9)和自然選擇式(10)策略將分割后的粒子進(jìn)行重新替換；

Step5 根據(jù)式(1)～(2)更新粒子速度和位置，更新每個(gè)粒子歷史最優(yōu)位置pbest和群體最優(yōu)值gbest。判斷是否陷入早熟，如果陷入早熟則加入高斯擾動(dòng)；

Step6若滿足終止條件，則輸出最優(yōu)值，否則轉(zhuǎn)入步驟(2)，進(jìn)入下一次尋優(yōu)。

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證WVPSO算法的性能，本文選取7種具有代表性的群智能算法進(jìn)行對(duì)比，分別為：PSO，LinwPSO[13]，DGLCPSO[14]，PSOGSA[7]，AMBPSO[10]和(DE/best/1，DE/rand/1)[12]。實(shí)驗(yàn)環(huán)境為：Windows10操作系統(tǒng)，Intel酷睿i5處理器，主頻3.2GHz，8G內(nèi)存，開發(fā)工具為Matlab R2016b。

表1給出了7個(gè)經(jīng)典的測(cè)試函數(shù)，其中4個(gè)單峰函數(shù)測(cè)試算法的收斂速度與收斂精度，3個(gè)多峰函數(shù)測(cè)試算法跳出局部最優(yōu)的能力。各個(gè)算法的參數(shù)設(shè)置為：粒子種群個(gè)數(shù)為50；每個(gè)算法獨(dú)立運(yùn)行10次，每次實(shí)驗(yàn)最大適應(yīng)度評(píng)估次數(shù)為1000；WVPSO的自身學(xué)習(xí)因子下限c1low=0.5，上限c1up=2.5，群體學(xué)習(xí)因子下限c2low=0.8，上限c2up=3.5。

表1 7個(gè)經(jīng)典的測(cè)試函數(shù)

針對(duì)本文提出的3種改進(jìn)方案，每一種改進(jìn)方案均在標(biāo)準(zhǔn)PSO基礎(chǔ)上做實(shí)驗(yàn)對(duì)比分析，記引入自適應(yīng)權(quán)重和自適應(yīng)學(xué)習(xí)因子改進(jìn)的粒子群算法為ⅠPSO，引入算術(shù)交叉和自然選擇機(jī)制改進(jìn)的粒子群算法為ⅡPSO，引入高斯擾動(dòng)改進(jìn)的粒子群算法為ⅢPSO。其中對(duì)4個(gè)測(cè)試函數(shù)單峰和多峰函數(shù)做對(duì)比分析，結(jié)果如表2所示。

表2 不同算法的收斂精度及穩(wěn)定性對(duì)比

圖1給出了算法在函數(shù)f1，f2，f3，f4，f7尋優(yōu)過程的迭代曲線，圖中橫坐標(biāo)t表示迭代次數(shù)，fitness表示算法所得適應(yīng)值。

由表2和圖1可得出，無論在最優(yōu)結(jié)果、均值還是方差上，3種改進(jìn)方式都明顯優(yōu)于標(biāo)準(zhǔn)的粒子群算法。從3種改進(jìn)的結(jié)果來看，引入算術(shù)交叉和自然選擇機(jī)制改進(jìn)的策略比另兩種策略得出的結(jié)果精度要高出1～32個(gè)數(shù)量級(jí)，在函數(shù)f1，f2，f4的收斂速度上也是第2種策略更快，驗(yàn)證了本文采取的3種策略在綜合性能上更佳。

由表3可以看出，WVPSO在7個(gè)測(cè)試函數(shù)上最優(yōu)值、均值和方差都具有明顯的優(yōu)勢(shì)。具體來講，在單峰函數(shù)f1，f2，f3和多峰函數(shù)f4上，盡管WVPSO在最優(yōu)值上沒有達(dá)到極值0，但各個(gè)指標(biāo)依相比其它算法優(yōu)勢(shì)明顯，其中函數(shù)f1，f4在最優(yōu)值上比AMBPSO算法至少提高了29和3個(gè)數(shù)量級(jí)，說明WVPSO在收斂精度和穩(wěn)定性方面比AMBPSO算法要好，這得益于WVPSO采用自然選擇策略，實(shí)現(xiàn)了快速收斂并優(yōu)化粒子的目標(biāo)，并且采用算術(shù)交叉保證了粒子的多樣性和靈活性。在多峰函數(shù)f7優(yōu)化上，WVPSO的最優(yōu)值和均值都優(yōu)于其它7個(gè)智能算法，只有方差微弱于AMBPSO；在多峰函數(shù)f5和f6上，WVPSO都能夠在最優(yōu)值上達(dá)到了全局最優(yōu)值0，遠(yuǎn)遠(yuǎn)優(yōu)于其它6個(gè)智能算法，在多峰函數(shù)f6優(yōu)化上，雖然WVPSO和AMBPSO在最優(yōu)值上達(dá)到了極值0，但本文算法均值與方差都為0，可以看出WVPSO對(duì)比AMBPSO在多峰函數(shù)f6優(yōu)化上性能更加穩(wěn)定。這說明了本文算法對(duì)復(fù)雜的多峰函數(shù)具有非常好的效果，即引入高斯擾動(dòng)的粒子變異策略大幅度提高了粒子跳出早熟的能力。

圖1 各函數(shù)尋優(yōu)曲線迭代圖

表3 不同算法的收斂精度及穩(wěn)定性對(duì)比

對(duì)表3所得實(shí)驗(yàn)數(shù)據(jù)進(jìn)行Friedman檢驗(yàn)，所得結(jié)果中，WVPSO的所得秩均值評(píng)價(jià)指標(biāo)最小(1.21)，驗(yàn)證了WVPSO算法的優(yōu)化性能比其它7種智能粒子群算法更好，綜合優(yōu)化性能更強(qiáng)。

圖2給出了不同算法在函數(shù)f1～f7尋優(yōu)過程的迭代曲線，圖2中橫坐標(biāo)t表示迭代次數(shù)，fitness表示算法所得適應(yīng)值。從圖2中不難發(fā)現(xiàn)，對(duì)比其它7個(gè)算法，WVPSO在收斂速度和精度這兩個(gè)重要的評(píng)價(jià)指標(biāo)上均有明顯優(yōu)勢(shì)。在單峰函數(shù)f1～f3、多峰函數(shù)f4，f7上，雖然WVPSO和AMBPSO兩個(gè)算法在最優(yōu)值、均值和方差上無法作出準(zhǔn)確比較，但是在迭代曲線圖中可以清晰地看到，WVPSO迭代曲線的下降速度明顯優(yōu)于AMPSO的下降速度。其較好的收斂特性得益于算法采用了自適應(yīng)權(quán)重和學(xué)習(xí)因子，使得粒子在算法迭代前期步長變化更快，能夠盡可能早地達(dá)到全局最優(yōu)值所在的區(qū)域。在算法迭代后期則減少步長的變化，讓粒子在該區(qū)域內(nèi)做精準(zhǔn)的搜索使之找到全局最優(yōu)解，同時(shí)自然選擇策略使粒子的多樣性提高，使得較差的粒子更多的向位置更優(yōu)的粒子移動(dòng)，極大地提高了粒子搜索效率；引入高斯擾動(dòng)的粒子變異策略也加大粒子跳出局部最優(yōu)的能力，從而保證了粒子的搜索精度。

圖2 各函數(shù)的尋優(yōu)曲線迭代圖

綜上所述，在處理高維函數(shù)尋優(yōu)的問題上，對(duì)比其它7個(gè)群智能算法，WVPSO算法在精度、收斂速度和穩(wěn)定性上都有著極大的優(yōu)勢(shì)。

4 結(jié)束語

本文針對(duì)標(biāo)準(zhǔn)PSO算法容易陷入早熟、收斂速度慢及收斂精度低的問題，提出了一種加權(quán)變異的粒子群算法WVPSO，通過對(duì)標(biāo)準(zhǔn)PSO算法粒子的位置和速度加權(quán)變異，以及慣性權(quán)重和學(xué)習(xí)因子的自適應(yīng)調(diào)整進(jìn)行改進(jìn)，不僅增加了粒子種群的多樣性，而且加快了算法的收斂速度，提高了收斂精度。從仿真實(shí)驗(yàn)結(jié)果可以看出，本文提出的算法均優(yōu)于其它的幾個(gè)群智能算法，在高維函數(shù)尋優(yōu)問題的處理上具有很好的性能和穩(wěn)定性，且在部分函數(shù)成功跳出局部最優(yōu)，達(dá)到了全局最優(yōu)值。但是本文算法并未完全擺脫陷入早熟的問題，如何更有效地使算法跳出局部最優(yōu)將是下一步研究的重點(diǎn)。