一種多樣性驅(qū)動的自適應(yīng)粒子群優(yōu)化算法

宗 敏，楊玉群，徐 剛*

(南昌大學(xué)a.數(shù)學(xué)系，江西 南昌 330031；b.附屬中學(xué)，江西 南昌 330047)

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是對鳥群覓食行為過程的模擬而提出的全局隨機(jī)搜索算法[1]。相對遺傳算法、模擬退火等算法而言，PSO具有算法簡單，參數(shù)少和易實(shí)現(xiàn)等優(yōu)點(diǎn)，一直是群智能優(yōu)化方法研究領(lǐng)域的熱點(diǎn)。仿真實(shí)驗(yàn)表明，PSO作為一種并行優(yōu)化算法，可以用于解決非線性、不可微和多峰值的復(fù)雜優(yōu)化問題，并已廣泛用于函數(shù)優(yōu)化、預(yù)測和運(yùn)輸問題等科學(xué)和工程領(lǐng)域[2-5]，但它存在陷入局部最優(yōu)和早熟問題，為此國內(nèi)外的研究者做了大量的工作，提出了各種改進(jìn)算法[6-11]。種群多樣性是影響PSO算法性能的一個(gè)重要因素，為避免PSO算法的缺陷，一些研究者提出了通過控制種群多樣性提高算法性能的方法[11-12]。

PSO算法搜索過程中，種群多樣性大，能提高算法的全局搜索能力，但局部搜索能力降低；種群多樣性小，局部搜索能力提高，但全局搜索能力降低。為了防止粒子陷入局部最優(yōu)和早熟，本文提出了一種多樣性驅(qū)動的自適應(yīng)粒子群優(yōu)化(Diversity driven adaptive particle swarm optimization,DDA-PSO)算法。本算法采用線性遞減慣性權(quán)重機(jī)制加速種群收斂；當(dāng)種群多樣性降低到一定的程度，利用多樣性驅(qū)動速度(DDV)策略進(jìn)行勘探，幫助粒子跳出局部最優(yōu)和防止早熟。采用的機(jī)制和策略自適應(yīng)地相互轉(zhuǎn)換，使得算法的勘探與開拓達(dá)到平衡。實(shí)驗(yàn)結(jié)果表明，DDA-PSO算法能有效地避免陷入局部最優(yōu)和防止早熟，PSO算法的性能得到顯著提高。

1 PSO算法與相關(guān)算法

1.1 PSO算法設(shè)搜索空間為D維，種群大小為N，第i個(gè)粒子位置表示為向量xi=(xi1,xi2,…,xiD)，迄今為止個(gè)體最優(yōu)位置為pi=(pi1,pi2,…,piD),整個(gè)粒子群迄今為止最優(yōu)位置為g=(g1,g2,…,gi)，第i個(gè)粒子的速度表示為向量vi=(vi1,vi2,…,viD)。粒子在進(jìn)化過程中速度和位置更新公式分別如下[1]：

(1)

(2)

其中i=1,2,…,N，d=1,2,…,D；c1和c2為加速常數(shù)，通常設(shè)為相同值；rand為[0,1]內(nèi)的隨機(jī)數(shù)；ω為慣性權(quán)重。

1.2 PSO-LDIW算法

從式(1)可以看出，ω表示保留原粒子速度的程度；ω較大，粒子速度較大，種群多樣性也較大，算法全局搜索能力較強(qiáng)，但局部搜索能力較弱；ω較小，粒子速度較小，種群多樣性也較小，這樣算法局部搜索能力較強(qiáng)，但全局搜索能力較弱。為了加快PSO算法的收斂速度，Shi[6]針對ω提出了基于慣性權(quán)重線性遞減機(jī)制的粒子群優(yōu)化(PSO-LDIW)算法，慣性權(quán)重線性遞減的表達(dá)式如下：

(3)

其中ωmax為最大慣性權(quán)重；ωmin為最小慣性權(quán)重；t為迭代次數(shù)；Tmax為最大迭代次數(shù)。

