謝金宵,高岳林，*，于宏利

(1.北方民族大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,寧夏 銀川 750021；2.北方民族大學(xué) 寧夏智能信息與大數(shù)據(jù)處理重點(diǎn)實(shí)驗(yàn)室,寧夏 銀川 750021)

1995年，JAMES KENNEDY博士和RUSSELL EHERHART博士共同提出了粒子群算法(PSO)[1]，該算法受鳥(niǎo)群在遷徙或覓食過(guò)程中的運(yùn)動(dòng)規(guī)律所啟發(fā)，將食物或棲息地看成所求問(wèn)題的解，將鳥(niǎo)群飛行的空間比作問(wèn)題的求解空間，鳥(niǎo)群中的每一只鳥(niǎo)被視為沒(méi)有質(zhì)量和體積的微粒，作為問(wèn)題的待選解[2]，問(wèn)題的求解過(guò)程被比作鳥(niǎo)群在尋找食物或棲息地的過(guò)程。由于粒子群算法具有簡(jiǎn)單、易實(shí)現(xiàn)、魯棒性強(qiáng)等好的性質(zhì)，在函數(shù)優(yōu)化，調(diào)度問(wèn)題及工業(yè)、交通等實(shí)際問(wèn)題中有著廣泛的應(yīng)用。但與其他智能算法類似，PSO同樣存在著許多不足之處。例如，所得到的解精度低，容易出現(xiàn)早熟收斂[3]等問(wèn)題。一直以來(lái)，國(guó)內(nèi)外許多學(xué)者為解決上述不足，做了許多方面的努力，使PSO在性能上有了很大的進(jìn)步。然而大多數(shù)改進(jìn)機(jī)制主要關(guān)注于對(duì)粒子群算法中的參數(shù)進(jìn)行優(yōu)化，而忽略了使算法陷入局部最優(yōu)解和收斂速度慢等問(wèn)題的底層機(jī)理，所以很難使算法從根本上解決上述不足。文獻(xiàn)[4]將遺傳算法中的選擇算子融合到粒子群算法中，從而改善了算法的收斂性。文獻(xiàn)[5]將差分進(jìn)化算法與粒子群算法融合,提高了算法全局尋優(yōu)能力。文獻(xiàn)[6]利用粒子群算法優(yōu)化核極限學(xué)習(xí)機(jī)的核參數(shù),有效提高了單核極限學(xué)習(xí)機(jī)分類器的性能。文獻(xiàn)[7]改進(jìn)了多目標(biāo)粒子群算法(MOPSO)，實(shí)現(xiàn)了交流濾波器多目標(biāo)優(yōu)化設(shè)計(jì)。文獻(xiàn)[8]加入了混合蛙跳算法的分組思想，提出了一種蛙跳簡(jiǎn)化粒子群算法,改進(jìn)的算法能夠有效地避免早熟收斂問(wèn)題,并能較大幅度地提高收斂速度和收斂精度。本文針對(duì)PSO求解精度低、全局搜索能力不足的缺點(diǎn)，提出了一種GLPSO算法，將高斯變異與Levy飛行策略引入到算法中，使算法更好地保持種群多樣性，降低過(guò)早陷入局部最優(yōu)解的可能，提高了算法的全局搜索能力和求解精度。

1 基本粒子群算法

在PSO中，首先隨機(jī)初始化一批粒子作為問(wèn)題的初始解[9]，同時(shí)初始化每個(gè)粒子的位置和速度。在每一次迭代中，每個(gè)粒子憑借所有粒子在搜索的歷史上最優(yōu)的記錄，既全局最優(yōu)值坐標(biāo)gbest和粒子在飛行過(guò)程中自身歷史上最優(yōu)的記錄(個(gè)體最優(yōu)值坐標(biāo))，其迭代公式如下：

vt+1=ωvt+c1r1(pbestt-xt)+

c2r2(gbestt-xt)，

(1)

