張志強 魯曉鋒 孫欽東 王侃

摘 要：為解決人工蜂群（ABC）算法收斂速度慢、精度不高和易于陷入局部最優(yōu)等問題，提出一種增強開發(fā)能力的改進人工蜂群算法。一方面，將得出的最優(yōu)解以兩種方式直接引入雇傭蜂搜索公式中，通過最優(yōu)解指導雇傭蜂的鄰域搜索行為，以增強算法的開發(fā)或局部搜索能力;另一方面，在旁觀蜂搜索公式中結合當前解及其隨機鄰域進行搜索，以改善算法的全局優(yōu)化能力。對多個常用基準測試函數的仿真實驗結果表明，在收斂速度、精度和全局優(yōu)化能力等方面，所提算法總體上優(yōu)于其他類似的ABC算法（例如ABC/best）和集成多種搜索策略的ABC算法（例如ABCVSS（ABC algorithm with Variable Search Strategy）和ABCMSSCE（ABC algorithm with Multi-Search Strategy Cooperative Evolutionary））。

關鍵詞：群體智能;人工蜂群算法;最優(yōu)解;鄰域搜索

中圖分類號：?TP301.6

文獻標志碼：A

文章編號：1001-9081（2019）04-0949-07

Abstract： The basic Artificial Bee Colony （ABC） algorithm has some shortcomings such as slow convergence， low precision and easily getting trapped in local optimum. To overcome these issues， an improved ABC algorithm with enhanced exploitation ability was proposed. On one hand， the obtained optimum solution was directly introduced into the search equations of employed bees in two different ways and guided the employed bees to perform neighborhood search， which enhanced the exploitation or local search ability of the algorithm. On the other hand， the search was performed by the combination of the current solution and its random neighborhood in the search equations of onlooker bees， which improved the global optimization ability of the algorithm. The simulation results on some common benchmark functions show that in convergence rate， precision， and global optimization or exploration ability， the proposed ABC algorithm is generally better than the other similar improved ABC algorithms such as global best ABC （ABC/best） algorithm， and some ABC algorithms with hybrid search strategy such as ABC algorithm with Variable Search Strategy （ABCVSS） and Multi-Search Strategy Cooperative Evolutionary （ABCMSSCE）.

Key words： swarm intelligence; Artificial Bee Colony （ABC） algorithm; optimum solution; neighborhood search

0?引言

人工蜂群（Artificial Bee Colony， ABC）是受蜜蜂群覓食行為啟發(fā)而提出的一種群體智能（Swarm Intelligence）算法[1]。與遺傳算法、差分進化、粒子群算法和進化策略相比，ABC算法具有較強的競爭力[2]，已被應用于人工神經網絡、工業(yè)工程、電子工程、數據挖掘、圖像處理等領域[3]。然而和其他群體智能算法類似：在解決復雜優(yōu)化問題時，ABC算法存在收斂速度慢和易于陷入局部最優(yōu)等問題。

為此，近年來已有學者提出了一些改進的ABC算法。例如，文獻[4]提出通過學習和按維更新策略的思維進化ABC算法，并對其收斂性進行了分析。文獻[5]提出雇傭蜂采用全局最優(yōu)引導的搜索策略，并且引導程度隨個體實驗次數自適應減小，以平衡算法的全局和局部搜索能力;旁觀蜂采用變異的異維學習策略，使算法的搜索具有跳躍性，以提高逃出局部最優(yōu)的概率。文獻[6]提出自適應步長的快速ABC算法，使旁觀蜂搜索階段的周邊食物源參數自適應化，并結合反向學習策略改進雇傭蜂搜索階段。文獻[7]提出在基本ABC算法全局搜索公式中引入反饋機制，直接搜索最優(yōu)解可能存在的區(qū)域，以提高算法的開發(fā)能力和收斂速度;加入線性微分遞增策略，平衡算法各個階段的開發(fā)能力和探索能力;根據叢林法則，算法隨機選擇較差個體進行初始化，以防止算法陷入局部最優(yōu)。文獻[8]提出在基本ABC算法基礎上引入隨機鄰域搜索策略和跨維搜索策略，并改進蜜蜂越限處理方式，使得算法搜索方式多樣化，從而使算法搜索更具跳躍性，不易陷入局部最優(yōu)解。文獻[9]提出利用反向學習方法構建初始種群，以提高初始化解的質量;利用分布估計算法構造優(yōu)秀個體解空間的概率模型進行鄰域搜索，以改善算法的搜索性能并防止陷入局部最優(yōu)。文獻[10]提出利用自適應思想定義新的位置更新公式，由此提高蜂群間交互的相關性;利用雙向隨機優(yōu)化機制約束適應度函數的搜索方向，由此提高算法的局部搜索能力;將粒子群算法引入基本ABC算法的初始階段，利用其收斂速度快的特性，以較少的迭代次數產生全局最優(yōu)解作為初始蜜源位置，提高算法的收斂速度。文獻[11]提出在雇傭蜂和旁觀蜂進行鄰域搜索時， 動態(tài)調整搜索的維數以提高搜索效率， 并結合5種不同的搜索策略使其協同進化，以平衡算法的局部搜索和全局搜索能力。

