0 引言

人工蜂群(Artificial Bee Colony, ABC)算法是Karaboga^[1]在2005年提出的具有参数少、算法原理简单且鲁棒性强等优点的一种模拟蜂群协作寻找蜜源的生物智能优化算法，主要被应用于电力调度问题、旅行商问题等各方面的寻优问题中。

虽然ABC算法具有简单、高效的特点，但是由于ABC算法的搜寻方式具有一定局限性，故较易满足于局部最优解，收敛速度较慢，降低了优化效果，因此，近些年来出现了不少对其进行改进的文章。比如，Gao等^[2]受DE/best/1的ABC/best/1的触发，提出了改良的人工蜂群(Modified Artificial Bee Colony, MABC)算法。或借鉴粒子群优化(Particle Swarm Optimization, PSO)算法的思想，在邻域搜索中加入了自适应的惯性因子，性能参数分段搜索^[3]。虽然这些方法在某种程度上强化了算法的性能，但仍存在许多问题，例如引入复杂参数使算法收敛速度慢，或没有从根本上增加种群的多样性。

针对这些问题，本文通过随机选择邻域，使得当前解的邻域扩大到随机选择的邻域。其次，在任意解上随机选择一维，使当前解的进行跨维学习，另外，针对传统人工蜂群算法中对蜜蜂跳出搜索空间边界时采用强制设置在边界处的方法，引入随机分布方式，使蜜蜂随机分布在在搜索空间中，从而增加蜂群的多样性，强化了算法摆脱局部最优解的能力。把这种方法称为多交互式人工蜂群算法(Multiple Interactive Artificial Bee Colony, MIABC)，MIABC不引入任何新的参数，故容易实现。在经典基准函数上对其进行仿真测试，并进行收敛性分析，验证方法有效性。

1 标准人工蜂群算法

在人工蜂群算法中，人工蜂群一般由三种角色构成，分别是采蜜蜂、跟随峰、侦察蜂。采蜜蜂在搜索空间中寻找蜜源(即可能存在的解)来进行开采，并记录蜜源的有关信息，然后与跟随蜂交流，跟随蜂采用轮盘赌选择法选择采蜜蜂，并在其附近采蜜。在一定情况(采蜜蜂放弃蜜源时)下，采蜜蜂变成侦察蜂重新寻找蜜源。

蜂群的50%由采蜜蜂构成，跟随蜂则为蜂群剩余的50%，一只采蜜蜂同一时刻只能在一处蜜源采蜜，同时，在实际的具体优化问题中，问题的可能存在的解就是蜜源对应的位置，而解的品质的好坏由蜜源的收益情况代表^[4]。

假设在蜂群搜索初始化时，产生了SN个D维初始解X_ij(i=1, 2, …, SN; j=1, 2, …, D)，SN为蜜源个数。根据式(1) 随机产生蜜源的初始位置：

${{\mathit{\boldsymbol{X}}}_{\rm{ij}}}={{\mathit{\boldsymbol{X}}}_{\rm{min,j}}}+\rm{rand}(0,1)({{\mathit{\boldsymbol{X}}}_{\rm{max,j}}}-{{\mathit{\boldsymbol{X}}}_{\rm{min,j}}})$

(1)

其中：X_ij表示当前位置，i∈{1, 2, …, SN}，j∈{1, 2, …, D}； X_{max, j}和X_{min, j}分别表示第j维蜂群搜索空间的边界上限和边界下限。

然后，采蜜蜂根据式(2) 所示的方式来搜寻并产生新的蜜源位置V_ij：

${{\mathit{\boldsymbol{V}}}_{ij}}={{\mathit{\boldsymbol{X}}}_{ij}}+{{\mathit{\boldsymbol{\varphi }}}_{ij}}({{\mathit{\boldsymbol{X}}}_{ij}}-{{\mathit{\boldsymbol{X}}}_{kj}})$

(2)

