基于欧氏距离与多种搜索策略的人工蜂群算法*

佘合一， 吴锡生

(江南大学 物联网工程学院，江苏 无锡 214122)

0 引 言

人工蜂群(artificial bee colony,ABC)算法[1]因结构简单、控制参数较少、鲁棒性强等特点，越来越多地被各界学者所关注与研究。但其在优化过程中，存在收敛精度低、收敛速度慢、易于早熟的缺点，其主要原因是ABC算法探索能力强而开发能力较弱[2]。

文献[3]将混沌序列引入蜂群算法中，并用禁忌表记录已搜索的局部最优点来达到控制性的搜索；文献[4]中针对标准ABC算法中新个体的产生,运用了一种互学习策略，让新个体的产生更倾向于在适应度更优的父代个体周围；文献[5]采用一种有方向的搜索策略，使搜索沿着最优个体的方向进行，减少了搜索过程中的盲目性。上述改进算法的性能都有了一定程度改善, 但仍缺少对算法的探索能力与开发能力的平衡。

为此，本文提出了一种基于欧氏距离与多种搜索策略的改进人工蜂群算法(improved ABC,IABC)。在IABC算法中，由三种具有不同特点的搜索策略组成策略池，用来实现更新的邻居由指定半径的欧氏距离决定。因每个搜索策略的特性不同，因而最大程度的平衡了算法的探索能力与开发能力。通过对标准测试函数的仿真实验,并与标准ABC算法及相关改进算法进行比较, 表明了本文所提出的IABC算法的有效性，较好地提高了算法的收敛速度和收敛精度。

1 人工蜂群算法搜索策略

对于一个D维空间的搜索问题，种群规模为2×SN,蜂群觅食过程中的蜜源相当于D维空间域中的一个可行解，第i个蜜源位置xi={xi,1,xi,2,…,xi,D}，每一个蜜源与雇佣蜂和跟随蜂一一对应(雇佣蜂个数=跟随蜂个数=SN)，蜜源的优异程度则对应其解的可行度，即适应度。

ABC算法最初根据问题域按式(1)随机产生一个初始种群

xij=xmin,j+rand(0,1)(xmax,j-xmin,j)

(1)

式中i=1,2,…,SN，j=1,2,…,D，xmin,j和xmax,j分别为变量xij的下界和上界。

初始化之后，雇佣蜂根据蜜源进行开采，在蜜源的周围由式(2)进行随机搜索

vij=xij+φij(xij-xkj)

(2)

式中k为随机产生的整数，k=1,2,…,SN且k≠i,j=1,2,…,D；φij∈[-1,1]为一个随机数。

2 本文IABC算法

2.1 3种搜索策略

不同的搜索策略需具有不同的搜索特性，满足不同特性的优化问题，使搜索的不同阶段都能有合适的搜索策略。在文献[2]提出了全局最优指导的蜂群算法(global ABC,GABC)，利用最优蜜源来指导候选蜜源的搜索。GABC的搜索策略公式如下

vij=xij+φij(xij-xkj)+ψij(gbestj-xij)

(3)

式中gbestj为全局最优解的第j维值，k=1,2,…,SN,且k≠i,j=1,2,…,D，φij∈[-1,1]，ψij∈[0,C]，当C=1.5时效果最好。

文献[6]提出了一种改进的ABC算法(modified ABC,MABC), MABC的搜索策略公式为

vij=xb,j+φij(xr1,j-xr2,j)

(4)

式中xb,j为全局最优解的第j维值,r1=1,2,…,SN，r2=1,2,…,SN且r1≠r2≠i，j=1,2,…,D。

GABC算法参考文献[7]进一步对式(4)修改为

vij=xb,j+φij(xb,j-xkj)

(5)

由式(3)、式(5)以及式(2)组成了搜索策略池。在跟随蜂开发蜜源阶段，利用策略池中3种搜索策略分别产生3个候选蜜源，由产生的候选蜜源计算对应的适应度，根据3个候选解的适应度进行择优选取。由策略池中3种不同特性的搜索策略可以在算法搜索阶段表现出不同的搜索特点，使算法在不同搜索阶段都有适合的搜索策略。

2.2 欧氏距离在搜索策略中的应用

在式(3)、式(5)中忽略了解结构相似性的联系，破坏解的多样性。考虑到解结构之间的相似性，可以采用欧氏距离来划分解的邻域[8]，邻居的解结构存在较高的相似度。

如二个蜜源xi与xm之间的欧氏距离用d(i,m)表示，那么对于xi与所有蜜源的平均距离可表示如下

(6)

如果d(i,m)≤r×mdi，则xm是xi的一个邻居，参数r为邻域半径。

蜜源xi获得其全部邻居蜜源后，根据每个邻居蜜源适应度选出邻居内最优蜜源xb，其计算公式如下

(7)

2.3 IABC算法流程

1)设置算法参数，最大循环次数FES，控制参数limit，随机产生初始解集,i=1,2,…,SN，j=1,2,…,D，计算解的适应度。