以上研究主要針對基本ABC算法中雇傭蜂和旁觀蜂搜索行為或公式提出了各種改進，在很大程度上克服了算法收斂速度慢和易于陷入局部最優(yōu)等缺點，然而存在的主要問題是：與基本ABC算法相比，改進算法的參數更多、運行機制更復雜[9-11];從實驗仿真結果來看，在解決復雜函數優(yōu)化問題方面，改進算法性能表現仍有待驗證。例如，文獻[4-5，7]測試的問題維數最高為50，而文獻[6]只測試了30維的問題，文獻[8]提出的ABC算法僅與基本的ABC算法和粒子群算法進行了比較等。為此，本文在基本ABC算法的雇傭蜂階段，提出兩種增強開發(fā)能力的搜索公式，利用最優(yōu)解和當前解進行鄰域搜索;在旁觀蜂階段，提出基于當前解和隨機鄰域解的兩種鄰域搜索公式，增加算法全局搜索方式的靈活性。

1?ABC算法模型與步驟

在ABC算法模型中，根據分工不同把蜜蜂群分為3組：雇傭（employed）蜂、旁觀（onlooker）蜂和偵查（scout）蜂。雇傭蜂負責采集以前勘察過的蜂蜜源，并向蜂巢中的旁觀蜂通告食物源質量;旁觀蜂根據雇傭蜂共享的信息決定要開采的食物源;偵查蜂隨機搜索蜂巢周圍環(huán)境以發(fā)現新的食物源。蜜蜂群的一半成員是雇傭蜂，另一半成員是旁觀蜂（偵查蜂僅有一只）。每個食物源代表優(yōu)化問題的一個解，它對應一個雇傭蜂和一個旁觀蜂，食物源個數是蜜蜂種群大小的一半。根據ABC算法官方網站https：//abc.erciyes.edu.tr/software.htm提供的源程序，ABC算法基本步驟如下所示：1）根據式（1）隨機生成食物源的初始位置：

故Xi表示某個食物源，即優(yōu)化問題的一個初始解。

2）計算解的成本（目標函數值），并按照式（2）求適應度：

其中：φi， j實際為區(qū)間[-1，1]內均勻分布的隨機數;Vi表示食物源Xi附近的鄰域解。隨后計算解Vi的成本并按照式（2）計算適應度，以進行原解Xi和新解Vi間的貪心式選擇：如果新解的適應度大于原解的適應度，則以新解替換原解;否則嘗試改進失敗次數計數器Trail加1。

4）?旁觀蜂根據式（4）計算食物源的選擇概率：

其中：Pi為旁觀蜂選擇食物源i的概率。適應度越高的食物源，被選中的概率越大。

5）旁觀蜂根據式（4），選擇概率最大的食物源，然后同樣根據式（3），對選中的食物源執(zhí)行鄰域搜索。

6）更新并保存算法獲得的（迄今為止）最優(yōu)解。

7）偵查蜂檢查食物源的計數器Trail是否大于預設的限制次數Limit，如果是則執(zhí)行式（1）重新初始化該食物源。

重復步驟3）～7），直至滿足某個條件則算法終止。

2?增強開發(fā)能力的ABC算法

