非洲蜂优化算法

引用本文

刘永利, 李仁杰. 非洲蜂优化算法[J]. 哈尔滨工程大学学报, 2020, 41(5): 738-746. DOI: 10.11990/jheu.201901004.

LIU Yongli, LI Renjie. African bee optimization algorithm[J]. Journal of Harbin Engineering University, 2020, 41(5): 738-746. DOI: 10.11990/jheu.201901004.

基金项目

国家自然科学基金项目（61872126）

通信作者

刘永利, E-mail:yongli.buaa@gmail.com.cn

作者简介

刘永利, 男, 副教授

文章历史

收稿日期：2019-01-02
网络出版日期：2020-03-23

Contents Abstract Full text Figures/Tables PDF

非洲蜂优化算法

刘永利 , 李仁杰

河南理工大学计算机科学与技术学院, 河南焦作 454000

收稿日期：2019-01-02；网络出版日期：2020-03-23

基金项目：国家自然科学基金项目（61872126）

作者简介：刘永利, 男, 副教授.

通信作者：刘永利, E-mail:yongli.buaa@gmail.com.cn.

摘要：在粒子群算法和鲸鱼群算法等进化算法中，代际之间的信息传递仅限于相邻2代个体之间，导致全局搜索参考信息单一，难以探索所有可行搜索区域并获得最优结果。本文提出一种全新的启发式算法：非洲蜂优化算法，该算法模拟了非洲蜂种群在迁徙过程中遇到威胁时的反应模式、蜂王的指令模式与记忆模式，借此实现最优化求解。为了验证非洲蜂优化算法的有效性，本文选择23种标准函数进行了对比实验，实验结果表明非洲蜂优化算法在保留较高收敛速度的同时，也保证了较好的收敛精度。

关键词：元启发算法进化算法最优化非洲蜂迁徙策略收敛精度标准函数

African bee optimization algorithm

LIU Yongli , LI Renjie

School of Computer Science and Technology, He'nan Polytechnic University, Jiaozuo 454000, China

Abstract: In evolutionary algorithms such as particle swarm optimization and the whale optimization algorithm, intergenerational communication only exists between two neighboring generations of individuals, which leads to insufficient reference information of a global search; therefore, it is difficult to search all feasible areas to obtain the optimal result. In this paper, a new heuristic algorithm is proposed, named the African bee optimization algorithm (ABOA). This algorithm simulates the reaction pattern of African bees, the command and memory patterns of the queen bee during the migration of the African bee population, and finally realizes the optimization solution. In the experiment, 23 benchmark functions were selected for comparison. The results show that the ABOA algorithm not only features a high convergence speed but also guarantees a good convergence accuracy.

Keywords: meta-heuristic algorithm evolutionary algorithm optimization African bee migration strategy convergence accuracy benchmark function

在最优化研究中，旅行商问题、指派问题、车间调度问题等超出了传统优化算法的能力范畴，研究者不断从生物学、物理学和社会学等领域寻找灵感，发展出适用于求解现实世界复杂问题的多种算法，即元启发式算法^[1-4]。元启发式算法以群体智能算法为主，主要有粒子群算法(particle swarm optimization, PSO)^[5]、人工蜂群算法(artificial bee colony, ABC)^[6]、鲸鱼群算法(whale optimization algorithm, WOA)^[7]、人工蚁群算法(ant colony optimization)^[8]、黄蜂群算法(wasp swarm algorithm)^[9]、猴子搜索算法(monkey search)^[10]和狼群搜索算法(wolf pack search algorithm)^[11]等，这些算法从生物进化及种群合作等机理中发展而来，在优化效果上较传统优化算法取得了提升。除生物学外，物理现象也是元启发式算法的理论来源，衍生的算法包括模拟退火(simulated annealing, SA)^[12]、引力搜索算法(gravitational search algorithm, GSA)^[13]、基于银河系搜索算法(galaxy-based search algorithm, GbSA)^[14]、电荷系统搜索(charged system search, CSS)^[15]、向心力优化(central force optimization, CFO)^[16]、黑洞算法(black hole, BH)^[17]等。

然而，在这些元启发算法中，前代信息一经淘汰便不会被二次充分搜索，导致部分需要以前代信息为“桥梁”的搜索失去线索，从而失去获得潜在解的可能。本文根据非洲蜂种群的社会行为，提出了一种新的优化算法，即非洲蜂优化算法(africanized bee optimization algorithm, ABOA)。该算法模拟了蜂王的信息素分泌以及信息素扩散淡化的过程，实现了多代信息的保留，并通过模型控制使其能够在一次迭代中同时作为参考。算法同时模拟了蜂群其他个体在信息素影响下的行为模式，使得整个种群能够不断更新全局最优解直至找到最优解。

1 元启发式算法

元启发式算法相对于优化算法而提出，旨在用随机与进化策略求得特定问题的最优解。多数元启发式算法的构造基于特定领域的相关知识或经验，如生物学知识、物理知识或社会学知识，并在此基础上构建出可接受花费时间内求解特定问题的进化算法。就目前而言，元启发式算法以仿生算法为主，其设计常取自生物学领域相关知识。

