APP下载

基于差分变异算子的改进人工蜂群算法

2020-04-09张怡森

无线互联科技 2020年3期

张怡森

摘   要:文章针对传统人工蜂群算法收敛速度慢、精度不高的问题,基于差分进化算法中的变异算子,对人工蜂群算法搜索方程进行改进,在种群更新过程中引入当前种群最优个体信息,以提升算法的收敛速度和局部优化能力。

关键词:人工蜂群算法;搜索方程;变异算子

人工蜂群算法(Artificial Bee Colony,ABC)是由Karaboga基于蜂群搜索蜜源行为提出的一种群体智能优化算法,该算法在搜索过程中同时兼顾局部搜索和全局搜索,控制参数少、易于实现、全局收敛性能好、具有良好的鲁棒性,并且其优化性能优于其他一些传统智能优化算法[1],如遗传算法、粒子群算法、差分进化算法等,特别是在非线性函数优化求解方面具有良好的性能。关于ABC算法的研究主要是对其选择机制和搜索方程进行改进,以提升算法性能。丁海军等[2]将boltzmann选择策略引入ABC算法,对其收敛速度和种群多样性进行平衡;毕晓君等[3]采用自由搜索算法中的信息素模型代替轮盘赌选择策略,提高了算法的全局搜索能力。在上述研究中由于没有对算法搜索方程进行改进,导致在处理复杂优化问题时收敛速度和寻优精度较低。因此,本文在对传统ABC算法分析基础上,考虑当前种群最优个体对种群更新的影响,对算法搜索方程进行改进,在数值实验中选用标准测试函数对算法性能进行验证。

1    人工蜂群算法

在ABC算法模型中,主要包含两部分:蜜源和人工蜂群。其中,蜜源位置代表优化问题的可行解,蜜源的花蜜量代表对应解的质量或适应度值。根据蜜蜂在搜索过程中的职能不同可将人工蜂群分为3类:采蜜蜂、观察蜂和侦查蜂。采蜜蜂和观察蜂数量各占蜂群一半,且等于蜜源数量,当采蜜蜂放弃对应蜜源后即成为侦查蜂。在ABC算法中,3类蜜蜂按以下顺序进行搜索:

(1)采蜜蜂对蜜源进行开采,评估花蜜量。在该过程中,采蜜蜂在蜜源附近搜索,并采用贪婪选择机制选择新蜜源位置以发现局部最优解。

(2)观察蜂对蜜源进行开采。根据采蜜蜂传递的蜜源信息,按照与花蜜量正相关的概率选择蜜源位置进行开采,同样地,采用贪婪选择机制选择新蜜源位置以发现局部最优解。

(3)确定侦查蜂。如果蜜源在经过一定次数后仍没有更新,说明该位置陷入局部最优。此时,采蜜蜂放弃该蜜源位置,相应的采蜜蜂变为侦查蜂。侦查蜂随机搜索新蜜源代替被放弃的蜜源。

在初始化蜜源位置基础上,ABC算法通过不断重复以上3种蜜蜂的活动搜索全局最优解。在上述ABC算法中,存在3个控制参数,描述如下。

(1)SN:种群数量。即种群中采蜜蜂和观察蜂的数量,且与蜜源数量相等。

(2)Limit:蜜源为更新次数。当蜜源循环次数超过Limit后仍没有改进,该蜜源位置被放弃,对应的采蜜蜂变为侦查蜂。

(3)Maxcycle:最大迭代次数。算法迭代次数大于Maxcycle时结束运行并输出最优个体。

在ABC算法优化过程中,首先随机产生SN个初始解,假设优化问题的每个解Xi,i=1,2,…SN,D为向量,D是优化变量个数。在此基础上,采蜜蜂和观察蜂通过以下搜索方程产生新蜜源(即新的可行解):

2    改进人工蜂群算法

基于上述分析可知,ABC算法的优化性能主要受搜索方程影响。在搜索方程式(1)中,Xk为随机选择的个体,新的可行解是通过当前个体向另一个随机个体的偏移得到。这种方法产生的可行解质量不能保证,对当前解的更新效率较低,而且在搜索过程中没有充分利用种群最优个体信息。因此,ABC算法局部优化能力较差,导致算法的收敛速度较慢。

