基于差分進化的量子粒子群優(yōu)化算法的研究

留黎欽， 孫波， 王保云， 張萍

( 1.莆田學(xué)院 信息工程學(xué)院， 福建 莆田 351100； 2.南京郵電大學(xué) 通信與信息工程學(xué)院， 江蘇 南京 210003 )

0 引言

群體智能算法通過模擬生物種群個體之間的合作、競爭、交互和學(xué)習(xí)，可以在缺少局部信息的情況下，完成復(fù)雜問題求解.目前，群體智能算法已被廣泛應(yīng)用于無線通信系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、圖像處理、網(wǎng)絡(luò)態(tài)勢預(yù)測、特征選擇、數(shù)據(jù)聚類等領(lǐng)域，其主要應(yīng)用的算法有遺傳算法、蟻群優(yōu)化算法、差分進化算法和粒子群優(yōu)化算法.差分進化算法(differential evolution，DE)[1]是一種全局優(yōu)化啟發(fā)式算法，它可通過選擇變異的策略和設(shè)置相關(guān)參數(shù)來尋找最優(yōu)解.差分進化算法具有簡單和易于實現(xiàn)的優(yōu)點，但若迭代次數(shù)過多，容易引起過早的局部收斂.粒子群優(yōu)化算法(PSO)是一種模擬鳥群尋找食物的智能優(yōu)化算法，該算法易于搜索，收斂速度快[2]，但容易陷入局部最優(yōu).為了提高粒子群優(yōu)化算法的性能， Shi等[3]在粒子群算法中引進慣性權(quán)重來平衡局部和全局的搜索，但該算法容易過早收斂，即容易造成局部收斂.Suganthan[4]將粒子群分為若干個小的“鄰居群”，通過對每個“鄰居群”進行PSO迭代來尋找最優(yōu)值，該方法雖然不容易陷入局部最優(yōu)，但計算較為復(fù)雜.量子粒子群算法(QPSO)[5]中的粒子處于被束縛狀態(tài)，它能夠通過搜索整個解空間來獲得全局最優(yōu)解，但該算法在收斂過程中會減少種群的多樣性.為了提高量子粒子群算法的性能，本文將差分進化的思想引入到量子粒子群算法中，并通過仿真實驗證明本文方法的有效性.

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

局部吸引點的定義為：

(1)

在QPSO算法中，粒子最終收斂在以局部吸引點為中心的δ勢阱中，并更新迭代.假設(shè)粒子群具有D維的量子空間，粒子群在第n次迭代中，第i個粒子在以局部吸引點pi為中心的δ勢阱中移動,則在第n+1次迭代中，粒子狀態(tài)的更新如下式所示：

(2)

(3)

(4)

在QPSO算法中，最后更新的是粒子個體最優(yōu)狀態(tài)pbesti,n+1和群體最優(yōu)狀態(tài)gbestn+1， 即:

(5)

(6)

2 差分進化算法

差分進化算法主要包括變異、交叉和選擇操作.

1)變異操作.變異操作是將兩個個體向量之間的加權(quán)差加到第3個向量來產(chǎn)生新的個體，即對n時刻的第i個個體xi,n進行變異操作以產(chǎn)生變異個體vi,n+1[6]，其表達式如下：

(7)

其中，r1,r2,r3∈[1,M],且為互不相同的整數(shù)，同時與i均不相等.在變異操作中，xi,n被稱為父基向量， (xr2,n-xr3,n)被稱為父差分向量，K為比例因子.

2)交叉操作.為了改善種群的多樣性，對變異個體vi,n+1按式(8)進行交叉操作，以此產(chǎn)生測試個體ui,n+1.

(8)

其中：CR是交叉概率，介于[0，1]；jrand是一個隨機數(shù)，滿足jrand∈[1,2,3，…，D].該操作可以保證個體至少在一個維度上發(fā)生變異.

3)選擇操作.由貪婪選擇算法確定進入下一次迭代的個體：

