极值个体引导的人工蜂群算法

2022-11-15王联国

计算机与生活 2022年11期

陈兰，王联国

1.甘肃农业大学机电工程学院，兰州730070

2.甘肃农业大学信息科学技术学院，兰州730070

仿生智能计算是一类模拟自然界中“优胜劣汰”行为的算法，具有自适应、自组织、自学习等特点，智能优化算法在解决诸多复杂优化问题方面已展现出优异的性能和巨大的发展潜力，例如：周蓉等[1]针对粒子群（particle swarm optimization，PSO）算法容易早熟收敛、易陷入局部最优、精度低等缺点，提出一种基于灰狼优化的反向学习粒子群算法，提高算法的收敛精度和速度；史春天等[2]将传统的人工智能和群体生物结合，在解空间中搜索最优解，为图像分割技术提供了新的解决思路；傅文渊[3]用布谷鸟巢穴间存在的万有引力进行加速搜索，提出了一种概率变异的方法，增大了种群多样性；张孟健等[4]将多种智能优化算法用于求解带约束的工程优化问题，通过基准测试函数的寻优测试，分析了智能优化算法的改进方法及其发展潜力。而人工蜂群算法（artificial bee colony，ABC）作为一种典型的仿生智能计算方法，是由土耳其学者Karaboga[5]于2005 年提出的，具有原理简单、控制参数少、容易实现、收敛速度快等优点，且己被证明是一种优异的全局优化算法，许多学者和研究人员对其进行了研究与改进。其中，刘渝根等[6]利用ABC 算法优化支持向量机（support vector machine，SVM）的接地网腐蚀速率预测模型，表明相对BP 神经网络模型和广义回归神经网络模型，采用ABC 算法优化的模型预测结果精确度和稳定性更高；宋晓宇等[7]提出一种多策略混合搜索ABC算法，利用不同搜索策略的特征及合适的混合比例，实现算法在探索和开发之间的平衡；孔德鹏等[8]提出一种基于排序选择和精英引导策略的ABC 算法，提高算法的收敛性能；赵凤等[9]提出一种多目标粒子群和人工蜂群混合优化的阈值图像分割算法，在雇佣蜂更新蜜源过程中引入PSO 算法中的全局最优解，改进搜索方程，使算法跳出局部最优解；杜振鑫等[10]提出了一种集成学习ABC 算法，挖掘种群中的有用信息来抑制早熟，使算法跳出局部最优解；郭佳等[11]提出一种基于马尔可夫（Markov）链的ABC 算法，根据Markov 链预测已知解空间的发展趋势，使改进算法在求解精度和收敛速度上高于基本ABC 算法；Huseyin[12]提出一种基于合格搜索策略的ABC 算法，使用四种不同的搜索方程提高算法的开发能力，实现全局和局部搜索之间的平衡；Gong 等[13]提出一种混合ABC 算法，设计有效的编码、解码、交叉和变异算子，并采用一种有效的局部搜索方法，提高了算法的收敛速度和开发能力；Zhao 等[14]提出了一种具有记忆功能的多种群ABC 算法，并将其应用到疏散管理中，在缩短时间的同时能有效地疏散多个场景中的密集人群；宋晓宇等[15]提出一种具有自适应搜索策略的混合ABC 算法，利用目标函数值和最优解的引导，提高算法的寻优能力；Anan[16]提出了一种基于图像边缘检测的ABC算法，利用ABC算法来寻找最优的边缘滤波器，在边缘检测过程中不断优化阈值。