1.1 粒子群算法

Kennedy等提出的粒子群算法是元启发算法的代表，因其性能优异、可扩展性强而广为人所。PSO算法模拟了鸟类种群觅食行为，通过再现鸟群中的集体协作和信息共享实现智能搜索。在该算法中，每个鸟类个体均被视为基本运算粒子，不同粒子之间通过合作及信息传递寻找最优目标。每个粒子的运行轨迹由原始运行方向、自身最优目标方向以及全局最优目标方向组成。

1.2 引力搜索算法

Rashedi等^[13]基于万有引力定律与牛顿第二定律提出了引力搜索算法(GSA)。该算法模拟了不同质量的粒子在特定物理条件下的运动情况，并通过不断改变粒子位置，使搜索粒子获得新的属性，以此推进搜索进程。在GSA的搜索过程中，所有粒子在相互作用下不断移动，最终靠近最优解。

1.3 鲸鱼群算法

Mirjalili等^[7]在2016年提出了鲸鱼群算法(WOA)，该算法模拟鲸鱼群捕食过程中的搜索、包围以及攻击行为，寻找全局最优。在WOA算法中，每个个体能够对最优目标的位置进行侦测，并对其实现包围。在搜索过程中，WOA算法会根据搜索现状调整搜索策略，使搜索在随机搜索代理或最佳搜索代理间展开。

2 非洲蜂优化算法 2.1 非洲蜂模式

非洲蜂，也称非洲杀人蜂。与其他蜜蜂种群一样，非洲蜂种群内部也有十分严格的工作分工。蜂王依靠其强大的信息素控制种群内的所有成员，并且负责传宗接代。蜂群每次产出多个蜂王幼虫，经过角逐，最终只能有一只幼虫成为蜂王。

每年旱季来临时，由于水源枯竭、食物短缺，非洲蜂种群需要在蜂王的指引下迁徙。在迁徙途中，当遇到威胁时，会发动成群攻击。每次迁徙对蜂王消耗较大，导致其信息素的分泌迅速减弱，最终被蜂群视为无用成员并将其遗弃。每年春季，在蜂王幼虫成熟时，会引发新的王位争夺，最终产生新的蜂王。

2.2 算法描述

本文受非洲蜂种群行为启发，提出了ABOA算法。在ABOA算法中，每次发现一个新的全局最优解时，蜂王都会散布一个最优解位置的信息素，令信息素残留时间为m次迭代，且随着迭代次数的增加，逐渐降低历史信息素的权重。蜂王根据历史信息素获得自身速度，并更新位置。为防止过多冗余信息，蜂王在经过m次迭代之后被判定为死亡，且其散布信息素将被清空，并由算法产生新的蜂王引领蜂群。所有非洲蜂个体在蜂王周围进行搜索并更新全局最优信息。ABOA算法的主要行为描述为：

1) 蜂王k产生及王位更迭：算法运行时，若没有蜂王在位，则产生一个新的蜂王，设定寿命长度为m，在m次迭代后判定其死亡，并将其销毁、清空其产生的所有信息素，m默认取值为5。

2) 蜂王信息素传播：假定蜂王在第j次迭代诞生，信息素残留时间为m，即能够记录m次迭代的全部最优解位置g_Best，g_Best(i)代表第i次迭代产生的全局最优值(威胁度)所在位置。信息素综合信息体现为：

$ \mathit{\boldsymbol{M}} = {[\begin{array}{*{20}{c}} {{g_{{\rm{ Best }}}}(j)}&{{g_{{\rm{ Best }}}}(j + 1)}& \cdots &{{g_{{\rm{ Best }}}}(j + m - 1)} \end{array}]^{\rm{T}}} $

(1)

3) 蜂王转移：在第t次迭代中，假定在位的蜂王诞生于第j次迭代，并根据自身位置x_k(t)和M中的g_Best(j)至g_Best(t-1)更新自身位置x_k(t+1)：

$ {x_k}(t + 1) = {x_k}(t) + \eta \odot {v_k}(t) $

(2)

式中：

$ \begin{array}{l} \eta \odot {v_k}(t) = \sum\limits_{i = 1}^{i - j + 1} {{a_i}} \cdot {\rm{rand}}{ _i} \cdot ({g_{{\rm{ Best }}}}({j^n} + i - 1) - \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {x_k}(t)) \end{array} $

(3)

式(3)代表蜂王t时刻速度，其中η表示为：

$ \eta = \{ {a_1},{a_2}, \cdots ,{a_m}\} $

(4)

式中：a₁=0.5(MaxIter-t)/MaxIter，信息素存留上限系数a_m的正常取值为1，而a₂, a₃, …, a_m-1取a₁~a_m等分值(以此实现随时间增加而降低历史信息素权重的目的)，MaxIter为最大迭代次数。

