0 引言

人工蜂群(Artificial Bee Colony, ABC)算法^[1]具有结构简单、控制参数少、性能优良等特点, 目前已被应用于解决多种不同的实际优化问题^[2-5], 并取得了较好的实验结果。但在ABC中, 雇佣蜂和观察蜂所采取的搜索策略在求解复杂函数时存在着过早收敛、容易陷入局部最优、求解精度不高等缺点。为此, 研究者提出了许多不同的搜索策略来改善算法性能, 其中的代表性研究工作是关于如何改进解搜索方程或提出新的解搜索方程^[6]。Zhu等^[7]受粒子群优化(Particle Swarm Optimization, PSO)算法启发, 提出在解搜索方程中加入全局最优解g_best信息引导ABC算法。另一研究趋势是探索如何与其他搜索算子相结合来提高算法搜索性能。比如, Gao等^[8]通过将ABC与局部搜索Powell方法相结合, 有效地提高了ABC的性能。

上述通过直接修改进化操作算子的方法虽一定程度上提高了算法性能, 但其都是在具体操作层面上的改进, 并没有充分考虑种群全局结构和局部算子的个体能力问题^[9], 没有从根本上解决在提高算法收敛性的同时该如何增加种群的多样性、避免陷入局部最优的问题, 其根本原因在于搜索策略的调节仍是被动适应^[10]。因而, 为有效解决蜂群间通信方式单一、协作不足所引发的种群在全局探索与局部寻优不平衡的问题，本文通过研究个体选择方式与搜索运算的性能特点间的联系, 提出了一种基于混合搜索的多种群人工蜂群(Multi-Population ABC, MPABC)算法, 该算法利用个体选择机制提升其在进化过程中的自我调节能力, 并通过融合多种进化策略改进种群的搜索效率与抗早熟能力。

1 ABC算法的基本计算机制

ABC作为一种元启发式的随机搜索算法, 通过对候选解组成的群体进行随机而有目标的进化以寻求最优解。其中, 食物源代表优化问题的可能解, 质量代表函数值, 其优劣程度取决于函数的适应度值, 因此, 适应值越高食物源就越优秀。ABC中解的个数SN等于雇佣蜂或观察蜂的个数, 且与食物源数目相等, 侦察蜂只有一个。用x_i=(x_i¹, x_i², …, x_i^D)表示第i(i=1, 2, …, SN)个食物源, D为搜索空间S的维数。初始化后, 根据蜜蜂的类型, 将优化过程分为三个阶段:

1) 雇佣蜂阶段。在该阶段, 雇佣蜂根据式(1) 在食物源附近进行邻域搜索, 生成一个候选食物源v_i^j, 并通过贪婪机制选出较优食物源。

$ {\boldsymbol{v}}_i^j = {\boldsymbol{x}}_i^j + \varphi _i^j\left( {{\boldsymbol{x}}_i^j-{\boldsymbol{x}}_k^j} \right) $

(1)

其中:φ_i^j为[-1, 1]上的随机数, 用于控制x_i^j的邻域半径；k和j随机选取, k=1, 2, …, SN, j=1, 2, …, D，且k≠i。

2) 观察蜂阶段。雇佣蜂完成勘探后, 观察蜂根据雇佣蜂分享的信息, 以轮盘赌方式选择一个食物源进一步开采, 则食物源被选中的概率为:

$ {P_i} = fi{t_i}/\sum\limits_{n = 1}^{SN} {fi{t_n}} $

(2)

其中: fit_i为第i个食物源的适应度函数值。对于最小化问题, fit_i与问题空间S的目标函数值trueFit_i对应关系为:

$ fi{t_i} = \left\{ \begin{array}{l} \frac{1}{{1 + trueFi{t_i}}},\;\;\;\;\;\;\;\;trueFi{t_i} \ge 0\\ 1 + \left| {trueFi{t_i}} \right|,\;\;trueFi{t_i} < 0 \end{array} \right. $

(3)

3) 侦察蜂阶段。当雇佣蜂对应食物源的适应值连续limit次未更新, 表明该食物源已被开采尽, 则对应雇佣蜂就放弃该食物源并变成侦察蜂, 同时随机产生一新食物源:

$ {\boldsymbol{x}}_i^j = {\boldsymbol{x}}_{lb}^j + rand \times \left( {{\boldsymbol{x}}_{ub}^j-{\boldsymbol{x}}_{lb}^j} \right) $

(4)