2.1?已有改進ABC算法搜索公式分析

從ABC算法工作原理與步驟來看，雇傭蜂和旁觀蜂在多維空間中搜索最優(yōu)解的過程是關鍵，對算法求解質量和性能表現有重要影響。然而在基本ABC算法中，雇傭蜂和旁觀蜂都僅在當前解的附近進行搜索，并使用相同的搜索公式或策略獲得鄰域解，導致算法的勘探（exploration）或全局搜索能力較強，而開發(fā)（exploitation）或局部搜索能力不足[12-15]，因而有學者提出如下常見的改進ABC算法搜索公式[12-16]：

文獻[12]提出基于粒子群算法的式（5），并用于雇傭蜂和旁觀蜂搜索;文獻[13]提出基于差分進化算法的式（6）～（7），并分別應用于雇傭蜂和旁觀蜂搜索;文獻[14]提出基于粒子群算法的式（8），并應用于雇傭蜂和旁觀蜂搜索;文獻[15]提出基于差分進化算法的式（9），并應用于雇傭蜂搜索;文獻[16]提出基于差分進化算法的式（10）～（11），并同時應用于雇傭蜂和旁觀蜂搜索。

上述改進ABC算法搜索公式既包含相似的結構和迭代方式，又存在一定的性能差異，易于集成后形成混合多種搜索策略的ABC算法[11，17]。然而，這些搜索公式存在的主要問題是：式（5）、（7）借鑒了粒子群算法的思想，導致算法參數更多、運行機制更復雜;式（8）、（11）忽視了算法在每次迭代過程中求出的最優(yōu)解的指導作用;盡管式（5）～（7）、（9）～（10）包含了最優(yōu)解信息，但是從其仿真實驗及結果來看，對高維復雜問題的優(yōu)化效果還有進一步提高的余地。

2.2?本文ABC算法搜索公式

雇傭蜂和旁觀蜂在多維空間中搜索出的最優(yōu)解，是蜜蜂群體合作取得的重要成果和寶貴經驗，因為它非常接近于或可能就是全局最優(yōu)解，

如果對其加以利用可增強算法的開發(fā)能力，并改善ABC算法的求解質量和性能表現。

然而在基本ABC算法中，只是簡單地在每次循環(huán)中記錄最優(yōu)解，并沒有在雇傭蜂和旁觀蜂搜索公式中發(fā)揮最優(yōu)解的引導作用。

有鑒于此，本文提出如下的雇傭蜂搜索公式：

式（12）、（13）都基于基本ABC算法雇傭蜂搜索公式：將式（3）中等號右邊的Xk， j替換為Xbest，k即可得式（12），將式（3）中等號右邊的Xi， j替換為Xbest，k即可得式（13）。在式（12）和（13）中，k和j的取值互不影響。因此問題維數越高，k和j取值相等的概率就越低，取值不同的k和j意味著雇傭蜂在執(zhí)行異維（或跨維）式的鄰域搜索。已有研究表明，異維搜索避免了ABC算法單一搜索模式的局限性，增強了ABC算法的全局搜索能力，有利于算法擺脫局部最優(yōu)[5，8]。

在式（12）中，鄰域解Vi是以當前食物源Xi為參考，并結合最優(yōu)解Xbest的信息執(zhí)行鄰域搜索獲得的新解;在式（13）中，鄰域解Vi是以最優(yōu)解Xbest為參考，并結合當前食物源Xi的信息執(zhí)行鄰域搜索獲得的新解。

其中：p與i、q與j的取值同樣各自獨立，依然利用了異維搜索帶來的好處。

在式（14）中，鄰域解Vi是以當前食物源Xi為參考，并結合隨機選擇的鄰域解Vp的信息進行鄰域搜索獲得的新解;在式（15）中，鄰域解Vi是以隨機選擇的鄰域解Xp為參考，并結合當前食物源Xi的信息進行鄰域搜索獲得的新解。

2.3?本文算法步驟

綜上所述，本文提出的增強開發(fā)能力的改進ABC算法主要步驟如下：1）根據式（1）隨機生成食物源的初始位置;

2）根據式（2）計算各個初始解的適應度，對比后保存最優(yōu)解;

