量子粒子群優(yōu)化的人工蜂群算法*

杜康宇, 毛 力, 毛 羽, 楊 弘, 肖 煒

(1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無(wú)錫 214122;2.中國(guó)水產(chǎn)科學(xué)研究院 淡水漁業(yè)研究中心,江蘇 無(wú)錫 214081)

0 引 言

人工蜂群(artificial bee colony，ABC)算法[1]具有結(jié)構(gòu)簡(jiǎn)單、魯棒性強(qiáng)、控制參數(shù)少、易于實(shí)現(xiàn)的優(yōu)點(diǎn)，近年來(lái)受到越來(lái)越多國(guó)內(nèi)外學(xué)者的關(guān)注，成為求解函數(shù)最優(yōu)化問(wèn)題的熱點(diǎn)之一。但文獻(xiàn)[2～6]表明與其他群智能算法一樣，ABC算法在求解函數(shù)優(yōu)化問(wèn)題中具有收斂速度慢、局部搜索能力低的缺點(diǎn)。針對(duì)上述問(wèn)題，葛宇等人[7]給出了一種新思路，針對(duì)跟隨蜂的局部搜索行為提出了新方案，即基于極值優(yōu)化策略高效率的尋優(yōu)機(jī)制；文獻(xiàn)[8]對(duì)傳統(tǒng)ABC算法在自種群分組、種群架構(gòu)、種群淘汰和步長(zhǎng)更新方面進(jìn)行了創(chuàng)新，引入了小生境技巧即時(shí)淘汰落入局部最優(yōu)的蜜蜂個(gè)體，利用種群交叉的Z型分組方式，同時(shí)結(jié)合均勻設(shè)計(jì)理論建立初始種群；文獻(xiàn)[9]利用邏輯運(yùn)算創(chuàng)新地提出了離散人工蜂群算法，通過(guò)引入一系列的邏輯運(yùn)算，不但成功避免了目前離散ABC算法中面臨的解不更新問(wèn)題，并且高效地保證了搜尋進(jìn)程的中心解和最后解均封鎖在原離散封閉集內(nèi)，使算法的搜索效率大幅提高，成功地解決了實(shí)數(shù)集與離散集間的映射問(wèn)題。以上方法在一定程度上使算法的精度提高了，改進(jìn)了ABC算法在求解函數(shù)優(yōu)化問(wèn)題中的局部搜尋能力，對(duì)增強(qiáng)算法的性能和擴(kuò)展其應(yīng)用范圍起到了重要的研究意義。

針對(duì)傳統(tǒng)ABC算法中局部搜索能力較差，收斂速度慢等問(wèn)題，本文提出了一種基于量子粒子群優(yōu)化(quantum-behaved particle swarm optimization,QPSO)的人工蜂群算法,即QPSOABC算法。將QPSO算法中粒子位移的更新方法引入到了跟隨蜂的搜索策略中，大幅提高了人工蜂群的局部搜索能力，同時(shí)算法的收斂速度和精度明顯提高。

1 人工蜂群算法

人工蜂群算法是一種新的隨機(jī)搜索方法，模擬了蜂蜜的行為模式，并成功地應(yīng)用于函數(shù)優(yōu)化問(wèn)題[10～12]。算法的具體描述如下：

1)初始化：在規(guī)定的上下界中隨機(jī)生成SN個(gè)可行解(蜜源)Xi=(Xi1，Xi2，…，XiD)，每個(gè)解與蜜源、雇傭蜂和跟隨蜂一一對(duì)應(yīng)。

2)雇傭蜂搜索階段：隨機(jī)選擇蜜源中的任意一維分量按式(1)進(jìn)行變異，搜索新蜜源

vi,j=xi,j+rand(-1,1)(xi,j-xk,j)

(1)

式中Vi,j為新蜜源的位置；xi,j為個(gè)體Xi的第j維分量；xk,j為個(gè)體Xk的第j維分量。進(jìn)入采蜜過(guò)程，雇傭蜂通過(guò)貪婪選擇策略對(duì)新蜜源進(jìn)行篩選，選取適應(yīng)度較高的蜜源。

