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

袁 琳，苑薇薇

(沈陽(yáng)理工大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng) 110159)

粒子群優(yōu)化算法是一種基于種群搜索的群智能進(jìn)化計(jì)算技術(shù)［1－2］，在標(biāo)準(zhǔn) PSO(Particle Swarm Optimization，粒子群優(yōu)化)算法中，慣性權(quán)重是非常重要的參數(shù)。文獻(xiàn)［3－4］對(duì)固定權(quán)重的選取做了深入討論，但對(duì)于解決復(fù)雜優(yōu)化問(wèn)題時(shí)，找到合適的固定權(quán)重是很困難的。本文關(guān)注時(shí)變權(quán)重的選取，同時(shí)根據(jù)種群多樣性自適應(yīng)調(diào)整慣性權(quán)重，平衡局部搜索能力和全局搜索能力，使之能改善標(biāo)準(zhǔn)PSO算法易陷入局部收斂的缺點(diǎn)，并在解決復(fù)雜優(yōu)化問(wèn)題中達(dá)到更好的效果。

1 粒子群優(yōu)化算法的基本原理

PSO算法的數(shù)學(xué)描述為:假設(shè)在一個(gè)N維搜索空間中，有m個(gè)粒子組成一個(gè)粒子種群，其中第i個(gè)粒子在搜索空間中的位置是xi，表示為向量xi，飛行速度表示為向量 vi=，第 i個(gè)粒子的個(gè)體極值記 pin=，全局極值記為了改善算法收斂性能，在速度和位置更新公式中引入慣性權(quán)重的概念［5］。

在每次迭代中，粒子根據(jù)下式更新速度和位置:

式中:i=1，2，…，m;n=1，2，…，N;k為當(dāng)前進(jìn)化代數(shù);c1和c2為加速常數(shù);r1和r2為均勻分布于(0，1)之間的隨機(jī)數(shù);w為慣性權(quán)重，其大小決定了對(duì)粒子當(dāng)前速度繼承的多少，適當(dāng)選取可以使粒子具有均衡的探索和開(kāi)發(fā)能力，可見(jiàn)原始PSO算法是慣性權(quán)重w=1的特殊情況。

粒子群優(yōu)化算法具有并行處理特性，魯棒性好，粒子只通過(guò)內(nèi)部速度進(jìn)行更新，因此原理更簡(jiǎn)單、參數(shù)更少、實(shí)現(xiàn)更容易［6］。但是，在算法運(yùn)行過(guò)程中，粒子易陷入局部最優(yōu)，會(huì)出現(xiàn)早熟收斂現(xiàn)象。針對(duì)其缺點(diǎn)，本文引入群體適應(yīng)度方差和群體位置方差，目的是保持種群多樣性，并對(duì)慣性權(quán)重進(jìn)行自適應(yīng)調(diào)整，使其快速收斂到最優(yōu)解。

2 改進(jìn)的粒子群優(yōu)化算法

2.1 PSO算法種群多樣性

(1)群體適應(yīng)度方差

式中:m為粒子群粒子數(shù);fi為第i個(gè)粒子的適應(yīng)度;favg為粒子群當(dāng)前的平均適應(yīng)度;f為歸一化因子。越小，則粒子群越收斂。

(2)群體位置方差

2.2 慣性權(quán)重調(diào)整策略

本文考慮種群多樣性的信息，慣性權(quán)重調(diào)整如下式所示。

慣性權(quán)重曲線見(jiàn)圖1。在尋優(yōu)初期，當(dāng)δ2p較大時(shí)，w保持在最大值附近，可提高算法的全局搜索能力;在尋優(yōu)后期，隨著δ2p由大到小的線性過(guò)渡，w隨種群多樣性的減少而遞減，可提高算法的局部搜索能力。

圖1 慣性權(quán)重曲線

2.3 慣性權(quán)重的多樣性調(diào)整

為了克服PSO算法的早熟收斂，當(dāng)群體滿足收斂條件即群體適應(yīng)度方差或群體位置方差時(shí)，利用各粒子的表現(xiàn)程度不同，將群體分成3個(gè)子群。適應(yīng)度較好粒子組成X子群;適應(yīng)度一般的粒子組成Y子群;其余適應(yīng)度較差的粒子組成Z子群。

2.3.1 X子群的慣性權(quán)重調(diào)整

X子群中的粒子適應(yīng)度較好，已經(jīng)比較接近全局最優(yōu)，慣性權(quán)重應(yīng)逐漸減小，提高局部搜索能力。慣性權(quán)重調(diào)整如下式:

2.3.2 Y子群的慣性權(quán)重調(diào)整

Y子群中的粒子適應(yīng)度一般，具有全局尋優(yōu)能力和局部尋優(yōu)能力，慣性權(quán)重調(diào)整如下式:

2.3.3 Z子群的慣性權(quán)重調(diào)整

Z子群中的粒子適應(yīng)度較差，慣性權(quán)重應(yīng)逐漸增大，提高全局尋優(yōu)能力。慣性權(quán)重調(diào)整如下式:

