羅金炎

(閩江學(xué)院數(shù)學(xué)系，福建福州 350108)

粒子群算法(PSO)是Kennedy和Eberhart于1995年提出的一種群體智能演化算法［1］，它源于對簡化社會模型的模擬.與其他進(jìn)化尋優(yōu)算法相類似，PSO算法也是通過個(gè)體間的協(xié)作與競爭，實(shí)現(xiàn)多維空間中最優(yōu)解的搜索.它首先生成初始種群，即在可行解空間中隨機(jī)初始化一群粒子，每個(gè)粒子都為尋優(yōu)問題的一個(gè)可行解，并用某個(gè)函數(shù)計(jì)算出相應(yīng)的適應(yīng)值，以確定是否達(dá)到尋優(yōu)目標(biāo).每個(gè)粒子將在解空間中運(yùn)動，并由一個(gè)矢量決定其運(yùn)動方向和位移.通常粒子將追隨當(dāng)前已知的最優(yōu)位置，并經(jīng)逐代搜索，最后得到最優(yōu)解.在每一進(jìn)化中，粒子將跟蹤兩個(gè)目標(biāo)位置，一為粒子本身迄今找到的最優(yōu)解，代表該粒子自身對尋優(yōu)方向的認(rèn)知水平;另一為全種群迄今找到的最優(yōu)解，代表社會認(rèn)知水平.粒子群算法已被廣泛應(yīng)用于各種優(yōu)化問題中，如神經(jīng)網(wǎng)絡(luò)訓(xùn)練、調(diào)度問題、組合優(yōu)化等.

為改善粒子群算法的搜索性能，Shi和Eberhart對基本PSO算法進(jìn)行了改進(jìn)，在粒子的速度進(jìn)化方程中引入慣性權(quán)重 w［2］.慣性權(quán)重 w控制著粒子運(yùn)動的慣性，使粒子有擴(kuò)展搜索空間的趨勢和開發(fā)新區(qū)域的能力.慣性權(quán)重w的取值對于保證算法的收斂和最優(yōu)地權(quán)衡搜索與開發(fā)極其重要，一般地，較大的權(quán)重有利于提高算法的全局開發(fā)能力，而較小的權(quán)重則能增強(qiáng)算法的局部搜索能力.針對慣性權(quán)重w的取值問題，國內(nèi)外的研究人員進(jìn)行了大量的工作［3-5］，其中線性遞減權(quán)重法相對簡單且收斂速度快，被廣泛采用.但是，PSO算法在實(shí)際搜索過程中多是高度復(fù)雜非線性的，線性遞減權(quán)重法不能反映實(shí)際的優(yōu)化搜索過程，也有研究人員據(jù)此提出了非線性遞減法［6-7］和引入其他因素的自適應(yīng)調(diào)整權(quán)重法［8］等.本文根據(jù)PSO算法慣性權(quán)重在優(yōu)化問題過程中的表現(xiàn)特征，提出了一種基于Logistic模型的動態(tài)慣性權(quán)重的策略，并與典型的線性遞減權(quán)重調(diào)整策略［3］進(jìn)行了比較，仿真實(shí)驗(yàn)表明:該策略在優(yōu)化復(fù)雜多峰值的問題方面體現(xiàn)了一定的優(yōu)越性.

1 粒子群優(yōu)化算法

設(shè)第 i個(gè)粒子位置為 xi=(xi1，xi2，…，xin)T，其位移為 vi=(vij，vi2，…，vin)T.它迄今搜索到的個(gè)體極值為 pi=(pi1，pi2，…，pin)T，而迄今搜索到的種群極值為 pg=(pg1，pg2，…，pgn)T.為使粒子位移變化不致過大，可以設(shè)定其上限Vmax，即若 vid＞ Vmax，則令 vid=Vmax，而若 vid＜ -Vmax，也令vid=-Vmax.每一次迭代，粒子通過兩個(gè)極值pi和pg來更新其速度和位置.粒子在解空間內(nèi)不斷跟蹤個(gè)體極值和鄰域極值進(jìn)行搜索，直到滿足迭代停止條件，即達(dá)到規(guī)定的迭代次數(shù)或滿足規(guī)定的誤差標(biāo)準(zhǔn).

假設(shè)尋優(yōu)問題為求目標(biāo)函數(shù)f(x)的最小值，那么粒子i的個(gè)體極值由下式確定

假設(shè)群體粒子數(shù)為m，則群體粒子的鄰域極值為:

按追隨當(dāng)前已知的最優(yōu)位置的原理，粒子xi將按式(3)改變位移方向和步長.

其中:d=1，2，…，n，n 為解空間的維數(shù)，即自變量個(gè)數(shù)，i=1，2，…，m，m 為種群規(guī)模，t為進(jìn)化代數(shù)，r1和r2為分布與［0，1］之間的隨機(jī)數(shù)，c1和c2為位移變化的限定因子，通常取為2.0.

