宗 敏，楊玉群，徐 剛*

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

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

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

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

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

(1)

(2)

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

1.2 PSO-LDIW算法

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

(3)

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

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

2.1 種群多樣性度量

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

(4)

(5)

2.2 種群速度度量

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

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

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

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

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

(7)

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

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

(8)

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

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

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

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

(9)

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

2.5 提出的算法

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

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

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

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

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

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

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

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

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

3 數(shù)值實驗及分析

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

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

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

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

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

3.2 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

函數(shù)f2、f3和f4都是復(fù)雜的多峰函數(shù)，算法很容易陷入局部最優(yōu)。由表2可知，除了在函數(shù)f2上DDA-PSO算法與APSO-MAM算法的收斂精度一樣，DDA-PSO算法的收斂精度遠優(yōu)于其他四個算法。在函數(shù)f2和函數(shù)f4上，DDA-PSO算法的收斂精度達到理論最優(yōu)值0。從圖2到圖4可以看出，前期五種算法的收斂速度非常接近。隨著迭代進化，DDA-PSO算法的收斂速度遠優(yōu)于其他四種算法。在函數(shù)f2上，雖然APSO-MAM算法的收斂精度也達到理論最優(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四個算法的收斂精度都受到較大的影響，然而，DF-APSO算法的性能不受旋轉(zhuǎn)的影響，收斂精度仍然達到理論最優(yōu)值0。從圖5可以看出，前期DF-APSO算法的收斂速度與其他四種算法相比不具優(yōu)勢，但隨著迭代進化，DDA-PSO算法的收斂速度遠優(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算法的收斂精度仍然最高，遠遠優(yōu)于PSO-LDIW算法，MPSO算法和APSO算法。雖然APSO-MAM算法的收斂精度接近于DF-APSO算法，但其標準差遠遠大于DF-APSO算法。從圖6可以看出，PSO-LDIW算法，MPSO算法和APSO算法很快陷入局部最優(yōu)。雖然APSO-MAM算法也能跳出局部最優(yōu)，但DF-APSO算法的收斂速度一直優(yōu)于APSO-MAM算法。

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

4 結(jié)論

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