量子粒子群優化的人工蜂群算法*

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

(1.江南大學 物聯網工程學院,江蘇 無錫 214122;2.中國水產科學研究院 淡水漁業研究中心,江蘇 無錫 214081)

0 引 言

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

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

1 人工蜂群算法

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

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

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

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

(1)

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

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

(2)

(3)

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

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

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

(4)

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

2 改進人工蜂群算法

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

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

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

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

P=aPbest+(1-a)Gbest

(5)

b=1.0-g/maxg×0.5

(6)

(7)

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

傳統的ABC算法每次都只修改一個維度的值，這樣做改變的內容較少。

2.2 QPSOABC算法流程

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

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

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

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

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

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

6)記錄當前的最優解。

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

3 仿真實驗分析

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

3.1 測試函數選擇

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

表1 測試函數的搜索范圍和理論最優值

6種函數形式如下：

Penalized2函數

3.2 實驗結果與分析

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

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

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

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

表2 30維函數測試結果

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

4 結束語

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

[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] 孫凌宇,冷 明,朱 平.一種基于貪心策略的啟發式云計算任務調度算法[J].井岡山大學學報:自然科學版,2015(6):56-61.

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

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

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

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