摘要：为解决人工蜂群（ABC）算法收敛速度慢、精度不高和易于陷入局部最优等问题，提出一种增强开发能力的改进人工蜂群算法。一方面，将得出的最优解以两种方式直接引入雇佣蜂搜索公式中，通过最优解指导雇佣蜂的邻域搜索行为，以增强算法的开发或局部搜索能力;另一方面，在旁观蜂搜索公式中结合当前解及其随机邻域进行搜索，以改善算法的全局优化能力。对多个常用基准测试函数的仿真实验结果表明，在收敛速度、精度和全局优化能力等方面，所提算法总体上优于其他类似的ABC算法（例如ABC/best）和集成多种搜索策略的ABC算法（例如ABCVSS（ABCalgorithmwithVariableSearchStrategy）和ABCMSSCE（ABCalgorithmwithMulti-SearchStrategyCooperativeEvolutionary））。
关键词：群体智能;人工蜂群算法;最优解;邻域搜索
中图分类号：TP301.6
文献标志码：A
Keywords：swarmintelligence;ArtificialBeeColony（ABC）algorithm;optimumsolution;neighborhoodsearch
0引言
人工蜂群（ArtificialBeeColony，ABC）是受蜜蜂群觅食行为启发而提出的一种群体智能（SwarmIntelligence）算法[1]。与遗传算法、差分进化、粒子群算法和进化策略相比，ABC算法具有较强的竞争力[2]，已被应用于人工神经网络、工业工程、电子工程、数据挖掘、图像处理等领域[3]。然而和其他群体智能算法类似：在解决复杂优化问题时，ABC算法存在收敛速度慢和易于陷入局部最优等问题。
以上研究主要针对基本ABC算法中雇佣蜂和旁观蜂搜索行为或公式提出了各种改进，在很大程度上克服了算法收敛速度慢和易于陷入局部最优等缺点，然而存在的主要问题是：与基本ABC算法相比，改进算法的参数更多、运行机制更复杂[9-11];从实验仿真结果来看，在解决复杂函数优化问题方面，改进算法性能表现仍有待验证。例如，文献[4-5，7]测试的问题维数最高为50，而文献[6]只测试了30维的问题，文献[8]提出的ABC算法仅与基本的ABC算法和粒子群算法进行了比较等。为此，本文在基本ABC算法的雇佣蜂阶段，提出两种增强开发能力的搜索公式，利用最优解和当前解进行邻域搜索;在旁观蜂阶段，提出基于当前解和随机邻域解的两种邻域搜索公式，增加算法全局搜索方式的灵活性。
1ABC算法模型与步骤
故Xi表示某个食物源，即优化问题的一个初始解。
2）计算解的成本（目标函数值），并按照式（2）求适应度：
其中：φi，j实际为区间[-1，1]内均匀分布的随机数;Vi表示食物源Xi附近的邻域解。随后计算解Vi的成本并按照式（2）计算适应度，以进行原解Xi和新解Vi间的贪心式选择：如果新解的适应度大于原解的适应度，则以新解替换原解;否则尝试改进失败次数计数器Trail加1。
4）旁观蜂根据式（4）计算食物源的选择概率：
其中：Pi为旁观蜂选择食物源i的概率。适应度越高的食物源，被选中的概率越大。
5）旁观蜂根据式（4），选择概率最大的食物源，然后同样根据式（3），对选中的食物源执行邻域搜索。
6）更新并保存算法获得的（迄今为止）最优解。
7）侦查蜂检查食物源的计数器Trail是否大于预设的限制次数Limit，如果是则执行式（1）重新初始化该食物源。
重复步骤3）～7），直至满足某个条件则算法终止。
2增强开发能力的ABC算法
2.1已有改进ABC算法搜索公式分析
从ABC算法工作原理与步骤来看，雇佣蜂和旁观蜂在多维空间中搜索最优解的过程是关键，对算法求解质量和性能表现有重要影响。然而在基本ABC算法中，雇佣蜂和旁观蜂都仅在当前解的附近进行搜索，并使用相同的搜索公式或策略获得邻域解，导致算法的勘探（exploration）或全局搜索能力较强，而开发（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）忽视了算法在每次迭代过程中求出的最优解的指导作用;尽管式（5）～（7）、（9）～（10）包含了最优解信息，但是从其仿真实验及结果来看，对高维复杂问题的优化效果还有进一步提高的余地。
2.2本文ABC算法搜索公式
雇佣蜂和旁观蜂在多维空间中搜索出的最优解，是蜜蜂群体合作取得的重要成果和宝贵经验，因为它非常接近于或可能就是全局最优解，
如果对其加以利用可增强算法的开发能力，并改善ABC算法的求解质量和性能表现。
然而在基本ABC算法中，只是简单地在每次循环中记录最优解，并没有在雇佣蜂和旁观蜂搜索公式中发挥最优解的引导作用。
有鑒于此，本文提出如下的雇佣蜂搜索公式：
式（12）、（13）都基于基本ABC算法雇佣蜂搜索公式：将式（3）中等号右边的Xk，j替换为Xbest，k即可得式（12），将式（3）中等号右边的Xi，j替换为Xbest，k即可得式（13）。在式（12）和（13）中，k和j的取值互不影响。因此问题维数越高，k和j取值相等的概率就越低，取值不同的k和j意味着雇佣蜂在执行异维（或跨维）式的邻域搜索。已有研究表明，异维搜索避免了ABC算法单一搜索模式的局限性，增强了ABC算法的全局搜索能力，有利于算法摆脱局部最优[5，8]。
在式（12）中，邻域解Vi是以当前食物源Xi为参考，并结合最优解Xbest的信息执行邻域搜索获得的新解;在式（13）中，邻域解Vi是以最优解Xbest为参考，并结合当前食物源Xi的信息执行邻域搜索获得的新解。
其中：p与i、q与j的取值同样各自独立，依然利用了异维搜索带来的好处。
在式（14）中，邻域解Vi是以当前食物源Xi为参考，并结合随机选择的邻域解Vp的信息进行邻域搜索获得的新解;在式（15）中，邻域解Vi是以随机选择的邻域解Xp为参考，并结合当前食物源Xi的信息进行邻域搜索获得的新解。
2.3本文算法步骤
综上所述，本文提出的增强开发能力的改进ABC算法主要步骤如下：1）根据式（1）随机生成食物源的初始位置;
2）根据式（2）计算各个初始解的适应度，对比后保存最优解;
3）根据式（12）或（13），分派雇佣蜂到食物源地点进行邻域搜索;
4）根据式（4）计算旁观蜂选择食物源的概率，并选择一个食物源;
5）旁观蜂对选中的食物源，根据式（14）或（15），进行邻域搜索;
6）更新并保存算法得到的最优解;
7）侦查蜂检查食物源的计数器Trail是否大于等于预设值Limit，如果是则将最优解赋值给该食物源，以充分利用最优解信息。
重复执行步骤3）～7），直至满足特定条件则本文算法终止。
綜上所述，和其他改进ABC算法相比，本文算法的主要优势在于：仅简单地修改了基本ABC算法的第3）、5）、7）步，算法主体结构并无变动;没有引入新的算法参数，无需额外的参数设置或调校;没有增加算法复杂度，易于编程实现。
3仿真实验及分析
本文算法采用C++编程语言实现了2个版本：以最大循环次数（MaximumCyclesNumber，MCN）为算法终止条件的MCN版、以最大适应度评估次数（MaximumFitnessEvaluations，MFE）为算法终止条件的MFE版。为便于实验仿真并和其他ABC算法比较，本文采用表1所示的文献中最常见的测试函数。
表1中9个测试函数均为实参数的数值优化问题，其定义可见文献[11，17]。
Sphere、Tablet、Step、Quartic、Schwefel、Rosenbrock是单峰函数，其定义域内仅有一个全局最小值，用于检验算法收敛速度和精度;Ackley、Rastrigin、Griewank是多峰函数，其定义域内存在多个局部最小值和一个全局最小值，用于检验算法全局优化能力。
首先将本文算法与基本ABC算法进行比较，二者参数设置均为：种群大小NP=40，食物源数SN=20，限制次数Limit=100，最大循环次数MCN=3000，测试函数维数D=100。图1是本文算法和基本ABC算法优化Sphere、Rosenbrock、Griewank、Rastrigin函数时的收敛曲线。
为了清晰地展示实验结果，图1的纵轴均采用对数坐标表示最优值。
根据图1（a）的单峰函数Sphere和图1（d）的多峰函数Rastrigin收敛曲线可以发现，本文算法的收敛速度、精度和全局优化能力优于基本ABC算法。根据图1（b）的单峰函数Rosenbrock和图1（c）的多峰函数Griewank收敛曲线可以发现：在基本ABC算法和本文算法执行的早期，收敛曲线有交叉重叠部分，两个算法表现差别较小;自算法执行中期以后，二者差距很快扩大，本文算法仍然优于基本ABC算法。此现象的主要成因是：Rosenbrock是一个病态的螺旋型函数（空间分布图见文献[9]），通常很难求出其全局最优解;Griewank是一个100维的复杂多峰函数，在其定义域内存在多个局部最优解;在本文算法执行的早期，最优解的质量难免较差，导致它对雇佣蜂邻域搜索行为的指导作用尚不明显;从本文算法执行中期以后，最优解的质量得到了改善，对雇佣蜂的邻域搜索行为开始发挥其重要的指导作用。此外，在整个算法执行过程中，旁观蜂的搜索行为不受最优解的影响，用于保持或增强算法的勘探能力。
在文献[4，6-10]的仿真实验中，均以最大循环次数为算法终止条件，然而算法参数和测试函数的搜索范围与维数却不相同。因此，再将本文算法的MCN版与这些ABC算法逐个地两两比较，具体做法是：1）每个对比组中的本文算法和其他ABC算法参数设置相同;2）每个对比组中测试函数的搜索范围和维数等均一致;3）其他ABC算法的实验结果都来自于对应的参考文献;4）如果文献中有不同维数测试函数的实验结果，则只取其中维数最高的进行比较。
首先以Sphere、Tablet、Step、Quartic、Schwefel、Rosenbrock等单峰函数为对象，测试本文算法的收敛速度和精度，实验结果如表2所示。
从表2可以发现，对于除Rosenbrock之外的其他单峰函数和对比组中的算法，本文算法实验结果的最差值、最优值、平均值和标准差，明显优于文献[4，6-8，10]算法;仅在求解Rosenbrock函数时，本文算法才稍逊于文献[9]算法。因此说明，在收敛速度和精度方面，本文算法总体上优于其他ABC算法。
再以Ackley、Rastrigin、Griewank等多峰函数为对象，测试本文算法的全局优化能力，实验结果如表3所示。
从表3可以发现，对于所有多峰函数和对比组中的2个算法，本文算法实验结果的最差值、最优值、平均值和标准差，明显优于对比算法。因此说明，在全局优化能力方面，本文算法优于其他对比算法。
值得注意的是，文献[18]指出一些ABC算法研究中存在误区：算法终止条件通常基于最大循环次数，而不是最大适应度评估次数。由于仅当算法不包含局部搜索过程或没有混合其他算法时，以最大循环次数为终止条件进行算法实验比较才算公平合理，所以建议以最大适应度评估次数为算法终止条件[18]。为了准确地与其他ABC算法进行比较，下面采用MFE版的本文算法，与同样以最大适应度评估次数为终止条件的ABC算法ABCMSSCE（ABCalgorithmwithMulti-SearchStrategyCooperativeEvolutionary）[11]、ABC/best1[13]、ABC/best2[13]、ABCVSS（ABCalgorithmwithVariableSearchStrategy）[17]进行比较，实验结果表4所示。
说明：1）所有测试函数的维数D=100;2）Schwefel2.21、Schwefel2.22、SumSquares、Schaffer等测试函数的定义详见文献[11];3）包括本文算法在内的所有ABC算法参数设置均为食物源数SN=20，限制次数Limit=SN×D，最大适应度评估次数MFE=5000×D，算法运行次数为30。
从表4可知：对于单峰函数，本文算法求解Sphere、Schwefel2.21、Schwefel2.22、SumSquares实验结果的最差值、最优值、平均值和标准差，明显优于其他对比算法，仅在求解Quartic时，本文算法才稍逊于ABCMSSCE算法[11]，这说明在收敛速度和精度方面，本文算法总体上优于其他对比算法。
对于多峰函数，本文算法求解Rastrigin和Ackley实验结果的最差值、最优值、平均值和标准差，优于其他对比算法，仅在求解Schaffer时，本文算法才稍逊于ABCMSSCE算法[11]，这说明在全局优化能力方面，本文算法总体上优于其他对比算法。
4结语
在解决复杂高维优化问题时，ABC算法在收敛速度、精度和全局优化能力方面仍然存在不足。本文算法研究的核心思想是，在基本ABC算法的雇佣蜂阶段，重视对最优解信息的利用，并提出两种增强开发能力的搜索公式，以增强算法的局部搜索能力;在基本ABC算法的旁观蜂阶段，提出利用当前解执行两种不同的随机邻域搜索。仿真实验结果表明，本文算法是有效的。
与蚁群算法和粒子群算法相比，ABC算法无疑还需要有关学者开展更多的理论及应用研究。例如，本文算法还可以结合其他学者提出的雇佣蜂和旁观蜂搜索公式（策略），以进一步增强本文算法的开发和勘探能力;本文提出的雇佣蜂和旁观蜂搜索公式，也为开发包含混合搜索策略的ABC算法提供了新思路;本文算法还可以应用于其他领域（如工程优化和机器学习），以解决其中的复杂优化或学习问题等。
参考文献（References）
[1]KARABOGAD，BASTURKB.Apowerfulandefficientalgorithmfornumericalfunctionoptimization：ArtificialBeeColony（ABC）algorithm[J].JournalofGlobalOptimization，2007，39（3）：459-471.
[2]KARABOGAD，AKAYB.Acomparativestudyofartificialbeecolonyalgorithm[J].AppliedMathematicsandComputation，2009，124（1）：108-132.
[3]KARABOGAD，GORKEMLIB，OZTURKC，etal.Acomprehensivesurvey：ArtificialBeeColony（ABC）algorithmandapplications[J].ArtificialIntelligenceReview，2014，42（1）：21-57.
[4]暴勵.一种思维进化蜂群算法[J].电子学报，2015，43（5）：948-955.（BAOL.Amindevolutionaryartificialbeecolonyalgorithm[J].ActaElectronicaSinica，2015，43（5）：948-955.）
[5]李冰，孙辉，赵嘉，等.异维学习人工蜂群算法[J].计算机应用研究，2016，33（4）：1028-1033.（LIB，SUNH，ZHAOJ，etal.Artificialbeecolonyalgorithmwithdifferentdimensionallearning[J].ApplicationResearchofComputers，2016，33（4）：1028-1033.）
[6]杨小健，董毅伟.基于反向学习的自适应快速人工蜂群算法[J].系统仿真学报，2016，28（11）：2684-2700.（YANGXJ，DONGYW.Adaptivequickartificialbeecolonyalgorithmbasedonoppositionlearning[J].JournalofSystemSimulation，2016，28（11）：2684-2700.）
[7]孔金生，李世通，周树亮，等.基于反馈机制和丛林法则的人工蜂群算法[J].计算机工程与应用，2017，53（17）：53-59.（KONGJS，LIST，ZHOUSL，etal.Artificialbeecolonyalgorithmbasedonfeedbackandlawofjungle[J].ComputerEngineeringandApplications，2017，53（17）：53-59.）
[8]林凯，陈国初，张鑫.多交互式人工蜂群算法及其收敛性分析[J].计算机应用，2017，37（3）：760-765.（LINK，CHENGC，ZHANGX.Multipleinteractiveartificialbeecolonyalgorithmanditsconvergenceanalysis[J].JournalofComputerApplications，2017，37（3）：760-765.）
[9]王永琦，吳飞，孙建华.求解连续空间优化问题的改进蜂群算法[J].计算机应用研究，2018，35（3）：658-704.（WANGYQ，WUF，SUNJH.ModifiedartificialbeecolonyalgorithmforSolvingContinuousspaceoptimizationproblems[J].ApplicationResearchofComputers，2018，35（3）：658-704.）
[10]刘鑫，杨霄鹏，姚昆，等.自适应随机优化策略的改进人工蜂群算法[J].小型微型计算机系统，2018，39（2）：235-239.（LIUX，YANGXP，YAOK，etal.Improvedartificialbeecolonyalgorithmbasedonself-adaptiverandomoptimizationstrategy[J].JournalofChineseComputerSystems，2018，39（2）：235-239.）
[11]王志刚，尚旭东，夏慧明，等.多搜索策略协同进化的人工蜂群算法[J].控制与决策，2018，33（2）：235-241.（WANGZG，SHANGXD，XIAHM，etal.Artificialbeecolonyalgorithmwithmulti-searchstrategycooperativeevolutionary[J].ControlandDecision，2018，33（2）：235-241.）
[12]ZHUG，KWONGS.Gbest-guidedartificialbeecolonyalgorithmfornumericalfunctionoptimization[J].AppliedMathematicsandComputation，2010，217（7）：3166-3173.
[13]GAOW，LIUS，HUANGL.Aglobalbestartificialbeecolonyalgorithmforglobaloptimization[J].JournalofComputationalandAppliedMathematics，2012，236（11）：2741-2753.
[14]GAOW，LIUS，HUANGL.Anovelartificialbeecolonyalgorithmbasedonmodifiedsearchequationandorthogonallearning[J].IEEETransactionsonCybernetics，2013，43（3）：1011-1024.
[15]GAOW，LIUS.Amodifiedartificialbeecolonyalgorithm[J].Computer&OperationsResearch，2012，39（3）：687-697.
[16]GAOW，LIUS.Improvedartificialbeecolonyalgorithmforglobaloptimization[J].InformationProcessingLetters，2011，111（17）：871-882.
[17]KIRANMS，HAKLIH，GUNDUZM，etal.Artificialbeecolonyalgorithmwithvariablesearchstrategyforcontinuousoptimization[J].InformationSciences，2015，300：140-157.
[18]MERNIKM，LIUSH，KARABOGAD，etal.Onclarifyingmisconceptionswhencomparingvariantsoftheartificialbeecolonyalgorithmbyofferinganewimplementation[J].InformationSciences，2015，291：115-127.