一種改進的人工蜂群算法研究

曹亞麗 余牧舟 楊俊峰 宋昕

摘 ?要： 針對人工蜂群算法在更新策略中精度與穩定性不高的問題，提出一種改進的人工蜂群算法。該改進的人工蜂群算法通過增加每次更新維度的個數來改善算法的精度，在文中所選擇的每次更新維度的個數為可行解維數的[12];同時，該算法選擇當前適應值最優的蜂蜜源在其周圍進行鄰域搜索，避免了由于隨機性而帶來的算法精度降低問題。最后，比較改進的人工蜂群算法與經典的粒子群算法，通過多個高維測試函數的仿真實驗表明，改進的人工蜂群算法比粒子群算法具有更高的精度和穩定性，展現了更好的性能。

關鍵詞： 人工蜂群算法; 算法改進; 數據分析; 更新維度; 領域搜索; 仿真實驗

中圖分類號： TN919?34 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）12?0133?05

Abstract： In allusion to the problem that the artificial bee colony algorithm has low accuracy and stability in the update strategy， an improved artificial bee colony algorithm is proposed. The accuracy of the algorithm is improved by increasing the number of dimensions per update， and the selected number of dimensions per update is half of the feasible solution dimensions in this paper; the honeycomb source with the best adaptive value is chosen to conduct a neighbourhood search around it， which avoids the reducing the accuracy of the algorithm caused by the randomness. The simulation results with multi high?dimensional testing functions show that， in comparison with the classical particle swarm optimization algorithm， the improved artificial bee colony algorithm has a higher accuracy and stability， and show better performance.

Keywords： artificial bee colony algorithm; algorithm improvement; data analysis; update dimension; area search; simulation experiment

0 ?引 言

人工蜂群算法（ABC）通過模仿蜜蜂覓食時群體之間的相互作用求得最優解，是一種有效的單目標問題的解決方案。該算法在2005年由Karaboga首次提出，有三種類型的蜜蜂參與人工蜂群算法[1]，分別是雇傭蜂、跟隨蜂和偵察蜂。它們參與不同的搜索過程。雇傭蜂多次通過鄰域搜索在特定范圍內鎖定蜜源的位置，并通過搖擺舞的方式將食物的相關信息傳遞給跟隨蜂[2]。搖擺舞中包含的信息有食物的數量和與蜂窩之間的間距等信息。蜜蜂覓食過程如圖1所示，在ABC中，雇傭蜂的數量與食物位置數量相同，即食物與雇傭蜂是一一對應的。每個蜜源位置坐標即代表優化問題的解坐標。蜜源的數量對應的是蜜源的適應值。蜜源數量越大，可行解的適應值越小（單目標最小化優化問題），可行解質量越高。當雇傭蜂多次位置未更新時，說明該位置陷入了局部最優值，雇傭蜂變為偵察蜂，通過局部搜索確定新蜜源位置[3]。跟隨蜂依據各個雇傭蜂所供給的關于食物的信息，按照比例與概率選擇蜜源，概率越大，代表食物越多，在各個跟隨蜂選定相應雇傭蜂之后，執行鄰域搜索，確定蜜源位置。在重復循環多次上述步驟之后，跟隨蜂中適應值最小食物源位置就是優化問題的最優可行解[4]。

現階段，已有許多文獻對人工蜂群算法的改進和應用進行了研究。文獻[5]將人工蜂群算法與前饋人工神經網絡（FF?ABC）相結合，用于混凝土中氯化物的滲透預測。文獻[6]針對柔性生產線的問題，提出了一種基于帕累托的人工蜂群算法（PGABC）。該算法可以得到具有三種不同導向機構的帕累托近似最優解。文獻[7]提出了一種多目標人工蜂群算法，該算法集成了兩種性能增強方案，首次解決了負載平衡和傳輸延遲的網絡編碼問題。在Khan的研究論文中，采用更新規則和k?opt操作對人工蜂群算法進行了改進，解決了旅行商問題[8]。Choong在人工蜂群算法中應用了一種超啟發式方法，即改進了選擇函數（MCF），該算法可以自動調節雇傭蜂和跟隨蜂的鄰域搜索選擇[9]。文獻[10]針對蒸汽驅注方案的優化問題，提出了一種基于改進人工蜂群算法的蒸汽驅注方案優化方法。文獻[11]基于子空間分解（ISD）和人工蜂群（ABC）算法，提出了一種稱為ISD?ABC的帶選擇技術，解決了HSI分類中維數減少的問題。

