多策略混合搜索的人工蜂群算法

宋晓宇，赵 月，赵 明

(沈阳建筑大学 信息与控制工程学院, 辽宁 沈阳 110168)

0 引 言

针对基本的人工蜂群算法[1,2](artificial bee colony，ABC)收敛速度慢[3]、开发能力[4]不足等问题，国内外学者根据不同应用背景提出不同的改进版本。其中部分学者通过改进搜索策略[5-7]提升ABC性能。而随着优化问题的日趋复杂，单一的搜索策略具有一定的局限性。一些学者提出具有多个搜索策略的改进算法：Kiran等[8]提出具有5个策略候选池的ABCVSS算法,并根据每个策略成功更新解的次数选择搜索策略；Lin等[9]在雇佣蜂阶段使用一个有邻域最优个体引导的搜索策略，观察蜂以自适应机制选择有最优解以及精英解引导的两个搜索策略，提出ABCLGII算法；Xiang等[10]引入重力模型到ABC算法中，并采用选择概率分别为95%、3%和2%的3个搜索策略，提出 ABCG 算法。

为平衡人工蜂群算法的探索与开发能力，本文提出多策略混合搜索的人工蜂群算法。在雇佣蜂阶段提出两个基于随机解搜索的搜索策略用于保持算法的探索能力，并分配不同的混合比例；观察蜂阶段修改两个搜索策略，引入精英解[11]作为搜索起点来提高算法的开发能力，并采用与雇佣蜂相同的混合比例，达到探索与开发的平衡，从而提升算法的搜索效率。

1 人工蜂群算法

人工蜂群算法是由土耳其大学的karaboga提出，模拟生物学中蜜蜂的智能采蜜行为。用于解决多变量函数优化问题。ABC算法中包括3种类型的蜜蜂：雇佣蜂，观察蜂，侦察蜂[12-14]。ABC算法的搜索过程主要分为以下几个阶段：

初始化：

首先，随机生成初始种群SN，即SN个具有D维变量的解

xi,j=xmin,j+rand(0,1)(xmax,j-xmin,j)

(1)

式中：i=1，2，…，SN,j=1,2,…,D,xmax和xmin为搜索空间的上界和下界。每个解xi代表一个D维向量。

雇佣蜂阶段：

雇佣蜂通过式(2)产生一个新的候选位置vi,j并检查新位置的花蜜量。如果新位置优于原位置xi,j，则该蜜蜂记住新位置并忘记原位置。即贪婪选择机制被用于决定新位置与原位置。所有的雇佣蜂完成搜索过程后，它们将记忆中的食物源信息通过舞蹈区与观察蜂共享

vi,j=xi,j+φi,j(xi,j-xk,j)

(2)

式中：k,j是随机选择的下标，且满足k∈{1,2，…,SN},j∈{1,2,…,D},k不等于i,φi,j为[-1,1]之间的随机数。

观察蜂阶段：

食物源的适应值以及观察蜂选择某个食物源的概率分别为

(3)

(4)

观察蜂根据轮盘赌机制选择一个食物源，像雇佣蜂那样生成一个新的位置，然后比较新位置与原位置，择优保留。

侦察蜂阶段：

在此阶段，如果一个食物源经过限定的循环次数limit后仍没有更新，则将该位置放弃。该处的雇佣蜂成为侦查蜂，侦查蜂按式(1)产生新位置。

2 改进的人工蜂群算法

众所周知，基本的人工蜂群算法探索性能好而开发性能弱，这是由于其搜索策略[13]决定的。其次，在雇佣蜂与观察蜂阶段使用同样的搜索策略，也是制约算法性能的因素。

根据蜜蜂采蜜的特性，算法在雇佣蜂阶段应侧重探索能力，使其在整个种群中探索，从而有大的概率发现好的区域。观察蜂则依据雇佣蜂分享的已知信息，在一个较好解附近进行开发，从而发现最优解(多峰函数：全局最优解)。

为了提升人工蜂群算法的性能，本文从改进搜索策略以及混合搜索方式两个方面进行改进。首先，提出两个新的基于高斯分布参数的搜索策略，用于保持算法的探索能力，并分配不同的混合比例，增加种群多样性；观察蜂修改两个搜索策略，引入精英解信息，并采用与雇佣蜂相同的混合比例，加快种群收敛。雇佣蜂与观察蜂的配合，保证算法在保持探索能力的同时增强开发能力，达到二者的平衡，进而提升算法的搜索效率。