其中：k为不同于i的蜜源，且k∈{1, 2, …, SN}，j为随机选择的下标，φ_ij为[-1,1]的随机数。搜索后，计算适应值，并对新解和最优解通过贪婪选择来选择。

跟随蜂根据轮盘赌选择方法^[4]以概率P_i选择蜜源采蜜，式(2) 则是其邻域搜索的搜索方式，并计算其对应适应值，对X_ij和V_ij进行贪婪选择。P_i根据式(3) 来计算：

${{P}_{i}}=fi{{t}_{i}}/\sum\limits_{n=1}^{SN}{fi{{t}_{n}}}$

(3)

其中fit_i为解X_i的适应度函数值，且适应度值的计算方式如式(4) 所示：

$fi{{t}_{i}}=\left\{ \begin{align} & \frac{1}{1+{{f}_{i}}}, & {{f}_{i}}\ge 0 \\ & 1+abs({{f}_{i}}), & {{f}_{i}} ＜0 \\ \end{align} \right.$

(4)

其中： f_i为第i个解的目标函数值。

当蜜源X_i连续经过limit次循环搜寻仍没有变化，则此处蜜源被放弃，同时，采蜜蜂转作侦察蜂，并通过式(1) 随机搜寻产生一个新蜜源替代原蜜源。

2 多交互式人工蜂群算法 2.1 采蜜蜂的随机邻域搜索策略

良好的优化算法在搜索过程必须平衡全局探索能力和局部开发能力^[5]。在初始搜索阶段^[6]，ABC算法从初始解出发，通过反复搜寻当前最优解的邻域得到较好的解，由于搜索搜索仅限定于当前的领域进行，搜索范围较小，使算法收敛较慢，全局搜索能力较弱。为了加强全局搜索能力，加大搜索范围，受小世界网络模型^[7]的启发，本文为采蜜蜂引入了随机邻域搜索策略。

定义1 随机邻域搜索(Random neighborhood search)。在同一维搜索空间中，随机选出第i个解和第n个解，i∈{1, 2, …, SN}，n∈{1, 2, …, SN}，则随机邻域搜索公式可定义为：

${{\mathit{\boldsymbol{V}}}_{ij}}={{\mathit{\boldsymbol{X}}}_{nj}}+{{\mathit{\boldsymbol{\varphi }}}_{ij}}({{\mathit{\boldsymbol{X}}}_{ij}}-{{\mathit{\boldsymbol{X}}}_{kj}})$

(5)

其中：k∈{1, 2, …, SN}，且k≠i，φ_ij为[-1,1]的随机数。

由式(5) 可以看出，随机邻域搜索策略使算法搜索空间不再只限制于当前解的邻域，可以扩展至其他解的邻域，扩大了算法搜索空间，若将同一维看作一个平面，则采蜜蜂在平面上的邻域搜索范围扩大了，同时，跟随蜂的搜索方式不变，通过采蜜蜂的较大空间搜寻方式与跟随蜂的搜寻方式相结合，使得算法加快收敛，解变得更具多样化，强化了算法跳出局部最优值的能力。

2.2 采蜜蜂的跨维搜索策略

由式(2) 可知，标准人工蜂群算法中，采蜜蜂采用的搜索策略是向当前邻域中同维学习，即新解位置的产生会被约束在当前解位置周围较小的同维空间。这使得若在某一维中，当前解位置分布范围集中在某一区域时，产生的新解将在一定迭代次数里难以跳出该区域。而随着算法进化，解的位置分布范围缩小，会导致这种现象的出现，这种现象会使算法陷入局部最优的概率大幅度增加。

本文针对该问题，采用了跨维搜索策略^[8]，如式(6) 所示。这使得算法能够在维度上实现跳跃式搜索，不再局限于同维搜索，使得在算法搜索后半阶段，即搜索范围变小时，还能保持有良好的全局与局部搜寻能力，使算法获得全局最优解的可能性加大，同时，跟随蜂的仍用式(2) 进行传统的局部搜索，通过采蜜蜂与跟随蜂两种不同的搜索方式相结合，这种搜索方式的思想和作用就相当于遗传算法中的变异选择思想和作用，从而令算法避免了单种搜索模式的局限性，使得蜂群搜索的解多元化，有利于算法摆脱局部最优解。

定义2 跨维搜索(Stereo search)。在一个D维的搜索空间中，随机选出第j维和第l维，j∈{1, 2, …, D}，l∈{1, 2, …, D}且j≠l，则基于随机邻域搜索的跨维搜索公式可以定义为：

${{\mathit{\boldsymbol{V}}}_{ij}}={{\mathit{\boldsymbol{X}}}_{nl}}+{{\mathit{\boldsymbol{\varphi }}}_{il}}({{\mathit{\boldsymbol{X}}}_{il}}-{{\mathit{\boldsymbol{X}}}_{kl}})$

(6)

其中：k∈{1, 2, …, SN}，n∈{1, 2, …, SN}，且k≠i。

2.3 蜂群搜索边界处理

蜂群的搜索空间是有一定的范围的，当蜜蜂在搜索过程中跳出了搜索空间的边界时，标准ABC算法的处理方式是将蜜蜂位置强制重新设置在边界处，这使得在算法搜索后期，可能有大部分的蜜蜂聚集在边界上，而且这种设置方式，在下次搜索时，蜜蜂仍有较大可能再次跳出边界，这就大幅度降低了算法搜索效率，所以，本文采用式(7) 来重新设置跨界蜜蜂：

$\left\{ \begin{align} & {{\mathit{\boldsymbol{X}}}_{ij}}={{\mathit{\boldsymbol{X}}}_{\min ,j}}+rand(0,1)({{\mathit{\boldsymbol{X}}}_{\max ,j}}-{{\mathit{\boldsymbol{X}}}_{\min ,j}}),{{\mathit{\boldsymbol{X}}}_{ij}} ＜{{\mathit{\boldsymbol{X}}}_{\min ,j}} \\ & {{\mathit{\boldsymbol{X}}}_{ij}}={{\mathit{\boldsymbol{X}}}_{\max ,j}}-rand(0,1)({{\mathit{\boldsymbol{X}}}_{\max ,j}}-{{\mathit{\boldsymbol{X}}}_{\min ,j}}),{{\mathit{\boldsymbol{X}}}_{ij}}>{{\mathit{\boldsymbol{X}}}_{\max ,j}} \\ \end{align} \right.$

(7)

其中：X_{max, j}、X_{min, j}和X_ij分别代表蜜蜂在第j维的搜索边界上限、下限以及当前解位置。式(7) 的处理方式使得算法在搜索后期蜜蜂均匀散落在搜索空间中，保证蜂群的活性。

2.4 MIABC算法的基本流程

整个改进算法的实现步骤如下。

1) 设置种群数目PN和开采次数limit

2) 初始化SN(SN=0.5PN)个蜜源位置X_ij(i=1, 2, …, SN; j=1, 2, …, D)