ABC算法是一种简单、高效的智能优化方法，已成为解决全局和局部优化问题的潜在工具。然而，对于某些优化问题，目前还没有一种特定的算法能够达到最优解。同时，ABC 算法也有一些缺点，例如开发能力差、易陷入局部最优、收敛速度慢。针对这些问题，本文在基本ABC算法的基础上，提出一种极值个体引导的人工蜂群算法（extreme individual guided artificial bee colony algorithm，EABC）。该算法在雇佣蜂和跟随蜂阶段发挥全局极值和邻域极值个体的引导作用，改进了搜索方程。全局极值个体引导搜索有利于种群中优良个体的保留和发展，避免算法陷入局部极值，向着全局最优的方向进行，提高算法全局搜索能力；邻域极值个体引导搜索使算法更快收敛，提高局部搜索能力；采用小概率变异方法，提高算法的搜索效率，增加种群多样性；通过基于目标函数值的贪婪选择，提高了算法的优化性能，并通过仿真实验验证EABC算法的有效性。

1 基本人工蜂群算法

ABC 算法包含雇佣蜂、跟随蜂和侦察蜂三种蜜蜂，雇佣蜂和跟随蜂主要负责食物源的开采过程，各占蜂群总数的一半，且与食物源数目相等。对于函数优化问题，食物源的位置代表优化问题的一个可行解，蜜蜂所带的花蜜量代表函数的适应度值，求解函数最优值的过程就是蜜蜂寻找最大花蜜量的过程。D为搜索空间的维数，SN为食物源的数目，该算法模型如下：

雇佣蜂：每个雇佣蜂对应一个食物源，雇佣蜂在食物源附近采用式（1）进行邻域搜索，并根据食物源的花蜜量进行贪婪选择，生成一个候选解。

跟随蜂：每只跟随蜂按照式（2）、式（3）的轮盘赌概率选择一个雇佣蜂进行跟随，并在其附近通过式（1）进行邻域搜索，产生候选食物源：

式中，fi为函数值；fiti为第i个食物源的适应度值；pi为第i只跟随蜂的跟随概率。

侦察蜂：如果一个食物源连续经过limit次搜索之后仍然没有得到改善，则该处的雇佣蜂将成为侦察蜂，并按式（4）随机产生一个新的食物源。

2 极值个体引导的人工蜂群算法

2.1 雇佣蜂和跟随蜂搜索方式

ABC 算法中雇佣蜂和跟随蜂采用式（1）进行搜索，该搜索过程在一定意义上是个体空间到个体空间的随机映射，它的概率分布显然只与当前的位置状态有关，没有利用全局或局部最优个体对种群中其他个体的引导作用，因此在整个过程中收敛速度较慢。

K邻域极值个体lbest：雇佣蜂和跟随蜂种群为{1,2,…,i,i+1,i+2,…,i+K-1,…,SN}，第i个个体的K邻域为{i,i+1,i+2,…,i+K-1}，lbest为{i,i+1,i+2,…,i+K-1}中目标函数值最小的个体。

本文提出的EABC算法，在雇佣蜂和跟随蜂搜索阶段中引入了全局极值个体gbest和邻域极值个体lbest，发挥其引导作用，改进的搜索公式为：

式中，r为随机数，r∈(0,1)，gbestj为gbest的第j维分量，lbestj为lbest的第j维分量，K为常数，通过多次实验进行验证，当K=5 时，算法优化效果较好。

在式（5）中，等号右边第二部分为全局极值个体引导项，表示当前个体向全局极值个体靠拢；第三部分为邻域极值个体引导项，表示当前个体向K邻域极值个体靠拢；第四部分为当前个体位置与随机个体的差分项，表示在当前位置向量附近邻域进行搜索。

改进搜索方式中，gbest引导新的候选解向全局最优靠拢，增强算法的全局搜索能力；lbest引导蜜蜂个体进行局部搜索；随机数r在平衡全局搜索和局部搜索方面起着重要的作用。结合ABC 算法中雇佣蜂、跟随蜂局部搜索和侦查蜂全局搜索的转换机制，当r较大时，雇佣蜂和跟随蜂以gbest引导搜索为主，lbest引导搜索为辅，使算法不断向全局最优解靠拢，使算法跳出局部极值，避免早熟收敛，提高全局搜索能力；当r较小时，以lbest引导搜索为主，gbest引导搜索为辅，蜜蜂个体在局部范围内进行搜索，加快收敛速度，提高算法搜索精度和局部搜索能力。