3)跟隨蜂搜索階段：搜索過(guò)程完成后，雇傭蜂將傳遞蜜源信息給跟隨蜂，根據(jù)式(2)、式(3)計(jì)算出選擇跟隨蜂的概率，并通過(guò)輪盤(pán)賭的形式對(duì)適應(yīng)度值較高的優(yōu)質(zhì)蜜源進(jìn)行更新，其中，跟隨蜂的更新公式和式(1)相同

(2)

(3)

式中fi為目標(biāo)函數(shù)f(Xi)的適應(yīng)度值；fiti為蜜源Xi對(duì)應(yīng)的適應(yīng)度。

4)偵查蜂搜索階段：如果蜜源在連續(xù)循環(huán)的規(guī)定時(shí)間后沒(méi)有改善，即轉(zhuǎn)化為偵察蜂。偵察蜂根據(jù)式(4)隨機(jī)生成一個(gè)新解取代當(dāng)前解，并記錄新蜜源適應(yīng)度

Xi=Xmin+rand(0,1)(Xmax-Xmin)

(4)

式中Xmax和Xmin為解空間的上、下邊界。

2 改進(jìn)人工蜂群算法

在算法的尋優(yōu)過(guò)程中，雇傭蜂負(fù)責(zé)全局搜索，偵察蜂由進(jìn)化停滯的雇傭蜂轉(zhuǎn)化而來(lái)，處理進(jìn)化停滯的個(gè)體，也屬于全局搜索，該算法全局搜索能力較強(qiáng)；原始ABC算法中，跟隨蜂的更新公式和雇傭蜂的跟隨公式相同，即算法局部搜索能力較差，因此，將其他算法中的局部更新方式與跟隨蜂的局部更新方式進(jìn)行結(jié)合即可相應(yīng)提高算法的精度和收斂速度。

2.1 基于QPSO的跟隨蜂局部搜索策略

在傳統(tǒng)的ABC算法中，雇傭蜂與跟隨蜂的搜索策略完全相同，因此,跟隨蜂的全局搜尋能力非常強(qiáng)大，但局部搜尋能力相對(duì)較弱。在改進(jìn)的算法中，為了提高跟隨蜂的局部搜尋能力，利用雇傭蜂個(gè)體極值和全局極值進(jìn)行局部尋優(yōu)，且在每次迭代中逐維更新蜜源每一維度的值，以確定蜜源是否改進(jìn)。

該算法融合量子能夠遍歷整個(gè)解空間的行為特性，根據(jù)蜜源位置的波函數(shù)與概率密度函數(shù)，基于量子δ勢(shì)阱模型進(jìn)行位移更新，QPSO中的位移操作實(shí)質(zhì)上是一種局部搜索策略，跟隨蜂按照式(5)～式(7)更新位置

P=aPbest+(1-a)Gbest

(5)

b=1.0-g/maxg×0.5

(6)

(7)

式中a,u為(0，1)之間的隨機(jī)數(shù)；Pbest為個(gè)體極值；Gbest為全局極值；b為收縮膨脹系數(shù)；g為當(dāng)前進(jìn)化代數(shù)；maxg為規(guī)定的最大進(jìn)化代數(shù)。

傳統(tǒng)的ABC算法每次都只修改一個(gè)維度的值，這樣做改變的內(nèi)容較少。

2.2 QPSOABC算法流程

對(duì)于最小值優(yōu)化問(wèn)題Minf(X)，改進(jìn)ABC算法實(shí)現(xiàn)的具體步驟如下：

1)初始化算法參數(shù)，隨機(jī)產(chǎn)生SN個(gè)解，每個(gè)解Xi=(Xi1，Xi2，…，XiD)為一個(gè)D維向量，最大迭代次數(shù)MCN，并指定控制參數(shù)limit的值，用于確定個(gè)體是否更新停滯。

2)對(duì)種群中每個(gè)雇傭蜂Xi在D維空間中利用式(1)逐維搜索，若新個(gè)體較原個(gè)體優(yōu)秀則更新；否則，保留Xi。

3)記錄雇傭蜂變化之后的個(gè)體極值Pbest和全體極值Gbest，并將其代入式(5)得到的結(jié)果代入式(2)和式(3)，并計(jì)算每個(gè)食物源被選擇的概率。