针对上述问题,本研究借鉴差分进化算法(Differential Evolution, DE)的变异算子对ABC算法搜索方程进行改进,以提高算法收敛速度。DE算法的变异算子充分利用了种群中最优个体的信息,可以使种群快速向最优个体聚拢,具有较强的局部优化能力。基于差分变异算子,新搜索方程为:

由上式可以看出,新的可行解只在最优个体附近产生,因此可以有效提高算法收敛速度。但采用该搜索方程也会在一定程度上降低种群的多样性,可能使得算法过早收敛,降低全局搜索能力。因此,为平衡算法的全局搜索和局部搜索能力,在采蜜蜂阶段采用式(1)产生新的可行解,尽可能扩展搜索区域,保证种群的多样性;由于观察蜂可以综合所有采蜜蜂得到的信息,进而判断出当前种群中最优个体位置,所以在观察蜂阶段,采用式(2)产生新的可行解,增强种群更新的趋势性。

3    数值实验

部分学者已对ABC算法与遗传算法、蚁群算法、粒子群算法等智能优化算法进行了较为详细的比较分析,因此这里只将本文提出的改进ABC算法(MABC)和原始ABC算法进行比较,验证MABC算法的性能和优越性。

为验证本文所提MABC算法的性能,选取3个不同类型的优化算法标准测试函数Sphere、Griewank和Rosebrock进行数值实验。表1给出了选用函数的函数名、表达式及搜索空间。Sphere为单峰高维函数,理论最优值为f(0,…,0)=0,设置维数为100,搜索空间为[-100,100]D;Griewank为多峰多极值的高维函数,理论最优值为f(0,…,0)=0,设置维数为100,搜索空间为[-600,600]D;Rosebrock为多峰少极值的低维函数,理论最优值为f(1,…,1)=0,设置维数为5,搜索空间为[-100,100]D。

ABC算法和MABC算法控制参数设置相同,如下所示:SN=50,Limit=50,Maxcycle=1 000。为测试算法性能,在以上参数设置下对每个测试函数独立运行算法30次,计算优化结果的平均值和标准差。在此基础上比较算法的鲁棒性和寻优精度,并通过优化过程对算法收敛速度进行分析。不同函数优化结果的平均值和方差如表1所示。

由表1可以看出,针对实验中的3个测试函数,本文提出的MABC算法所得优化结果平均值和标准差均优于原始ABC算法。特别是在多峰函数Griewank和Rosebrock中,ABC算法优化结果精度较差,难以得到满意解。因此,本文提出的MABC算法能够有效提高寻优精度及结果的鲁棒性,具有良好的全局搜索能力。

为直观对比两种算法的收敛性能,下面对以上3个测试函数在ABC和MABC算法下的优化过程进行分析。对Sphere函数来说,MABC算法在迭代600次后趨于收敛,ABC算法在迭代800次后趋于收敛;对Griewank函数来说,MABC算法在迭代700次后趋于收敛,ABC算法在迭代900次后趋于收敛;而对于Rosebrock函数,MABC算法在迭代500次后趋于收敛,ABC算法在迭代700次后趋于收敛;可以看出,MABC算法的收敛速度明显更快。由此可得,与传统ABC算法相比,MABC算法能够有效提高种群更新效率和收敛速度,具有良好的函数优化性能。

4    结语

本文在ABC算法机理分析基础上,结合DE算法的变异算子,将每代种群中最优个体信息引入搜索方程,在一定程度上提高了种群更新效率,平衡了算法全局优化和局部优化能力。数值实验结果表明,本文所提的改进方法能够有效提高ABC算法收敛速度和优化结果精度。

[参考文献]

[1]KARABOGA D,AKAY B.A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation,2009(1):108-132.

[2]丁海军,冯庆娴.基于boltzmann选择策略的人工蜂群算法[J].计算机工程与应用,2009(31):53-55.

[3]毕晓君,王艳娇.改进人工蜂群算法[J].哈尔滨工程大学学报,2012(1):117-123.