xt+1=xt+vt+1，

(2)

其中，ω是慣性系數(shù)，它是影響算法搜索性能的重要參數(shù)，其取值的大小表示粒子對(duì)當(dāng)前個(gè)體速度的繼承量；c1和c2均稱為加速因子，其中c1稱為認(rèn)知系數(shù)，表示粒子的自我認(rèn)知經(jīng)驗(yàn)，c2稱為社會(huì)系數(shù)，表示粒子從當(dāng)前全局最優(yōu)解中學(xué)習(xí)的能力；r1和r2是介于[0,1]之間相互獨(dú)立的隨機(jī)數(shù)；pbest是粒子i極值點(diǎn)的坐標(biāo)，gbest是全體粒子全局極值點(diǎn)的位置[10]。

PSO算法的具體步驟如下：

步驟1初始化種群，給定種群數(shù)量、初始位置及速度；

步驟2計(jì)算種群中所有個(gè)體的適應(yīng)能力；

步驟3根據(jù)步驟2中每個(gè)個(gè)體和適應(yīng)能力更新全局最優(yōu)值和個(gè)體最優(yōu)值，更新公式如下:

(3)

(4)

步驟4根據(jù)式(1)與(2)更新每個(gè)個(gè)體的位置與速度;

步驟5若達(dá)到終止條件，算法結(jié)束。否則，返回執(zhí)行步驟2。

2 基于高斯變異與Levy飛行策略的混合粒子群優(yōu)化算法

2.1 Levy飛行

Levy飛行是由法國(guó)數(shù)學(xué)家Levy提出的一種符合Levy分布的隨機(jī)游走模型[11]，從其過(guò)程來(lái)看具有馬爾可夫性質(zhì)，自然界中很多鳥(niǎo)類及昆蟲(chóng)的飛行軌跡符合Levy分布[12]。Levy飛行過(guò)程模擬的步幅多數(shù)情況下較小，偶爾也會(huì)出現(xiàn)較大步幅，其公式[13]如下：

(5)

其中，Levy(β)是服從參數(shù)為β的Levy分布，0<β<2，μ服從N(0,σ2)分布，ν服從N(0,1)分布，σ可由式(6)計(jì)算得到：

(6)

其中，Γ表示Gamma分布函數(shù)，β=1.5，Levy飛行隨機(jī)游走模擬圖像如圖1所示，其中橫坐標(biāo)與縱坐標(biāo)給出了粒子搜索空間范圍。為更一般表示Levy飛行的性質(zhì)，圖1中所涉及的步長(zhǎng)為無(wú)量綱的單位步長(zhǎng)。

圖1 Levy飛行模擬圖像Fig. 1 Levy flight simulation image

2.2 高斯變異

多數(shù)群智能算法中，其位置更新主要依靠個(gè)體間的信息相互交流，算法本身不具備變異能力從而使算法容易陷入局部最優(yōu)解。高斯變異[14]是在原有種群狀態(tài)上加入服從高斯分布的狀態(tài)函數(shù)，公式如下：

xk=xk×[0.5+τ×N(0,1)]，

(7)

其中，xk是種群中粒子迭代k次之后的狀態(tài)，τ是[0,1]之間的一個(gè)隨機(jī)變量，N(0,1)是均值為0，方差為1的正態(tài)分布。在原有粒子種群運(yùn)動(dòng)的基礎(chǔ)上，加入隨機(jī)的正態(tài)分布擾動(dòng)項(xiàng)，從而有利于算法減少陷入局部最優(yōu)解的可能，增強(qiáng)全局尋優(yōu)能力。

2.3 GLPSO算法流程

GLPSO是在PSO基礎(chǔ)上通過(guò)引入Levy飛行策略和高斯變異算子，使算法具有更高的全局尋優(yōu)能力和更加優(yōu)良的種群多樣性，其算法流程如下：

步驟1初始化種群；