2.1 基于高斯分布的搜索策略

在基本的ABC算法中，雇佣蜂采用式(2)生成候选解，其中，新的候选解是在父代附近产生的。这会导致算法易于陷入局部最优，从而找不到最优解。为增强算法的探索能力，Gao提出了CABC

vi,j=xr1,j+φi,j(xr1,j-xr2,j)

(5)

式中：xr1，xr2分别是从种群中随机选择的个体，互不相等且不等于xi。φi,j是均匀分布产生的[-1,1]之间的随机数。

在式(5)中，用于产生候选解的向量是从种群中随机选取的，有较高的随机性，因而探索能力较强，对搜索方向没有偏好。

由于式(5)已有非常强的探索性，为更好地平衡探索与开发，本文将参数φi,j修改为高斯分布N(0,0.4) 产生的随机数。并将修改后的二项式搜索策略命名为CABC1。由于参数φi,j是高斯分布随机数，相对于均匀分布随机数，可以提供相对集中的搜索区域，加速算法收敛。根据高斯分布的特性，φi,j有68.3%的概率落在(-0.4，0.4)之间提高开发能力，其余31.7%的概率散落在(-0.4，0.4)外的取值扩大搜索范围，增加种群多样性。将CABC1用于雇佣蜂阶段搜索，可以保证探索能力。然而，因CABC1中产生候选解的个体是从种群中随机选取的，在单峰函数中可以快速收敛到最优解，但是在多峰函数中，易于陷入局部最优。为此，提出另一个三项式搜索策略CABC2如下

vi,j=xr1,j+φi,j(xr1,j-xr2,j)+ψi,j(xr3,j-xr4,j)

(6)

式中：xr1，xr2，xr3，xr4分别是从种群中随机选择的个体，互不相等且不等于xi。φi,j是均匀分布产生的随机数且φi,j∈[-1,1]，ψi,j是高斯分布N(0，0.3) 产生的随机数。

在式(6)中，第二项两个随机解及均匀分布参数φi,j的使用，保证算法的探索能力。而第三项的引入，提供了步长组合的更多可能性，增加了逃出局部最优的概率。此外，高斯分布参数ψi,j的使用，调控xr3与xr4项的步长，使其有高的概率集中在(-0.3,0.3)之间，小步长避免错过最优解，同时，散落在(-0.3,0.3)之外的取值加快收敛。三项式提供了SN(SN-1)(SN-2)(SN-3) 的步长组合，维持了种群多样性，对于步长方向的选择提供更多可能性，在一定程度上平衡了算法的探索与开发能力。

2.2 精英解引导的搜索策略

由于真实的蜂群中，观察蜂需要在雇佣蜂的引导下进行搜索，这就表明观察蜂需要利用当前搜索信息进行搜索，从而提高算法的开发能力。因此，在观察蜂阶段，对CABC1与CABC2改进如下

vi,j=xpbest,j+φi,j(xr1,j-xr2,j)

(7)

vi,j=xpbest,j+φi,j(xr1,j-xr2,j)+
ψi,j(xr3,j-xr4,j)

(8)

其中，xpbest是从精英组(本文中，认为种群中前20%的个体为精英，即4个个体)中随机选择的精英解，其它参数与CABC1，CABC2相同。以当前种群中精英解作为搜索起始点，可以促进种群更快地收敛到最优区域，从而增强开发能力。此外，式(7)的二项式保证算法具有一定的探索能力，式(8)的三项式提供了更多的步长与方向的组合，维持种群的多样性，在增强算法开发能力的同时保证了探索能力。

虽然引入精英解会加快收敛，但同时也会降低探索能力，所以，在雇佣蜂阶段采用随机解，而在观察蜂阶段引入精英解。此外，为降低选择压力，给每个解一个均等的开发机会，观察蜂阶段弃用轮盘赌选择机制，而采用与雇佣蜂相同的食物源选择方式。

2.3 混合搜索机制

