增强开发能力的改进人工蜂群算法

张志强 鲁晓锋 孙钦东 王侃

摘 要：为解决人工蜂群（ABC）算法收敛速度慢、精度不高和易于陷入局部最优等问题，提出一种增强开发能力的改进人工蜂群算法。一方面，将得出的最优解以两种方式直接引入雇佣蜂搜索公式中，通过最优解指导雇佣蜂的邻域搜索行为，以增强算法的开发或局部搜索能力;另一方面，在旁观蜂搜索公式中结合当前解及其随机邻域进行搜索，以改善算法的全局优化能力。对多个常用基准测试函数的仿真实验结果表明，在收敛速度、精度和全局优化能力等方面，所提算法总体上优于其他类似的ABC算法（例如ABC/best）和集成多种搜索策略的ABC算法（例如ABCVSS（ABC algorithm with Variable Search Strategy）和ABCMSSCE（ABC algorithm with Multi-Search Strategy Cooperative Evolutionary））。

关键词：群体智能;人工蜂群算法;最优解;邻域搜索

中图分类号： 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）是受蜜蜂群觅食行为启发而提出的一种群体智能（Swarm Intelligence）算法[1]。与遗传算法、差分进化、粒子群算法和进化策略相比，ABC算法具有较强的竞争力[2]，已被应用于人工神经网络、工业工程、电子工程、数据挖掘、图像处理等领域[3]。然而和其他群体智能算法类似：在解决复杂优化问题时，ABC算法存在收敛速度慢和易于陷入局部最优等问题。

为此，近年来已有学者提出了一些改进的ABC算法。例如，文献[4]提出通过学习和按维更新策略的思维进化ABC算法，并对其收敛性进行了分析。文献[5]提出雇佣蜂采用全局最优引导的搜索策略，并且引导程度随个体实验次数自适应减小，以平衡算法的全局和局部搜索能力;旁观蜂采用变异的异维学习策略，使算法的搜索具有跳跃性，以提高逃出局部最优的概率。文献[6]提出自适应步长的快速ABC算法，使旁观蜂搜索阶段的周边食物源参数自适应化，并结合反向学习策略改进雇佣蜂搜索阶段。文献[7]提出在基本ABC算法全局搜索公式中引入反馈机制，直接搜索最优解可能存在的区域，以提高算法的开发能力和收敛速度;加入线性微分递增策略，平衡算法各个阶段的开发能力和探索能力;根据丛林法则，算法随机选择较差个体进行初始化，以防止算法陷入局部最优。文献[8]提出在基本ABC算法基础上引入随机邻域搜索策略和跨维搜索策略，并改进蜜蜂越限处理方式，使得算法搜索方式多样化，从而使算法搜索更具跳跃性，不易陷入局部最优解。文献[9]提出利用反向学习方法构建初始种群，以提高初始化解的质量;利用分布估计算法构造优秀个体解空间的概率模型进行邻域搜索，以改善算法的搜索性能并防止陷入局部最优。文献[10]提出利用自适应思想定义新的位置更新公式，由此提高蜂群间交互的相关性;利用双向随机优化机制约束适应度函数的搜索方向，由此提高算法的局部搜索能力;将粒子群算法引入基本ABC算法的初始阶段，利用其收敛速度快的特性，以较少的迭代次数产生全局最优解作为初始蜜源位置，提高算法的收敛速度。文献[11]提出在雇佣蜂和旁观蜂进行邻域搜索时， 动态调整搜索的维数以提高搜索效率， 并结合5种不同的搜索策略使其協同进化，以平衡算法的局部搜索和全局搜索能力。

以上研究主要针对基本ABC算法中雇佣蜂和旁观蜂搜索行为或公式提出了各种改进，在很大程度上克服了算法收敛速度慢和易于陷入局部最优等缺点，然而存在的主要问题是：与基本ABC算法相比，改进算法的参数更多、运行机制更复杂[9-11];从实验仿真结果来看，在解决复杂函数优化问题方面，改进算法性能表现仍有待验证。例如，文献[4-5，7]测试的问题维数最高为50，而文献[6]只测试了30维的问题，文献[8]提出的ABC算法仅与基本的ABC算法和粒子群算法进行了比较等。为此，本文在基本ABC算法的雇佣蜂阶段，提出两种增强开发能力的搜索公式，利用最优解和当前解进行邻域搜索;在旁观蜂阶段，提出基于当前解和随机邻域解的两种邻域搜索公式，增加算法全局搜索方式的灵活性。

1 ABC算法模型与步骤

在ABC算法模型中，根据分工不同把蜜蜂群分为3组：雇佣（employed）蜂、旁观（onlooker）蜂和侦查（scout）蜂。雇佣蜂负责采集以前勘察过的蜂蜜源，并向蜂巢中的旁观蜂通告食物源质量;旁观蜂根据雇佣蜂共享的信息决定要开采的食物源;侦查蜂随机搜索蜂巢周围环境以发现新的食物源。蜜蜂群的一半成员是雇佣蜂，另一半成员是旁观蜂（侦查蜂仅有一只）。每个食物源代表优化问题的一个解，它对应一个雇佣蜂和一个旁观蜂，食物源个数是蜜蜂种群大小的一半。根据ABC算法官方网站https：//abc.erciyes.edu.tr/software.htm提供的源程序，ABC算法基本步骤如下所示：1）根据式（1）随机生成食物源的初始位置：

故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个版本：以最大循环次数（Maximum Cycles Number， MCN）为算法终止条件的MCN版、以最大适应度评估次数（Maximum Fitness Evaluations， 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（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实验结果的最差值、最优值、平均值和标准差，明显优于其他对比算法，仅在求解Quartic时，本文算法才稍逊于ABCMSSCE算法[11]，这说明在收敛速度和精度方面，本文算法总体上优于其他对比算法。

对于多峰函数，本文算法求解Rastrigin和Ackley实验结果的最差值、最优值、平均值和标准差，优于其他对比算法，仅在求解Schaffer时，本文算法才稍逊于ABCMSSCE算法[11]，这说明在全局优化能力方面，本文算法总体上优于其他对比算法。

4 结语

在解决复杂高维优化问题时，ABC算法在收敛速度、精度和全局优化能力方面仍然存在不足。本文算法研究的核心思想是，在基本ABC算法的雇佣蜂阶段，重视对最优解信息的利用，并提出两种增强开发能力的搜索公式，以增强算法的局部搜索能力;在基本ABC算法的旁观蜂阶段，提出利用当前解执行两种不同的随机邻域搜索。仿真实验结果表明，本文算法是有效的。

与蚁群算法和粒子群算法相比，ABC算法无疑还需要有关学者开展更多的理论及应用研究。例如，本文算法还可以结合其他学者提出的雇佣蜂和旁观蜂搜索公式（策略），以进一步增强本文算法的开发和勘探能力;本文提出的雇佣蜂和旁观蜂搜索公式，也为开发包含混合搜索策略的ABC算法提供了新思路;本文算法还可以应用于其他领域（如工程优化和机器学习），以解决其中的复杂优化或学习问题等。

参考文献（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]. 系统仿真学报， 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] 王永琦， 吳飞， 孙建华. 求解连续空间优化问题的改进蜂群算法[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] 刘鑫， 杨霄鹏， 姚昆， 等. 自适应随机优化策略的改进人工蜂群算法[J]. 小型微型计算机系统， 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.