3) 计算初始蜜源的目标函数值Objval和适应值fit

4) while((iter＜=maxCycle))do

5)  for i=1 to SN do

6)   随机选择邻域k∈{1, 2, …, SN}，n∈{1, 2, …, SN}，且k≠i

7)   随机选择一维度j∈{1, 2, …, D}，l∈{1, 2, …, D}，且j≠l

8)   根据公式V_ij=X_nl+(X_il-X_kl)进行邻域搜索

9)   根据式(7) 对跳出搜索边界的蜜源进行边界处理

10)   根据式(4) 计算适应值fit_i和式(3) 计算概率P_i

11)    对V_ij和X_ij进行贪婪选择

12)  end for

13)   i=1，t=0

14)  产生随机数r∈(0, 1) ，如果r＜P_i, 则t=t+1

15)   根据公式V_ij=X_ij+(X_ij-X_kj)进行邻域搜索

16)   根据式(7) 对跳出搜索边界的蜜源进行边界处理

17)   对V_ij和X_ij进行贪婪选择

18)   i=i+1，until i=SN

19)   for i=1 to SN do

20)    如果trial>limit，根据式(1) 初始化X_ij

21)   end for

22)   记录迄今为止最好的解

23) end while

3 MIABC算法优化性能 3.1 测试函数