2 多樣性驅(qū)動的自適應(yīng)粒子群優(yōu)化算法

2.1 種群多樣性度量

在PSO算法中，種群多樣性用于描述單個(gè)粒子在搜索區(qū)域的分布，是影響PSO算法全局性能的一個(gè)重要因素。PSO算法在搜索時(shí)，通常伴隨著種群多樣性的缺失，致使算法陷入局部最優(yōu)和早熟。一般來說，種群多樣性越好，算法的全局收斂概率越高。本文利用種群多樣性作為每個(gè)粒子感知到的一種群體信息，并用它來指導(dǎo)粒子的行為。種群多樣性的度量公式[14]如下：

(4)

(5)

2.2 種群速度度量

由于式(1)包含了隨機(jī)項(xiàng)，速度vi(t)會產(chǎn)生波動，所有粒子的平均速度的絕對值(va)可以作為種群速度度量來了解所有粒子的敏捷度。va表達(dá)式[15]如下：

va較大值意味著粒子當(dāng)前位置關(guān)于個(gè)體最優(yōu)位置和全局最優(yōu)位置發(fā)生了較大的改變，從而能提高算法的勘探能力，保持了種群的多樣性。va較小值意味著粒子在個(gè)體最優(yōu)位置和全局最優(yōu)位置附近進(jìn)行搜索，種群多樣性較小。

2.3 多樣性驅(qū)動速度策略

根據(jù)基本PSO算法的收斂性分析[13]，隨著迭代運(yùn)行，粒子之間變得越來越靠近，種群多樣性減小，影響算法的全局搜索能力，導(dǎo)致算法陷入局部最優(yōu)和早熟。粒子速度是改變種群多樣性的根本原因，如果種群多樣性變小，可以增大粒子速度來提高種群多樣性。根據(jù)PSO算法的全局搜索特性，隨著算法的迭代運(yùn)行，希望粒子的速度由大到小逐漸減小，這能保證前期種群多樣性大，有利于全局搜索，后期種群多樣性小，有利于局部搜索，達(dá)到了勘探和開拓的平衡。鑒于上面的分析，為了防止局部收斂或早熟，需要多樣性驅(qū)動速度(DDV)策略，幫助粒子跳出局部最優(yōu)或防止早熟。在DDV策略中，本文使用的多樣性驅(qū)動速度(vD)函數(shù)如下：

vD(t)=vmax·e-kDiv(t)

(7)

其中vmax是最大速度限制值。k>0是一個(gè)系統(tǒng)參數(shù)，用于確定算法搜索性能對種群多樣性的依賴程度。

根據(jù)式(7)可以看出，種群多樣性較小時(shí)，vD較大；當(dāng)種群多樣性較大時(shí)，vD較小。當(dāng)算法陷入局部最優(yōu)或早熟時(shí)，粒子速度較小，同時(shí)種群多樣性也較小，這時(shí)需要通過vD來驅(qū)動粒子速度使其增大，從而提高種群多樣性。為了能夠根據(jù)多樣性的變化驅(qū)動粒子速度(即步長)自適應(yīng)改變，使粒子跳出局部最優(yōu)和防止早熟，本文根據(jù)vD與va比較，通過改變權(quán)重ω，使得粒子的步長發(fā)生改變，從而達(dá)到種群多樣性驅(qū)動速度的目標(biāo)。慣性權(quán)重值變化如下，

(8)

其中ωini是慣性權(quán)重的最大值；ωfin是慣性權(quán)重的最小值；Δω是慣性重量的步長。根據(jù)文獻(xiàn)[11]建議，ωini=0.9，ωfin=0.3。

當(dāng)多樣性迅速減小時(shí)，應(yīng)及時(shí)增大慣性權(quán)值，提高粒子速度，增強(qiáng)算法全局探索能力；反之，當(dāng)多樣性不斷增大時(shí)，應(yīng)減小慣性權(quán)值，降低粒子速度，加強(qiáng)算法局部開拓能力。同時(shí)應(yīng)該注意，進(jìn)化后期的慣性權(quán)值不應(yīng)取值過大，否則種群無法精確尋優(yōu)且算法很難收斂。

