基于搜索能力均衡的人工蜂群算法

向万里 ，安美清 ，何瑞春 ，张静芳 ，马昌喜

1.兰州交通大学 交通运输学院，兰州 730070

2.天津大学 系统工程研究所，天津 300072

基于搜索能力均衡的人工蜂群算法

向万里1，2，安美清1，何瑞春1，张静芳1，马昌喜1

1.兰州交通大学 交通运输学院，兰州 730070

2.天津大学 系统工程研究所，天津 300072

1 引言

人工蜂群算法（Artificial Bee Colony，ABC）是由土耳其开塞利大学教授Karaboga D于2005年首先提出的一种模仿自然界蜂群集体觅食行为的群体智能优化算法[1]。随后，Karaboga D与Basturk B将ABC用于约束优化问题的求解[2]，紧接着，Karaboga D与Akay B将ABC与遗传算法（GA）、粒子群算法（PSO）、差分进化（DE）等元启发式算法在由近50个函数组成的测试平台上进行了全面的性能比较，发现ABC总体上优于GA、PSO和DE。加之ABC算法结构简单、控制参数少、无需梯度信息、易于实现等优点，近来受到越来越多的学者所关注，并已在函数优化[1，3-8]、多目标优化[9]、离散优化[10-12]等领域得到广泛的应用。

然而，ABC算法各主要阶段（雇佣蜂阶段、跟随蜂阶段和侦察蜂阶段）涉及的解搜索方程更适合于全局探索（Exploration），局部开发能力（Exploitation）欠佳[8]，从而导致ABC的收敛精度和收敛速度还有待进一步提高。为此，众多学者从各方面进行改进以提高ABC的收敛性能。例如：Akay B和Karaboga D[4]在ABC解搜索方程中引入一个扰动概率参数MR（Modify Rate）用以确定每次进化过程中每个个体会有多少个分量发生扰动，并在此基础上提出一个自适应尺度因子ASF（Adaptive Scaling Factor）来控制扰动的大小，从而形成一种改进的人工蜂群算法MABC，并取得了不错的收敛效果；Atalas B[5]则通过引入混沌映射实现种群初始化及在侦察蜂搜索阶段利用混沌映射实现混沌搜索，进而提出混沌人工蜂群算法CABC，并且在不同混沌映射作用下作了性能比较分析，指出CABC比ABC取得了更好的收敛精度及更易于跳出局部最优；暴励、曾建潮等人[6]则使用差分进化（DE）和人工蜂群算法相结合提出了一种新的双种群差分蜂群算法BDABC，并设计了种群间的学习机制，在仿真实验过程中BDABC展示了较好的全局搜索性能；Gao W F及Liu S Y[7]采用混沌映射和反向学习理论初始化ABC种群，并在ABC中引入差分变异搜索机制和一个均衡全局搜索和局部利用能力的概率以提高算法的全局收敛性能；此外，Zhu G等[8]基于适应度最好的个体构建解搜索方程，即在ABC解搜索方程的基础上添加了有最好个体best的引导项，提出了Gbest-guided ABC（GABC），GABC的解搜索方程能有效利用最好个体best的方向引导信息，从而加快ABC的收敛速度和提高收敛精度。在众多研究的基础上，本文为进一步提高ABC的收敛性能，提出一种改进的人工蜂群算法（IABC）。首先，为提高ABC的局部开发能力，在ABC的雇佣蜂阶段引入了一个新的具有最好个体引导的解搜索方程，从而使得IABC能有效共享利用最好个体信息并指导种群进化；尔后，为均衡ABC的搜索能力，在ABC跟随蜂阶段的搜索策略中引入了新的随机因素以增强ABC的全局探索能力，使得IABC能有效利用这两个新的搜索策略来均衡IABC的搜索能力，从而达到提高收敛性能的同时提高收敛精度。最后，在由12个复杂基准测试函数组成的仿真测试平台上，比较了IABC和ABC及GABC的收敛性能，结果表明IABC的收敛精度和收敛速度都有显著提高，为进一步验证IABC的有效性，将IABC与差分进化（DE）及由黄玲玲，刘三阳及高卫峰[13]最近提出的具有人工蜂群搜索策略的差分进化算法（SSDE2）相比较，比较结果亦显示IABC优势明显。