4) 蜂群转移：蜂群中每个个体i根据自身原有速度v_i(t)和蜂王的位置x_k(t)更新速度v_i(t+1)与位置x_i(t+1)：

$ \begin{array}{l} {v_i}(t + 1) = {\delta _1} \cdot {\rm{ran}}{{\rm{d}}_1} \cdot {v_i}(t) + {\delta _2} \cdot {\rm{ran}}{{\rm{d}}_2} \cdot \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} ({x_k}(t) - {x_i}(t)) \end{array} $

(5)

$ {{x_i}(t + 1) = {x_i}(t) + {v_i}(t + 1)} $

(6)

式中：δ₁与δ₂为控制参数，一般选取δ₁=1.3, δ₂=0.6。

5) 蜂群攻击：根据当前位置x_i(t)，计算威胁度(适应度)数值f_i(x_i(t))，并将发现的威胁度与全局威胁度(全局最优)值f_Best(t-1)作对比，更新全局威胁度f_Best(t)，并更新全局威胁度位置g_Best(t)。

ABOA算法的具体步骤如下：

1) 初始化参数：最大迭代次数MaxIter，蜂王寿命m，非洲蜂种群数N_p，信息素存留上限系数a_m。

2) 种群初始化：随机初始化蜂群所有个体位置，并计算所在位置威胁度f_i(x_i(t))和速度v_i(t)。

3) 检查蜂王是否存在，若不存在，则初始化蜂王位置x_k为当前最高威胁值点(最优值点)，并初始化速度v_k和信息素向量M。检查蜂王寿命，若寿命达到m，则将其销毁。

4) 蜂王将当前全局威胁度最高点录入信息素向量M，并根据式(3)和式(2)获得蜂王速度并更新蜂王位置x_k。

5) 蜂群个体根据式(6)更新自身位置，即以自身原有速度及蜂王位置获得新的自身速度并更新位置。

6) 计算所有个体威胁度值(适应度值)，并更新全局威胁度(全局最优值)。判断是否达到最大迭代次数MaxIter，若未达到，则返回步骤3)。否则，转向步骤7)。

7) 算法终止，输出最终种群状态及目标点。

其中，步骤4)对信息素向量M进行操作，将每次迭代产生的全局最优值录入其中，以此实现多带信息的保留。

2.3 收敛性证明

下面对ABOA算法的收敛性进行证明。

定义1 若P{K_T(x)=x}>0，则称位置x′是从x通过更新可达的，其中K_T(x)表示由x通过更新(蜂王转移行为与蜂群转移行为)计算产生的点，P{ ·}表示随机事件{ ·}的概率。

定义2 若P{‖K_T(x)-x′‖_∞≤ε}>0，‖ ·‖_∞代表Rⁿ上定义的范数，ε>0为给定的任意小正数，则称x′是从x通过更新为ε精度可达的。

引理1 若一个群体智能算法满足下列2个条件：1)对可行域中任意2个点x′和x，x′是从x通过更新为ε精度可达的；2)种群序列f_Best(1), f_Best(2), …, f_Best(t), …是单调的，即对∀t，f_Best(t+1)非劣于f_Best(t)，则该群体智能算法以概率1收敛到问题的全局最优解集^[18]。

定理1对充分小的ε>0，若f(x)在搜索空间[L_B, U_B]上连续，则ABOA以概率1收敛到优化问题具有ε精度的最优解，即

$ P\{ \mathop {{\rm{lim}}}\limits_{t \to \infty } {\left\| {{\mathit{\boldsymbol{f}}_{{\rm{Best}}}}(t) - {\mathit{\boldsymbol{f}}_{{\rm{ Best \ true }}}}} \right\|_\infty } \le \varepsilon \} = 1 $

(7)

其中，f_{Best true}代表优化问题的全局最优解，‖f_Best (t)- f_{Best true}‖_∞≤ε表示{‖x-x^*‖_∞≤ε|∀x∈g_Best(t), ∀x^*= g_{Best true}}，g_{Best true}代表优化问题全局最优解所在位置。

证明要证ABOA对任意2个点x′和x∈[LB, UB]，x′是从x通过ABOA中更新为ε精度可达的，即证：

$ P\{ {\left\| {{\mathit{\boldsymbol{K}}_T}(x) - {\mathit{\boldsymbol{x}}^\prime }} \right\|_\infty } \le \varepsilon \} > 0 $

(8)

式中：K(x)为ABOA下x通过蜂王转移行为产生的点；T(x)为ABOA下x通过蜂群转移行为产生的点。

令x_k为蜂王位置，可将上述证明转换为：对任意点x_k∈[L_B, U_B]，x′是从x_k通过ABOA中蜂王转移行为更新为ε精度可达，且对任意点x∈[L_B, U_B]，x_k是从x通过ABOA中蜂群转移行为更新为ε精度可达，即证：

