集成学习人工蜂群算法

杜振鑫，刘广钟，赵学华

(1.韩山师范学院 计算机与信息工程学院，广东 潮州 521041；2.上海海事大学 信息工程学院，上海 201306；3.深圳信息职业技术学院 数字媒体学院，广东 深圳 518172)

进化算法在解决复杂优化问题方面具有较大优势，因此受到越来越多的关注。主要的进化算法包括粒子群算法(Particle Swarm Optimization, PSO)[1]、差分进化算法(Differential Evolution, DE)[2]、人工蜂群算法(Artificial Bee Colony, ABC)[3]等。人工蜂群算法结构简单，参数较少，相比其他进化算法具有一定优势[3-8]，受到了大量的关注。但是，人工蜂群算法也存在一定的缺点。许多研究表明[4-8]，人工蜂群算法由于搜索公式中的邻居选择机制随机性太强，导致人工蜂群算法擅长勘探而不擅长开采[5]。目前，多数算法采用全局最优解来增强人工蜂群算法的开采能力，但是如果全局最优解位于一个错误的位置，将带领整个种群陷入局部最优解。另外，全局最优解虽然是总体表现最好的解，却未必在每个维度上都处于最好位置，而不同维度上的最好位置往往分散在不同的解中。因此，如何集成已有的种群信息，更准确地估计理论最优解的位置，从多个维度上快速接近理论最优解，从而避免算法陷入局部最优解，是一个值得研究的问题。笔者通过集成多个较好解的信息来构造一个更加“正确”的集成最优解，代替全局最优解引导算法进化，显著地提高了算法的性能。

1 相关工作

1.1 基本人工蜂群算法

人工蜂群[5]包含雇佣蜂、观察蜂和侦察蜂3类。假设在D维空间中，种群规模为2×N(雇佣蜂个数=观察蜂个数=N)，蜜源与雇佣蜂一一对应。第i个蜜源的位置记为Xi=(Xi,1,Xi,2,…,Xi,D),代表搜索空间中的一个候选解，i=1,…,N，D是待优化问题的维数。按照下式生成N个初始解：

(1)

人工蜂群算法可分3个阶段循环搜索：

(1)雇佣蜂阶段。每只雇佣蜂在对应的食物源Xi处根据式(2)生成候选解Vi=(Vi,1,Vi,2,…,Vi,D)。若f(Vi)

Vi,j=Xi,j+φi,j(Xi,j-Xk,j) ，

(2)

式中，φi,j是[-1,1]之间的随机数；k是随机选择的一个食物源，且k≠i;j是随机选择的维数。

(2)观察蜂阶段。雇佣蜂完成勘探之后，观察蜂按照下面的概率随机选择一个食物源i进一步开采：

(3)

式中，Fi是食物源Xi的适应度值。根据式(3)，食物源的适应值越大，被观察蜂选中的概率越高。式(3)中，

这里fi是第i个解的目标函数值。

(3)侦察蜂阶段。对每轮循环选择搜索失败次数最大且超过l次的食物源Xi，用式(1)随机初始化。

1.2 改进的人工蜂群算法

Zhu[4]受到粒子群算法的启发，通过引入全局最优解Xbest项，提出一种改进公式：

Vi,j=Xi,j+φi,j·(Xi,j-Xk,j)+ψi,j·(Xbest,j-Xi,j) ,

(4)

式中，ψi,j是[0,1.5]之间的随机数，Xbest是全局最优解。 文献[6]指出：式(4)右边两项可能位于相反的方向，容易导致算法震荡。因此，提出改进公式：

Vi,j=Xr1,j+φi,j·(Xr1,j-Xr2,j) ,

(5)

式中，r1≠r2,r1与r2是{1,2,…,N}中随机选择的食物源序号。由于式(5)只有一个引导项φi,j(xr1,j-xr2,j)，因此避免了式(4)中的震荡问题。同时，式(5)去掉了Xbest的引导，不易早熟。文献[7]认为式(5)中全局最优解未得到利用，提出一种精英人工蜂群算法 (Depth FirSt and elite-guided ABC, DFSABC_elite),重新引入全局最优解Xbest，并通过精英解平衡全局最优解的引导作用：

Vi,j=Xe,j+φi,j·(Xe,j-Xk,j) ,

(6)

(7)

式(6)用于雇佣蜂阶段，式(7)用于观察蜂阶段。Xe是从种群最好的p×N个个体中随机选择的精英解, 0

文献[8]提出一种改进的算法 (Modified GABC, MGABC)：

(8)

式中，0

2 笔者提出的算法

全局最优解的使用，是增强进化算法开采能力、加速收敛最重要的途径之一[5]。但由于全局最优解仅是算法当前发现的最优解，如果全局最优解本身处于一个错误位置，容易带领整个算法陷入局部最优解，因此仅使用全局最优解的单一引导，容易导致算法早熟。为此，人们提出了大量改进算法。在粒子群算法领域，2016年提出的动态指导粒子群[1]按照一定概率向全局最优解学习，既利用了全局最优解的信息，也抑制了早熟问题。2017年提出的改进粒子群[9]对全局最优解施加扰动以免早熟。2017年，文献[10]在差分算法中引入全局最优解，通过提取多个解的信息抑制早熟。在人工蜂群算法领域，式(4)最早采用全局最优解来增强算法的开采能力[4]；式(5)去掉了全局最优解引导，抑制了早熟问题。DFSABC_elite[7]通过精英解弱化全局最优解的引导，而MGABC[8]则按一定概率使用全局最优解抑制早熟。