3）根據式（12）或（13），分派雇傭蜂到食物源地點進行鄰域搜索;

4）根據式（4）計算旁觀蜂選擇食物源的概率，并選擇一個食物源;

5）旁觀蜂對選中的食物源，根據式（14）或（15），進行鄰域搜索;

6）更新并保存算法得到的最優(yōu)解;

7）偵查蜂檢查食物源的計數器Trail是否大于等于預設值Limit，如果是則將最優(yōu)解賦值給該食物源，以充分利用最優(yōu)解信息。

重復執(zhí)行步驟3）～7），直至滿足特定條件則本文算法終止。

綜上所述，和其他改進ABC算法相比，本文算法的主要優(yōu)勢在于：僅簡單地修改了基本ABC算法的第3）、5）、7）步，算法主體結構并無變動;沒有引入新的算法參數，無需額外的參數設置或調校;沒有增加算法復雜度，易于編程實現。

3?仿真實驗及分析

本文算法采用C++編程語言實現了2個版本：以最大循環(huán)次數（Maximum Cycles Number， MCN）為算法終止條件的MCN版、以最大適應度評估次數（Maximum Fitness Evaluations， MFE）為算法終止條件的MFE版。為便于實驗仿真并和其他ABC算法比較，本文采用表1所示的文獻中最常見的測試函數。

表1中9個測試函數均為實參數的數值優(yōu)化問題，其定義可見文獻[11，17]。

Sphere、Tablet、Step、Quartic、Schwefel、Rosenbrock是單峰函數，其定義域內僅有一個全局最小值，用于檢驗算法收斂速度和精度;Ackley、Rastrigin、Griewank是多峰函數，其定義域內存在多個局部最小值和一個全局最小值，用于檢驗算法全局優(yōu)化能力。

首先將本文算法與基本ABC算法進行比較，二者參數設置均為：種群大小NP=40，食物源數SN=20，限制次數Limit=100，最大循環(huán)次數MCN=3000，測試函數維數D=100。圖1是本文算法和基本ABC算法優(yōu)化Sphere、Rosenbrock、Griewank、Rastrigin函數時的收斂曲線。

為了清晰地展示實驗結果，圖1的縱軸均采用對數坐標表示最優(yōu)值。

根據圖1（a）的單峰函數Sphere和圖1（d）的多峰函數Rastrigin收斂曲線可以發(fā)現，本文算法的收斂速度、精度和全局優(yōu)化能力優(yōu)于基本ABC算法。根據圖1（b）的單峰函數Rosenbrock和圖1（c）的多峰函數Griewank收斂曲線可以發(fā)現：在基本ABC算法和本文算法執(zhí)行的早期，收斂曲線有交叉重疊部分，兩個算法表現差別較小;自算法執(zhí)行中期以后，二者差距很快擴大，本文算法仍然優(yōu)于基本ABC算法。此現象的主要成因是：Rosenbrock是一個病態(tài)的螺旋型函數（空間分布圖見文獻[9]），通常很難求出其全局最優(yōu)解;Griewank是一個100維的復雜多峰函數，在其定義域內存在多個局部最優(yōu)解;在本文算法執(zhí)行的早期，最優(yōu)解的質量難免較差，導致它對雇傭蜂鄰域搜索行為的指導作用尚不明顯;從本文算法執(zhí)行中期以后，最優(yōu)解的質量得到了改善，對雇傭蜂的鄰域搜索行為開始發(fā)揮其重要的指導作用。此外，在整個算法執(zhí)行過程中，旁觀蜂的搜索行為不受最優(yōu)解的影響，用于保持或增強算法的勘探能力。

在文獻[4，6-10]的仿真實驗中，均以最大循環(huán)次數為算法終止條件，然而算法參數和測試函數的搜索范圍與維數卻不相同。因此，再將本文算法的MCN版與這些ABC算法逐個地兩兩比較，具體做法是：1）每個對比組中的本文算法和其他ABC算法參數設置相同;2）每個對比組中測試函數的搜索范圍和維數等均一致;3）其他ABC算法的實驗結果都來自于對應的參考文獻;4）如果文獻中有不同維數測試函數的實驗結果，則只取其中維數最高的進行比較。

