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

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

0 引 言

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

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

1 人工蜂群算法

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

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

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

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

(1)

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

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

(2)

(3)

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

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

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

(4)

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

2 改進人工蜂群算法

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

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

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

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

P=aPbest+(1-a)Gbest

(5)

b=1.0-g/maxg×0.5

(6)

(7)

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

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

2.2 QPSOABC算法流程

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

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

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

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

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

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

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

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

3 仿真實驗分析

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

3.1 測試函數(shù)選擇

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

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

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

Penalized2函數(shù)

3.2 實驗結(jié)果與分析

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

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

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

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

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

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

4 結(jié)束語

根據(jù)傳統(tǒng)ABC算法的不足，提出了一種針對跟隨蜂局部搜索能力的具體改進方案。算法將量子粒子群優(yōu)化算法中粒子位移的更新方法引入到跟隨蜂的局部搜索策略中，大幅提高了人工蜂群的局部搜索能力，使該算法的收斂速度和精度明顯提高。仿真實驗結(jié)果表明：在求解函數(shù)最小值優(yōu)化問題時，本文算法不僅可以有效避免函數(shù)陷入局部最優(yōu)，而且具有較好的魯棒性，進而提高了算法的收斂速度和尋優(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ā)式云計算任務(wù)調(diào)度算法[J].井岡山大學(xué)學(xué)報:自然科學(xué)版,2015(6):56-61.

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

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

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

[9] 邱劍鋒.人工蜂群算法的改進方法與收斂性理論的研究[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é)民,曹玉蘋.改進搜索策略的人工蜂群算法[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] 羅 浩,劉 宇.一種強化互學(xué)習的人工蜂群算法[J].計算機工程與應(yīng)用,2016,52(16):23-29.