2.2 小概率变异

EABC算法中，雇佣蜂和跟随蜂采用相应搜索公式更新解后，为克服算法陷入局部极值点并出现早熟收敛的现象，对蜜蜂个体的各维度按式（6）以较小的概率进行变异，在搜索范围内随机取值。

式中，φ3为随机数，φ3∈(0,1)，当φ3＜0.02 时，在搜索范围内随机取值，否则，保持不变。小概率变异算子增加了群体的多样性，有利于提高算法的全局搜索能力，使算法更容易跳出局部极值。

2.3 选择策略

在ABC 算法中，三种蜜蜂都采用基于适应度值的贪婪选择方法选择食物源，若候选食物源的适应值优于原来食物源的适应值，则将其取代。但是对于函数优化问题，当目标函数值大于0 且无限接近0时，对应的适应值不具有区分度。为解决此问题，本文提出的改进算法采用基于目标函数值的贪婪选择方法选择食物源[17]。

2.4 算法实现步骤

EABC算法的实现步骤如下：

步骤1计算每个个体的目标函数值，并找出全局最优个体；

步骤2雇佣蜂按式（5）、式（6）更新每个个体；

步骤3按式（2）、式（3）计算选择概率；

步骤4跟随蜂根据轮盘赌方式选择蜜源，并按式（5）、式（6）更新每个个体；

步骤5执行侦察蜂策略；

步骤6更新全局最优个体；

步骤7终止条件是否满足？若满足，停止迭代并输出全局最优解，否则转向步骤3。

EABC算法对应的伪代码如下所示：

算法1极值个体引导的人工蜂群算法（EABC）

输入参数并初始化：

2.5 算法收敛性分析

算法的收敛性是衡量算法优劣的一个重要指标，优化算法的好坏很大程度上取决于其收敛性能和收敛速度，因此，不同的改进策略具有不同的收敛效果。如宁爱平等[18]利用随机过程理论，并结合随机搜索算法的全局收敛准则，证明了ABC 算法满足随机搜索算法全局收敛的两个假设；火久元等[19]采用数形结合的方式，分析算法的收敛过程，证明了ABC算法的收敛优势及收敛概率的变化过程；Nasr等[20]基于ABC 算法变量与食物源更新方程通解之间的关系，证明了蜂群算法的收敛性；Bansal 等[21]利用冯·诺依曼稳定性和收敛性判据，证明了改进的ABC 算法依概率收敛。

综合上述文献，本文采用阶段性分析的方法将EABC 算法的运行过程分为全局搜索阶段和局部搜索阶段。全局搜索阶段，EABC算法的初始收敛概率较小，随着迭代次数的增加，收敛概率逐渐变大。因此，此阶段中算法的收敛速度较慢且需要进行多次迭代，从而收敛到全局最优。局部搜索阶段，EABC算法的转移速度加快，任意两点之间的区域长度以极快的速度减小，算法收敛概率变大，能较快收敛到全局最优。因此，此阶段算法的收敛速度快、精度高。此外，EABC 算法属于随机搜索算法的范畴，因此可以利用随机算法收敛准则来判定EABC 算法的收敛性。根据收敛准则[22]，EABC算法同时满足假设1 和假设2，因此，在经过一定次数的迭代后，算法依概率收敛。

综上所述，本文提出的EABC算法通过全局极值和邻域极值个体的引导，依概率收敛到全局最优。

3 仿真实验

3.1 实验设计

为了分析和比较EABC算法的优化性能，使用表1中的28个基准函数[23]进行仿真实验，这些函数具有单峰、多峰、可分和不可分等不同的性质。函数的这些属性在表1的C列中给出，M表示函数是多峰的，U表示函数是单峰的，S 表示函数是可分离的，N 表示不可分离函数的特性，D列表示各问题的维数。