$ \begin{array}{*{20}{l}} {P\{ {{\left\| {\mathit{\boldsymbol{K}}({x_k}) - {\mathit{\boldsymbol{x}}^\prime }} \right\|}_\infty } \le \varepsilon \} > 0}\\ {{\rm{且 }}P\{ {{\left\| {\mathit{\boldsymbol{T}}(x) - {\mathit{\boldsymbol{x}}_k}} \right\|}_\infty } \le \varepsilon \} > 0} \end{array} $

(9)

首先证明P{‖K(x_k)-x′‖_∞≤ε}>0，分为以下3种情况：

1) 由式(2)、(3)可知，当任一g_Best(t)=x′，且g_Best(t)在式(3)中所对应参数a_i取值为1，对应rand′_i取值为1，其他rand_i取值为0时，K(x_k)=x′。必然存在η，rand′_i取值小于等于1-η，其他rand_i≠0时，使得|xk-x′|≤ε成立，即x′是从x_k通过ABOA中蜂王转移行为更新为ε精度可达。

2) 令δ=g_Best(t)-x′，由式(2)、(3)可知，存在η，当δ所有分量取值小于等于η，rand′ _i取值为1，其他randi取值为0时，使得|xk-x′|≤ε成立，即x_k通过ABOA中蜂王转移行为更新为ε精度可达。

3) 由式(2)、(3)知，当任一g_Best(t)≠x′时，η⊙v_k(t)由多个向量构成，在随机参数作用下任意点可达，可知P{x_k(t)+η⊙v_k(t)-x′≤ε}>0，即x_k通过ABOA中蜂王转移行为更新为ε精度可达。

其次证明P{‖T(x)-x_k‖_∞≤ε}>0：

由式(5)、(6)可知，v_i(t)根据x_k及x_i更新，必然存在x_i使得P{‖T(x_i)-x_k‖_∞≤ε}>0成立。

又由步骤6)可知，对于∀t，ABOA所产生序列中，任意f_Best(t+1)非劣于f_Best(t)，于是f_Best(1), f_Best(2), …, f_Best(t), …是单调的。

综上所述，由引理1及定理1可得：

$ P\{ \mathop {{\rm{lim}}}\limits_{t \to \infty } {\left\| {{\mathit{\boldsymbol{f}}_{{\rm{Best}}}}(t) - {\mathit{\boldsymbol{f}}_{{\rm{ Best \ true }}}}} \right\|_\infty } \le \varepsilon \} = 1 $

(10)

即ABOA以概率1收敛到优化问题具有ε精度的最优解。

3 标准函数测试实验及结果 3.1 实验说明

为验证ABOA算法的收敛性及搜索性能，选取23个标准函数进行实验^[19]，并将实验结果与WOA、GSA和PSO算法进行对比。WOA与GSA采用默认参数，PSO选取标准参数：w=0.4, c₁=2, c₂=2。表 1给出23个标准函数中7个单峰函数的具体公式、取值范围以及最优精度取值，表 4则给出了16个多峰函数的具体信息。函数F₁至F₁₃取维度Dim=30进行测试，函数F₁₄~F₂₃则根据要求取相应维度进行测试。ABOA算法的参数赋值情况为：m=5，a_m=1，δ₁=1.3和δ₂=0.6。所有参与测试算法均选取相同的种群规模(N_p=30)与最大迭代次数(MaxIter=500)，分别独立进行30次实验，并记录每次实验所得最优结果、30次实验结果均值及标准差，实验结果如表 2与表 3所示。

表 1 单峰标准函数F₁~F₇ Table 1 Unimodal functions F₁~F₇

表 2 单峰函数对比运行结果 Table 2 Comparing operation results of unimodal function

函数	参数	ABOA	WOA	GSA	PSO
	Best	1.819 5×10^-31	1.034 7×10^-85	1.225 4×10^-16	4.654 2×10^-8
F₁	Avg	3.114 5×10^-29	2.038 7×10^-74	3.64 12×10^-5	1 000.000 0
	Std	4.683 7×10^-29	7.777 7×10^-74	0.000 2	3 051.285 8
	Best	1.718 8×10^-16	2.463 3×10^-59	5.190 3×10^-8	1.387 2×10^-5
F₂	Avg	1.426 6×10^-15	4.775 9×10^-51	0.077 2	20.666 9
	Std	1.328 5×10^-15	1.614 9×10^-50	0.287 2	14.605 8
	Best	2.757 8×10^-28	22 772.754 7	497.078 3	1 297.104 7
F₃	Avg	8.423 5×10^-26	43 971.702 0	995.474 6	16 522.911 1
	Std	1.996 9×10^-25	10 767.745 1	500.611 3	7 809.029 4
	Best	4.238 6×10^-16	2.506 1	5.387 1	10.222 8
F₄	Avg	8.125 9×10^-15	47.155 0	8.113 5	19.398 5
	Std	8.846 9×10^-15	27.460 5	1.679 8	5.700 7
	Best	27.513 9	27.056 5	23.067 4	20.667 4
F₅	Avg	28.454 1	28.102 6	50.1089	12 399.217 5
	Std	0.413 2	0.503 2	37.926 1	30 977.668 7
	Best	0.000 0	0.000 0	0.000 0	0.000 0
