近似梯度引導的人工蜂群搜索策略*

謝 娟，蘇守寶，汪繼文

1.安徽建筑大學 數理學院，合肥 230601

2.金陵科技學院 計算機學院，南京 211169

3.安徽大學 計算機科學與技術學院，合肥 230601

近似梯度引導的人工蜂群搜索策略*

謝 娟1，蘇守寶2+，汪繼文3

1.安徽建筑大學 數理學院，合肥 230601

2.金陵科技學院 計算機學院，南京 211169

3.安徽大學 計算機科學與技術學院，合肥 230601

XIE Juan,SU Shoubao,WANG Jiwen.Search strategy of artificial bee colony algorithm guided by approximate gradient.Journal of Frontiers of Computer Science and Technology 2016,10(12)：1773-1782.

針對人工蜂群算法自身存在的局部搜索能力較差，收斂較慢，易受到局部最優束縛的問題，在種群搜索過程中引入梯度信息，并利用中心差分格式對梯度做近似處理，提出了一種基于種群的梯度搜索策略，并用于人工蜂群算法采蜜蜂階段的搜索，提高算法的局部搜索能力。同時，偵察蜂采用了全局隨機搜索策略，以避免在解決多峰問題時，由于快速收斂而導致的早熟現象。在6個標準測試函數上的仿真實驗結果表明，這種新的搜索機制在局部求解與全局探索之間取得了較好的平衡，使得改進后的算法在不同類型問題上的優化能力有了明顯改善。

人工蜂群算法；近似梯度；局部搜索；合作與共享

1 引言

人工蜂群算法（artificial bee colony algorithm，ABC）是由土耳其學者Karaboga于2005年提出的一種基于蜂群智能行為的啟發式優化算法[1]。ABC算法通過對蜂群個體之間在覓食過程中的勞動分工以及不同個體之間的信息共享機制——搖擺舞的模擬來實現對最優蜜源的選取。整個蜂群由采蜜蜂、觀察蜂和偵察蜂3種類型的蜜蜂組成。采蜜蜂負責對巢穴周圍的蜜源進行開采，記錄每個蜜源的含密量及與巢穴的距離，通過搖擺舞的方式與巢穴周圍的觀察蜂共享蜜源信息，進而招募更多的觀察蜂前去開采，以期發現更優質蜜源；在經過一段時間開采后，有些蜜源的質量無法得到進一步提高，則該蜜源將被拋棄，對應的采蜜蜂轉變為偵察蜂，重新選擇新的蜜源繼續進行開采。相對于其他的群智能優化算法，ABC算法能夠在局部搜索和全局探測之間做到較好的平衡，有效增加發現最優解的可能性，同時具有模型簡單，參數少，易于理解，魯棒性強的特點[2]，近年來受到國內外學者的廣泛關注，并且在函數優化[3-4]、聚類分析[5]、圖像處理[6-7]、負荷經濟調度[8-9]等多個領域得到廣泛應用。

在基本ABC算法中，采蜜蜂和偵察蜂負責在整個搜索范圍內發現潛在最優解，即全局探測；而觀察蜂是在“獲取”采蜜蜂所共享的信息后，受優質蜜源的“招募”，對其進行進一步開采以提高最優解的質量，即局部搜索。ABC算法中的這種勞動分工機制導致了算法的局部搜索能力較弱，收斂較慢，尤其在解決多峰優化問題時，易出現早熟現象[10-11]。針對上述問題，國內外學者提出了不同的改進策略以提高其局部搜索能力，促進算法的全局優化能力的提升。Zhu等人將當前全局最優解引入ABC算法的搜索策略中，提出GABC（Gbest-guided ABC）算法，在當前全局最優解的引導下，整個蜂群快速向其聚集，提高了算法的局部搜索能力和收斂速度[11]。Gao等人將差分進化的思想引入到ABC算法的搜索策略中，同時在種群的初始化中利用混沌及反向學習技術以提高種群初始化質量，提出了ABC/best/1和ABC/best/2算法[3]。然而，無論是GABC還是ABC/ best/1、ABC/best/2算法，其相似之處都在于將當前全局最優解引入蜜源的搜索策略，在優化過程中容易出現“早熟”現象，這一點在多峰問題中尤為明顯。由于單一的搜索策略難以克服復雜多變的優化問題，Kiran等人集成了具有不同特征的搜索方程，針對不同類型的優化問題選擇相應的搜索策略，提高解的質量和算法的魯棒性[12]。然而，為了選擇較好的搜索策略，需要對候選解的質量進行多次評價，增加了時間開銷。韓建權等人將基于當前最優解的混沌局部搜索策略和基于當前最優解的自適應偵查策略分別用于觀察蜂和偵察蜂的搜索策略，提高了人工蜂群算法的局部搜索能力，有效地避免了其陷入局部最優[13]。此外，其他學者也在此方面做了卓有成效的改進研究工作[14-17]，詳細的內容可以參考最近國內外關于ABC算法的文獻綜述[18-19]。

