張 超,賀興時(shí),葉亞榮

(西安工程大學(xué) 理學(xué)院, 陜西 西安 710048)

0 引 言

粒子群優(yōu)化算法[1](PSO)是由Kennedy和Eberhart提出的一種群智能隨機(jī)優(yōu)化算法.它具有結(jié)構(gòu)簡(jiǎn)單、收斂速度快等特點(diǎn).自提出以后,粒子群算法已經(jīng)被廣泛用于許多領(lǐng)域.比如數(shù)據(jù)挖掘[2],模式識(shí)別與分類[3],信號(hào)控制[4],Steiner樹問題[5],旅行商問題[6].粒子群優(yōu)化算法對(duì)于單峰函數(shù)的優(yōu)化,具有良好的效果,但是對(duì)于多峰函數(shù)優(yōu)化,卻經(jīng)常發(fā)生早熟過早收斂,從而不能很好求出全局最優(yōu)值.針對(duì)粒子群算法易過早收斂的問題,很多學(xué)者提出了改進(jìn)方法.如文獻(xiàn)[7] 將粒子群算法應(yīng)用于布谷鳥搜索算法中,提高布谷鳥搜索算法的收斂速度和計(jì)算精度．文獻(xiàn)[8]提出了一種粒子群算法與人工魚群算法的混合算法,該算法將人工魚群的公告板、群聚和隨行策略的模式應(yīng)用于粒子群的速度與位置變更中,從而提高了粒子的搜索精度和搜索效率;文獻(xiàn)[9]將粒子群算法與模擬退火算法相結(jié)合,新混合算法在粒子群算法搜索停滯時(shí),在最優(yōu)位置用模擬退火算法繼續(xù)搜尋最優(yōu)解.新混合算法具有收斂速度快,求解精度高的特點(diǎn);文獻(xiàn)[10]將粒子群算法與蟻群算法相結(jié)合,新混合算法中添加交叉與變異、和免疫選擇等過程,實(shí)驗(yàn)結(jié)果表明該混合算法提高了算法的全局尋優(yōu)能力.文獻(xiàn)[11]利用反向?qū)W習(xí)策略和具有Levy飛行特征的改進(jìn)搜索策略對(duì)出現(xiàn)停滯的粒子進(jìn)行判斷.實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法在前期的搜索能力和后期的搜索精度上都優(yōu)于其他幾種算法.由此可見,將不同的智能算法結(jié)合或者引入其他搜索機(jī)制的思想可以很好的改善算法的性能.本文針對(duì)標(biāo)準(zhǔn)粒子群算法已陷入局部最優(yōu)的缺陷,提出了一種基于精英策略和Levy飛行的粒子群算法,通過引入精英策略的思想和Levy飛行機(jī)制來提高粒子群算法的搜索效率,避免粒子陷入局部最優(yōu).使算法具有更快的收斂速度和更高的收斂精度.

1 粒子群算法與精英策略

1.1 標(biāo)準(zhǔn)的粒子群優(yōu)化算法

粒子群算法是一種群智能優(yōu)化算法, 粒子當(dāng)前位置的優(yōu)劣是由被優(yōu)化的函數(shù)適應(yīng)度值來評(píng)價(jià).如果粒子種群是由N個(gè)粒子構(gòu)成,在D維搜索空間中, 向量Xi=(xi1,xi2,…,xid),i=1,2,…,N.表示第i個(gè)粒子在搜索空間中的位置,向量Vi=(vi1,vi2,…,vid)表示粒子的速度,Pi=(pi1,pi2,…,pid) 表示第i個(gè)粒子搜索到的最優(yōu)位置,Pg=(pg1,pg2,…,pgd)表示整個(gè)粒子群能搜索到的最優(yōu)位置.則粒子的更新方程為

vid(t+1)=ωvid(t)+c1r1(pid-xid(t))+c2r2(pgd-xid(t)).

(1)

xid(t+1)=xid(t)+vid(t+1).

(2)

式中:d=1,2,…,D;ω稱為慣性權(quán)重;c1和c2稱為學(xué)習(xí)因子;r1和r2為2個(gè)隨機(jī)數(shù);它們?cè)?0,1)內(nèi)取值;當(dāng)前迭代次數(shù)為t.

1.2 精英反向?qū)W習(xí)策略