为了考察算法性能，本文给出了MIABC算法在经典基准测试函数上的仿真结果和分析，表 1中为5个经典基准测试函数^[9]，其中f₁为单模函数，考察算法的寻优精度和收敛速度，多模函数为f₂~f₅，考察算法摆脱局部最优解的能力和全局搜寻能力。

3.2 实验结果与分析

在MIABC算法的测试过程中，为了让实验结果更具说服力，将对以上5种经典基准测试函数进行优化，并与标准人工蜂群算法相比较。表 1所示的为测试函数的相关信息。本文通过大量实验确定算法参数阈值。蜂群算法的参数设置如下：蜂群数目NP=100，迭代次数maxCycle=2 000，最大允许的连续开采次数limit=50，误差极限为1E-20。PSO算法参数设置如下：粒子群数目sizepop=100，w=0.8，c₁=c₂=1.494 5，v_max=1，v_min=-1。在每个基准测试函数都进行20维、50维、80维这三种不同维度的测试，每组都独立测试30次，对结果中的平均值、最优值、标准差这三种指标进行比较。优化结果如表 2所示，图 1则为ABC算法、MIABC算法和PSO算法的收敛曲线。

从表 2可知，ABC算法和MIABC算法在函数f₃ 的20维均找到了理论最优值，但MIABC算法在测试函数f₃的20维、50维、80维和f₂函数的20维均能找到理论最优值。比较表 2中三种算法的平均值、标准差和最优值，对函数f₁、f₄和f₅，MIABC算法在寻优结果精度和稳定性上领先于标准ABC算法，且MIABC算法在不同维数上的优化结果精度下降幅度远小于标准ABC算法，而在这5种经典测试函数上，MIABC算法无论在寻优结果精度上和稳定性都优于PSO算法，因此，相比于基本ABC算法和PSO算法，MIABC算法的寻优性能更佳，结果更精准和稳定。

图 1为MIABC算法、ABC算法和PSO算法在5种基准测试函数3种不同维度上搜索最优解的收敛曲线(其中图 1(a)和图 1(m)为更清晰地呈现差异，只显示差异较大的前1 000次迭代)。由图 1可见，在迭代过程中，MIABC曲线下降收敛速度均快于ABC和PSO曲线的收敛速度，只有个别测试函数上在搜索初始阶段下降收敛速度略慢于PSO算法。MIABC曲线更加接近最优解，未到最大迭代次数时就已经找到比ABC算法和PSO算法更优的解。由此可以看出MIABC算法能更精准快速地找到最优解。

3.3 时间复杂度实验

如果反复搜索导致时间无限延长，则无异于穷举搜索，故在CPU为i7-6700，内存8GB的惠普笔记本上进行时间复杂度实验。以上述5种经典测试函数的20维为例，其中除f₃在20维分别以目标函数值等于-8 379.66为迭代结束条件，其他4种函数皆以目标函数值小于1E-2为迭代结束条件。同理，3种算法在上述5种测试函数50维情况下迭代2 000次，将这两个方面的每组实验都独立测试10次，并求得平均运行时间分别列于表 3。

由表 2~3中数据对比可知，在相同迭代次数下，MIABC算法与ABC算法寻优速度相差不大，但在解的质量上好很多，而相比于PSO算法则有更快的寻优速度和更优的解，同时，从表 3和图 1中，可以得知，同等精度下，MIABC算法寻优速度更快。

4 MIABC算法收敛性

MIABC算法与ABC算法都属于随机搜索算法^[10-12]的范畴，所以同样可以利用随机算法收敛准则来判定MIABC的收敛性。