2 改进的人工蜂群算法

2.1 种群初始化

人工蜂群算法通过模拟自然界中蜜蜂的觅食行为实现蜂群个体相互协作，最终实现蜂群采蜜行为涌现的一种群体智能优化算法。因此，在实现人工蜂群算法之初，需要对人工蜂群信息初始化。一般而言，通过式（1）随机产生SN个雇佣蜂的食物源位置 Xi(Xi=(xi1，xi2，…，xiD))借以表示雇佣蜂个体信息。

其中，i=1，2，…，SN;j=1，2，…，D;xmjin表示第 j个分量所能赋予的最小取值，xmjax表示第 j个分量所能赋予的最大取值，rand(0，1)表示随机产生[0，1]之间的均匀分布随机数。

2.2 具有最好个体引导的雇佣蜂策略

对于标准人工蜂群算法，雇佣蜂i在雇佣蜂阶段主要是借助式（2）对正在开采的食物源位置进行一次局部开发，并更新食物源位置，以期获得更好的食物源。

其中 xi，j表示雇佣蜂 i的第 j个分量信息，vi，j表示雇佣蜂i在xi，j基础上探索或开采出的新食物源位置的第 j个分量位置；k∈[1，2，…，SN]{i}，j∈{1 ，2，…，D} 分别是随机选择的雇佣蜂个体及对应的食物源位置的第 j个分量；ϕij∈[-1，1]是一个随机数，用于控制雇佣蜂i进一步搜索的邻域半径。

从方程（2）可以看出：原ABC雇佣蜂阶段搜索策略中包含3个随机项：j，k，ϕij，使得ABC在搜索过程中具有更多不确定性，ABC从而表现出较好的全局探索（global exploration）能力，而局部开发（local exploitation）能力稍显不足[8]。为进一步提高ABC的收敛性能，受DE/best/1[14]以及改进的人工蜂群算法GABC[8]的启示，将ABC搜索方程式（2）修改为具有最好个体引导的式（3）以提高ABC的局部开发能力。

其中，best表示适应度最好的雇佣蜂的索引ID，其余变量含义与式（2）一致。

从式（3）可以看出：新的雇佣蜂搜索策略包含的随机因素相对式（2）减少了一个随机索引k的产生，且式（3）有最好的雇佣蜂xbest的引导，使得新的解搜索方程减少不确定因素影响的同时提供了有方向引导的搜索信息，从而强化了ABC的局部开发能力。

2.3 基于适应度尺度变换的选择概率

为了模仿自然界中的物竞天择，适者生存的自然选择规律，包括ABC在内的进化算法一般采用如式（4）所示的轮盘赌选择机制选择个体，即ABC采用如下方法为跟随蜂选择食物源位置提供选择概率信息pi：

其中，fiti表示适应度，且 fiti由式（5）确定。

其中，f(Xi)表示雇佣蜂i对应的解 Xi的目标函数值，a，b∈R为适应度尺度线性变换参数，当a=1，b=1时，表示适应度计算没有进行尺度缩放。

经典ABC算法中，跟随蜂采用式（2）对选择的雇佣蜂食物源位置进行进一步的开采。考虑到在改进的人工蜂群算法IABC中，雇佣蜂阶段食物源的开采采用的搜索方程式（3）具有较强的局部开发能力，为了平衡IABC的搜索能力，以免IABC陷入局部最优而早熟收敛，在式（2）中加入更多随机因素以使IABC跳出局部最优，提高全局搜索能力，修改后的搜索方程如式（6）所示。

其中，k1≠k2∈[1，2，…，SN]{} i是一随机整数，j∈[1，2，…，D]是随机选择的分量指标。易见式（6）比式（2）多了一项随机项 xk1，j，从而在式（6）的引导下使得IABC更易于跳出局部最优，能更好地平衡IABC的局部开发和全局探索能力。

2.5 改进的侦察蜂阶段

