一种基于混合搜索策略的人工蜂群算法研究

丁 华，王志刚，尚旭东

（南京师范大学泰州学院，江苏 泰州 225300）

人工蜂群[1](artificial bee colony，简称ABC)算法是由土耳其学者Karaboga提出的一种元启发式算法.算采用不同类型蜜蜂的分工协作的机制来求得问题的最优解.实验结果表明，ABC算法的性能要优于或相当于粒子群算法、差分进化算法和遗传算法.目前，ABC算法已被成功应用于求解不同类型的实际应用问题，如作业车间调度、聚类分析、无线传感网络、车辆路径问题等.但在ABC算法中，求解复杂函数时，引领蜂和跟随蜂对食物源的附近进行搜索时所采用的搜索策略在收敛速度、求解精度、最优解等方面仍存在缺点.为解决这些问题，专家们提出了不同的搜索策略来改善算法的性能.利用分段搜索策略实现对最优食物源的充分优化，对食物源进行贪婪更新，并招募所有跟随蜂选择当前最优食物源；引入两个参数来控制搜索策略中的扰动频率和扰动尺度，提出了改进的ABC算法[2-3]；受差分进化算法中DE/best/1和DE/rand/1变异策略的启发[4-5]，提出ABC/best/1和ABC/rand/1两种改进的搜索策略，并引入概率选择参数来控制这两种搜索策略的使用频率.

本文研究了一种人基于混合搜索策略的人工蜂群算法—ABCMSS.新算法在引领蜂和跟随蜂对食物源的附近进行搜索时依据混合搜索策略以平衡算法的局部搜索能力和全局搜索能力.本文设计仿真实验，将ABCMSS算法与ABC算法和3种不同类型的改进算法进行了对比，验证ABCMSS算法的性能.

2 人工蜂群算法

ABC算法中，因蜜蜂不同的分工，引领蜂负责在食物源附近进行搜索，其与所采集的食物源一一对应.引领蜂负责在食物源附近进行搜索并获得对应食物源的位置、食物源的存储量等相关信息，通过一定的方式与跟随蜂交换信息，跟随蜂根据与引领蜂交换的信息以一定的概率挑选较优的食物源继续开采.若一个食物源由于开采完而被放弃时，相应的引领蜂会转变他们的工作角色，成为侦察蜂并在蜂巢附近搜索的新的食物源.在求解优化问题时，引领蜂的数量等于跟随蜂的数量，1个食物源对应问题的一个可能解，食物源的存储量对应于解的适应值.

假设 xi=(xi1,xi2,…,xiD)表示第 i个食物源(i=1,2,…,SN)，D表示待优化问题的维数.算法首先根据问题域的范围按下式产生一个初始种群：

式中，i=1,2,…,SN，j=1,2,…,D，rand 为(0,1)之间均匀分布的随机数，Lj、Dj分别是蜂群搜索空间的下界和上界.初始化种群后，ABC算法根据蜜蜂的类型，把优化过程分位下面3个阶段.

1）引领蜂阶段：每一只引领蜂在食物源xi附近采用如下搜索策略进行搜索，并生成新食物源vi

式中，k∈{1,2,…,SN}和 j∈{1,2,…,D}是随机选取的，但k≠i，φij是[-1,1]间的随机数，若 vi处的蜂蜜量更多，则将其替换xi.

2）跟随蜂阶段：引领蜂在食物源附近搜索完毕后，跟随蜂则根据从引领蜂处接收到的信息采用如下概率来选择食物源

式中，Pi是第i个食物源被选中的概率，fiti为第i个食物源的适应值.fiti计算公式为

式中，fi为第i个食物源的目标函数值.跟随蜂选中食物源后，采用与引领蜂相同的搜索策略在食物源附近进行搜索并生成新食物源.

3）侦察蜂阶段：若引领蜂对应的食物源经过limit次循环后仍未得到改进，则放弃该食物源，且该食物源处的引领蜂就转变为侦察蜂，并按式(1)重新随机搜索一个新食物源.

3 基于混合搜索策略的人工蜂群算法