首先以Sphere、Tablet、Step、Quartic、Schwefel、Rosenbrock等單峰函數為對象，測試本文算法的收斂速度和精度，實驗結果如表2所示。

從表2可以發(fā)現，對于除Rosenbrock之外的其他單峰函數和對比組中的算法，本文算法實驗結果的最差值、最優(yōu)值、平均值和標準差，明顯優(yōu)于文獻[4，6-8，10]算法;僅在求解Rosenbrock函數時，本文算法才稍遜于文獻[9]算法。因此說明，在收斂速度和精度方面，本文算法總體上優(yōu)于其他ABC算法。

再以Ackley、Rastrigin、Griewank等多峰函數為對象，測試本文算法的全局優(yōu)化能力，實驗結果如表3所示。

從表3可以發(fā)現，對于所有多峰函數和對比組中的2個算法，本文算法實驗結果的最差值、最優(yōu)值、平均值和標準差，明顯優(yōu)于對比算法。因此說明，在全局優(yōu)化能力方面，本文算法優(yōu)于其他對比算法。

值得注意的是，文獻[18]指出一些ABC算法研究中存在誤區(qū)：算法終止條件通?；谧畲笱h(huán)次數，而不是最大適應度評估次數。由于僅當算法不包含局部搜索過程或沒有混合其他算法時，以最大循環(huán)次數為終止條件進行算法實驗比較才算公平合理，所以建議以最大適應度評估次數為算法終止條件[18]。為了準確地與其他ABC算法進行比較，下面采用MFE版的本文算法，與同樣以最大適應度評估次數為終止條件的ABC算法ABCMSSCE（ABC algorithm with Multi-Search Strategy Cooperative Evolutionary）[11]、ABC/best1[13]、ABC/best2[13]、ABCVSS（ABC algorithm with Variable Search Strategy）[17]進行比較，實驗結果表4所示。

說明：1）所有測試函數的維數D=100;2）Schwefel 2.21、Schwefel 2.22、SumSquares、Schaffer等測試函數的定義詳見文獻[11];3）包括本文算法在內的所有ABC算法參數設置均為食物源數SN=20，限制次數Limit=SN×D，最大適應度評估次數MFE=5000×D，算法運行次數為30。

從表4可知：對于單峰函數，本文算法求解Sphere、Schwefel 2.21、Schwefel 2.22、SumSquares實驗結果的最差值、最優(yōu)值、平均值和標準差，明顯優(yōu)于其他對比算法，僅在求解Quartic時，本文算法才稍遜于ABCMSSCE算法[11]，這說明在收斂速度和精度方面，本文算法總體上優(yōu)于其他對比算法。

對于多峰函數，本文算法求解Rastrigin和Ackley實驗結果的最差值、最優(yōu)值、平均值和標準差，優(yōu)于其他對比算法，僅在求解Schaffer時，本文算法才稍遜于ABCMSSCE算法[11]，這說明在全局優(yōu)化能力方面，本文算法總體上優(yōu)于其他對比算法。

4?結語

在解決復雜高維優(yōu)化問題時，ABC算法在收斂速度、精度和全局優(yōu)化能力方面仍然存在不足。本文算法研究的核心思想是，在基本ABC算法的雇傭蜂階段，重視對最優(yōu)解信息的利用，并提出兩種增強開發(fā)能力的搜索公式，以增強算法的局部搜索能力;在基本ABC算法的旁觀蜂階段，提出利用當前解執(zhí)行兩種不同的隨機鄰域搜索。仿真實驗結果表明，本文算法是有效的。

與蟻群算法和粒子群算法相比，ABC算法無疑還需要有關學者開展更多的理論及應用研究。例如，本文算法還可以結合其他學者提出的雇傭蜂和旁觀蜂搜索公式（策略），以進一步增強本文算法的開發(fā)和勘探能力;本文提出的雇傭蜂和旁觀蜂搜索公式，也為開發(fā)包含混合搜索策略的ABC算法提供了新思路;本文算法還可以應用于其他領域（如工程優(yōu)化和機器學習），以解決其中的復雜優(yōu)化或學習問題等。

參考文獻（References）