其中:rand为(0, 1) 内的随机数; x_lb^j、x_ub^j分别为空间S第j维分量的下界和上界。

为进一步研究ABC算法的计算机制, 图 1~2给出了单峰函数F06(Step)与多峰函数F09(Rastrigin)利用ABC在搜索最优解过程中函数收敛曲线与群体多样性曲线。参数设置为:迭代次数Max.FE=1000次；控制参数limit=10, 80次; 收敛精度为10^-5。其中，收敛精度取对数后，所得函数值为-5，则收敛精度曲线与横坐标相互重合。

为了便于对ABC性能的分析, 首先给出一些基本定义:

定义1 个体x_i和x_j之间的相似性可通过欧氏距离比Dis_ij来度量:

$ Di{s_{ij}} = Dis\left( {{{\boldsymbol{x}}_i}, {{\boldsymbol{x}}_j}} \right) = \left\| {{{\boldsymbol{x}}_i}-{{\boldsymbol{x}}_j}} \right\|/\left\| {{{\boldsymbol{x}}_{ub}}-{{\boldsymbol{x}}_{lb}}} \right\| $

(5)

其中:‖ x_i-x_j‖表示两个实数向量的欧几里得范数。显然Dis_ij在区间[0, 1]内, Dis_ij愈趋近0, 个体差异性越小; 反之则相反。

定义2 群体的平均间距meanDis为:

$ meanDis = \frac{1}{{C_{SN}^2}}\sum\limits_{i = 1}^{SN-1} {\sum\limits_{j = i + 1}^{SN} {Di{s_{ij}}} } $

(6)

其中:C_SN²表示在空间大小为SN的群体中, 任选2个个体出现的总可能数。meanDis∈[0, 1], 从侧面反映出个体的分布情况。其值愈接近0说明群体的平均差异性越小, 反之则正好相反, 故常作为种群多样性与收敛性的观察指标。

limit作为ABC算法中衡量全局搜索代价的重要参数, 直接关系到算法的计算性能与收敛速度。如图 1~2所示, 当函数F06与F09的limit值较小时, 算法虽然具有较强的随机性能与全局搜索性能, 但其收敛速度非常缓慢且精度远没有达到实验要求；当limit较大时, 算法虽然增强了局部搜索能力, 提升了收敛速度, 但却因受到局部最优解的束缚而陷入早熟收敛。以上分析说明limit的取值差异使式(1) 参数倾向于不同搜索策略, 偏向全局搜索的参数使曲线表现出过度的全局搜索趋势, 偏向局部搜索的参数使曲线表现出过度的局部搜索趋势, 其根本原因在于ABC单一搜索模式具有的较高的耦合性, 难以实现全局搜索和局部搜索间的有效协调。

2 基于子群与多进化策略的改进机制 2.1 子群的构造机制

针对上述研究中的不足, 通过对个体间编码差异及其问题空间的分布与其所参与搜索运算的性能特点间存在的联系^[11]进行研究, 发现其主要表现为个体编码差异对搜索运算的控制, 或是个体空间分布形态所形成的结构对系统整体计算的调节, 但这种隐式的结构关系并不利于其对计算过程的主动控制。因此, 就需要设计出一种更为明显的种群关系。

队列作为实际生活中一种常见的有序群体, 其特点是队头与队尾个体差异较大, 中间个体差异较小且数目众多, 这说明有序队列不同位置中的个体之间具有一定间距关系。基于以上分析, 本文提出一种新思路, 将种群先按适应值大小进行排序, 分为三类有序子群; 再通过子群控制个体的选择范围, 以构建出不同的差异向量进行群体搜索。

为便于计算, 本文采用一种简单的种群划分方法。首先计算群体平均适应值$ \overline {fit} $, 其次进行划分。具体公式如下:

$ {{\boldsymbol{x}}_{\boldsymbol{i}}} \in \left\{ \begin{array}{l} {R_g},\;\;fi{t_i} < \overline {fit} \\ {C_g},\;\;fi{t_i} \ge \overline {fit} ,i < \left( {SN - {N_{{\rm{rand}}}}} \right) \times \mu \\ {B_g},\;\;fi{t_i} \ge \overline {fit} ,i \ge \left( {SN - {N_{{\rm{rand}}}}} \right) \times \mu \end{array} \right. $

(7)

其中:R_g、C_g和B_g分别表示随机子群、核心子群和平衡子群; N_rand表示随机子群的个体总数; N_other=SN-N_rand表示C_g和B_g的个体总数; μ是群体划分比例, 实验取值为0.3。

图 3是由式(7) 得到的种群类结构图, 子群内个体相似性最大, 而子群间差异性最大。因而, 本文利用这三类子群实现对具有不同适应度函数值个体的有效控制, 以达到调节全局和局部搜索的目的。

2.2 分类机制对群体搜索状态的影响分析 2.2.1 利用分类结构调节全局和局部搜索过程

本节从两方面分析算法是如何利用三类子群实现对群体搜索过程的调节：一是通过对三类子群的平均间距进行分析, 说明其可调节全局与局部搜索的原因；二是利用个体选择机制实现其对搜索过程的调节。图 4和图 5分别表示函数F03(SumPower)运用MPABC算法在搜索最优解过程中子群的平均间距meanDis与个体数目number的变化曲线, 实验结果为20次独立实验(参数为D=30, Max.FE=1000) 的平均值。

首先, 由图 4可知, C_g个体数目下降迅速, 在400代左右就下降到非常低; B_g下降较为缓慢, 在800代以后才能取得较低的值; 而R_g在整个进化过程中下降最为缓慢, 且维持在一个相对稳定的水平。这说明在进化过程中三类子群的平均间距值变化各不相同, 从而使其处于群体搜索的不同水平。具体而言, 个体在C_g中具有较高平均适应值和较小的平均间距, 与最优解最为接近, 此时在C_g中筛选个体, 可通过减少搜索步长实现对算法局部搜索能力的增强, 有效避免了在搜索过程中出现步长过大而错失最优解。R_g中个体具有较小$ \overline {fit} $与较大的meanDis, 处于群体的劣势地位，此时通过在R_g乃至整个群体中筛选个体, 保证所选个体之间的差异性最大, 实现了以加大搜索步长来提高群体的全局探索能力, 避免了出现搜索速度过于缓慢的现象。由于B_g中的$ \overline {fit} $与meanDis均处于群体的中间水平，为保证新产生的个体具有与子群相同的特性, 通过设计出一种可调节的搜索模式, 将其搜索水平维持在C_g与R_g之间, 有效地平衡了算法的勘探与开采能力。

另外, 根据三类子群间独立又彼此联系的结构, 可以方便地将具有不同计算结构和运算特性的搜索方法有效结合在一起, 通过个体选择机制实现对群体全局和局部搜索的动态调节。如图 5所示, 进化过程分为三个阶段, 其中, C_g与B_g的个体数目不断增大, R_g数目却逐渐减小, 这种变化使看起来独立的各类子群之间又彼此关联。

基于以上分析, 针对不同的搜索水平设计出一种新型的个体选择机制:

$ \left\{ {\left. {{{\boldsymbol{c}}_{\boldsymbol{i}}}} \right|{{\boldsymbol{c}}_{\boldsymbol{i}}} \in {C_g}, i = p1, p2} \right\} $

(8)

B_g的全局到局部的过渡搜索:

$ \left\{ {\left. {{{\boldsymbol{b}}_{\boldsymbol{i}}}} \right|{{\boldsymbol{b}}_{\boldsymbol{i}}} \in {B_g}, i = p1, p2} \right\} $

(9)

R_g的全局搜索:

$ \left\{ {\left. {{{\boldsymbol{r}}_{\boldsymbol{i}}}} \right|{{\boldsymbol{r}}_i} \in {C_g} \cup {B_g} \cup {R_g}, i = p1, p2, \cdots, p5} \right\} $

(10)

其中: c_i表示在C_g中随机选出2个个体, 记为c_p1和c_p2; 同理b_i与r_i分别表示在B_g与R_g中选出的个体。

进化搜索中三类子群的搜索频率由个体数目决定, 故其取值大小将直接影响每代进行全局及局部搜索的比例。进化前期, R_g在群体中number值比重最大且B_g与C_g比重较小, 形成以“全局搜索方式为主与其他搜索方式为辅”的计算机制, 有效地丰富了群体多样性并降低了算法早熟收敛的可能; 进化中期, 三类子群number值均处于一种相对稳定的状态, 形成了一种“过渡搜索+全局搜索+局部搜索”的搜索组合; 而随着C_g中number逐渐增大, 其他子群值的不断减小, 使得进化后期形成了以“局部搜索和过渡搜索为主与全局搜索方式为辅”的计算机制, 从而提高了算法寻找最优解的速度。

2.2.2 基于分类调节的新型差分进化算法计算机制的性能分析

为有效降低ABC算法搜索机制因单一盲目性所带来的负面影响, 在分类调节机制的基础上通过进一步引入差分进化(Differential Evolution, DE)算法的多种搜索方式, 有效地提高了系统的计算效率。为了便于研究, 将DE的五种进化模式分为三类^[12], 其特点是:第一类模式中个体自由探索性突出, 全局收敛较强, 不易陷入局部最优, 但收敛速度较慢；第二类模式的个体在该区域的自由探索性相对较弱, 局部收敛性和继承性较强, 收敛速度较快, 但易陷入局部最优；第三类模式特点是群体自由探索性和继承性相对保持均衡, 具有良好的适应性。

通过以上分析, 为有效提升算法的搜索性能，本文按照子群平均间距值对种群的搜索水平进行类别划分, 则三类子群的搜索机制如下:

C_g搜索策略:

$ {\boldsymbol{v}}_i^j = {\boldsymbol{c}}_{{\rm{best}}}^j + \varphi _i^j \times \left( {{\boldsymbol{c}}_{p1}^j-{\boldsymbol{c}}_{p2}^j} \right) $

(11)

B_g搜索策略:

$ {\boldsymbol{v}}_i^j = {\boldsymbol{b}}_i^j + \varphi _i^j \times \left( {{\boldsymbol{c}}_{{\rm{best}}}^j-{\boldsymbol{b}}_i^j} \right) + \varphi _i^j \times \left( {{\boldsymbol{b}}_{p1}^j-{\boldsymbol{b}}_{p2}^j} \right) $

(12)

R_g搜索策略:

$ {\boldsymbol{v}}_i^j = {\boldsymbol{r}}_{p1}^j + \varphi _i^j \times \left( {{\boldsymbol{r}}_{p2}^j-{\boldsymbol{r}}_{p3}^j} \right) + \varphi _i^j \times \left( {{\boldsymbol{r}}_{p4}^j-{\boldsymbol{r}}_{p5}^j} \right) $

(13)

根据每个个体在搜索过程中的不同表现, 对于不同子群的个体, 在寻优过程中它需要加强该子群所需要的能力。即, 在C_g中加强局部寻优来搜索极值点, R_g中通过全局搜索来增强算法的勘探能力, 而B_g主要是对算法全局搜索能力和局部搜索能力的协调。

2.3 基于多进化模式协作的人工蜂群算法

在前述基础上提出了一种新算法MPABC, 即在分类调节机制的基础上进一步引入DE计算机制来改进全局与局部的计算效果。图 6为MPABC的架构。

如图 6所示, MPABC计算模式分为三大模块:模块一是系统初始化, 包括种群初始化与子群的构建, 最后得到三类有序子群体; 模块二针对不同子群设计出一种更具针对性且协调性更佳的搜索机制组合, 实现对搜索过程的调节; 模块三是利用观察蜂进行局部寻优来找出最优解。先通过式(8)~(9) 计算出观察蜂的搜索区间, 再利用式(11) 进行局部搜索, 进一步提升算法的寻优能力。

3 仿真实验及结果分析

为验证MPABC的求解性能, 采用16个典型的Benchmark^[13]146函数(F01~F16) 用于仿真实验。其中：F01~F08是单峰函数；F06是非连续函数；F07是带噪声函数, 在维度大于3时为多峰函数; F09~F16是多峰函数。通常单峰函数用于测试算法的寻优精度以及考察算法的执行性能。而多峰函数中的局部最优点会伴随维数的增加而指数增长, 常用于检验算法跳出局部最优的能力。

整个实验分为两部分：第一部分是对ABC和MPABC的优化性能与测试结果进行比较；第二部分是将其与近年的ABC变种算法进行比较分析, 包括具有可变搜索策略的人工蜂群算法(ABC algorithm with Variable Search Strategy, ABCVSS)^[13]148-151、基于选择概率的改进人工蜂群算法(Modified ABC algorithm based on selection probability, MABC)^[13]152、基于粒子群策略的多精英人工蜂群(Particle Swarm-inspired Multi-Elitist ABC, PS-MEABC)算法^[14]、基于符号函数的多搜索策略人工蜂群(Multi-Search Strategy of the ABC, MSSABC)算法^[15]和优化高维复杂函数的改进人工蜂群算法(Improved ABC algorithm for optimizing high-dimensional complex functions, IABC)^[16]。

3.1 MPABC和ABC的收敛性比较

为验证MPABC的寻优能力在复杂高维函数的有效性。将MPABC与ABC从结果精度、收敛速度和维度扩展性三个方面进行比较分析。实验参数设置为: NP=40;limit=200;D=30, 60, 100;Max.FE=5000;收敛精度为10^-5。表 1给出了当D=30, 60, 100时算法的测试结果(每个函数独立运行20次)。其中：最优值和最差值反映了解的质量, 平均值反映了在给定最大评价次数时算法的求解精度, 标准差则反映了算法的稳定性和鲁棒性。

由表 1计算结果可以看出：在30维情况下, MPABC在大部分函数上的性能要显著优于ABC。对部分函数(如F05、F07、F08、F12和F14), 两者性能相当; 尤其是在函数F06、F09~F11上, ABC与MPABC均能取得理论最优值0。而对于其他函数(F01~F04), MPABC的收敛精度比ABC则有了大幅度提升。并且随着维度的增长, MPABC的求解结果仍要优于或同ABC一样得到理论最优值0(如函数F06、F11)。

函数无论是在30、60还是100维上, MPABC算法的最优值和最差值的精度与ABC相比得到明显提高, 并且对各测试函数均具有较高的寻优精度, 尤其在函数F01~F04、F10、F11上。其次, 在相同迭代次数下, 针对绝大部分函数(F01、F03、F6~F11、F13~F14), MPABC算法寻优速度更快。其中一部分原因是系统利用种群分类结构直接控制群体的搜索过程, 实现对全局和局部搜索过程的调节; 另一部分是因为在分类调节机制的基础上进一步引入DE计算机制来改进全局与局部的计算效果, 使MPABC在计算的不同阶段形成更具针对性且协调性更佳的搜索机制组合, 实现了在不同复杂结构的问题空间中更高效、稳定的搜索。

为了直观反映MPABC的收敛性能, 图 7~8给出了两种算法对于部分测试函数在D=30, Max.FE =200时的收敛曲线与群体多样性图。从图 7~8可以看出, MPABC虽然在迭代初期的性能略差, 但随着迭代次数的增加, 函数收敛曲线和群体多样性曲线的下降速度明显高于ABC算法, 有利于群体在后期快速收敛到较高精度的解。

由图 7的收敛曲线可以看出:MPABC算法不但在函数F06上找到理论最优值0, 而且其收敛速度明显高于ABC; 在复杂非线性函数F08和多模态函数F15上, MPABC的性能仅略优于ABC; 而对多模态函数F13和F14, MPABC的收敛精度和速度均显著高于ABC。由图 8的多样性曲线可以看出, MPABC的群体多样性值在前期仅略高于ABC, 能够较好地减缓算法在前期的收敛速度; 随后MPABC算法的群体多样性迅速降低并逐渐趋于0, 其多样性明显低于ABC算法。此时群体差异性最小, 促使其加速收敛到最优值。综上, 说明改进后的MPABC算法性能优于ABC。

3.2 MPABC和其他改进算法的比较

将MPABC与近几年所提出的改进算法ABCVSS、MABC、PS-MEABC、MSSABC、IABC在D=30时进行比较。为了比较的公平性, MPABC参数设置为Max.FE=5000, limit=200;另外5种算法参数均为Max.FE=5000×D, limit=SN×D, 其余参数保持不变, 实验数据直接取自各文献。

由表 2可以看出, 在16个基准测试函数中, 6种算法在函数F06、F09~F11上都能求得理论最优值; 对于其他函数, MPABC在解的精度和稳定性上明显优于ABCVSS、MABC、PS-MEABC、MSSABC, 在绝大部分函数上则优于IABC。

从上述实验结果可以看出, MPABC算法可以在较小的评价次数下达到相同甚至更高的精度。不仅具有较强的全局搜索能力, 而且具有较强的局部搜索能力, 能有效克服ABC算法收敛速度慢和易陷入局部最优的缺陷, 并随着函数维度的增加, 仍能保持较好的有效性和鲁棒性。

4 结语

本文提出在种群分类调节机制的基础上进一步引入DE计算机制来改进种群全局与局部的计算效果, 形成了一种新型的进化搜索算法, 基于混合搜索的多种群人工蜂群算法。对16个基准测试函数的仿真实验结果表明, 算法有效克服了ABC演化过程中局部停滞的问题, 能有效处理高维函数优化问题并获得较高的寻优精度。但其也存在局限性, 例如对Schwefel 2.26(F12) 函数的求解效果并不理想。因而, 如何使算法能够在函数上表现出更好的性能以及将本文算法应用到多目标优化、约束优化等领域将是下一步的研究工作。