梯度信息往往給出了其方向導數在某點處取極值的方向，將其與其他智能優化算法結合，如差分進化[20]、遺傳算法[21]，提高了算法的優化能力。然而，可微性的要求限制了梯度信息在優化算法中的廣泛應用。Kuo等人在2015年提出了一種新的基于種群的梯度進化優化算法（gradient evolution，GE）[22]。受GE算法的啟發，本文將近似梯度的計算方法引入采蜜蜂階段的搜索，提出了一種基于梯度信息的人工蜂群算法（gradient based artificial bee colony algorithm，GdABC），以改進ABC算法的局部搜索能力，提高算法的優化性能。其優勢在于利用梯度具有方向性的特點，“引導”個體提高自身的局部搜索性能，從而進一步提高算法的局部搜索能力和收斂速度。

2 基本的人工蜂群算法

在ABC算法中，每一個蜜源表示優化問題的一個可行解，通常用一個D維向量xi表示：

其中NP為種群大小。蜜源（可行解）的優劣用適應度函數Fitness表示；參數trial記錄了每個蜜源沒有得到更新的次數；Limit給出了每個蜜源最多被更新的次數上限。一旦蜜源相應的trial值超過Limit，該蜜源將被拋棄。算法在種群初始化后，通過采蜜蜂、觀察蜂和偵察蜂3個階段的相互合作，反復迭代直至滿足迭代終止條件為止。下面從采蜜蜂、觀察蜂和偵察蜂3個階段概述基本ABC算法。

ABC算法首選在整個搜索空間內初始化NP個蜜源xi，每個蜜源用一個D維向量表示。為每個蜜源xi分配一個采蜜蜂，依據策略（2）在其鄰域內生成新的候選解vi：

其中k∈[1,2,…,NP],k≠i，j∈[1,2,…,D]。評估兩個蜜源的適應度值，采用貪婪選擇機制，如果新的蜜源vi的適應度優于原有蜜源xi，則更新xi，triali置0；否則保留原有蜜源xi，triali加1。在所有采蜜蜂完成搜索之后返回信息共享區域，計算每個蜜源的適應度在所有蜜源中的百分比，如式（3）所示：

巢穴附近的觀察蜂根據采蜜蜂所共享的蜜源信息（3），采用輪盤賭的方式選擇相應蜜源，即采蜜蜂所在蜜源的適應度百分比越高，能招募到更多的觀察蜂。觀察蜂被招募之后，進而轉變為采蜜蜂，仍然依據策略（2）在其鄰域內進行搜索。

當每個蜜源的triali超過能夠被評估的上限值Limit而解的質量仍未提高，則該蜜源將被拋棄，采蜜蜂轉變為偵察蜂，按式（4）在搜索空間內重新生成新的蜜源。

其中xjmin、xjmax分別為第 j維方向上的最小和最大值。ABC算法的邏輯框架如下所示：

3 近似梯度引導下的人工蜂群算法