4.1 相关数学描述和定义

定义3 人工蜂群算法在搜索过程中搜索到的蜜源位置称为人工蜂状态，记为X，X∈L，L是可行解空间。故人工蜂群状态则由所有的人工蜂的状态组成，记作ξ=(X₁, X₂, …, X_SN)。

定义4 人工蜂群状态空间定义为所有人工蜂群状态的集合，记作S={ξ₁, ξ₂, …, ξ_N|0≤N≤maxCycle}。

定义5 在MIABC算法中，人工蜂从一个状态X_i到另一个状态X_j的变换，称为人工蜂状态转移，记为T_ξ(X_i)= X_j。而转移概率为人工蜂状态转移的概率，记为p(T_ξ(X_i)=X_j)。

定义6 对于∀ξ_i∈S，∀ξ_j∈S，MIABC算法迭代中，人工蜂群状态从ξ_i转移到ξ_j，记为T_S(ξ_i)= ξ_j，则人工蜂群状态由ξ_i一步转移到ξ_j的转移概率为:

$p({{T}_{S}}({{\mathit{\boldsymbol{\xi }}}_{i}})={{\mathit{\boldsymbol{\xi }}}_{j}})=\prod\limits_{m}^{SN}{p({{T}_{\xi }}({{\mathit{\boldsymbol{X}}}_{im}})={{\mathit{\boldsymbol{X}}}_{jm}})}$

(8)

4.2 收敛准则

本文所讨论的优化问题是极小化问题，适应值函数为目标函数倒数或绝对值。对于优化问题〈L, f〉，有随机算法D，第k次迭代结果为x_k，则下一次迭代结果为x_k+1=D(x_k, ζ)。其中L为可行解空间，f为适应值函数，ζ为算法D在迭代过程中曾经搜索到的解^[13]。

假设1 f(D(x, ζ))≤f(x)，若∀ζ∈L，则有:

$f(D(\mathit{\boldsymbol{x}},\mathit{\boldsymbol{\zeta }}))\ge f(\mathit{\boldsymbol{x}})$

(9)

假设2对于L的任意Borel子集G，若其测度s.t.v[G]>0，则有$\prod\limits_{k=0}^{\infty }{(1-{{\mu }_{k}}[G])}=0$，其中μ_k[G]为算法第k次迭代搜索解在子集G上的概率。

定理1 算法全局收敛的充要条件是算法同时满足假设1和假设2。

证明 若算法满足假设1，则可以说明算法的适应度f(x)是递增的；若满足假设2，则说明算法迭代足够多次后，不能搜到近似最优解的概率为0。当假设1和假设2被同时满足时，在迭代一定次数后，算法找到最优解的概率为1，则说明算法是全局收敛的。

4.3 MIABC收敛性分析

引理1  MIABC算法满足假设1。

证明 MIABC算法的每次迭代都会进行贪婪选择，如式(10) 所示：