为了进一步均衡改进的人工蜂群算法IABC的局部开发能力和全局探索能力，在此阶段，与传统ABC不一样，对于每一个雇佣蜂i，均检测其连续未进化的次数trialsi与控制参数limit的关系，以确定该食物源是否被丢弃，若该雇佣蜂i对应的食物源被丢弃，相应地，雇佣蜂i变成侦察蜂，采用式（1）随机探索一个食物源位置作为侦察蜂新的食物源，同时侦察蜂变为雇佣蜂，trialsi被置为0。

2.6 IABC算法的基本思想和步骤

Zhu G和Kwong S[8]在GABC中指出传统人工蜂群算法（ABC）擅长全局探索而局部开发能力不足，即表示ABC在优化过程中存在收敛速度慢的缺点。对此，本文提出一种搜索能力均衡的人工蜂群算法，其基本思想是：首先在ABC的迭代过程中引入最好个体来指导ABC的进化，同时为均衡这种增强的局部开发能力，进而引入一种具有更好全局探索能力的新的跟随蜂搜索策略，使ABC能有效防止陷入早熟收敛。这两种新的搜索策略在ABC迭代中循环交替执行，从而使得IABC全局搜索与局部开发能力得以均衡，并使IABC性能大幅提升。具体步骤如下：

步骤1种群随机初始化。设置循环迭代变量FEs=0；设置最大适应度评估次数maxFEs，控制参数limit以及雇佣蜂个数SN和函数维数D的值；并对所有的trialsi(i=1，2，…，SN)置0。

步骤2SetFEs=FEs+SN。

又三年过去，当她的脚跟上再一次多出一道伤疤，她终于相信这绝不是偶然。她还相信这些伤疤肯定因为秦川。秦川向她隐瞒了太多。

步骤3雇佣蜂阶段。

步骤3-1i=0；

步骤3-2i=i+1and FEs=FEs+1，对每一个雇佣蜂对应的食物源位置Xi，根据式（3）产生一个临时新位置Vi；

步骤3-4 ifi＜SN then转步骤3-2，否则转步骤4。

步骤4依据式（4）和式（5）计算选择概率。

步骤5跟随蜂阶段。

步骤5-1t=0；i=1；

步骤5-2对每一个跟随蜂，依据概率 pi选择一个雇佣蜂对应的食物源位置Xi，即

ifrand(0，1)＜pithen 按式（6）产生一个临时新位置 V andt=t+1and FEs=FEs+1；otherwise，转步骤5-4；

步骤5-4i=i+1，ifi==(SN+1)theni=1；

步骤 5-5 ift≤SN then 转步骤 5-2，otherwise，转步骤6。

步骤6侦察蜂阶段。

步骤6-1 fori=1toSN

步骤6-2 iftrialsi＞limitthen

利用式（1）随机产生一个食物源位置，同时令trialsi=0。

步骤6-3 end for

步骤7记录到目前为止最好的个体适应度值及其相应信息。

步骤8if FEs≤maxFEsthen转步骤3，否则，算法终止。

3 仿真实验

3.1 基准函数及实验设置

为了验证IABC算法的有效性，将本文提出的IABC算法与标准ABC及GABC[8]进行了比较。仿真实验中选择了广泛使用的12个具有各种特征的复杂基准测试函数[3，9，7，13]，主要有单模态和多模态及其复杂的移位函数，表1列出了这些函数的名称、搜索空间及最优值。为了科学比较算法获得的结果，每个算法均独立运行20次。仿真实验过程中，对于GABC涉及的特殊参数C设置为文献中推荐的值1.5，对于其他共有的参数，为了公平起见，均设置为：群体规模SN=30，函数维数D=30，控制参数limit=100，最大适应度评估次数maxFEs=5E4。此外，对于IABC中的线性适应度尺度变换参数a=100，b=100。

表1 标准测试函数

3.2 仿真实验性能对比

为了有效对比IABC，ABC及GABC的收敛性能，在Matlab 2009a平台上对3种算法性能进行仿真测试，各算法分别独立运行20次，采集20次运行的统计结果：最好值（best），均值（Mean），方差（Std.）。各算法采集的数据如表2所示。