2.4 種群多樣性設(shè)置

DDA-PSO算法啟動多樣性驅(qū)動速度策略，種群多樣性會不斷地提高，但種群多樣性不宜一直增大，否則粒子很難進(jìn)行精細(xì)搜索，因此需要設(shè)定種群多樣性最大值(di)，一旦種群多樣性達(dá)到最大值，多樣性驅(qū)動速度策略停止執(zhí)行。根據(jù)PSO算法的搜索特性，DDA-PSO算法的種群多樣性在早期應(yīng)較大，有利于進(jìn)行勘探；種群多樣性在后期應(yīng)較小，以便進(jìn)行開拓。鑒于上述分析，di使用隨時(shí)間線性遞減的方式，其表達(dá)式如下：

(9)

其中d1和d2分別是種群多樣性的最大值和最小值。

2.5 提出的算法

DDA-PSO算法分為吸引階段和多樣性驅(qū)動階段。在吸引階段，DDA-PSO算法采用慣性權(quán)重線性遞減機(jī)制，既加速算法收斂，又能進(jìn)行局部精細(xì)搜索，這正好是PSO-LDIW算法[6],但種群多樣性逐漸降低，從而粒子容易陷入局部最優(yōu)。為了能預(yù)估PSO算法陷入局部最優(yōu)，利用計(jì)數(shù)器(記作NC)跟蹤最佳適應(yīng)值一直未改變的次數(shù)。當(dāng)計(jì)數(shù)超過設(shè)定次數(shù)時(shí)，DDA-PSO算法切換到多樣性驅(qū)動階段。在多樣性驅(qū)動階段，DF-APSO采用DDV策略提高粒子速度，從而增加種群多樣性，幫助粒子跳出局部最優(yōu)或防止早熟。一旦種群多樣性達(dá)到設(shè)定值，多樣性驅(qū)動階段停止，DDA-PSO算法再次切換到吸引階段，重復(fù)此過程，直到達(dá)到最大迭代次數(shù)或滿足停止標(biāo)準(zhǔn)。為清晰起見，DDA-PSO算法的主要步驟描述如下：

步驟1：對粒子的位置，速度和系統(tǒng)參數(shù)進(jìn)行初始化；

步驟2：計(jì)算粒子的適應(yīng)度值，根據(jù)適應(yīng)度值確定個(gè)體最優(yōu)位置和全局最優(yōu)位置；

步驟3：執(zhí)行PSO-LDIW算法進(jìn)行搜索；

步驟4：如果全局最優(yōu)值保持不變，NC加1，否則NC設(shè)置為0；

步驟5：如果NC大于等于設(shè)定值，停止PSO-LDIW算法搜索，采用DDV策略；

步驟6：更新粒子速度、位置、個(gè)體極值和全局最優(yōu)值，根據(jù)式(9)計(jì)算di；

步驟7：根據(jù)式(4)計(jì)算Div，如果Div>=di，停止DDV策略；如果Div

步驟8：判斷算法終止準(zhǔn)則是否滿足，如果滿足，算法停止，否則轉(zhuǎn)向步驟3。

3 數(shù)值實(shí)驗(yàn)及分析

3.1 基準(zhǔn)函數(shù)和比較算法

為了提供一個(gè)全面的比較，6個(gè)具有不同特性的基準(zhǔn)函數(shù)[11]用于實(shí)驗(yàn)測試。表1列出了這些基準(zhǔn)函數(shù)的簡要說明。根據(jù)它們的特性，6個(gè)基準(zhǔn)函數(shù)包括單峰函數(shù)(f1)、多峰函數(shù)(f2,f3,f4)、旋轉(zhuǎn)多峰函數(shù)(f5)和復(fù)合函數(shù)(f6)。為了驗(yàn)證算法的性能，DDA-PSO分別與PSO-LDIW[6]，MPSO[10]，APSO[7]和APSO-MAM[9]在6個(gè)基準(zhǔn)函數(shù)上進(jìn)行仿真比較。根據(jù)原文獻(xiàn)，所有PSO算法的參數(shù)設(shè)置見表2。通過實(shí)驗(yàn)分析，本文k=1和NC=50。根據(jù)文獻(xiàn)建議[16]，d1=0.25，d2=0.05。