${{\mathit{\boldsymbol{V}}}_{ij}}=\left\{ \begin{align} & {{\mathit{\boldsymbol{V}}}_{ij}},f({{\mathit{\boldsymbol{V}}}_{ij}})\ge f({{\mathit{\boldsymbol{X}}}_{ij}}) \\ & {{\mathit{\boldsymbol{X}}}_{ij}},f({{\mathit{\boldsymbol{V}}}_{ij}})\le f({{\mathit{\boldsymbol{X}}}_{ij}}) \\ \end{align} \right.$

(10)

因此，MIABC算法每次迭代都保存了群体最优解，满足了假设1。

定义7 人工蜂群最优状态集合B={ξ^*=(X₁, X₂, …, X_n)|f(X_n)=f(b^*), ξ^*∈S}, 其中b^*是优化问题的最优解，且B⊂L。

定理2  MIABC算法中，由人工蜂群最优状态构成的人工蜂群最优状态集合B是闭集。

证明 ∀ξ_i∈B，∀ξ_j∉B，对于蜂群状态经过k(k≤1) 步由状态ξ_i转移到ξ_j的转移概率为：

${{p}^{k}}({{T}_{S}}({{\mathit{\boldsymbol{\xi }}}_{i}})={{\mathit{\boldsymbol{\xi }}}_{j}})=\prod\limits_{l=1}^{k}{p({{T}_{S}}({{\mathit{\boldsymbol{\xi }}}_{i}})={{\mathit{\boldsymbol{\xi }}}_{j-l+1}})}$

(11)

蜂群状态转移概率可由定义5可得：

$p({{T}_{S}}({{\mathit{\boldsymbol{\xi }}}_{i}})={{\mathit{\boldsymbol{\xi }}}_{j-l+1}})=\prod\limits_{m}^{SN}{p({{T}_{\xi }}({{\mathit{\boldsymbol{X}}}_{im}})={{\mathit{\boldsymbol{X}}}_{j-l+1,m}})}$

(12)

由∀ξ_i∈B，∀ξ_j∉B，在k次的迭代过程中必然$\exists {{\mathit{\boldsymbol{\xi }}}_{j-l+1}}\notin B$(1≤l≤k)，则有f(X_j-l+1)≤f(X_j-1)=f(b^*)，由贪婪选择可知，至少存在一项p(T_S(ξ_j-l)= ξ_j-l+1)=0，则p^k(T_S(ξ_i)= ξ_j)=0，所以B是S上的闭集。

定理3 人工蜂群状态空间S上不存在非空闭集G，使得G∩B=$\varnothing $。

证明 假设人工蜂群状态空间S上存在非空闭集E，设ξ_i^*=(b_i1^*, b_i2^*, …, b_ic^*)∈B, ξ_j=(X_j1, X_j2, …, X_jn)∈E，则有f(ζ_jn)≤f(b_ic^*)，则p^k(T_S(ξ_j)= ξ_j^*)>0，则由定理2的证明过程可得，E不是闭集，这与题设矛盾，故定理3得证。

定理4 当蜂群的迭代次数趋近于无穷时，蜂群的状态序列定然进入到最优状态集B。

证明 由上述定理2，3可知，人工蜂群的状态空间S上不含除最优蜂群状态集B之外的闭集。当ζ_j∉B时，有$\underset{n\to \infty }{\mathop{\lim }}\,p({{T}_{S}}({{\mathit{\boldsymbol{X}}}_{n}})={{\mathit{\boldsymbol{X}}}_{j}})=0$，即蜂群状态必将在最优蜂群状态集B中。

引理2  MIABC算法满足假设2。

证明 由上述的定理4可知，连续迭代趋近于无穷次时，全局最优解未能被搜索到的概率为0，故有0＜μ_k[G]＜1，则有$\prod\limits_{k=0}^{\infty }{(1-{{\mu }_{k}}[G])}=0$，其中G在MIABC算法中为优化函数的最优解集B，满足假设2。

则由上述这些定理和证明可知，因为MIABC算法同时满足假设1和假设2，所以由全局收敛的充要条件(定理1) 可得，MIABC算法是全局收敛的。

5 结语

本文为了开发蜂群搜索能力，在标准人工蜂群算法的基础上，进行了三处改进:在采蜜蜂搜索方式上采用随机邻域搜索策略、跨维度搜索策略以及改进的边界越限设定方式，扩大了采蜜蜂搜索范围，增加了种群多样性，构建了多交互式人工蜂群算法(MIABC)。从五种经典基准测试函数上测试的结果可以看出，MIABC算法的寻优性能、收敛速度、寻优精度和稳定性明显提高，同时通过收敛性分析，可以得出MIABC算法全局收敛。不过，MIABC算法还存在一些不足，对于低维数问题的求解没有明显优势，但是，MIABC算法的改进策略使得其适用于多维且各维取值范围相似或相同的寻优问题和多维无约束问题求解，例如风电场调度问题、火电机组调度问题、旅行商问题等。