步驟2計(jì)算種群中每個(gè)粒子的適應(yīng)度；

步驟3根據(jù)每個(gè)個(gè)體和適應(yīng)度更新全局最優(yōu)值和個(gè)體最優(yōu)；

步驟4根據(jù)Levy飛行，更新每個(gè)粒子的飛行方式，公式如下:

(8)

步驟5記錄每次迭代后的最優(yōu)值，在全局最優(yōu)值迭代10次不發(fā)生改變后，認(rèn)為算法陷入局部最優(yōu)解，則執(zhí)行步驟6，否則執(zhí)行步驟7；

步驟6對(duì)種群中的個(gè)體進(jìn)行高斯變異操作；

步驟7算法達(dá)到終止條件，則執(zhí)行步驟8，否則執(zhí)行步驟2;

步驟8輸出算法全局最優(yōu)解。

3 GLPSO算法收斂性分析

3.1 群智能隨機(jī)算法收斂的充分條件

SOLIS et al[15]已證明群智能隨機(jī)算法依概率1收斂于全局最優(yōu)解的充分條件為以下2點(diǎn)：

條件1：如果F(f(z,τ))≤F(z)，并且若τ∈S，則F(f(z,τ))≤F(z)，其中F為待求解函數(shù)，f為生成解函數(shù)，z為S中的一個(gè)點(diǎn)，其能保證F有一個(gè)下確界，τ是一個(gè)隨機(jī)生成向量[16]。

3.2 GLPSO算法收斂性證明

引理1GLPSO算法滿足條件1。

證明在GLPSO算法中，函數(shù)f可定義為：

f(pbk+1,gbk+1)=

(9)

由于GLPSO算法總是保留問(wèn)題更優(yōu)的解，即采用精英保留策略，所以算法滿足條件1。

引理2GLPSO算法滿足條件2。

Mi,k=x(t)+ω(x(t-1))-

x(t-2)+φ1(pi-x(t-1))+
φ2(pg-x(t-2)),

(10)

其中0≤φ≤c1，0≤φ2≤c2?？芍琈i,k為一個(gè)超矩形，其中一個(gè)頂點(diǎn)為(φ1,φ2)=(0,0)，另外一個(gè)頂點(diǎn)為(φ1,φ2)=(c1,c2)。

當(dāng)

max{c1|pi-x(t-1)|,

c2|pg-x(t-1)|}≤0.5diamj(S)

成立時(shí)，v(Mi,k∩S)≤v(S)。diamj(S)表示解空間S第j維分量的長(zhǎng)度。由于xi收斂于(φ1pi+φ2pg)/(φ1+φ2)，故Mi,j→0。隨著迭代次數(shù)k的增加,v(Mi,k∩S)逐漸減小，從而存在一個(gè)正整數(shù)K,當(dāng)k>K時(shí)，有A?S，因?yàn)橛兄渭疢i,k=S,同時(shí)令S的Borel支撐子集為A=Mi,k[17],則

定理1GLPSO算法搜索序列依概率1收斂于全局最優(yōu)解。

證明因?yàn)镚LPSO算法滿足條件1與條件2，因此GLPSO算法搜索序列依概率1收斂于全局最優(yōu)解。

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

4.1 測(cè)試函數(shù)與參數(shù)設(shè)置

為驗(yàn)證GLPSO算法的有效性，本文將GLPSO算法與基本PSO算法及帶有慣性因子的WPSO算法進(jìn)行了比較，選用的測(cè)試函數(shù)見(jiàn)表1，其中列出了所用測(cè)試函數(shù)的搜索范圍、理論最優(yōu)值和維數(shù)。參數(shù)設(shè)置如下：c1=2，c2=2，ω=0.75，N=100，GLPSO算法中β=1.5。其余參數(shù)均相同。

表1 測(cè)試函數(shù)Tab. 1 Test functions

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