表1 用于測試的基準(zhǔn)函數(shù)及其參數(shù)Tab.1 Benchmark functions and their parameters for testing

所有粒子群優(yōu)化算法的粒子位置初始化都均勻地分布在表1中描述的初始范圍內(nèi)以體現(xiàn)算法的搜索能力。為了防止種群初值影響測試結(jié)果，對每個(gè)基準(zhǔn)函數(shù)進(jìn)行30次獨(dú)立實(shí)驗(yàn)后取其最優(yōu)適應(yīng)值的平均值。根據(jù)文獻(xiàn)建議[17]，所有PSO算法的種群大小均設(shè)定為40，最大迭代次數(shù)為10 000。

表2 各種PSO算法的參數(shù)設(shè)置Tab.2 Parameter setting of various PSO algorithms

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

仿真結(jié)果與統(tǒng)計(jì)數(shù)據(jù)見表3。表3列出了6個(gè)基準(zhǔn)函數(shù)在30維的最優(yōu)適應(yīng)值的平均值和標(biāo)準(zhǔn)差(標(biāo)準(zhǔn)差顯示在括號中)。圖1～圖6是6個(gè)基準(zhǔn)函數(shù)分別采用5個(gè)PSO算法迭代10 000次后得到的平均最佳適應(yīng)度進(jìn)化曲線，F(xiàn)Es表示迭代次數(shù)，F(xiàn)unction1-6按順序分別為表1中的f1，f2，f3，f4，f5，f6。

表3 優(yōu)化基準(zhǔn)函數(shù)搜索結(jié)果的比較Fig.3 Comparison of benchmark functhion search results

FEs圖1 Sphere函數(shù)的平均最優(yōu)適應(yīng)度進(jìn)化曲線Fig.1 Evolution curve of average optimal fitness of Sphere

FEs圖2 Rastrigin函數(shù)的平均最優(yōu)適應(yīng)度進(jìn)化曲線Fig.2 Evolution curve of average optimal fitness of Rastrigin

FEs圖3 Weierstrass函數(shù)的平均最優(yōu)適應(yīng)度進(jìn)化曲線Fig.3 Evolution curve of average optimal fitness of Weierstrass

FEs圖4 Griewank函數(shù)的平均最優(yōu)適應(yīng)度進(jìn)化曲線Fig.4 Evolution curve of average optimal fitness of Griewank

FEs圖5 旋轉(zhuǎn)Griewank函數(shù)的平均最優(yōu)適應(yīng)度進(jìn)化曲線Fig.5 Evolution curve of average optimal fitness of Rotation Griewank

FEs圖6 Hybrid composite CF5函數(shù)的平均最優(yōu)適應(yīng)度進(jìn)化曲線Fig.6 Evolution curve of average optimal fitness of Hybrid composite CF5

函數(shù)f1是簡單的單峰函數(shù)，由表3可知幾乎所有的算法在求解精度上都能提供最好的性能。DDA-PSO算法的收斂精度排第一，遠(yuǎn)優(yōu)于排第二的APSO算法。從圖1可以看出，前期APSO-MAM算法的收斂速度優(yōu)于其他四種算法，且其他四種算法的收斂速度非常接近。隨著迭代進(jìn)化，DDA-PSO算法的收斂速度和精度遠(yuǎn)優(yōu)于其他四種算法。

