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

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

0 引言

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

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

局部吸引點(diǎn)的定義為：

(1)

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

(2)

(3)

(4)

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

(5)

(6)

2 差分進(jìn)化算法

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

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

(7)

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

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

(8)

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

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

(9)

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

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

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

(10)

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

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

(11)

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)與分析

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

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

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

4 結(jié)論

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