F₆	Avg	0.000 0	0.000 0	12.533 3	333.433 3
	Std	0.000 0	0.000 0	20.729 3	1 825.723 0
	Best	3.776 8×10^-6	0.000 3	0.026 3	0.025 0
F₇	Avg	0.000 1	0.004 6	0.081 0	0.697 3
	Std	0.000 1	0.003 9	0.049 5	3.427 0

表 2 单峰函数对比运行结果 Table 2 Comparing operation results of unimodal function

表 3 多峰函数对比运行结果 Table 3 Comparing operation results of multimodal function

函数	参数	ABOA	WOA	GSA	PSO
	Best	-10 461.776 7	-12 569.466 0	-4 269.744 6	-10 133.904 6
F₈	Avg	-6 638.120 6	-9 822.012 1	-2 671.092 9	-9095.5266
	Std	1 318.428 2	1 646.264 6	552.864 6	703.490 7
	Best	0.000 0	0.000 0	15.919 3	63.713 7
F₉	Avg	0.000 0	0.000 0	27.693 0	123.608 2
	Std	0.000 0	0.000 0	8.332 9	34.261 0
	Best	8.881 8×10^-16	8.881 8×10^-16	9.608 0×10^-9	0.002 1
F₁₀	Avg	7.519 9×10^-15	1.006 6×10^-15	0.514 5	9.902 6
	Std	3.928 9×10^-15	6.486 3×10^-16	0.5204	6.547 0
	Best	0.000 0	0.000 0	19.834 6	1.299 3×10^-8
F₁₁	Avg	0.000 0	0.000 0	34.132 9	3.218 0×10^-7
	Std	0.000 0	0.000 0	8.709 6	9.380 3×10^-7
	Best	0.128 9	0.005 7	0.188 0	5.161 8×10^-5
F₁₂	Avg	0.270 8	0.021 0	1.651 5	0.636 6
	Std	0.090 6	0.012 9	0.892 1	0.836 9
	Best	1.411 1	-0.862 7	-0.606 7	-1.150 3
F₁₃	Avg	2.403 9	0.098 7	8.078 0	-1.056 0
	Std	0.486 1	0.514 8	6.617 0	0.135 0
	Best	0.376 9	0.377 8	0.376 9	0.376 9
F₁₄	Avg	0.521 6	0.470 6	0.605 5	0.381 5
	Std	0.213 5	0.137 2	0.254 2	0.004 4
	Best	3.074 9×10^-4	3.185 5×10^-4	0.001 8	3.074 9×10^-4
F₁₅	Avg	0.001 7	0.000 644 94	0.004 764 50	0.006 0
	Std	0.0051	0.000 445 32	0.003 024 70	0.009 0
	Best	-1.0316	-1.031 6	-1.031 6	-1.031 6
F₁₆	Avg	-1.031 6	-1.031 6	-1.031 6	-1.031 6
	Std	6.045 9×10^-16	1.052 6×10^-9	4.790 8×10^-16	6.648 6×10^-16
	Best	0.397 9	0.397 9	0.397 9	0.397 9
F₁₇	Avg	0.397 9	0.397 9	0.397 9	0.397 9
	Std	0.000 0	6.423 6×10^-6	0.000 0	0.000 0
	Best	3.000 0	3.000 0	3.000 0	3.000 0
F₁₈	Avg	3.000 0	3.900 0	3.000 0	3.000 0
	Std	7.721 4×10^-11	4.929 500 00	4.078 5×10^-15	5.831 2×10^-16
	Best	-3.862 8	-3.862 8	-3.862 8	-3.862 8
F₁₉	Avg	-3.861 7	-3.856 5	-3.862 8	-3.862 8
	Std	0.002 7	0.013 0	2.291 3×10^-15	2.710 1×10^-15
	Best	-3.322 0	-3.321 6	-3.322 0	-3.322 0
F₂₀	Avg	-3.290 9	-3.248 3	-3.318 0	-3.270 9
	Std	0.056 85	0.116 9	0.022 0	0.070 8
	Best	-10.153 2	-10.148 2	-10.153 2	-10.153 2
F₂₁	Avg	-6.414 5	-7.771 0	-6.016 7	-5.638 3
	Std	2.292 7	2.809 7	3.710 6	3.374 6
	Best	-10.402 9	-10.401 6	-10.402 9	-10.402 9
F₂₂	Avg	-5.796 4	-8.146 5	-10.213 1	-6.532 7
	Std	1.837 7	3.037 2	0.808 4	3.714 6
	Best	-10.536 4	-10.535 6	-10.536 4	-10.536 4
F₂₃	Avg	-5.488 9	-7.882 9	-10.087 8	-6.575 8
	Std	1.371 8	3.111 0	1.731 3	3.637 3

表 3 多峰函数对比运行结果 Table 3 Comparing operation results of multimodal function

表 4 多峰基准函数F₈~F₂₃ Table 4 Multimodal benchmark functions F₈ to F₂₃