通過(guò)上述給定的5個(gè)經(jīng)典測(cè)試函數(shù)對(duì)GLPSO算法的尋優(yōu)能力進(jìn)行分析，并與PSO算法和WPSO算法進(jìn)行對(duì)比。為保證實(shí)驗(yàn)的有效性，所有算法的最大迭代次數(shù)均設(shè)為200次。各算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行40次，并求40次計(jì)算結(jié)果的最優(yōu)值、最差值、平均值與方差。表2-表6給出了各算法之間的實(shí)驗(yàn)數(shù)據(jù)對(duì)比結(jié)果。

表2 函數(shù)F1實(shí)驗(yàn)結(jié)果比較Tab. 2 Experimental results of function F1

表3 函數(shù)F2實(shí)驗(yàn)結(jié)果比較Tab. 3 Experimental results of function F2

表4 函數(shù)F3實(shí)驗(yàn)結(jié)果比較Tab. 4 Experimental results of function F3

表5 函數(shù)F4實(shí)驗(yàn)結(jié)果比較Tab. 5 Experimental results of function F4

表6 函數(shù)F5實(shí)驗(yàn)結(jié)果比較Tab. 6 Experimental results of function F5

由表2-表6可知，PSO算法在尋優(yōu)過(guò)程中有很大的概率陷入局部最優(yōu)值，在3個(gè)算法的比較中效果最差。WPSO算法在引入慣性系數(shù)后改進(jìn)了算法的尋優(yōu)能力，提高了算法的尋優(yōu)精度和全局搜索能力，但WPSO算法的求解精度和搜索能力與GLPSO相比并不令人滿意，算法求解精度仍然偏低。本文所提出的GLPSO算法融合了高斯變異與Levy飛行方法，使算法中的種群具備了變異能力，提高了算法的全局尋優(yōu)性能，使算法更容易跳出局部最優(yōu)解。GLPSO算法在最優(yōu)值、最差值、方差和平均值方面均優(yōu)于PSO和WPSO算法，這表明GLPSO尋優(yōu)精度高，擁有更好的優(yōu)化能力，算法的穩(wěn)定性更高。

為進(jìn)一步分析算法的性能，圖2-圖6給出了算法在優(yōu)化不同函數(shù)時(shí)的收斂圖像。

圖2 F1函數(shù)收斂曲線Fig. 2 Convergence curve of F1 function

由圖2，圖3，圖5可知，GLPSO與PSO和WPSO相比其求解精度更高，算法不容易陷入局部最優(yōu)，有更強(qiáng)的全局尋優(yōu)能力。由圖4可知，GLPSO優(yōu)勢(shì)并不明顯，但從實(shí)驗(yàn)數(shù)值上來(lái)看，依然優(yōu)于對(duì)比算法。由圖6可知，GLPSO收斂速度更快，并由數(shù)值實(shí)驗(yàn)結(jié)果分析，GLSPO有更高的求解精度。

圖3 F2函數(shù)收斂曲線Fig. 3 Convergence curve of F2 function

圖4 F3函數(shù)收斂曲線Fig. 4 Convergence curve of F3 function

圖5 F4函數(shù)收斂曲線Fig. 5 Convergence curve of F4 function

圖6 F5函數(shù)收斂曲線Fig. 6 Convergence curve of F5 function

5 結(jié)語(yǔ)

本文在 PSO 原理的基礎(chǔ)上引入具有跳躍性質(zhì)的Levy飛行策略，并將高斯變異算子引入到算法中，使算法中的群體具有了變異能力，有效地保持了種群多樣性，減小了陷入局部最優(yōu)的概率。通過(guò)5個(gè)經(jīng)典函數(shù)對(duì)GLPSO算法的性能測(cè)試結(jié)果表明，GLPSO算法相對(duì)于基本PSO算法與帶有慣性系數(shù)的WPSO算法，具有更高的求解精度和更強(qiáng)的全局尋優(yōu)能力。因此，該算法擁有更廣闊的應(yīng)用前景。