1.2.1 精英反向?qū)W習(xí) 反向?qū)W習(xí)(opposition-based learning)的概念是由Tizhoosh[12]于2005年提出的,它可以較好地緩解粒子過早收斂的問題.在考慮當(dāng)前粒子的同時(shí)考慮其反向粒子,增大了粒子的搜索空間,改善算法的性能,使粒子避免過早收斂,實(shí)現(xiàn)全局尋優(yōu).

(3)

定義2[13]基于反向解的優(yōu)化(opposite-based optimization).如果待求解的優(yōu)化問題是求最小值,f(*)評(píng)估函數(shù),通過f(*)計(jì)算候選解的適應(yīng)度值,如果待求解的優(yōu)化問題的可行解是X,X*是X的反向解;如果f(X*)

定義3[13]動(dòng)態(tài)反向?qū)W習(xí)(dynamic generalized opposition-based learning).

(4)

(5)

1.2.2 Levy飛行 Levy分布是由法國(guó)數(shù)學(xué)家萊維 (Levy) 提出的一種概率分布,之后很多研究者對(duì)Levy分布進(jìn)行了大量的研究.截至目前, 自然界的很多動(dòng)物覓食軌跡遵從Levy分布(Levy distribution)[15]的事實(shí)已經(jīng)得到了證明.Levy飛行服從Levy分布[16].很多隨機(jī)現(xiàn)象的原理,如布朗運(yùn)動(dòng)、隨機(jī)行走等遵從Levy飛行.目前Levy飛行在智能優(yōu)化領(lǐng)域已經(jīng)被廣泛應(yīng)用,比如布谷鳥算法中就采用Levy飛行進(jìn)行位置更新[17],Levy飛行可以擴(kuò)大搜索空間, 因此把Levy飛行引入智能優(yōu)化算法中更容易使算法避免過早收斂[18].Levy飛行位置更新式為

(6)

Levy～u=t-λ,1<λ≤3.

(7)

Levy飛行實(shí)質(zhì)是一種隨機(jī)步長(zhǎng),其步長(zhǎng)遵從Levy分布,由于Levy分布比較復(fù)雜,所以Levy分布通常由Mantegna算法來模擬實(shí)現(xiàn),步長(zhǎng)s計(jì)算為[19]

(8)

式中:μ,v為正態(tài)分布,定義

(9)

(10)

式中:

(11)

σν=1.

(12)

式中:β通常取值為常數(shù)1.5.

1.2.3 自適應(yīng)動(dòng)態(tài)步長(zhǎng) 由于Levy飛行中的步長(zhǎng)α為固定常數(shù),導(dǎo)致在搜索過程中存在搜尋能力差,搜索精度低的問題,本文提出自適應(yīng)動(dòng)態(tài)函數(shù)步長(zhǎng)α1來代替α．由于尋優(yōu)初期粒子位置更新變化較大,需要較大步長(zhǎng),使粒子個(gè)體能快速尋找到最優(yōu)解;尋優(yōu)后期,需要較小步長(zhǎng)來提高最優(yōu)解的精度,因此需使步長(zhǎng)的變化呈遞減趨勢(shì)．步長(zhǎng)的改進(jìn)為

(13)

將式(13)代入式(6)可得到改進(jìn)之后的自適應(yīng)Levy飛行步長(zhǎng)公式,即

(14)

2 改進(jìn)算法—ELPSO

利用精英粒子的良好反向搜索能力，以及自適應(yīng)動(dòng)態(tài)Levy飛行更新因早熟而無法進(jìn)化到更好位置的粒子，進(jìn)行算法的進(jìn)一步優(yōu)化.具體步驟為

(1) 種群初始化.

(2) 依據(jù)精英策略產(chǎn)生精英反向個(gè)體,將每個(gè)粒子的適應(yīng)度值計(jì)算出來,并且將粒子的適應(yīng)度值存儲(chǔ)在pbest中,從當(dāng)前個(gè)體和精英反向個(gè)體中選擇出適應(yīng)度值最優(yōu)的個(gè)體,讓適應(yīng)度值最優(yōu)的個(gè)體作為下一代種群,并將最優(yōu)個(gè)體的適應(yīng)度值存儲(chǔ)于gbest中.

(3) 更新粒子的速度和位置.根據(jù)式(1)和(2)進(jìn)行更新.

(4) 更新個(gè)體最優(yōu).比較粒子更新前后的適應(yīng)度值,取較好的粒子作為下一代粒子.