表1 28个标准测试函数参数Table 1 Parameters of 28 standard test functions

表1 （续）

3.2 两种选择策略的性能比较

为了验证基于目标函数值的贪婪选择的有效性，选择表1中的部分函数f1、f3、f5、f8、f16、f17、f24、f26进行仿真实验，并与基于适应度值的贪婪选择方法进行比较，实验中参数设置为维度D=30，种群规模S=30，最大迭代次数T=5 000，实验独立运行次数runtime=30，最大限制搜索次数limit=600，实验结果采用30次的平均函数值。图1是基于适应度值和目标函数值的贪婪选择方法选择食物源的收敛曲线图。在每幅图中，纵坐标用函数平均最优值的对数表示，横坐标为迭代次数。由图1 可知，基于目标函数值的贪婪选择方法的优化效果更好。因此，在EABC算法中，利用目标函数值代替适应度值进行贪婪选择，能有效地提高算法的优化性能。

图1 两种贪婪选择策略收敛曲线Fig.1 Convergence curves of two greedy selection strategies

3.3 两种算法的性能比较

3.3.1 结果与分析

为了评价EABC 算法的性能，分别用ABC 算法和EABC算法以求解28个测试函数的最小值为例进行仿真实验，最终的测试结果采用独立运行30 次后的平均值进行统计。

实验中参数设置为：维度D=30，种群规模S=30，最大迭代次数T=5 000，实验独立运行次数runtime=30，最大限制搜索次数limit=600，两种算法的比较结果如表2所示。

由表2中两种算法的实验结果比较可以看出：对于平均最优值和标准差，EABC算法对f1、f2、f3、f4、f5、f7、f8、f16、f18、f19、f24、f26、f2813个函数的优化效果远远好于ABC 算法，对f9、f13、f14、f21、f22等5个函数的优化效果略优于ABC算法，其余10个函数中，EABC算法和ABC算法的优化效果相当；对于最差值和最优值，EABC算法对f6、f11、f13、f15、f20、f21、f22、f23、f25、f2710 个函数的结果与ABC 算法相当，其余18个函数中，EABC算法求得的结果均优于ABC算法；对于运行时间，EABC算法对f3、f6、f7、f8、f9、f11、f20、f21、f25、f2610 个函数的结果与ABC 算法相当，其余18个函数中，EABC算法的平均运行时间略小于ABC 算法，说明EABC 算法的时间复杂度与ABC相当。

此外，实验中使用的基准测试函数优化问题单峰、多峰、可分离性和不可分离性等不同性质[23]。结合表2仿真实验结果，对EABC算法处理不同类型数据集的能力进行分析：对于单峰函数，只有一个局部极小值且为函数全局极小值。因此，很容易找到全局最优值；对于多峰函数，具有一个以上局部极小值，且要求优化方法具有有效的全局和局部搜索能力。由于EABC 算法通过全局极值和邻域极值个体的引导，具有很好的全局和局部搜索能力，能够求得复杂多峰函数的全局最优值；对于可分离函数，可被重新表述为n个单变量函数的和。因此，能较快求得全局最优值；对于不可分离函数，函数的变量之间存在相互关系，当改变某一变量时其他变量将会受到影响[23]。因此，不可分离函数的最优值求解过程较可分离函数困难得多。

表2 两种算法的实验结果Table 2 Experimental results of two optimization algorithms

3.3.2 维度扩展性比较

ABC算法作为一种基于群体智能的全局优化算法，在优化过程中，测试函数维度的增加会使算法复杂度增加，优化性能下降。为了分析测试函数的维度对算法性能的影响，本文将测试函数的维度扩展到60、100维，其他参数不变，实验结果见表3和表4。