随着对大量搜索策略的研究，不同的搜索策略在处理不同问题或者同一问题的不同阶段上面展示出不同的特性。因此，一个混合的方式对于组合不同特性的搜索策略来改进ABC的性能是有必要的。在本文中，为了确保每个搜索策略充分发挥其作用，在雇佣蜂阶段与观察蜂阶段均采用混合搜索的方式。

由于不同的混合比例影响算法的搜索效率，本文通过实验选取合适的混合比例：采用单峰、多峰、可分离及不可分离的4组不同特性函数对不同的混合比例进行实验。混合比例分别采取3∶7，4∶6，5∶5，6∶4，7∶3，8∶2。实验结果见表1。在测试中发现：比值越大，即二项式搜索策略被分配更多的使用机会，算法的收敛速度越快，但同时在多峰函数易于陷入局部最优，算法不稳定；比值越小，即三项式搜索策略被分配更多的使用机会，则收敛速度降低，但稳定性增加。这是因为，二项式搜索策略中随机选取个体以及高斯分布的特点，加速种群收敛，但随着进化，个体之间趋同，种群多样性降低，易于陷入局部最优。而三项式搜索策略可以提供更多的步长方向的组合，提高跳出局部最优的可能性，但代价是收敛速度降低。在考虑算法的综合性能前提下，本文设置混合比例为6∶4。即二项式搜索策略被分配60%的使用机会，三项式搜索策略被分配40%的使用机会。

表1 混合比例测试

2.4 MHABC算法流程

(1)参数初始化，SN=NP/2,limit=SN*D, max_FEs=5000*D, q=0.2

(2)通过式(1)生成初始种群

(3)评估种群， 令FEs=SN，trial[i]=0;