(5) 更新全局最優(yōu).把pbest和gbest的值進(jìn)行比較,如果pbest的值比gbest的值更優(yōu),那么把pbest的值賦值給gbest并使gbest進(jìn)行更新.

(6) Levy飛行.如果粒子位置停留在局部的迭代次數(shù)大于等于10.那么使用式(14)使粒子的位置進(jìn)行更新.根據(jù)步驟(4)和(5)更新個(gè)體最優(yōu)pbest和全局最優(yōu)gbest.

(7) 算法終止.如果算法符合迭代結(jié)束條件,則使算法停止運(yùn)行; 否則返回步驟(3) 繼續(xù)搜索.

3 仿真實(shí)驗(yàn)

為了檢驗(yàn)ELPSO算法的性能,將ELPSO算法與標(biāo)準(zhǔn)PSO算法和RWPSO算法用于6個(gè)典型的測(cè)試函數(shù)中,并對(duì)結(jié)果進(jìn)行比較.

3.1 實(shí)驗(yàn)設(shè)計(jì)

ELPSO算法的參數(shù)設(shè)置如下: 粒子數(shù)為N=50,維數(shù)為D=10,迭代次數(shù)為150次,c1=1.496 2,c2=1.496 2,w=0.729 8,p=0.25,p為執(zhí)行精英反向?qū)W習(xí)的概率.Levy飛行的參數(shù)β設(shè)置為1.5.RWPSO算法為權(quán)重線性遞減的改進(jìn)粒子群算法,它的參數(shù)除過w,p,β這3個(gè)參數(shù)與ELPSO算法有所不同之外,其他參數(shù)均與ELPSO算法參數(shù)相同,本次實(shí)驗(yàn)選取了6個(gè)典型的測(cè)試函數(shù),表1給出了本次實(shí)驗(yàn)測(cè)試函數(shù)的特征.

(5) Booth函數(shù)f5(x)=(x1+2x2-7)2+(2x1+x2-5)2.

表 1 函數(shù)的基本特征Table 1 Basic features of the function

3.2 結(jié)果分析

3.2.1 實(shí)驗(yàn)一 對(duì)PSO算法、RWPSO算法和ELPSO算法的平均適應(yīng)值,方差Best值，Worst值進(jìn)行比較.在不同維數(shù)下,3種算法獨(dú)立實(shí)驗(yàn)50次所得到的結(jié)果見表2.

由表2可知,ELPSO算法的平均適應(yīng)值和方差的算法精度顯著高于PSO算法和改進(jìn)的RWPSO算法,說明ELPSO算法性能比PSO算法和RWPSO算法的性能更好.

表 2 6個(gè)測(cè)試函數(shù)的均值、方差、Best及Worst比較Table 2 Comparison of mean, variance, Best and Worst of 6 test functions

3.2.2 實(shí)驗(yàn)二 圖1是3種算法針對(duì)不同測(cè)試函數(shù)的進(jìn)化曲線圖.

(a) Ackley函數(shù) (b)Beale函數(shù) (c) Griewank函數(shù)

(d) Levy函數(shù) (e) Booth函數(shù) (f) Rosenbrock函數(shù)圖 1 6種測(cè)試函數(shù)的收斂曲線Fig.1 The convergence curve of six test functions

對(duì)于Ackley函數(shù),進(jìn)化初期ELPSO算法的收斂速度明顯快于RWPSO算法和PSO算法,隨著迭代次數(shù)的增加ELPSO算法快速收斂,在較少的迭代次數(shù)下尋找到全局最優(yōu)值.對(duì)于Beale函數(shù),在進(jìn)化后期階段RWPSO算法和PSO算法收斂較慢,而ELPSO算法能保持很快的速度收斂.對(duì)于Griewank函數(shù)和Levy函數(shù),在進(jìn)化前期PSO算法和RWPSO算法能較快的收斂,隨著迭代次數(shù)增加,PSO算法和RWPSO算法收斂速度變慢甚至出現(xiàn)停滯,而ELPSO算法始終能保持很快的速度收斂.對(duì)于Booth函數(shù),在進(jìn)化的整個(gè)過程中ELPSO算法的收斂速度都快于PSO算法和RWPSO算法.對(duì)于Rosenbrock函數(shù),在PSO算法出現(xiàn)停滯以及RWPSO算法收斂速度變緩的情況下,ELPSO算法仍保持著很快的速度收斂.