(9)

3 基于差分進化的粒子群優(yōu)化算法(DE-QPSO)

DE-QPSO算法與QPSO算法的不同之處在于在粒子更新過程中引進了DE算法中的變異、交叉和選擇操作[7]，具體操作如下：

1)變異操作.當(dāng)粒子進行狀態(tài)更新時，添加一個擾動以生成一個變異粒子vi,n+1， 即

(10)

其中F為縮放因子.為了充分利用QPSO算法中粒子全局收斂的優(yōu)勢，在變異操作中不僅保留了QPSO算法中的局部吸引子和δ勢阱，還增加了差分向量.通過該方法不僅可以增加擾動，而且可以提高種群的多樣性.

2)交叉操作.對由公式(10)產(chǎn)生的變異粒子vi,n+1進行交叉操作，以此產(chǎn)生測試粒子ui,n+1：

(11)

其中：CR是交叉概率，介于(0，1)；jrand是一個隨機數(shù)，滿足jrand∈[1,2,3,…,D].

3)選擇操作.DE-QPSO算法的選擇操作和DE算法相同，如公式(9)表示.

粒子狀態(tài)更新結(jié)束后，更新粒子個體最優(yōu)pbesti,n+1和群體最優(yōu)gbestn+1，其更新過程如公式(5)—(6)所示.

DE -QPSO算法的具體步驟如下：

步驟2 計算平均最優(yōu)位置Cn，選擇合適的α.

步驟3 根據(jù)公式(1)計算每個粒子的局部吸引點.

步驟4 根據(jù)公式(10)進行變異操作.

步驟5 根據(jù)公式(11)進行交叉操作.

步驟6 根據(jù)公式(9)進行選擇操作.

步驟7 通過目標(biāo)函數(shù)，計算粒子的適應(yīng)值，并通過式(5)和式(6)更新全局最優(yōu)gbestn+1和個體最優(yōu)pbesti,n+1；

步驟8 若不滿足收斂條件，則返回步驟2，繼續(xù)執(zhí)行；否則，結(jié)束算法，輸出結(jié)果.

4 仿真實驗與分析

使用5個標(biāo)準(zhǔn)函數(shù)(Rosenbrock函數(shù)、Sphere函數(shù)、Griewank函數(shù)、Rastrigin函數(shù)以及Ackley函數(shù))測試DE-QPSO、PSO和QPSO算法的性能.各算法的迭代次數(shù)為1 000次，粒子的維度為10，粒子數(shù)為40個.利用各函數(shù)分別對目標(biāo)函數(shù)求解50次，并求解出各函數(shù)的平均最優(yōu)值和方差.測試結(jié)果見表1.由表1可以看出，DE-QPSO算法在5個函數(shù)中均獲得最優(yōu)解，而另外兩種算法沒有獲得最優(yōu)解.由圖1可以看出，在不同的測試函數(shù)上，DE -QPSO算法在收斂速度和收斂精度上均優(yōu)于QPSO和PSO算法.這說明，DE -QPSO算法不僅能夠保持種群的多樣性，而且有較好的收斂速度和收斂精度.

表1 各函數(shù)運行50次后的平均最優(yōu)值和方差

(a) Sphere函數(shù) (b) Rosenbrock函數(shù)圖1 3種算法在不同標(biāo)準(zhǔn)測試函數(shù)上的收斂曲線

4 結(jié)論

研究結(jié)果表明，本文提出的差分進化量子粒子群算法在5個標(biāo)準(zhǔn)函數(shù)(Rosenbrock函數(shù)、Sphere函數(shù)、Griewank函數(shù)、Rastrigin函數(shù)以及Ackley函數(shù))中都獲得了最優(yōu)解，且其收斂速度和收斂精度優(yōu)于PSO和QPSO算法.今后我們將進一步研究DE -QPSO算法在光纖通信信道分配方案問題中的應(yīng)用.