从表2中的数据结果可以看出：对于所有的标准测试函数，IABC获得的收敛精度和稳定性均胜于ABC和GABC。其中，对于单模态函数 f1、f2及移位单模态函数 f10而言，GABC由于有best个体引导，发现GABC的收敛精度明显好于ABC，而IABC中best的引导机制是直接在最好个体的选定分量附近探索，不同于GABC中搜索方程的作用是驱动当前个体向best个体靠近，从而使IABC有更强的局部开发能力，表2中的对比结果也显示IABC对于函数 f1、f2及移位单模态函数 f10的收敛精度明显好于GABC和ABC；对于复杂多模态函数f3～f9及移位多模态函数 f11，f12而言，GABC大都好于ABC，说明最好个体的指导信息对于算法的收敛性能起了关键作用，而IABC好于GABC表明引入IABC的两个新搜索策略能很好地均衡全局探索和局部开发能力，从而表现出加快收敛速度的同时获得更好质量的解，尤其是在多模态函数 f3上，IABC获得了最优值0。

总而言之，从以上性能对比分析可以看出：IABC中对搜索方程的改进起到了加速算法收敛的同时很好地均衡了局部开发和全局探索能力，从而获得了更好的收敛性能。

为了进一步验证IABC的收敛性能，将IABC与差分进化算法（DE）以及黄玲玲和刘三阳等[13]最近提出的SSDE2算法的结果进行比较。为公平起见，算法最大的评估次数设置与文献[13]相同，即100 000。此外，考虑到结果的可靠性，表3中的比较结果除了IABC算法获得结果值以外，有关DE，SSDE2的结果均直接采用文献[13]的结果。

表2 3种算法对12个函数的计算结果比较

从表3可以看出：SSDE2和IABC都明显好于DE。而IABC在除函数 f6以外的9个函数上明显优于SSDE2，尤其是对于函数 f3，f4及移位多模态函数 f11，f12，IABC均获得理论极值0，精度远高于SSDE2，表明IABC具有极好的寻优能力。此外，对于多模态函数 f6而言，SSDE2虽然获得了比IABC更好的均值和方差，但从表3的注解中可以发现IABC对此函数的20次求解中，有19次获得了理论极值0，表明IABC有极强的获取最优值的能力，且这些最好值优于文献[13]中报道的best值2.22E－016。可以说，表3的对比分析结果再次表明具有搜索能力均衡的人工蜂群算法IABC的收敛性能有较大的改善。

表3 IABC与DE，SSDE2的性能比较

4 结束语

由于标准ABC算法的搜索方程有利于全局搜索，而局部开发能力不足[8]，为进一步提高ABC收敛性能，提出一种改进搜索策略的人工蜂群算法IABC，在改进的IABC中加入了最好雇佣蜂个体best的引导机制，起到向最好个体周围快速聚集的作用，从而加速算法收敛，提高局部开发能力，同时为了平衡算法的全局探索和局部开发能力，在跟随蜂阶段的解搜索方程中增加了一个随机项，进而提高IABC的全局探索能力，有利于跳出局部最优，避免IABC早熟收敛。接着，在侦察蜂阶段，对于每一个雇佣蜂个体，都检测其是否变为侦察蜂，再一次使用随机生成新个体的方式增强IABC后期搜索跳出局部最优的能力，而且在IABC迭代过程中，具有全局探索能力的搜索方程与具有较好局部开发能力的搜索方程交替执行，起到了均衡IABC搜索性能的作用。总之，改进后的IABC在提供局部开发能力的同时，通过在跟随蜂和侦察蜂阶段增加一些随机策略来均衡IABC的局部开发和全局探索。最后，在由12个常用的复杂基准测试函数组成的测试平台上进行了仿真测试，发现：本文提出的IABC算法在求解精度、收敛速度及鲁棒性方面都比标准的ABC，GABC以及SSDE2均有较大幅度的提高，取得了令人满意的效果。

[1]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Kayseri，Turkey：Erciyes University，2005.

[2]Karaboga D，Basturk B.Artificial Bee Colony（ABC） optimization algorithm for solving constrained optimization problems[C]//Proceedings 12th International Fuzzy Systems Association World Congress，2007：789-798.

[3]Karaboga D，Akay B.A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation，2009，241（1）：108-132.