[1] KARABOGA D， BASTURK B. A powerful and efficient algorithm for numerical function optimization： Artificial Bee Colony （ABC） algorithm [J]. Journal of Global Optimization， 2007， 39（3）： 459-471.

[2] KARABOGA D， AKAY B. A comparative study of artificial bee colony algorithm [J]. Applied Mathematics and Computation， 2009， 124（1）： 108-132.

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

[4] 暴勵.一種思維進化蜂群算法[J]. 電子學報， 2015， 43（5）： 948-955. （BAO L. A mind evolutionary artificial bee colony algorithm [J]. Acta Electronica Sinica， 2015， 43（5）： 948-955.）

[5] 李冰， 孫輝， 趙嘉， 等. 異維學習人工蜂群算法[J]. 計算機應用研究， 2016， 33（4）： 1028-1033. （LI B， SUN H， ZHAO J， et al. Artificial bee colony algorithm with different dimensional learning[J]. Application Research of Computers， 2016， 33（4）： 1028-1033.）

[6] 楊小健， 董毅偉. 基于反向學習的自適應快速人工蜂群算法[J]. 系統(tǒng)仿真學報， 2016， 28（11）： 2684-2700. （YANG X J， DONG Y W. Adaptive quick artificial bee colony algorithm based on opposition learning [J]. Journal of System Simulation， 2016， 28（11）： 2684-2700.）

[7] 孔金生， 李世通， 周樹亮， 等. 基于反饋機制和叢林法則的人工蜂群算法[J]. 計算機工程與應用， 2017， 53（17）： 53-59. （KONG J S， LI S T， ZHOU S L， et al. Artificial bee colony algorithm based on feedback and law of jungle [J]. Computer Engineering and Applications， 2017， 53（17）： 53-59.）

[8] 林凱， 陳國初， 張鑫. 多交互式人工蜂群算法及其收斂性分析[J]. 計算機應用， 2017， 37（3）： 760-765. （LIN K， CHEN G C， ZHANG X. Multiple interactive artificial bee colony algorithm and its convergence analysis [J]. Journal of Computer Applications， 2017， 37（3）： 760-765.）

[9] 王永琦， 吳飛， 孫建華. 求解連續(xù)空間優(yōu)化問題的改進蜂群算法[J]. 計算機應用研究， 2018， 35（3）： 658-704. （WANG Y Q， WU F， SUN J H. Modified artificial bee colony algorithm for Solving Continuous space optimization problems [J]. Application Research of Computers， 2018， 35（3）： 658-704.）

[10] 劉鑫， 楊霄鵬， 姚昆， 等. 自適應隨機優(yōu)化策略的改進人工蜂群算法[J]. 小型微型計算機系統(tǒng)， 2018， 39（2）： 235-239. （LIU X， YANG X P， YAO K， et al. Improved artificial bee colony algorithm based on self-adaptive random optimization strategy[J]. Journal of Chinese Computer Systems， 2018， 39（2）： 235-239.）

[11] 王志剛， 尚旭東， 夏慧明， 等. 多搜索策略協同進化的人工蜂群算法[J]. 控制與決策， 2018， 33（2）： 235-241. （WANG Z G， SHANG X D， XIA H M， et al. Artificial bee colony algorithm with multi-search strategy cooperative evolutionary[J]. Control and Decision， 2018， 33（2）： 235-241.）

[12] ZHU G， KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization [J]. Applied Mathematics and Computation， 2010， 217（7）： 3166-3173.

[13] GAO W， LIU S， HUANG L. A global best artificial bee colony algorithm for global optimization [J]. Journal of Computational and Applied Mathematics， 2012， 236（11）： 2741-2753.

[14] GAO W， LIU S， HUANG L. A novel artificial bee colony algorithm based on modified search equation and orthogonal learning [J]. IEEE Transactions on Cybernetics， 2013， 43（3）： 1011-1024.

[15] GAO W， LIU S. A modified artificial bee colony algorithm [J]. Computer & Operations Research， 2012， 39（3）： 687-697.

[16] GAO W， LIU S. Improved artificial bee colony algorithm for global optimization [J]. Information Processing Letters， 2011， 111（17）： 871-882.

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

[18] MERNIK M， LIU S H， KARABOGA D， 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.