受到文献[10]的启发，假设待优化问题是求最小值。对于当前种群中待更新的第i个个体Xi，首先对当前种群X按照函数值从好到坏排序[10]，排序后的种群称为R.按式(9)求得种群X中待更新个体i在搜索公式中使用的集成最优解(ensemble best, ebest),用集成最优解Xebest代替原来搜索公式中的全局最优解Xbest。

(9)

(10)

(11)

图1 集成学习原理(种群规模N=5，待更新个体i=5)

)

对于嵌入集成学习框架的MGABC_EL，需要增加一个额外的排序操作，增加的排序操作的复杂度是O(N·log(N))。 由于MGABC的计算复杂度为O(D·N)[8],则MGABC_EL的复杂度是O(N·log(N)+D·N)。因为D一般远大于log(N),所以O(N·log(N)+D·N)可以简化为O(D·N)。因此，MGABC_EL与MGABC复杂度相同。可见加入集成学习框架不会改变原始算法的复杂度。

3 实验与分析

为了测试集成学习框架的有效性，限于篇幅，在MGABC[8], DFSABC_elite[7], MGBDE[2]与SRPSO[11]这4种性能较高且较新的算法上进行了测试。4种进化算法都采用全局最优解引导算法进化，其中SRPSO是最近提出的改进粒子群算法；MGBDE是著名的高斯骨干差分进化算法，具有无参数特性及较高的性能。嵌入集成学习框架的4种算法分别称为MGABC_EL, DFSABC_elite_EL， MGBDE_EL， SRPSO_EL。测试函数的定义、函数名称、搜索范围及理论最优解见文献[7]。其中，函数f1～f8是单峰函数；f9是带噪声的函数；f10是Rosenbrock函数，当测试维数D>2时，是多峰函数[7]；f11～f22是多峰函数。表1用于测试集成学习框架是否可以增强人工蜂群算法的性能，测试函数的维数D=50，所有人工蜂群算法的种群规模按照文献[7]设置，即种群规模N=50。按照文献[7]的建议，算法最大评价次数M=5 000·D。其余参数设置均参照相应算法的原始文献设置。表2用于测试集成学习框架是否可以增强差分、粒子群算法的性能，种群规模同样取50，其余参数均按照原始文献设置。测试在同样条件下重复30次。 其中，Mean表示平均结果，反映了算法在给定最大评价次数时的求解精度；std表示标准差，反映了算法的稳定性。 表1与表2给出了非参数统计[12]的结果，显著性水平为0.05。表中的符号“+”“=”“-”分别表示嵌入集成学习框架的算法好于、等于、差于相应的原始算法。

表1 利用集成学习框架增强其他人工蜂群算法变种的实验结果(D=50,N=50)

根据表1，嵌入集成学习框架的MGABC_EL在除f14之外的21个函数上明显好于MGABC。同样，嵌入集成学习框架的DFSABC_elite_EL在除了f22之外的所有其他函数上都好于DFSABC_elite。实验结果表明，由于集成框架采用集成最优解带领算法进化，集成了多个较好解的信息，弱化了全局最优解的引导作用，从而抑制了早熟收敛，因此集成最优解能够带领整个种群搜索更有希望的方向，明显提高算法的性能。另外，集成学习框架对不同算法的提高幅度是不同的，例如在表1的实验结果中，MGABC_EL大幅度提高了MGABC的性能，而DFSABC_elite_EL对DFSABC_elite的提高幅度小一些。这主要是由于在MGABC中，在雇佣蜂阶段与观察蜂阶段都使用全局最优解引导，全局最优解的作用较大，因此集成学习框架可以很好地帮助MGABC抑制早熟收敛。而DFSABC_elite仅在观察蜂阶段使用全局最优解引导，全局最优解的作用小一些，且DFSABC_elite本身已经好于大量优秀算法[7],进一步提高性能的难度较大。但总体而言，集成学习框架仍能明显提高DFSABC_elite的性能。表1的最后一列给出了最新提出的高性能的改进算法ABCLGII[13]的实验结果。可以看出，嵌入集成学习框架的DFSABC_elite_EL虽然稍差于ABCLGII(两者分别有6个、7个函数好于对方)，但是集成学习框架具有更好的推广能力。表2给出了利用集成学习框架增强新提出的MGBDE[2]、SRPSO[11]算法性能的实验结果，可以看出，集成学习框架可以有效地提高全局最优解引导的差分进化算法与粒子群算法的性能。

表2 D=30时，利用集成学习框架增强差分、粒子群算法的实验结果

根据式(9)，个体i的集成最优解由i在排序种群R中的排序序号si与好于i的解在排序种群中的序号k决定。当种群规模N变大时，由于较差解的排序序号si较大，因此好于i的较好解较多，会造成较好解在集成最优解中的权重下降。为了考查这一影响，表3给出了当种群规模N=100时的实验结果，其余参数与表1相同。对比表3与表1可以发现，在表3中嵌入集成学习框架的改进算法MGABC_EL与DFSABC_elite_EL相对于MGABC、DFSABC_elite的优势不如表1大。造成优势下降的主要原因是当种群规模N增大时，函数值靠后的个体使用的集成最优解中全局最优解等好解的权重下降，因此算法收敛速度受到影响。但是根据表3，集成学习框架仍能明显增强MGABC与DFSABC_elite的性能。

表3 利用集成学习框架增强其他人工蜂群算法变种的实验结果(D=50,N=100)

4 结 论

为了抑制传统人工蜂群算法中全局最优解引导导致的早熟问题，提出一种集成学习框架。该框架通过集成多个较好解的信息抑制早熟收敛，且容易实施，可以嵌入其他全局最优解引导的人工蜂群、差分及粒子群算法，显著增强这些算法的性能，而没有增加这些算法的计算复杂度。