4)跟隨蜂遵循輪盤(pán)賭的方式在部分優(yōu)質(zhì)蜜源附近局部搜索，選擇部分適應(yīng)度值較高的蜜源，然后每個(gè)跟隨蜂在D維空間內(nèi)利用式(7)更新種群中的所有蜜源。

5)當(dāng)蜜源在連續(xù)limit次迭代后未更新時(shí)，根據(jù)式(4)隨機(jī)生成一個(gè)新蜜源替代原蜜源。

6)記錄當(dāng)前的最優(yōu)解。

7)判別是否達(dá)到最大迭代次數(shù)MCN，如果滿足，則輸出最優(yōu)解；否則，轉(zhuǎn)到步驟(2)。

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

為評(píng)估QPSO算法的性能，本文采用6個(gè)典型的測(cè)試函數(shù)[13]對(duì)QPSOABC算法、ABC算法以及文獻(xiàn)[14,15]中改進(jìn)ABC算法的穩(wěn)定性、收斂速度和尋優(yōu)精度進(jìn)行對(duì)比實(shí)驗(yàn)。

3.1 測(cè)試函數(shù)選擇

表1列出了6個(gè)測(cè)試函數(shù)的搜索范圍和理論最優(yōu)值。其中：f1～f3為單模態(tài)函數(shù)，在定義域內(nèi)只有一個(gè)極值點(diǎn)，主要用于測(cè)試函數(shù)的收斂速度和尋優(yōu)精度；f4～f6為非線性多模態(tài)函數(shù)，存在多個(gè)局部極值點(diǎn)，用于測(cè)試算法的全局尋優(yōu)性能和避免早熟的能力。

表1 測(cè)試函數(shù)的搜索范圍和理論最優(yōu)值

6種函數(shù)形式如下：

Penalized2函數(shù)

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

在QPSOABC，Best-so-far ABC，ABC 3種對(duì)比算法的實(shí)驗(yàn)中，參數(shù)設(shè)置如下：種群規(guī)模SN=50，確定是否落入停頓的循環(huán)控制參數(shù)limit=10，維度D=30，最大迭代次數(shù)MCN=1 000。

為了測(cè)試該算法的性能，采用上述3種算法對(duì)6個(gè)測(cè)試函數(shù)在30維的條件下進(jìn)行30次獨(dú)立實(shí)驗(yàn)，記錄其所對(duì)應(yīng)的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差和平均耗時(shí)，平均耗時(shí)即6個(gè)測(cè)試函數(shù)在單獨(dú)運(yùn)行30次到達(dá)收斂穩(wěn)定精度所需要的時(shí)間的平均值。

表2中的數(shù)據(jù)表明：傳統(tǒng)的ABC算法具有收斂速度慢、收斂精度不高、算法穩(wěn)定性較差的缺點(diǎn)；Best-so-far ABC算法采用當(dāng)前最優(yōu)解及其對(duì)應(yīng)的適應(yīng)度值改良跟隨蜂的鄰域搜尋方式，從而提高了算法的局部搜尋能力，使算法的質(zhì)量有了較大提高。QPSOABC算法將量子粒子群優(yōu)化算法中粒子位移的更新方法引入到了跟隨蜂的局部搜索策略中，大幅提高了人工蜂群的局部搜索能力，使該算法的收斂速度和精度明顯提高。

在測(cè)試函數(shù)f1,f2中，由于Best-so-far ABC算法陷入局部最優(yōu)解，因此出現(xiàn)了方差較小的結(jié)果。針對(duì)單峰函數(shù)sphere函數(shù)f1、多峰Schwefel函數(shù)f2、The Rotated Elliptic函數(shù)f4以及Griewank函數(shù)f5，由于傳統(tǒng)ABC的隨機(jī)性問(wèn)題，收斂速度明顯較其他2種算法慢，而B(niǎo)est-so-far ABC算法中雖然最終效果相對(duì)原算法較好，但是前期收斂速度慢，并且后期由于部分個(gè)體落入局部最優(yōu)解的問(wèn)題，使得算法精度并未達(dá)到理想的效果。本文算法可以有效地避免局部?jī)?yōu)化，收斂速度快，可以收斂到理想的精度。針對(duì)單峰Rosenbrock函數(shù)f3，多峰Penalized2函數(shù)f6，傳統(tǒng)ABC算法和Best-so-far ABC算法的收斂速度和收斂精度均很不理想，本文改進(jìn)的算法收斂速度和收斂精度明顯改進(jìn)，不過(guò)未克服易陷入局部最優(yōu)的問(wèn)題，算法仍有改進(jìn)空間。