梯度能夠引導算法的搜索快速指向可行解區域，有效地提高收斂速度。受GE算法的啟發[22]，本文在ABC算法的采蜜蜂階段引入梯度信息，提出基于梯度信息的采蜜蜂局部搜索策略。

采蜜蜂階段的更新策略使個體從當前位置xt移動到下一個可能的位置xt+1(xt+1=xt+Δx)，優化函數f(x)在x+Δx處的泰勒級數展開為：

對式（5）兩邊取一階導數，則有：

假設x+Δx處存在極值點，則 f′(x+Δx)=0，代入式（6）得：

利用牛頓-拉夫遜方法推導出下一個可能的位置xt+1可以表示為：

由中心差分公式對 f(x)的一階和二階導數做近似處理，最終可得對式（8）進行數值計算的中心差分格式：

在采蜜蜂的搜索策略中，將梯度信息作為引導蜜源的移動方向，采用類似式的搜索方程[22]。然而，由于ABC算法是一個基于種群的搜索算法，直接采用式（9）會額外增加目標函數的計算，影響優化算法的效率，增加計算時間。因此在式（9）的基礎上，結合GE算法的思想，給出適應于ABC算法搜索策略的梯度引導規則，主要包括以下幾個方面（以最小化問題為例）：

在更新蜜源后，根據采蜜蜂所攜帶的蜜源信息招募觀察蜂前往開采，仍然采用基本ABC算法中的更新規則（2）。當蜜源沒有被更新的次數trial超過Limit，蜜源將被拋棄，重新按照式（4）生成新的蜜源。綜上所述，本文提出的GdABC算法的邏輯框架如下所示：

4 仿真實驗及結果分析

為了驗證本文算法的有效性，選擇了經典的6個標準測試函數來驗證本文GdABC算法與基本ABC算法、GABC算法[11]在收斂精度、收斂速度等方面的比較。

4.1 標準測試函數

本文采用的6個基本測試函數如表1所示。

Table 1 Benchmark functions表1 標準測試函數

表1所給出的標準測試函數同時也是在其他文獻中被廣泛引用的[13,23]，F1～F6分別表示Sphere、Step、Schwefel、Rastrigin、Griewank和Rosenbrock測試函數。表1同時也給出了每個函數的類型：“U”表示僅有一個極值的單峰函數，主要用于對算法的收斂精度及速度的驗證；“M”表示存在多個極值的多峰函數，用于對算法的全局優化能力的驗證；此外，“S”、“N”分別表示優化函數的可分和不可分性。

4.2 實驗參數設置及實驗步驟

為了使實驗的比較盡可能公平，本文采用了Karaboga在其網站公開的ABC算法的源碼（http:// mf.erciyes.edu.tr/abc/publ.htm）。同時，作者對文獻[11]提出的GABC算法重新編碼，并依據文獻中參數設置進行了驗證。下面的實驗中統一采用如下參數配置：種群大小為100，其中采蜜蜂和偵察蜂的數量各為50，參數Limit為100，以最大迭代次數作為循環終止條件。

4.3 實驗結果及分析

仿真實驗在30維，最大迭代次數1 000和60維，最大迭代次數3 000兩種情況下分別獨立運行30次。同時，采用Wilcoxon秩和檢驗，在置信水平為0.05時，對算法均值之間的顯著性差異進行統計檢驗。表2和表3分別記錄了每個算法在不同維數下的最優值、最差值、均值、方差及顯著性差異。其中，在所比較的兩個算法的sign值中，“+”表示前者與后者之間的差異顯著，“－”表示兩者差異不顯著。圖1～圖12分別給出了3種算法（GdABC、GABC和ABC）在30維（圖1～圖6）和60維（圖7～圖12）下對6個標準測試函數的收斂曲線。