w為慣性權(quán)重，較大的權(quán)重有利于提高算法的全局開發(fā)能力，并增加種群的多樣性;而較小的權(quán)重則能增強(qiáng)算法的局部搜索能力.然而過大的權(quán)重將使種群發(fā)散，粒子不能改變運(yùn)動方向以轉(zhuǎn)回需要搜索的指定區(qū)域;過小的權(quán)重將導(dǎo)致種群的搜索能力喪失，只有很小的慣性從上一步迭代中保存下來，加劇了速度的改變.動態(tài)的慣性權(quán)重調(diào)整通常采用線性遞減策略LDIW［9］，即:

其中T為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)，wmax為初始慣性權(quán)值，wmin為進(jìn)化到最大代數(shù)時(shí)的慣性權(quán)值.

2 非線性權(quán)重遞減策略

在PSO算法的搜索過程中可以對慣性權(quán)重w進(jìn)行動態(tài)調(diào)整.在算法開始時(shí)，給w選取較大的值，隨著搜索的進(jìn)行，可以動態(tài)地遞減w的取值，這樣可以保證算法在開始時(shí)，各粒子能夠以較大的速度步長在全局范圍內(nèi)開發(fā)較好的種子;而在搜索后期，較小的w值則保證粒子能夠在極點(diǎn)周圍做精細(xì)地搜索，使算法有較大的幾率以一定精度收斂于全局最優(yōu)解.

在標(biāo)準(zhǔn)PSO算法中，存在粒子容易過早收斂于局部極值的早熟現(xiàn)象，在慣性權(quán)重線性遞減策略中尤為突出.由于僅僅簡單地線性減小權(quán)重w，使得函數(shù)一旦進(jìn)入局部極值點(diǎn)鄰域內(nèi)就很難跳出，極易收斂到局部極值點(diǎn).這主要還是因?yàn)樵谒阉鬟^程中，種群中粒子在位置上缺乏多樣性導(dǎo)致的早熟.可以考慮在搜索初期盡可能地保持較大的權(quán)重w，使種群粒子飛躍整個(gè)搜索空間，以獲得更好的多樣性，從而盡可能擺脫局部極值的干擾;而當(dāng)種群搜索到全局最優(yōu)點(diǎn)附近時(shí)，及時(shí)快速降低權(quán)重w，并在搜索后期保持較小的權(quán)重w，使得種群以較強(qiáng)的局部搜索能力收斂到全局最優(yōu)點(diǎn).據(jù)此，根據(jù)Logistic函數(shù)的特征，提出一種基于Logistic動態(tài)調(diào)整慣性權(quán)重w的策略LgDW算法，慣性權(quán)重w將按S形曲線非線性遞減，如圖1所示.

圖1 Logistic動態(tài)慣性權(quán)重w變化趨勢Fig.1 The evolution of Logistic dynamic inertia weight

其變化公式為

式中:wmax、wmin、Tmax和 T與(4)式一致;a和 b為調(diào)整因子，它們的取值范圍為a＞0，0＜b＜1.

3 實(shí)驗(yàn)分析

為檢驗(yàn)Logistic動態(tài)慣性權(quán)重PSO算法的效率，并分析確定調(diào)整因子，現(xiàn)采用優(yōu)化領(lǐng)域中常用的4個(gè)經(jīng)典函數(shù)來測試分析.

Sphere函數(shù):

其為非凸、病態(tài)函數(shù)，在xi=0處達(dá)到全局最小值f(X*)=0.

Rastrigrin函數(shù):

其為多峰函數(shù)，在xi=0處達(dá)到全局最小值f(X*)=0.

Griewank函數(shù):

其在xi=0處達(dá)到全局最小值f(X*)=0.Schaffer函數(shù):

其全局最大值為f(0，0)=1，在距離全局最大點(diǎn)附近存在大量的次全局極大點(diǎn)，函數(shù)的強(qiáng)烈震蕩使其難于全局最優(yōu)化.

3.1 調(diào)整因子的確定

LgDW算法慣性權(quán)重公式(5)中的調(diào)整因子a和b可以根據(jù)目標(biāo)函數(shù)不同的適應(yīng)值動態(tài)地確定，它們對算法的性能有較大的影響.實(shí)驗(yàn)表明:過大的a和b值容易使算法失效，而過小的a和b值則容易使算法陷入局部收斂.它們的取值在10＜a＜50，0.8＜b＜0.93時(shí)，算法的性能比較好.表1、表2所示的是在a和b不同取值下對5維Rastrigrin函數(shù)的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)中算法的每組因子隨機(jī)運(yùn)行50次，粒子數(shù)為30，要求精度為10-8，最大迭代次數(shù)為2 000次.

表1 a=30時(shí)取不同b值的性能比較Table 1 Comparative results of different b values with a=30

表2 b=0.88時(shí)取不同a值的性能比較Table 2 Comparative results of different a values with b=0.88

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