2)雇佣蜂按式(2)搜索候选蜜源vi，计算其适应度，并进行贪婪选择,若vi适应度仍小于原先蜜源，则limit+1。

3)跟随蜂根据轮盘赌方式对蜜源进行概率性选择，对选择的蜜源计算与其他蜜源欧氏距离，根据式(6)计算出平均距离mdi，确定其邻居蜜源。

5)分别用式(2)与步骤(4)更新的式 (3)、式(5)，产生3个候选蜜源，计算3个蜜源的适应度，并根据3个候选蜜源的适应度进行贪婪选择，生成vi。

6)对生成的vi与原先蜜源进行贪婪选择，若vi的适应度仍小于原先蜜源，则limit+3。

7)判断是否有需要被放弃的蜜源,若有, 则重新产生新的蜜源。

8)如果满足终止条件, 则算法结束, 输出最终结果; 否则,转步骤(2)。

3 实验与结果分析

3.1 测试函数选择

本文选取了6个典型的测试函数进行测试。其中，f1,f2,f3(Sphere,Rosenbrock,Schwefel)为单峰函数，在定义域范围内只有1个极值，用于测试算法的收敛精度与收敛速度；f4,f5,f6(Rastrigin,Griewank,Ackley)为多峰函数，在定义域范围内存在多个极值，用于测试算法避免早熟能力与全局寻优能力。其中,f2全局极小值位于一条平滑而狭长的抛物线形状的山谷底部,该函数中变量之间具有很强的关联性，不易找到其全局极小值，通常用该函数来评价优化算法的性能。

3.2 结果分析

在对本文算法(IABC),ABC算法,文献[5] (directed ABC,dABC)算法和文献[9](quick ABC,qABC)算法进行对比实验时,实验参数设置为：种群规模为50(SN=25)，函数维度D=30，limit=300，最大循环次数FES=1 000，邻域半径r=1.5。将4种算法对每个测试函数独立运行30次，测试结果如表1所示。

表1 4种算法性能比较

从表1可以看出:在所有的测试函数中标准的ABC算法的平均值最高，除了函数f2的方差要低于dABC算法与qABC算法，其他函数的方差均高于其他3个算法，说明标准ABC算法解的精度与稳定性较差;dABC算法与qABC算法相对于标准的ABC算法，无论在单峰函数还是在多峰函数中，最优值、最差值与平均值3个方面的实验数据均明显好于标准ABC算法，其中，qABC算法在函数f4中得到了函数的理论最优值，只有在函数f2中的方差要比标准ABC算法大,可知dABC算法与qABC算法解的精度较好。在稳定性方面，总体上较标准ABC算法要好。

本文IABC算法在6个函数中，其性能都优势明显。为了更直观地显示本文IABC算法的收敛速度与收敛精度，图1～图6为4种算法对测试函数的收敛曲线。结合表1与图1～图6，可以发现，本文算法在每一个测试函数中，每项数据都明显优于另外3种算法。在所有测试函数中，本文IABC算法的最优值、最差值与平均值与方差都优于其他算法。对于解的精度：在测试函数f2中，标准ABC算法、dABC算法与qABC算法很容易陷入局部最优解，很容易早熟收敛，而本文IABC算法的解明显好于另外3个算法的解，并且仍然有向最优解进化趋势。根据图4和图5可以看到本文IABC算法对测试函数f4与f5分别迭代500多次与600多次便找到了理论最优值。对于收敛速度：从图1～图6可以直观的看出，标准ABC算法收敛速度缓慢，dABC算法与qABC算法相对标准ABC来说，收敛速度得到改善，但改善的幅度仍然不是很大，而本文IABC算法的收敛速度相比较另外3个算法的收敛速度都有了很大改善。

图1 Sphere函数进化曲线

图2 Rosenbrock函数进化曲线

图3 Schwefel函数进化曲线

图4 Rastrigin函数进化曲线

图5 Griewank函数进化曲线

本文IABC算法与qABC算法都引入了欧氏距离，来确定具有相似解结构的最优邻居，以避免利用全局最优解而忽略其他较优解的开发能力。但本文IABC算法在欧氏距离的基础上，用3种不同的搜索策略，来满足不同搜索阶段的特性，使搜索过程中每个阶段都有适合的搜索策略，以此均衡算法的探索能力与开发能力，增加解的多样性，使算法更容易找出最优值，从而进一步提高了收敛速度与精度。

图6 Ackley函数进化曲线

4 结 论

提出了一种改进的基于欧氏距离与多种搜索策略的人工蜂群算法(IABC)。仿真结果表明：本文算法在求解函数最小值优化问题时,能够显著提高收敛速度，并能有效地避免算法陷入局部最优，提升解的收敛精度。该算法可以很好地解决复杂优化问题，可以将本文IABC算法应用到图像处理中。如何利用IABC算法进行图像分割中最优阈值的选取是下一步的研究内容。