表2 30維函數(shù)測(cè)試結(jié)果

上述實(shí)驗(yàn)結(jié)果表明：與傳統(tǒng)ABC算法和Best-so-far ABC算法相比，QPSOABC算法具有更快的收斂速度和更高的收斂精度。QPSOABC算法將量子粒子群優(yōu)化算法中粒子位移的更新方法引入到跟隨蜂的局部搜索策略中，大幅提高了人工蜂群的局部搜索能力，使算法的收斂速度和精度明顯提高。

4 結(jié)束語(yǔ)

根據(jù)傳統(tǒng)ABC算法的不足，提出了一種針對(duì)跟隨蜂局部搜索能力的具體改進(jìn)方案。算法將量子粒子群優(yōu)化算法中粒子位移的更新方法引入到跟隨蜂的局部搜索策略中，大幅提高了人工蜂群的局部搜索能力，使該算法的收斂速度和精度明顯提高。仿真實(shí)驗(yàn)結(jié)果表明：在求解函數(shù)最小值優(yōu)化問(wèn)題時(shí)，本文算法不僅可以有效避免函數(shù)陷入局部最優(yōu)，而且具有較好的魯棒性，進(jìn)而提高了算法的收斂速度和尋優(yōu)精度。

[1] Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm[J].Applied Soft Computing,2008,8(1):687-697.

[2] Sarangi P P,Sahu A,Panda M.Training a feed-forward neural network using artificial bee colony with back-propagation algorithm[J].Advances in Intelligent Systems & Computing,2014,243:511-519.

[3] Karaboga D,Ozturk C.Neural networks training by artificial bee colony algorithm on pattern classification[J].Neural Network World,Neural Network World,2009,19(3):279-292.

[4] Banharnsakun A,Sirinaovakul B,Achalakul T.Job shop scheduling with the best-so-far ABC[J].Engineering Applications of Artificial Intelligence,2012,25(3):583-593.

[5] 孫凌宇,冷 明,朱 平.一種基于貪心策略的啟發(fā)式云計(jì)算任務(wù)調(diào)度算法[J].井岡山大學(xué)學(xué)報(bào):自然科學(xué)版,2015(6):56-61.

[6] 丁婷婷,高美鳳.改進(jìn)粒子濾波的無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法[J].傳感器與微系統(tǒng),2016,35(7):140-142.

[7] 葛 宇,梁 靜,王學(xué)平,等.求解函數(shù)優(yōu)化問(wèn)題的改進(jìn)的人工蜂群算法[J].計(jì)算機(jī)科學(xué),2013,40(8):252-257.

[8] 臧明相,馬 軒,段奕明.一種改進(jìn)的人工蜂群算法[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2015,42(2):65-70.

[9] 邱劍鋒.人工蜂群算法的改進(jìn)方法與收斂性理論的研究[D].合肥：安徽大學(xué),2014.

[10] Banharnsakun A,Achalakul T,Sirinaovakul B.The best-so-far selection in artificial bee colony algorithm[J].Applied Soft Computing,2011,11(2):2888-2901.

[11] Li X,Yang G.Artificial bee colony algorithm with memory[J].Applied Soft Computing,2016,41:362-372.

[12] Li X,Yin M.Parameter estimation for chaotic systems by hybrid differential evolution algorithm and artificial bee colony algo-rithm[J].Nonlinear Dynamics,2014,77(1-2):1-11.

[13] 張銀雪,田學(xué)民,曹玉蘋(píng).改進(jìn)搜索策略的人工蜂群算法[J].計(jì)算機(jī)應(yīng)用,2012,32(12):3326-3330.

[14] Banharnsakun A,Achalakul T,Sirinaovakul B.The best-so-far selection in artificial bee colony algorithm[J].Applied Soft Computing,2011,11(2):2888-2901.

[15] 羅 浩,劉 宇.一種強(qiáng)化互學(xué)習(xí)的人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(16):23-29.