函数	维数	取值范围	最优取值
${F_8}(x) = \sum\limits_{i = 1}^n - {x_i}\sin (\sqrt {\left\| {{x_i}} \right\|})$	30	[-500, 500]	-12 569.5
${F_9}(x) = \sum\limits_{i = 1}^n {\left[{x_i^2- 10\cos \left({2{\rm{ \mathsf{ π} }}{x_i}} \right) + 10} \right]} $	30	[-5.12, 5.12]	0
${F_{10}}(x) =- 20\exp (- 0.2\sqrt {\frac{1}{n}\mathop \sum \limits_{i = 1}^n }) - \exp \left({\frac{1}{n}\sum\limits_{i = 1}^n {\cos } \left({2{\rm{ \mathsf{ π} }}{x_i}} \right)} \right) + 20 + e$	30	[-32, 32]	0
${F_{11}}(x) = \frac{1}{{4\; 000}}\sum\limits_{i = 1}^n {x_i^2} - \prod\limits_{i = 1}^n {\cos } \left({\frac{{{x_i}}}{{\sqrt i }}} \right) + 1$	30	[-600, 600]	0
$\begin{array}{l} {F_{12}}(x) = \frac{{\rm{ \mathsf{ π} }}}{n}\left\{ {10\sin \left({{\rm{ \mathsf{ π} }}{y_1}} \right) + \sum\limits_{i = 1}^n {{{\left({{y_i} - 1} \right)}^2}} \left[{1 + 10{{\sin }^2}\left({{\rm{ \mathsf{ π} }}{y_{i + 1}}} \right)} \right] + {{\left({{y_n} - 1} \right)}^2}} \right\} + \\ \; \; \; \; \; \; \; \; \; \; \; \; \; \sum\limits_{i = 1}^n u \left({{x_i}, 10, 100, 4} \right)\\ {y_i} = 1 + 0.25\left({{x_i} + 1} \right), u\left({{x_i}, a, k, m} \right) = \left\{ {\begin{array}{*{20}{l}} {k{{\left({{x_i} - a} \right)}^m}} & {{x_i} > a}\\ 0 & { - a < {x_i} < a}\\ {k{{\left({ - {x_i} - a} \right)}^m}} & {{x_i} < - a} \end{array}} \right. \end{array}$	30	[-50, 50]	0
$\begin{array}{*{20}{l}} {{F_{13}}(x) = 0.1\left\{ {{{\sin }^2}\left({3{\rm{ \mathsf{ π} }}{x_1}} \right) + \sum\limits_{i = 1}^n {{{\left({{x_i} - 1} \right)}^2}} \left[{1 + {{\sin }^2}\left({3{\rm{ \mathsf{ π} }}{x_i} + 1} \right)} \right] + } \right.}\\ {\left. {{{\left({{x_n} - 1} \right)}^2}\left[{1 + {{\sin }^2}\left({2{\rm{ \mathsf{ π} }}{x_n}} \right)} \right]} \right\} + \sum\limits_{i = 1}^n u \left({{x_i}, 10, 100, 4} \right)} \end{array}$	30	[-50, 50]	0
${F_{14}}(x) = {\left({\frac{1}{{500}} + \sum_{j = 1}^{25} {\frac{1}{{j + \sum_{i = 1}^2 {{{\left({{x_i} - {a_{ij}}} \right)}^6}} }}} } \right)^{ - 1}}$	2	[-65, 65]	1
${F_{15}}(x) = \sum\limits_{i = 1}^{11} {{{\left[{{a_i}- \frac{{\left. {b_i^2 + {b_i}{x_2}} \right)}}{{b_i^2 + {b_i}{x_3} + {x_4}}}} \right]}^2}} $	4	[-5, 5]	0.000 30
${F_{16}}(x) = 4x_1^2- 2.1x_1^2 + \frac{1}{3}x_1^6 + {x_1}{x_2} - 4x_2^2 + 4x_2^4$	2	[-5, 5]	-1.031 6
${F_{17}}(x) = {\left({{x_2} - \frac{{5.1}}{{4{{\rm{ \mathsf{ π} }}^2}}}x_1^2 + \frac{{\rm{ \mathsf{ π} }}}{5}{x_1} - 6} \right)^2} + 10\left({1 - \frac{1}{{8{\rm{ \mathsf{ π} }}}}} \right)\cos \left({{x_1}} \right) + 10$	2	[-5, 5]	0.398
$\begin{array}{l} {F_{18}}(x) = \left[{1 + {{\left({{x_1} + {x_2} + 1} \right)}^2}\left({19 - 14{x_1} + 3x_1^2 - 14{x_2} + 6{x_1}{x_2} + 3x_2^2} \right)} \right] \times \\ \; \; \; \; \; \; \; \; \; \; \; \; \left[{30 + {{\left({2{x_1} - 3{x_2}} \right)}^2}\left({18 - 32{x_1} + 12x_1^2 + 48{x_2} - 36{x_1}{x_2} + 27x_2^2} \right)} \right] \end{array}$	2	[-2, 2]	3
${F_{19}}(x) =- \sum\limits_{i = 1}^4 {{c_i}} \exp \left({ - \sum_{j = 1}^3 {{a_{ij}}} {{\left({{x_j} - {p_{ij}}} \right)}^2}} \right)$	3	^{[1, 3]}	-3.86
${F_{20}}(x) =- \sum\limits_{i = 1}^4 {{c_i}} \exp \left({ - \sum_{j = 1}^6 {{a_{ij}}} {{\left({{x_j} - {p_{ij}}} \right)}^2}} \right)$	6	[0, 1]	-3.32
${F_{21}}(x) =- \sum\limits_{i = 1}^5 {{{\left[{\left({X - {a_i}} \right){{\left({X - {a_i}} \right)}^{\rm{T}}} + {c_i}} \right]}^{ - 1}}} $	4	[0, 10]	-10.153 2
${F_{22}}(x) =- \sum\limits_{i = 1}^7 {{{\left[{\left({X - {a_i}} \right){{\left({X - {a_i}} \right)}^{\rm{T}}} + {c_i}} \right]}^{ - 1}}} $	4	[0, 10]	-10.402 8
${F_{23}}(x) =- \sum_{i = 1}^{10} {{{\left[{\left({X - {a_i}} \right){{\left({X - {a_i}} \right)}^{\rm{T}}} + {c_i}} \right]}^{ - 1}}} $	4	[0, 10]	-10.536 3