[4]Akay B，Karaboga D.A modified artificial bee colony algorithm for real-parameter optimization[J].Information Sciences，2012，192：120-142.

[5]Alatas B.Chaotic bee colony algorithms for global numerical optimization[J].Expert System with Applications，2010，37（8）：5682-5687.

[6]暴励，曾建潮.一种双种群差分蜂群算法[J].控制理论与应用，2011，28（2）：266-272.

[7]Gao W F，Liu S Y.A modified artificial bee colony algorithm[J].Computers&Operations Research，2012，39（3）：687-697.

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

[9]Akbari R，Hedayatzadeh R，Ziarati K，et al.A multi-objective artificial bee colony algorithm[J].Swarm and Evolutionary Computation，2012，2：39-52.

[10]Kashan M H，Nahavandi N，Kashan A H.DisABC：a new artificial bee colony algorithm for binary optimization[J]. Applied Soft Computing，2012，12（1）：342-352.

[11]Pan Q K，Fatih Tasgetiren M，Suganthan P N，et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J].Information Sciences，2011，181（12）：2455-2468.

[12]Szeto W Y，Wu Y，Ho S C.An artificial bee colony algorithm for the capacitated vehicle routing problem[J].European Journal of Operational Research，2011，215（1）：126-135.

[13]黄玲玲，刘三阳，高卫峰.具有人工蜂群搜索策略的差分进化算法[J].控制与决策，2012，27（11）：1644-1648.

[14]Storn R，Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997，11（4）：341-359.

XIANG Wanli1，2,AN Meiqing1,HE Ruichun1,ZHANG Jingfang1,MA Changxi1

1.School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,China
2.Institute of Systems Engineering,Tianjin University,Tianjin 300072,China

In view of the defect that Artificial Bee Colony（ABC）algorithm is poor at exploitation,an Improved Artificial Bee Colony（IABC）algorithm is proposed based on two new solution search strategies.A new solution search equation, in which the other individual can be driven under the guidance of the best individual with best fitness value,is introduced so as to improve the capability of exploitation.To achieve a good tradeoff between the exploitation and exploration,a new random item is integrated into the original solution search equation to enhance the ability of exploration on the onlooker bee phase of ABC.To further balance the ability of exploration and exploitation,some modifications are done on the scout bee phase of ABC.In order to validate the convergence performance of IABC,experiments tested on twelve benchmark functions are conducted.And the experimental results show that the convergence performance of IABC is enhanced conspicuously.

artificial bee colony algorithm;solution search equation;global exploration;local exploitation;tradeoff

鉴于标准人工蜂群算法（ABC）局部开发能力不足，提出一种改进搜索策略的人工蜂群算法（IABC）。为提高ABC的局部开发能力，在其雇佣蜂阶段引入了一个新的具有最好个体引导的解搜索方程，为均衡ABC的搜索能力，在ABC跟随蜂阶段的搜索策略中引入了新的随机因素以增强ABC的全局探索能力，为了进一步平衡全局探索和局部开发能力，改进了ABC的侦察蜂搜索机制。为验证IABC的收敛效果，通过在12个复杂基准测试函数上的仿真实验并与其他算法相比较，发现IABC的收敛性能有显著提高。

人工蜂群算法；搜索方程；全局探索；局部开发；均衡

A

TP301.6

10.3778/j.issn.1002-8331.1305-0076

XIANG Wanli,AN Meiqing,HE Ruichun,et al.Improved artificial bee colony algorithm based on balance of searching ability.Computer Engineering and Applications,2014,50（23）：51-55.

国家自然科学基金（No.61064012，No.61164003）；兰州交通大学青年科学基金（No.2012029）；兰州交通大学科技支撑基金（No.ZC2014010）。

向万里（1978—），男，博士，副教授，研究领域为进化算法及应用；安美清（1981—），女，讲师，研究领域为智能计算及应用；何瑞春（1970—），女，博士，教授，博导，研究领域为人工智能、交通运输系统优化。E-mail：xiangwl@tju.edu.cn

2013-05-10

2013-06-26

1002-8331（2014）23-0051-05

CNKI网络优先出版：2013-08-05,http://www.cnki.net/kcms/detail/11.2127.TP.20130805.0943.010.html