由上述實驗結果可以得出如下結論：從收斂精度上看，由于GdABC算法利用梯度信息引導采蜜蜂的搜索，提高了算法的局部搜索能力。30次獨立運行所得均值在30維情況下，GdABC算法在函數F1、F3、F4、F5的結果均優于其他兩種算法，F2和F6上的結果不低于其他兩種算法；在60維情況下，GdABC算法均優于其他算法。在0.05置信水平的假設檢驗結果亦表明GdABC算法在F1～F5上相對其他兩種算法均表現出顯著的差異性，而在F6上差異性不明顯，這與本文的實驗結果是一致的。

同時，由于偵察蜂仍采取全局隨機搜索策略，在一定程度上減少了算法在優化多峰問題早熟的風險。此外，在收斂速度上看，圖1～圖12的收斂曲線反映出GdABC算法的收斂速度明顯優于其他兩種算法。

5 結束語

針對基本ABC算法本身存在的局部搜索能力較弱，收斂較慢的問題，將梯度信息引入采蜜蜂的搜索策略中，并采用中心差分公式對梯度做近似處理，提

高了算法的局部搜索能力。同時偵察蜂仍然采取隨機的全局搜索策略，以保證算法仍具備較強的全局搜索能力。對6個典型標準測試函數的實驗結果表明，GdABC算法能夠較快地發現最優解，同時避免了多峰優化問題時易陷入局部最優的風險，整體優化性能有了較明顯提高。

Table 2 Experiment results on three algorithms（Dim=30,Maxiteration=1 000）表2 3種算法在30維最大迭代1 000次下的實驗結果

Table 3 Experiment results on three algorithms（Dim=60,Maxiteration=3 000）表3 3種算法在60維最大迭代3 000次下的實驗結果

Fig.1 Convergent curve of Sphere function in 30 dimensions圖1 Sphere函數在30維時的收斂曲線

Fig.2 Convergent curve of Step function in 30 dimensions圖2 Step函數在30維時的收斂曲線

Fig.3 Convergent curve of Schwefel function in 30 dimensions圖3 Schwefel函數在30維時的收斂曲線

Fig.4 Convergent curve of Rastrigin function in 30 dimensions圖4 Rastrigin函數在30維時的收斂曲線

Fig.5 Convergent curve of Griewank function in 30 dimensions圖5 Griewank函數在30維時的收斂曲線

Fig.6 Convergent curve of Rosenbrock function in 30 dimensions圖6 Rosenbrock函數在30維時的收斂曲線

Fig.7 Convergent curve of Sphere function in 60 dimensions圖7 Sphere函數在60維時的收斂曲線

Fig.8 Convergent curve of Step function in 60 dimensions圖8 Step函數在60維時的收斂曲線

Fig.9 Convergent curve of Schwefel function in 60 dimensions圖9 Schwefel函數在60維時的收斂曲線

Fig.10 Convergent curve of Rastrigin function in 60 dimensions圖10 Rastrigin函數在60維時的收斂曲線

Fig.11 Convergent curve of Griewank function in 60 dimensions圖11 Griewank函數在60維時的收斂曲線

Fig.12 Convergent curve of Rosenbrock function in 60 dimensions圖12 Rosenbrock函數在60維時的收斂曲線

[1]Karaboga D.An idea based on honeybee swarm for numerical optimization,TR06[R].Kayseri:Erciyes University,Engineering Faculty,Computer Engineering Department,2005.

[2]Gao Weifeng,Liu Sanyang.Improved artificial bee colony algorithm for global optimization[J].Information Processing Letters,2011,111(17):871-882.

[3]Gao Weifeng,Liu Sanyang,Huang Lingling.A global best artificial bee colony algorithm for global optimization[J]. Journal of Computational&Applied Mathematics,2012, 236(11):2741-2753.

[4]Tsai P W,Pan J S,Liao B Y,et al.Enhanced artificial bee colony optimization[J].International Journal of Innovative Computing Information&Control,2009,5(12):5081-5092.

[5]Tran D C,Wu Zhijian,Wang Zelin,et al.A novel hybrid data clustering algorithm based on artificial bee colony algorithm and K-means[J].Chinese Journal of Electronics,2015, 24(4):694-701.