分析圖1可知,ELPSO算法的性能比RWPSO算法和PSO算法的性能更好,在迭代次數(shù)相同的情況下,ELPSO算法的收斂速度更快且精度更高.ELPSO算法在尋優(yōu)過程中,依據(jù)精英反向?qū)W習(xí),選擇適應(yīng)度值較好的個(gè)體作為下一代個(gè)體,使算法的全局搜索能力得到了提高.利用Levy飛行機(jī)制來更新個(gè)體的位置,提高了粒子的跳躍能力,可以使其避免過早收斂.ELPSO算法顯著提高了PSO算法的精度和收斂速度,具有更優(yōu)的性能.

表 3 ELSPO算法與PSO算法和 RWPSO算法的T檢驗(yàn)Table 3 T-test of ELSPO algorithm and PSO algorithm and RWPSO algorithm

3.2.3 實(shí)驗(yàn)三 統(tǒng)計(jì)檢驗(yàn).在實(shí)驗(yàn)中,3種算法在6種測(cè)試函數(shù)上均獨(dú)立運(yùn)行40次,因此對(duì)于單獨(dú)的測(cè)試函數(shù),每種算法都得到40個(gè)樣本.采用T檢驗(yàn)法對(duì)PSO算法,RWPSO算 法,ELPSO算法的性能進(jìn)行比較.該T檢驗(yàn)采用顯著水平為0.05的雙尾檢驗(yàn).實(shí)驗(yàn)結(jié)果為 “=”或 者 “+”.“=”表示在相同的測(cè)試函數(shù)上ELPSO算法與PSO算法或者RWPSO算法顯著性相同,“+”表示ELPSO算法的顯著性比PSO算法或者RWPSO算法更優(yōu).從表3中可以看出,ELPSO算法的顯著性比PSO算法和RWPSO算法更優(yōu).

3.2.4 實(shí)驗(yàn)四 為驗(yàn)證算法的有效性,收集了全國(guó)31個(gè)城市的坐標(biāo),每個(gè)用戶的位置及物資需求量由表4給出,這里的物資需求量是經(jīng)過規(guī)范化處理之后的數(shù)據(jù),不代表實(shí)際值．從中選擇6個(gè)作為物流配送中心．依據(jù)本文算法步驟對(duì)上述問題進(jìn)行求解,算法的參數(shù)分別為:種群規(guī)模為50,迭代次數(shù)為100次．

表 4 用戶的位置及其物資需求量Table 4 User′s location and its material requirements

表4中，j表示城市的序號(hào),(Uj,Vj)表示用戶的位置,aj表示物資需求量．改進(jìn)的算法及原算法的收斂曲線如圖2所示,得到的物流配送中心選址方案如圖3所示．

圖3中方框表示配送中心,圓點(diǎn)表示城市點(diǎn),方框與點(diǎn)之間有連線表示該城市的物資由連接的配送中心配送．實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法比原算法收斂更快,更有效．

圖 2 2種算法的收斂曲線 圖 3 物流配送中心選址方案Fig.2 Convergence curves of the two center Fig.3 Location plan of logistics distribution algorithms

4 結(jié)束語

本文針對(duì)PSO算法容易陷入局部最優(yōu)的缺陷,將精英策略和自適應(yīng)動(dòng)態(tài)Levy飛行步長(zhǎng)引入到 PSO算法中,擴(kuò)大粒子的搜索空間,使粒子避免過早收斂.選取6種測(cè)試函數(shù)對(duì)ELPSO算法進(jìn)行仿真實(shí)驗(yàn),仿真結(jié)果表明ELPSO算法在相同迭代次數(shù)下比PSO和RWPSO算法收斂速度更快、精度更高;t檢驗(yàn)結(jié)果更說明ELPSO算法比PSO和RWPSO算法更具優(yōu)越性.最后通過物流中心選址的算例對(duì)改進(jìn)的算法進(jìn)行測(cè)試,實(shí)驗(yàn)結(jié)果表明本文能更快收斂到全局最優(yōu)解,求解的精度也更好,能很好地解決物流中心選址問題．本文提出的改進(jìn)算法不是唯一的,還可以嘗試與其他算法結(jié)合,尋找更加高效的實(shí)現(xiàn)全局尋優(yōu)的智能優(yōu)化算法.