1 ?人工蜂群算法

在人工蜂群算法（ABC）中，人工蜂群包含三種類別的蜜蜂。它們分別是雇傭蜂、跟隨蜂和觀察蜂。其中雇傭蜂和跟隨蜂的數量相同，并且分別占蜂群總數的[12]。每個雇傭蜂對應一個蜂蜜源，這些雇傭蜂的主要工作是尋找并記錄與之對應的蜂蜜源。然后將蜂蜜源的相關信息通過圓擺舞的方式傳遞給跟隨蜂，跟隨蜂就根據這些信息來選擇蜂蜜源[12]。當雇傭蜂對應的蜂蜜源的位置多次未改變，雇傭蜂變為觀察蜂，通過局部搜索確定新蜂蜜源的位置[13?15]。

在該算法中，每個蜂蜜源位置坐標表示一個可行解。本文給出了每個蜂蜜源的適應值[fit（i）]，該值用于評估每個蜂蜜源的花蜜量[16]。在算法每一次循環中，雇傭蜂都通過鄰域搜索尋找每個蜂蜜源，并計算每個蜂蜜源對應的適應值。根據雇傭蜂傳遞的信息（即每個蜂蜜源的適應值），跟隨蜂通過一定的概率來選擇蜂蜜源，并在選擇的蜂蜜源周圍尋找新的蜂蜜源，并計算它們的適應值[17?19]。

這種學習策略使得雇傭蜂和跟隨蜂在當前最優的蜂蜜源周圍進行鄰域搜索，提高了搜索的精度，并且每次的搜索過程是多維度的，提高了搜索的速度。圖3是改進的人工蜂群算法在每一個維度上的潛在搜索空間。

3 ?仿真實驗分析

3.1 ?測試函數

為了測試改進ABC算法的求解精度與收斂速度[20?21]，采用5個標準測試函數：Sphere函數、Rosenbrock 函數、Rastrigin函數、Griewank 函數和Ackley 函數，并與粒子群算法（PSO）進行了比較。

3.1.6 ?PSO算法

粒子群優化算法（PSO）是一種進化計算技術（Evolutionary Computation），1995 年由Eberhart和Kennedy提出，源于對鳥群捕食的行為研究。該算法最初是受到飛鳥集群活動的規律性啟發，進而利用群體智能建立的一個簡化模型。粒子群算法在對動物集群活動行為觀察基礎上，利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中產生從無序到有序的演化過程，從而獲得最優解。

3.2 ?實驗結果

在仿真實驗中，為了保證結果的公平與有效性，對改進的ABC算法與PSO算法進行了初值的設置，其中，蜂群數量與粒子群數量大小均設置為100，算法的運算次數均為50次。每次算法執行中，循環的次數均設置為1 500次。在這兩種算法中就5個測試函數分別運行50次后，求平均值得到了改進的ABC算法與PSO算法在50維空間與100維空間的數據結果如表1和表2所示。

表1、表2中，均值分別代表兩種算法就每個函數運行50次后的平均水平，且能最大程度地降低偶然誤差的影響，因此將均值作為兩種算法的評價指標，并將該結果數字在表中加粗。均值越接近理論值，則代表該算法的優化效果越好。根據表中的數據可知，在50維和100維的空間中，對于Sphere，Rosenbrock，Rastrigin，Griewank和Ackley 函數的優化結果，改進的ABC算法較PSO算法更接近理論值。由此可見，改進的ABC算法有更好的求解精度。

5個測試函數的仿真曲線如圖4～圖8所示。根據圖4 ～圖8運行結果可知，對于Sphere 函數，改進的ABC算法在大約第250次循環時達到1，PSO算法在大約第100次循環時穩定到1.5;對于Rosenbrock 函數，改進的ABC算法在大約第500次循環時穩定在160，PSO算法在大約第100次循環時穩定到200;對于Rastrigin 函數，改進的ABC算法在大約第500次循環時達到80，PSO算法在大約第100次循環時穩定到200;對于Griewank 函數，改進的ABC算法在大約第500次循環時達到0.01，PSO算法在大約第100次循環時穩定到0.025;對于Ackley 函數，改進的ABC算法在大約第400次循環時達到0.5，PSO算法在大約第50次循環時穩定到2。由此可見，改進的ABC算法較PSO算法展示了更好的求解精度與穩定性，但在收斂效果方面略有不足，這也是以后有待于改進的地方。