在ABC算法中，算法性能的优劣在很大程度上取决于引领蜂和跟随蜂所采用的搜索策略.但从式(2)可以看出，引领蜂和跟随蜂所采用的搜索策略是在当前食物源的邻域内产生新食物源，这使得算法具有较好的全局搜索能力，但局部搜索能力不足，该算法在收敛速度和求解精度等方面存在问题.受差分进化算法中DE/rand/1和DE/best/1变异操作模式的启发，专家们提出了如下搜索策略：

上式中，r，r1，r2∈{1,2,…,SN}，j∈{1,2,…,D}，r≠r1≠r2≠i，xbest为种群的全局最优个体.

式(5)由种群中三个互不相同的随机个体组成，有利于保持种群的多样性，全局搜索能力强，但收敛速度较慢.式(6)由于有种群的全局最优个体xbest作引导，因而局部搜索能力强，收敛速度快，但会加大算法陷入局部最优的可能性.众所周知，平衡全局搜索能力和局部搜索能力是智能优化算法获得较高性能的关键，但ABC算法中使用的单一搜索策略很难同时平衡算法的全局搜索能力和局部搜索能力.通过上述对式(5)和式(6)两种搜索策略的分析，结合这两种搜索策略的特点，本文提出一种新的混合搜索策略：

此外，ABC算法中的蜂群在对食物源的贪婪选择过程中都是基于适应值fiti，但由式(4)可以看出，若函数优化问题的目标函数值大于0且无限接近0时，对应的适应值fiti就不具有区分度.因此，本文算法在蜂群对食物源的选择过程中直接采用目标函数值fi来代替适应值.

4 仿真实验

为验证ABCMSS算法的性能，选取8个常用的基准测试函数用于仿真实验，表1给出了8个基准测试函数的名称、表达式、类型、搜索范围和最优值.其中，在函数类型中，U表示单峰函数，M表示多峰函数，S为可分函数，N为不可分函数.

表1 基准测试函数

4.1 ABCMSS算法与ABC算法的收敛性能比较

将ABCMSS算法与ABC算法在D=30时进行仿真实验，并对测试结果进行比较.实验时，种群规模均为SN=20，limit=SN×D，最大评价次数MaxFEs=5000D.两种算法在每个函数上独立运行30次.

图1 Schwefel 2.21函数收敛曲线

图2 Quartic函数收敛曲线

在单峰函数的测试中，ABCMSS算法在解的精度和稳定性两方面都明显优于ABC算法.在多峰函数的测试中，对于f5(x)，ABCMSS算法和ABC算法都能得到理论最优值，而对于f6(x)，ABCMSS算法可以求得理论最优值，ABC算法则陷入局部最优，对于其他的复杂多峰函数，ABCMSS算法的求解结果要明显优于ABC算法.

图3 Ackley函数收敛曲线

图4 Schaffer函数收敛曲线

图1-图4给出了ABCMSS算法和ABC算法对于部分测试函数在30维时的收敛曲线，从图中可以看出，ABCMSS算法的收敛曲线下降速度比ABC算法的收敛曲线下降速度要快，且能够收敛到较高精度的解.

4.2 ABCMSS算法与几种改进的ABC算法比较

为进一步测试ABCMSS算法的性能，将其与GABC、MSSABC、ABCVSS等改进算法在 时进行了比较，所有算法的最大评价次数均为MaxFEs=5000D，SN=20，limit=SN×D.表2给出了4种算法的测试结果.

表2 4种算法的测试结果

从表2可以看出，在8个基准测试函数中，对于f5(x)，4种算法都能求得理论最优值，对于f6(x)，只有ABCMSS和ABCVSS两种算法能求得理论最优值，对于其他函数，ABCMSS算法在解的精度和稳定性两方面都优于GABC、MSSABC以及ABCVSS等改进算法.

5 结论

针对ABC算法搜索策略存在的不足，提出一种基于混合搜索策略的人工蜂群算法.在该算法中，引领蜂和跟随蜂进行邻域搜索时混合使用两种不同的搜索策略，使算法可以较好的平衡全局搜索能力和局部搜索能力，避免了ABC算法收敛速度慢和易陷入局部最优的缺陷.8个基准测试函数的仿真实验结果表明，与基本人工蜂群算法及一些改进的人工蜂群算法相比，新算法在优化性能和鲁棒性等方面有了较大的改善.下一步的研究工作将考虑把算法应用到多目标优化、图像处理等实际优化问题中，并结合其他一些新兴的智能优化算法，提出性能更好的优化算法.