表 4 多峰基准函数F₈~F₂₃ Table 4 Multimodal benchmark functions F₈ to F₂₃

在表 2与表 3中，Best代表算法在多次运算求得的最优结果，该结果体现了算法对于最优解的“挖掘”能力；Avg为30次运算所求结果的平均值；Std代表 30次运算结果的标准差。Avg和Std从侧面反映了算法在搜索当前函数时的稳定性。所有标准函数均求最小值，因此在测试结果中Best、Avg与Std取值越小越好。限于篇幅，图 1与图 2仅选取性能差别较为明显的函数：F₁、F₂、F₃、F₄、F₅、F₇、F₈、F₉、F₁₀、F₁₁、F₁₂、F₁₈、F₂₀、F₂₁、F₂₃的收敛性能予以描述，具体内容为30次运算所得每代全局最优值的平均值变化曲线。

	Download: JPG larger image
图 1 高维度下(Dim=30)函数单峰函数收敛性能 Fig. 1 Convergence performance of unimodal functions (Dim=30)

	Download: JPG larger image
图 2 高维度下(Dim=30)多峰函数收敛性能 Fig. 2 Convergence performance of multimodal functions (Dim=30)

3.2 单峰函数实验结果及分析

单峰函数局部最优点唯一(即全局最优点)，可以用于检验算法的局部搜索能力。结合表 2对比其他算法，ABOA在函数F₃、F₄、F₇中均找到最优解，且其结果平均值(Avg)与结果标准差(Std)都较小，显示出良好的稳定性。但是，由于函数F₆本身问题的限制ABOA相较于其他算法在最优结果上并没有太大提升，但从图 1可知，ABOA在函数6的测试中，收敛性能优于其他算法。ABOA对于函数F₁和F₂的测试结果虽未优于WOA，但相比于GSA与PSO有着明显的改进，并且维持了相对较小的均值与标准差。

对于函数F₅，ABOA虽未取得最优结果，但是相比其他算法，具有更好的标准差与平均值，即拥有更好的稳定性，稳定收敛于最优点附近。

对于函数F₃和F₄，对比算法WOA、GSA与PSO均未能达到理想精度，而ABOA的表现则十分突出，其结果获得了较高的精度。此外，从图 1可以看出，ABOA算法在处理此类函数时，不仅能够获得高精度结果，且能够实现快速收敛，即能够迅速贴近最优数值，提高了搜索的效率。

3.3 多峰函数实验结果及分析

函数F₈至F₂₃为多峰函数，包含多个局部最优点，可以检验算法的全局搜索能力。由表 3可知，ABOA对于多数多峰函数(F₉、F₁₀、F₁₁、F₁₄、F₁₆、F₁₇、F₁₈、F₁₉、F₂₀、F₂₁)均有较好的表现，能够搜索到最优值，虽然均值与标准差并非最优，但仍维持在较小的数量级上，其主要原因与ABOA同时考虑多个最优候选有关，使其会在现有最优值点与相近历史最优值点之间进行小规模的深度搜索，在有多个最优点时，ABOA会增加在同一区域中的搜索密度，使其在十分相近的最优点之间进行小规模震荡，这一特性确保了ABOA能够获得全局最优结果。

对于函数F₂₂、F₂₃，由于问题本身具有一定复杂度，有多个相近全局最优值，算法ABOA虽然找到了最优结果，相较其他算法而言稳定性上并未有太大提升，但收敛性能相对较好。