2.4 改進(jìn)粒子群算法流程

改進(jìn)粒子群算法步驟如下:

(1)隨機(jī)初始化一群粒子及其速度和位置，對(duì)每個(gè)粒子計(jì)算其適應(yīng)度;

(3)根據(jù)每個(gè)粒子的適應(yīng)度，如果好于該粒子當(dāng)前的個(gè)體極值，則將其作為當(dāng)前粒子的個(gè)體最優(yōu)值;如果所有粒子中最好的個(gè)體極值優(yōu)于當(dāng)前的全局極值，則將其作為群體最優(yōu)值;

(4)判斷是否達(dá)到算法終止條件，若滿足，則結(jié)束;否則，轉(zhuǎn)至步驟(5);

(6)按式(1)和式(2)更新粒子的速度和位置后轉(zhuǎn)至步驟(2)。

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

本文通過(guò)4個(gè)典型基準(zhǔn)函數(shù)(見(jiàn)表1)的優(yōu)化問(wèn)題測(cè)試改進(jìn)后算法的性能，同時(shí)與GA算法與PSO算法進(jìn)行比較。實(shí)驗(yàn)參數(shù)設(shè)置如下:GA算法、PSO算法和改進(jìn)算法各運(yùn)行100次，粒子群的種群規(guī)模均為40，迭代次數(shù)均為5000次，在改進(jìn)的算法中。為比較優(yōu)化結(jié)果，選擇觀察其達(dá)優(yōu)率及其取得平均最優(yōu)值的迭代次數(shù)。

表1 用于測(cè)試的基準(zhǔn)函數(shù)及其參數(shù)

測(cè)試結(jié)果與統(tǒng)計(jì)數(shù)據(jù)見(jiàn)表2～表5。

表2 Sphere的優(yōu)化結(jié)果

表3 Rosenbrock的優(yōu)化結(jié)果

表4 Rastrigrin的優(yōu)化結(jié)果

表5 Griewank的優(yōu)化結(jié)果

實(shí)驗(yàn)表明:對(duì)于Sphere和Rosenbrock單峰函數(shù)，改進(jìn)后的優(yōu)化效果要優(yōu)于GA算法，和PSO算法的優(yōu)化結(jié)果近似。對(duì)于Rastrigrin多峰函數(shù)，GA算法優(yōu)化效果較差，在迭代1500次還未收斂到全局最優(yōu)點(diǎn)，而改進(jìn)算法和PSO算法都可以在迭代1000次以內(nèi)找到最優(yōu)解，且改進(jìn)算法的達(dá)優(yōu)率要比PSO算法高，能較快地到達(dá)全局最優(yōu)值附近，其效果明顯優(yōu)于PSO算法和GA算法。對(duì)于Griewank函數(shù)，當(dāng)空間維數(shù)超過(guò)20后，其特性趨向于單峰，改進(jìn)算法的優(yōu)越性并不明顯，可見(jiàn)，改進(jìn)算法更適于解決多峰函數(shù)優(yōu)化問(wèn)題。

4 結(jié)論

通過(guò)對(duì)基準(zhǔn)函數(shù)的測(cè)試，驗(yàn)證了改進(jìn)算法的收斂精度較高，收斂速度(這里是指算法迭代的次數(shù))比GA算法和PSO算法要快。這要?dú)w結(jié)于在算法中引入群體適應(yīng)度方差和群體位置方差協(xié)調(diào)種群多樣性。根據(jù)種群多樣性，對(duì)慣性權(quán)重自適應(yīng)調(diào)整，保持了慣性權(quán)重的多樣性，從而提高了優(yōu)化性能。當(dāng)優(yōu)化問(wèn)題是高維、多峰等復(fù)雜問(wèn)題時(shí)，改進(jìn)算法的優(yōu)越性更加明顯。

［1］ Kennedy J，Karnhart R C.Swarm Intelligence［M］.San Francisco，CA:Morgan Kaufmann Publishers Inc，2001.

［2］ Karnhart R C，Kennedy J.A new optimizer using particle swarm theory［C］.Proc of the 6th international symposium On Micro Machine and Human Science，Nagoya，Japan:IEEE Service Center，1995:39 －43.

［3］柯晶，錢(qián)積新，喬誼正.一種改進(jìn)粒子群優(yōu)化算法［J］.電路與系統(tǒng)學(xué)報(bào)，2003，8(5):87 －91.

［4］唐劍東，熊信艮，吳耀武，等.基于改進(jìn)PSO算法的電力系統(tǒng)無(wú)功優(yōu)化［J］.電力自動(dòng)化設(shè)備，2004，24(7):81－84.

［5］周暉，周任軍，談順濤，等.用于無(wú)功電壓綜合控制的改進(jìn)粒子群優(yōu)化算法［J］.電網(wǎng)技術(shù)，2004，28(13):45－49.

［6］聞朝中，李智.粒子群算法在配電網(wǎng)絡(luò)無(wú)功補(bǔ)償優(yōu)化中的應(yīng)用［J］.武漢工業(yè)學(xué)院學(xué)報(bào)，2004，23(1):18－21.