4 ?結 ?語

為了解決這個問題，本文提出了一個改進的人工蜂群算法。通過增加每次更新的維度個數來改善算法的穩定性，并且選擇當前適應值最優的蜂蜜源周圍進行鄰域搜索來提高算法的精度，但在收斂速度方面存在不足，有待于進一步改善。總之本文將所提出的算法與粒子群算法在高維空間進行比較，通過多組測試函數的仿真表明所提出的算法具有較好的性能。

參考文獻

[1] KIRAN M S， HAKLI H， GUNDUZ M， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization [J]. Information sciences， 2015， 300： 140?157.

[2] 梁靜，葛宇，冉曉娟，等.一種人工蜂群算法改進方案[J].計算機應用研究，2015，32（11）：3295?3299.

[3] ZHU G P， KWONG S. Gbest?guided artificial bee colony algorithm for numerical function optimization [J]. Applied mathematics & computation， 2010（7）： 3166?3173.

[4] 林小軍，葉東毅.一種帶規范知識引導的改進人工蜂群算法[J].模式識別與人工智能，2013，26（3）：307?314.

[5] MEYSAM N， NADER G， MEHDI N. Modeling chloride penetration in self?consolidating concrete using artificial neural network combined with artificial bee colony algorithm [J]. Journal of building engineering， 2019， 22： 216?226.

[6] YUE L， GUAN Z L， ZHANG L， et al. Multi?objective lotsizing and scheduling with material constraints in flexible parallel lines using a Pareto based guided artificial bee colony algorithm [J]. Computers & industrial engineering， 2018（16）： 659?680.

[7] XING H L， SONG F H， YAN L S， et al. On multicast routing with network coding： a multiobjective artificial bee colony algorithm [J]. China communication， 2019， 16（2）： 170?186.

[8] KHAN I， MAITI M K. A swap sequence based Artificial Bee Colony algorithm for traveling salesman problem [J]. Swarm and evolutionary computation， 2019， 44： 428?438.

[9] CHOONG S S， WONG L P， LIM C P. An artificial bee colony algorithm with a modified choice function for the traveling salesman problem [J]. Swarm and evolutionary computation， 2019， 44： 622?635.

[10] NI H M， LIU Y J， FAN Y C. Optimization of injection scheme to maximizing cumulative oil steam ratio based on improved artificial bee colony algorithm [J]. Journal of petroleum science and engineering， 2019， 173： 371?380.

[11] XIE F D， LI F F， LEI C K， et al. Unsupervised band selection based on artificial bee colony algorithm for hyper?spectral image classification [J]. Applied soft computing， 2019， 75： 428?440.

[12] 李華，盧靜.改進人工蜂群算法的無線傳感器網絡覆蓋優化[J].現代電子技術，2018，41（3）：14?18.

[13] MUSTAFA Servet Kiran， HUSEYIN Hakli， MESUT Gunduz， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization [J]. Information sciences， 2015， 300： 140?157.

[14] 田屏.一種基于混沌搜索改進的人工蜂群算法[J].西南師范大學學報（自然科學版），2018，43（7）：39?45.

[15] 劉曉芳，柳培忠，駱炎民，等.一種增強局部搜索能力的改進人工蜂群算法[J].智能系統學報，2017，12（5）：684?693.

[16] MARJAN Mernik， SHIH Hsi Liu， DERVIS Karaboga， et al. On clarifying misconceptions when comparing variants of the artificial bee colony algorithm by offering a new implementation [J]. Information sciences， 2015， 291： 115?127.

[17] XUE Yu， JIANG Jiongming， ZHAO Binping， et al. Aself?adaptive ?artificial bee colony algorithm ?based on ?global best for global optimization [J]. Soft computing， 2017（8）： 1?18.

[18] 王繼超，李擎，崔家瑞，等.一種改進的人工蜂群算法：粒子蜂群算法[J].工程科學學報，2018，40（7）：871?881.

[19] LIN Qinzhen， ZHU Miaomiao， LI Genghui， et al. A novel artificial bee colony algorithm with local and global information interaction [J]. Applied soft computing journal， 2018， 62： 702?735.

[20] 楊慧婷，楊文忠，殷亞博，等.基于深度信念網絡的K?means 聚類算法研究[J].現代電子技術，2019，42（8）：145?150.

[21] 張志強，魯曉鋒，孫欽東，等.一種增強開發能力的改進人工蜂群算法研究[J].計算機應用，2018（12）：1?9.