[6]Draa A,Bouaziz A.An artificial bee colony algorithm for image contrast enhancement[J].Swarm and Evolutionary Computation,2014,16:69-84.

[7]Charansiriphaisan K,Chiewchanwattana S,Sunat K.Acomparative study of improved artificial bee colony algorithms applied to multilevel image thresholding[J].Mathematical Problems in Engineering,2013:17.

[8]Abro A G,Mohamad-Saleh J.Enhanced probability-selection artificial bee colony algorithm for economic load dispatch: a comprehensive analysis[J].Engineering Optimization, 2014,46(10):1315-1330.

[9]Bulut O,Tasgetiren M F.An artificial bee colony algorithm for the economic lot scheduling problem[J].International Journal of Production Research,2014,52(4):1150-1170.

[10]Li Guoqiang,Niu Peifeng,Xiao Xingjun.Development and investigation of efficient artificial bee colony algorithm for numerical function optimization[J].Applied Soft Computing, 2012,12(1):320-332.

[11]Zhu Guopu,Kwong S.Gbest-guided artificial bee colony algorithm for numerical function optimization[J].Applied Mathematics and Computation,2010,217(7):3166-3173.

[12]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.

[13]Han Jianquan,Mao Li,Zhou Changxi.Artificial bee colony algorithm based on improved local search strategy[J].Journal of Frontiers of Computer Science and Technology, 2015,9(6):761-767.

[14]Tang Lingyun,Mao Li,Zhou Changxi.Improved artificial bee colony algorithm for function optimization[J].Journal of Frontiers of Computer Science and Technology,2015,9 (7):854-860.

[15]Xie Juan,Qiu Jianfeng,Min Jie,et al.Improved artificial bee colony algorithm with dual cognitive abilitied and performance analysis[J].Computer Science,2014,41(11):269-272.

[16]Zhou Xinyu,Wu Zhijian,Deng Changshou,et al.Neighbour search-based artificial bee colony algorithm[J].Journal of Central South University:Science and Technology, 2015,46(2):534-546.

[17]Zang Peiquan,Sun Chen’ao,Gu Xiaofeng,et al.An artificial bee colony bee colony algorithm with adaptive chemotaxis and guiding factors[J].Computer Engineering and Science,2015,37(9):1692-1697.

[18]Qin Quande,Cheng Shi,Li Li,et al.Artificial bee colony algorithm:a survey[J].CAAI Transactions on Intelligent Systems,2014,9(2):127-135.

[19]Karaboga D,Gorkemli B,Ozturk C,et al.A comprehensive survey:artificial bee colony(ABC)algorithm and applications[J].Artificial Intelligence Review,2014,42(1):21-57.

[20]Ibtissem C,Nouredine L.A hybrid method based on conjugate gradient trained neural network and differential evolution for non linear systems identification[C]//Proceedings of the 2013 International Conference on Electrical Engineering and Software Applications,Hammamet,Mar 21-23, 2013.Piscataway,USA:IEEE,2013:1-5.

[21]Du Tingsong,Fei Pusheng,Shen Yanjun.A modified niche genetic algorithm based on evolution gradient and its simulation analysis[C]//Proceedings of the 3rd International Conference on Natural Computation,Haikou,Aug 24-27,2007. Piscataway,USA:IEEE,2007:35-39.

[22]Kuo R J,Zulvia F E.The gradient evolution algorithm:a new metaheuristic[J].Information Sciences,2015,316:246-265.

[23]Cao Chunhong,Xu Guangxing.Geometric constraint solvingbased on improved artificial bee colony algorithm[J].Journal of Frontiers of Computer Science and Technology,2015, 9(9):1122-1131.

附中文參考文獻：

[13]韓建權,毛力,周長喜.基于改進局部搜索策略的人工蜂群算法[J].計算機科學與探索,2015,9(6):761-767.

[14]唐凌蕓,毛力,周長喜.求解函數優化問題的改進人工蜂群算法[J].計算機科學與探索,2015,9(7):854-860.