值得注意的是，ABOA对于F₉、F₁₁、F₁₅表现优异，在搜索到最优值的同时，均值与标准差同比较优。虽对函数F₈、F₁₂、F₁₃效果一般，但结果比其他算法仍较为优秀。同时，结合图 2可知，ABOA在处理多峰函数时，也有较好的收敛性能。

4 结论

1) 本文根据非洲蜂种群的社会行为，提出非洲蜂优化算法(ABOA)，该算法改进了以往只参考单代信息的策略，对多代信息进行综合处理，在保留较高搜索精度的同时，扩展了潜在的搜索空间。

2) 对于F₃和F₄，由于问题本身特性，使得已有算法难以深入搜索并获得最优结果，而ABOA算法能够迅速深入最优搜索区域，避免了重复劳动，提高了搜索效率。在实际工业设计问题中，ABOA亦表现出较好的收敛性能与寻优精度。

参考文献

[1]	ABDEL-BASSET M, MANOGARAN G, EL-SHAHAT D, et al. A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem[J]. Future generation computer systems, 2018, 85: 129-145. DOI:10.1016/j.future.2018.03.020 (0)
[2]	AZIZ M A E, EWEES A A, HASSANIEN A E. Whale Optimization Algorithm and Moth-Flame Optimization for multilevel thresholding image segmentation[J]. Expert systems with applications, 2017, 83: 242-256. DOI:10.1016/j.eswa.2017.04.023 (0)
[3]	MAFARJA M M, MIRJALILI S. Hybrid Whale Optimization Algorithm with simulated annealing for feature selection[J]. Neurocomputing, 2017, 260: 302-312. DOI:10.1016/j.neucom.2017.04.053 (0)
[4]	OLIVA D, AZIZ M A E, HASSANIEN A E. Parameter estimation of photovoltaic cells using an improved chaotic whale optimization algorithm[J]. Applied energy, 2017, 200: 141-154. DOI:10.1016/j.apenergy.2017.05.029 (0)
[5]	KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN'95-International Conference on Neural Networks. Perth, WA, Australia: IEEE, 1995: 1942-1948. (0)
[6]	KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization:artificial bee colony (ABC) algorithm[J]. Journal of global optimization, 2007, 39(3): 459-471. DOI:10.1007/s10898-007-9149-x (0)
[7]	MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in engineering software, 2016, 95: 51-67. DOI:10.1016/j.advengsoft.2016.01.008 (0)
[8]	DORIGO M, BIRATTARI M, STUTZLE T. Ant colony optimization[J]. IEEE computational intelligence magazine, 2006, 1(4): 28-39. DOI:10.1109/MCI.2006.329691 (0)
[9]	PINTO P C, RUNKLER T A, SOUSA J M C. Wasp swarm algorithm for dynamic MAX-SAT problems[C]//Proceedings of the 8th International Conference on Adaptive and Natural Computing Algorithms. Warsaw, Poland: Springer, 2007: 350-357. (0)
[10]	MUCHERINO A, SEREF O. Monkey search:a novel metaheuristic search for global optimization[J]. AIP conference proceedings, 2007, 953(1): 162-173. (0)
[11]	YANG Chenguang, TU Xuyan, CHEN Jie. Algorithm of marriage in honey bees optimization based on the wolf pack search[C]//Proceedings of 2007 International Conference on Intelligent Pervasive Computing. Jeju City, South Korea: IEEE, 2007: 462-467. (0)
[12]	KIRKPATRICK S, GELATT JR C G, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680. DOI:10.1126/science.220.4598.671 (0)
[13]	RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA:a gravitational search algorithm[J]. Information sciences, 2009, 179(13): 2232-2248. DOI:10.1016/j.ins.2009.03.004 (0)
[14]	SHAH-HOSSEINI H. Principal components analysis by the galaxy-based search algorithm:a novel metaheuristic for continuous optimisation[J]. International journal of computational science and engineering, 2011, 6(1/2): 132-140. DOI:10.1504/IJCSE.2011.041221 (0)
[15]	KAVEH A, TALATAHARI S. A novel heuristic optimization method:charged system search[J]. Acta mechanica, 2010, 213(3/4): 267-289. (0)
[16]	FORMATO R A. Central force optimization:a new metaheuristic with applications in applied electromagnetics[J]. Progress in electromagnetics research, 2007, 77: 425-491. DOI:10.2528/PIER07082403 (0)
[17]	HATAMLOU A. Black hole:a new heuristic optimization approach for data clustering[J]. Information sciences, 2013, 222: 175-184. DOI:10.1016/j.ins.2012.08.023 (0)
[18]	BACK T. Evolutionary algorithms in theory and practice:evolution strategies, evolutionary programming, genetic algorithms[M]. Oxford: Oxford University Press, 1996: 21-28. (0)
[19]	YAO Xin, LIU Yong, LIN Guangming. Evolutionary programming made faster[J]. IEEE transactions on evolutionary computation, 1999, 3(2): 82-102. DOI:10.1109/4235.771163 (0)