从表3 中60 维的测试实验结果分析得出：对于平均最优值和标准差，EABC 算法对f10、f11、f12、f15、f20、f21、f24、f258 个函数的优化效果与ABC 算法相当；其余20个函数中，EABC算法的优化效果均好于ABC 算法；对于平均运行时间，EABC 算法对f1、f3、f8、f9、f10、f276 个函数的平均运行时间与ABC 算法相当，其余22个函数中，EABC算法的平均运行时间略低于ABC 算法。从表4 中100 维的测试实验结果分析得出：对于平均最优值和标准差，EABC 算法对f10、f11、f12、f19、f20、f25、f277个函数的优化效果与ABC算法相当；其余21 个函数中，EABC 算法的优化效果均好于ABC算法；对于平均运行时间，EABC算法对f1、f3、f7、f8、f9、f10、f14、f15、f21、f24、f25、f2812个函数的平均运行时间与ABC算法相当，其余16个函数，EABC 算法的平均运行时间略低于ABC 算法。因此，在同一维度水平下，EABC 算法的优化效果更好，随着目标函数维度的增加，EABC 算法仍能保持较好的优化性能。

表3 ABC和EABC的实验结果（D=60）Table 3 Experimental results of ABC and EABC(D=60)

表4 ABC和EABC的实验结果（D=100）Table 4 Experimental results of ABC and EABC(D=100)

3.4 EABC与其他智能优化算法的比较

3.4.1 优化性能比较

为考察EABC 算法的优化性能，将其与ABC[5]、ABCVSS[23]、GABC[24]、ABCBest1[25]、MSSABC[26]和MABC[27]等较新的ABC改进算法进行比较。几种算法中，种群大小N=30，维度D=30，最大迭代次数T=5 000，算法独立运行次数runtime=30，最大限制搜索次数limit=600，实验结果见表5和图2，ABCVSS算法的实验结果直接取自文献[23]，MABC算法的实验结果直接取自文献[27]。

由表5 可以看出，对于f1、f2、f3、f5、f8、f9、f13、f15、f16、f17、f21、f22、f24、f26、f2715 个函数，EABC 算法的优化效果更好；对于f7、f11、f12、f254个函数，几种算法的优化效果一致，都达到了最优值；其余9 个函数中，EABC 算法与其他几种算法的优化效果相当。由此说明EABC算法具有更高的优化精度，能有效克服ABC 算法收敛速度慢和陷入局部最优的缺点，具有更高的优化性能。

图2是选取表5中ABC、GABC、ABCBest1、MSSABC、EABC这五种算法对不同属性的部分函数运行30 次后得到的收敛曲线图。每幅图中，纵坐标用函数平均最优值的对数表示，横坐标为迭代次数。

从图2 中可以看出：在单峰可分离函数中，对于f1、f3、f8，EABC算法前期的收敛速度略低于MSSABC算法，但当迭代次数达到3 700左右时，EABC算法优于其他算法并达到理论最优值；对于f9，几种算法收敛趋势一致，但EABC 算法收敛速度更快，优化精度更高。在单峰不可分离函数中，对于f2、f5，当迭代次数小于3 700 时，EABC 算法的收敛速度略低于MSSABC算法，当迭代次数大于3 700时，EABC算法的收敛速度明显加快，并且在迭代次数约4 500时开始收敛直到趋向全局最优解。在多峰不可分离函数中，对于f16、f17，EABC 与MSSABC 算法收敛趋势一致，EABC 算法前期的收敛速度略低于MSSABC 算法，当迭代次数达到1 500 后，EABC 算法收敛速度快，优化精度高；对于f26，相比其他5 种算法，EABC算法前期的收敛速度略低于MSSABC 和GABC 算法，但当迭代次数达到3 500后，EABC算法的优化精度高于其他算法。在多峰可分离函数中，对于f18，EABC与ABC算法收敛趋势一致，且EABC算法收敛速度大于其他5种算法，优化效果更好。