(4)while(FEs

(5)雇佣蜂:

(6)fori=1:SN

(7) 随机生成[0,1]之间的随机数rt

(8)if(rt<0.6)

(9) 通过CABC1生成一个新的候选解

(10)else

(11) 通过CABC2生成一个新的候选解

(12)endif

(13) set FEs=FEs+1

(14)iff(vi)

(15)xi=vi,trial[i]=0; if (f(xi)≤Accept) break;

(16)elsetrial[i]=trial[i]+1;

(17)endif

(18)endfor

(19) 对种群进行排序， 并从中选择前T=q*SN个解作为精英解

(20)观察蜂:

(21)fori=1:SN

(22) 随机生成[0,1]之间的随机数rt

(23)if(rt<0.6)

(24) 通过式(7)生成一个新的候选解

(25)else

(26) 通过式(8)生成一个新的候选解

(27)endif

(28) set FEs=FEs+1.

(29)iff(vi)

(30)xi=vi,trial[i]=0; if (f(xi)≤Accept) break;

(31)elsetrial[i]=trial[i]+1;

(32)endif

(33)endfor

(34) 更新全局最优解

(35)侦察蜂:

(36)fori=1：SN

(37)if(trial[i]>limit)

(38) 通过式(1)重置食物源

(39) FEs=FEs+1,trial[i]=0;

(40)endif

(41)endfor

(42)endwhile

2.5 时间复杂度分析

MHABC算法所需时间复杂度与基本的ABC算法相比，在雇佣蜂阶段二者相同，MHABC选择精英解所需时间复杂度为O(q*SN*SN)， 观察蜂取消轮盘赌选择机制，时间复杂度为O(SN*D)。 因为q*SN

2.6 高斯分布参数分析

由于高斯分布参数影响着搜索策略的更新效率，为分析不同的φi,j与ψi,j取值对算法性能的影响，本文通过22个标准函数测试集对不同的高斯分布参数取值进行实验。取值如下：φi,j,ψi,j∈{N(0,0.1),N(0,0.2),N(0,0.3),N(0,0.4),N(0,0.5),N(0,0.6),N(0,0.7),N(0,0.8),N(0,0.9),N(0,1.0)}。 经过参数的不同组合测试发现：当φi,j取值集中在N(0,0.4) 附近，ψi,j取值集中在N(0,0.3) 附近时，算法取得较好性能。因此，本文设置高斯参数φi,j=N(0,0.4)。ψi,j=N(0,0.3)。 由于篇幅有限实验数据将不进行展示。

3 实验与分析

为了测试本文提出算法的性能，本文采用文献[15]中定义的22个标准函数测试集以及函数可接受值测试其性能，并与其它ABC及ABC变体算法进行对比。这22个函数包括单峰，多峰，可分离，不可分离等特性。其中，f1-f6，f8是单峰连续函数，f7是非连续函数，f9是噪声函数，f10在高维是多峰函数，f11-f22是多峰函数。如表2所示，D代表问题的维度，函数可接受值代表当一个函数的测试结果小于等于可接受值，即认为这个结果是成功的。

本文选取4个算法(ABC，ABCLGII，ABCG，ABCVSS)与MHABC算法在30维与100维进行对比。所有算法均使用VC++6.0软件，基于Win 10操作系统进行实验。为了公平比较，所有算法均采用其初始文章中设置的参数。具体设置如下：对于NP，除ABCLGII=100外，其它均为40，对于limit除ABCG=200外，其它均为SN*D。为公平起见，所有算法设置相同的停止条件，即最大评价次数为5000*D。每个算法独立运行25次，测试其均值与标准差。

表3、表4分别为30，100维的均值与标准差测试结果，表中加粗字体为表现最好的结果。最后一行为平均秩和，其值越小，代表此算法综合排名越靠前。可以看出，30维除ABCG略优于MHABC，其它算法均劣于MHABC，100维MHABC排名第一。

为了进一步测试算法的稳定性及其效率，每个算法独立运行50次，在其可接受解下，测试其成功率(SR)与函数评价次数(FEs)。为方便比较，有如下定义：成功率SR=达到可接受解的次数/总次数；成功性能SP=FEs/SR； 加速比AR=SP(其它算法)/SP(MHABC)。 可以看出，成功率越高说明算法越稳定。对于加速比，是以本文提出的算法作为一个基准，当AR大于100%时，说明对于同样的问题，该算法需要比MHABC多付出代价才可以达到相同精度的解，即MHABC具有更高的效率；反之，则说明该算法更高效。

表5、表6分别为每个算法在22个函数测试集下的30，50，100维的成功率与加速比(AR)汇总表。从表5的结果可以看出，除100维时，ABCVSS的成功率略高于MHABC，其它算法均不如MHABC，并且，3个维度的平均成功率排名，MHABC居于第一位。表6是加速比的汇总，ABCVSS的平均AR为119.33%，说明对于同样的问题，ABCVSS需要比MHABC多付出19.33%的函数评价代价才可以达到同样的精度。其它算法的AR也是均高于MHABC，说明它们同样需要比MHABC多付出代价。通过成功率与加速比的结果可以看出，MHABC较之于对比的算法具有更高的稳定性及效率。

为了更直观地看出每个算法的收敛速度，图1～图4给出4个函数在100维时的收敛过程，其中，横坐标为函数评价次数，纵坐标为函数值。从图中可以看出，对于单峰函数(f1)和多峰函数(f18)，MHABC均具有更快的收敛速度以及能找到精度更高的解；对于f10，虽然最后求解的精度不是最高，但是通过斜率可以看出，MHABC有较快的收敛速度；对于f13，各个算法均可以找到函数最优值，但是MHABC有更快的收敛速度。精度、成功率与加速比、收敛图的测试结果，说明MHABC算法相比于其它算法具有更优的性能。

表2 函数测试集

表3 30维均值与标准差比较结果

表4 100维均值与标准差比较结果

表5 成功率汇总/%

表6 加速比汇总/%

图1 Sphere函数收敛

图2 Rosenbrock函数收敛

图3 Griewank函数收敛

图4 Alpine函数收敛

4 结束语

为解决人工蜂群算法收敛速度慢，开发能力弱等问题，本文提出一种MHABC算法。在雇佣蜂阶段采用两个基于高斯分布参数的二项式与三项式搜索策略，保证算法有较好的探索能力；观察蜂阶段通过改变搜索起点，使其在精英解的引导下搜索，可以快速收敛到好的区域，增强开发能力。6∶4的混合比例将具有不同特征的搜索策略相结合，可以在进化的不同阶段提供合适的策略产生候选解，达到探索与开发能力的平衡。通过22个标准函数测试集的实验对比结果，提出的算法在搜索精度、稳定性、收敛速度方面都优于ABC算法及其它对比的算法。进一步将考虑自适应方式混合不同的搜索策略。