函數(shù)f2、f3和f4都是復(fù)雜的多峰函數(shù)，算法很容易陷入局部最優(yōu)。由表2可知，除了在函數(shù)f2上DDA-PSO算法與APSO-MAM算法的收斂精度一樣，DDA-PSO算法的收斂精度遠(yuǎn)優(yōu)于其他四個(gè)算法。在函數(shù)f2和函數(shù)f4上，DDA-PSO算法的收斂精度達(dá)到理論最優(yōu)值0。從圖2到圖4可以看出，前期五種算法的收斂速度非常接近。隨著迭代進(jìn)化，DDA-PSO算法的收斂速度遠(yuǎn)優(yōu)于其他四種算法。在函數(shù)f2上，雖然APSO-MAM算法的收斂精度也達(dá)到理論最優(yōu)值0，但由圖2可以看出，APSO-MAM算法的收斂速度低于DDA-PSO算法。

函數(shù)f5由Griewank函數(shù)旋轉(zhuǎn)而得，是非常復(fù)雜的多峰函數(shù)，算法非常容易陷入局部最優(yōu)。由表3可見，PSO-LDIW，MPSO，APSO和APSO-MAM四個(gè)算法的收斂精度都受到較大的影響，然而，DF-APSO算法的性能不受旋轉(zhuǎn)的影響，收斂精度仍然達(dá)到理論最優(yōu)值0。從圖5可以看出，前期DF-APSO算法的收斂速度與其他四種算法相比不具優(yōu)勢，但隨著迭代進(jìn)化，DDA-PSO算法的收斂速度遠(yuǎn)優(yōu)于PSO-LDIW算法，MPSO算法和APSO算法。雖然APSO-MAM算法的收斂速度也較快，但DF-APSO算法的收斂速度一直優(yōu)于APSO-MAM算法。

函數(shù)f6是帶旋轉(zhuǎn)和非對稱多峰的復(fù)合函數(shù)，在不同的區(qū)域具有不同的性質(zhì)，這種函數(shù)更難找到全局最優(yōu)解，會削弱所有粒子群算法的搜索能力。由表3可見，雖然所有粒子群算法的收斂精度都有所降低，但DF-APSO算法的收斂精度仍然最高，遠(yuǎn)遠(yuǎn)優(yōu)于PSO-LDIW算法，MPSO算法和APSO算法。雖然APSO-MAM算法的收斂精度接近于DF-APSO算法，但其標(biāo)準(zhǔn)差遠(yuǎn)遠(yuǎn)大于DF-APSO算法。從圖6可以看出，PSO-LDIW算法，MPSO算法和APSO算法很快陷入局部最優(yōu)。雖然APSO-MAM算法也能跳出局部最優(yōu)，但DF-APSO算法的收斂速度一直優(yōu)于APSO-MAM算法。

綜上可以看出，DDA-PSO算法在6個(gè)基準(zhǔn)函數(shù)上的收斂精度和收斂速度都優(yōu)于其他四種算法，這歸因于DDA-PSO算法在吸引階段利用慣性權(quán)重線性遞減機(jī)制加速算法收斂，粒子能進(jìn)行局部開拓；驅(qū)動階段利用多樣性驅(qū)動速度策略提高粒子群的多樣性，粒子能進(jìn)行全局勘探。兩階段能自適應(yīng)地相互轉(zhuǎn)換，勘探和開拓達(dá)到平衡，保持了種群多樣性，使得粒子能跳出局部最優(yōu)，且防止了早熟收斂，大大提高了全局搜索能力，同時(shí)提高了收斂速度。

4 結(jié)論

本文針對粒子群優(yōu)化算法容易陷入局部最優(yōu)和早熟問題，在基本PSO算法的基礎(chǔ)上引入慣性權(quán)重線性遞減機(jī)制和多樣性驅(qū)動速度策略對PSO算法進(jìn)行了改進(jìn)，提出了一種多樣性驅(qū)動的自適應(yīng)粒子群優(yōu)化算法。在6個(gè)基準(zhǔn)函數(shù)上，DDA-PSO算法與4個(gè)已有的粒子群優(yōu)化算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，DDA-PSO算法不僅具有很強(qiáng)的全局搜索能力，而且收斂速度明顯提高，收斂精度得到改善，很大程度上防止了早熟和避免了陷入局部最優(yōu)。