實(shí)驗(yàn)中，分別用LDIW策略 PSO算法和LgDW策略PSO算法對4個(gè)測試函數(shù)進(jìn)行計(jì)算，參數(shù)取值 wmax=1.2，wmin=0.1，c1=c2=2.0，a=30，b=0.88，隨機(jī)運(yùn)行50次，粒子數(shù)為30.實(shí)驗(yàn)所得的各測試函數(shù)平均最優(yōu)適應(yīng)值進(jìn)化情況如圖2～圖5所示，數(shù)值結(jié)果如表3所示.

由進(jìn)化曲線圖可以看出:除了單峰Sphere函數(shù)，在優(yōu)化多峰值的復(fù)雜函數(shù)(Rastrigrin函數(shù)、Griewank函數(shù)和Schaffer函數(shù))方面，LgDW策略PSO算法都能較快地收斂于最優(yōu)解，優(yōu)于線性遞減策略的PSO算法.這主要是較大的慣性權(quán)重有利于全局探索，而較小的慣性權(quán)重有利于算法的局部開發(fā)，加速算法的收斂.

由實(shí)驗(yàn)所得的數(shù)值結(jié)果可以看出:LgDW策略PSO算法對于后面3個(gè)多峰函數(shù)的優(yōu)化，最優(yōu)值、均值及方差均有所改善，其主要原因是在初期較大的慣性權(quán)重能增大算法的搜索能力，保持了種群的多樣性;而在Sphere函數(shù)和高維的Griewank函數(shù)改善較小，是因?yàn)镾phere函數(shù)為單峰函數(shù)，而超過15維后Griewank函數(shù)特性趨于單峰.說明LgDW策略PSO算法對于多峰值復(fù)雜函數(shù)具有一定的優(yōu)越性.

圖2 Sphere函數(shù)平均最優(yōu)適應(yīng)值進(jìn)化曲線Fig.2 Comparative evolutionary process on Sphere

圖3 Rastrigrin函數(shù)平均最優(yōu)適應(yīng)值進(jìn)化曲線Fig.3 Comparative evolutionary process on Rastrigrin

圖4 Griewank函數(shù)平均最優(yōu)適應(yīng)值進(jìn)化曲線Fig.4 Comparative evolutionary process on Griewank

圖5 Schaffer函數(shù)平均最優(yōu)適應(yīng)值進(jìn)化曲線Fig.5 Comparative evolutionary process on Schaffer

表3 數(shù)值結(jié)果統(tǒng)計(jì)Table 3 Comparative results of LDIW and LgDW on Test Problems

4 結(jié)論

作為新的進(jìn)化計(jì)算方法，粒子群優(yōu)化(PSO)給大量非線性、不可微和多峰值復(fù)雜問題的優(yōu)化提供了一種新的思路.本文根據(jù)PSO算法慣性權(quán)重在優(yōu)化問題過程中的表現(xiàn)特征，提出了一種基于Logistic模型的動態(tài)慣性權(quán)重的LgDW策略，數(shù)值實(shí)驗(yàn)表明:LgDW策略對于多峰值的復(fù)雜函數(shù)的優(yōu)化體現(xiàn)出了較好的性能，具有一定的優(yōu)越性.

［1］ Kennedy J，Eberhart R C.Particle Swarm Optimization［C］//Proc of IEEE Int Conf on Neural Networks.Perth:IEEE，1995:1942-1948.

［2］ Shi Y，Eberhart R C.A Modified Particle Swarm Optimizer［C］//Proceedings of the IEEE Congress on Evolutionary Computation.Now York:IEEE，1998:303-308.

［3］ Shi Y，Eberhart R C.Parameter Selection in Particle Swarm Optimization［C］//In Proceedings of the Seventh Annual Conference on Evolutionary Programming.New York:Springer-Verlag，1998:591-600.

［4］ Shi Y，Eberhart R C.Fuzzy Adaptive Particle Swarm Optimization［C］//The IEEE Congress on Evolutionary Computation.San Francisco:IEEE，2001:101-106.

［5］ Eberhart R C，Shi Y.Tracking and Optimization Dy-namic Systems with Particle Swarms［C］//The IEEE Congress on Evolutionary Computation.San Francisco:IEEE，2001:94-100.

［6］ Chatterjee A，Siarry P.Nonlinear Inertia Weight Variation for Dynamic Adaptation in Particle Swarm Optimization［J］.Computers and Operations Research，2006，33(3):859-871.

［7］ 陳貴敏，賈建援，韓琪，等.粒子群優(yōu)化算法的慣性權(quán)重遞減策略研究［J］.西安交通大學(xué)學(xué)報(bào)，2006，40(1):53-56.

［8］ 張選平，杜玉平，秦國強(qiáng)，等.一種動態(tài)改變慣性權(quán)的自適應(yīng)粒子群算法［J］.西安交通大學(xué)學(xué)報(bào)，2005，39(10):1039-1042.

［9］ Shi Y H，Eberhart R C.Empirical Study of Particle Swarm Optimization［C］//Proc of IEEE Congress on Evolutionary Computation.Washington:IEEE，1999:629.