[15]謝娟,邱劍鋒,閔杰,等.具有雙重認知能力的人工蜂群算法及性能分析[J].計算機科學,2014,41(11):269-272.

[16]周新宇,吳志健,鄧長壽,等.一種鄰域搜索的人工蜂群算法[J].中南大學學報:自然科學版,2015,46(2):534-546.

[17]臧培荃,孫晨驁,顧曉峰,等.具有自適應趨向性和引導因子的人工蜂群算法[J].計算機工程與科學,2015,37(9): 1692-1697.

[18]秦全德,程適,李麗,等.人工蜂群算法研究綜述[J].智能系統學報,2014,9(2):127-135.

[23]曹春紅,許光星.基于改進人工蜂群算法的幾何約束求解[J].計算機科學與探索,2015,9(9):1122-1131.

XIE Juan was born in 1980.She received the M.S.degree from Anhui University in 2007.Now she is an associate professor at Anhui Jianzhu University.Her research interests include intelligent optimization algorithm,evolutionary computing and machine learning,etc.

謝娟（1980—），女，安徽淮北人，2007年于安徽大學獲得碩士學位，現為安徽建筑大學副教授，主要研究領域為智能優化算法，進化計算，機器學習等。

SU Shoubao was born in 1965.He received the Ph.D.degree from Anhui University in 2009.Now he is a professor and M.S.supervisor at Jinling Institute of Technology,and the senior member of CCF.His research interests include swarm intelligence,big data computing and embedded control optimization,etc.

蘇守寶（1965—），男，安徽六安人，2009年于安徽大學獲得博士學位，現為金陵科技學院教授、碩士生導師，CCF高級會員，主要研究領域為群智能，大數據計算，嵌入式控制優化等。

WANG Jiwen was born in 1958.He received the Ph.D.degree from University of Science and Technology of China in 2001.Now he is a professor and Ph.D.supervisor at Anhui University.His research interests include intelligent computing and machine learning,etc.

汪繼文（1958—），男，安徽宿松人，2001年于中國科學技術大學獲得博士學位，現為安徽大學教授、博士生導師，主要研究領域為智能計算，機器學習等。

Search Strategy of Artificial Bee Colony Algorithm Guided by Approximate Gradient*

XIE Juan1,SU Shoubao2+,WANG Jiwen3
1.School of Mathematics&Physics,Anhui Jianzhu University,Hefei 230601,China
2.School of Computer,Jinling Institute of Technology,Nanjing 211169,China
3.School of Computer Science&Technology,Anhui University,Hefei 230601,China
+Corresponding author:E-mail:showbo@jit.edu.cn

To solve the problems of inferior local search ability,slow convergence and easily trapping into the local optimization existing in the artificial bee colony algorithm,this paper proposes a gradient search strategy based on population by introducing gradient information and using central difference schemes for gradient approximation processing.The novel search strategy used by employed bees improves the local search ability while the scout bees still employ global random searching strategy to avoid premature phenomenon led by fast convergence in solving multimodal problems.Simulation results in six standard test functions show that the proposed searching mechanism gives a good balance between local solution and global exploration and improves the optimization ability of differentkinds of optimization problems.

artificial bee colony algorithm;approximate gradient;local search;cooperation and sharing

10.3778/j.issn.1673-9418.1601072

A

TP301.6

*The National Natural Science Foundation of China under Grant No.61375121(國家自然科學基金);the Provincial Projects of Natural Science for Anhui Universities under Grant No.KJ2013A009(安徽高校省級自然科學研究項目);the Doctoral Scientific Research Foundation of Anhui University(安徽大學博士啟動基金);the Scientific Research Program for Introducing Talents of Jinling Institute of Technology under Grant No.jit-rcyj-201505(金科院引進人才科研項目).

Received 2016-01,Accepted 2016-04.

CNKI網絡優先出版:2016-04-01,http://www.cnki.net/kcms/detail/11.5602.TP.20160401.1614.006.html