高文欣,刘 升,肖子雅,于建芳
(上海工程技术大学 管理学院,上海 201620)
蝴蝶优化算法(butterfly optimization algorithm,BOA)[1]模拟自然界中的蝴蝶采食花蜜的行为。BOA算法调节参数少,原理简单,易于实现。BOA算法已经成功解决很多问题如:焊接条、压力器容器、齿轮、输气压缩机和悬臂梁设计等工程优化问题[2],特征选择[3],机器学习等。
BOA算法与常见的元启发式算法类似,也存在易陷入局部最优值(多模态函数的鞍点位置),迭代后期的收敛速度变缓慢,寻优精度低等元启发式算法常见的缺陷。许多学者提出了改进策略。参考文献[4]将自适应学习机制引入BOA算法中平衡了全局搜索和局部开采的权重,但是增加了时间复杂度;文献[5]将莱维飞行策略引入全局和局部位置更新处,但改进后移动策略仍较为单一使群体多样性比较低,并未改善BOA算法易陷入鞍点位置的问题;文献[6]提出了一种基于动态感觉模态变化的蝴蝶优化算法提升了算法的局部开采和全局搜索能力,该策略针对感觉模态参数进行优化,没有从根本上优化蝴蝶个体位置更新方式,寻优能力差,并未显著提高BOA算法的收敛性能。
在BOA算法中,全局位置更新是通过向散发香味最浓的蝴蝶方向飞行,局部位置更新则是通过蝴蝶个体随机游走,即位置更新具有全局探索能力强而局部开采能力弱的缺陷。针对以上不足,本文提出了改进的个体位置更新方式,受鲸鱼优化算法(WOA)[7]的启发将收缩包围机制中的收敛因子a引入全局位置更新处以协调算法的探索和开发能力,提高收敛精度;将黄金正弦算法(GSA)[8]作为一种局部算子融入BOA算法中促进信息在种群内部快速传播加快个体间信息交流,弥补迭代后期算法的收敛速度慢,种群多样性下降等问题,加快算法跳出局部最优。
蝴蝶优化算法是通过模拟蝴蝶进行觅食(花蜜)和繁衍行为而衍生出的一种仿生智能算法,其具体的定义可以参考文献[9]中的论述。
针对蝴蝶的行为,我们提出如下假设:
(1)每只蝴蝶个体都能散发出香味,使蝴蝶个体在接收到来自空气中的香味时能够相互吸引。
(2)所有的蝴蝶个体都会随机或向发出最多香味的最优蝴蝶移动[10]。
(3)蝴蝶个体产生的刺激强度这一参数受目标函数的影响或决定。
(4)蝴蝶搜索的局部搜索更新和全局位置开采更新使用转换概率p进行控制,受到物理的因素以及雨、风、雷电等各种其它自然因素,局部搜索和全局位置更新中的参数p具有重要意义。
蝴蝶个体在觅食求偶过程中产生的香味浓度的公式如下
fi=cIa
(1)
fi是第i只蝴蝶个体感知香味的强度,c是一个蝴蝶个体感官模态参数,I是受到其它蝴蝶散发的香味的刺激强度参数,a是取决于感官模态的幂指数参数,它的大小取决于香味的吸收程度。
在BOA算法的全局探索阶段,每只蝴蝶朝着最优的蝴蝶/解g*移动。用式(2)表示
(2)
在局部开采过程中,每只蝴蝶的位置更新公式如式(3)
(3)
为进一步增强BOA算法的探索能力和提高收敛精度,受到鲸鱼优化算法的启发,将鲸鱼优化算法中非线性收敛因子a引入基本蝴蝶优化算法的全局位置更新处,希望迭代前期a值较大以增强全局勘探能力且递减速度较快,而迭代后期a值收敛到较小值且递减速度变缓慢,以实现前期快速收敛,提高算法后期的收敛精度。a随着迭代次数的增加由2减小到0。公式如下
a=2-t/tmax
(4)
式中:t是当前迭代次数,tmax是最大迭代次数。
改进后全局位置更新公式如下
(5)
黄金正弦算法(golden sine algorithm,Golden-SA)[8]是Tanyildizi提出的新型元启发式算法。根据正弦函数定义中与单位圆的关系,遍历单位圆上所有正弦值的行为与优化算法中搜索代理在搜索空间中进行寻优的原理是一致的,受此启发产生了黄金正弦算法。在该算法中,创建随机个体的数量与每个具有均匀分布的搜索代理的数量相同。与其它元启发式方法相比,Gold-SA具有更少的依赖于算法的参数和运算符,Gold-SA算法通过使当前解空间更接近目标值的方式来搜索以在每次迭代中得到更好的搜索空间,搜索空间被黄金比例系数缩小以便获得更小的解空间而不是整个解空间,从而有效提升寻优速度。黄金正弦算法的具体定义及推导过程请参考文献[8,11,12]。
(6)
本文将黄金正弦算法作为局部算子融入基本BOA中,在迭代后期对整个BOA算法进行黄金正弦优化,能够弥补算法在迭代后期的收敛速度慢,收敛精度不高的缺陷,基本的BOA算法在局部搜索阶段采用随机游走的方式,搜索空间比较广泛;然而元启发式算法的主要目标是探索被认为是最佳搜索空间的区域,并确保尽可能完整地扫描这些区域,搜索空间的广泛性是解决问题的主要问题。在解决问题时缩小搜索空间的效果会显著影响寻优效果,而在Gold-SA算法中的参数r1和r2能够有效控制位置更新距离和方向,逐步缩小搜索空间,指引蝴蝶个体迅速向最优个体靠近,加快种群中信息交流,降低算法陷入局部最优值的可能性,从而提高算法的收敛速度和寻优精度。本文提出的融合非线性收敛因子和黄金正弦指引机制的蝴蝶优化算法(AGSABOA)的具体步骤如下。
步骤1 初始化种群个数及初始化主要参数设置;
步骤2 根据香味浓度公式计算每只蝴蝶个体的香味浓度,得到每个个体的初始的适应度值,并且求出当前算法的最优解;
步骤3 若动态转换概率p>rand,此时根据式(5)进行全局开采的更新;
步骤4 如果概率p
步骤5 对步骤4生成的蝴蝶个体进行黄金正弦优化,即根据式(6)进行寻优位置更新;
步骤6 计算步骤4和步骤5目标函数的适应度值,若得到的函数值优于前一代的值,则进行更新;
步骤7 重复上述步骤2~步骤6,当迭代次数达到给定值,则停止更新,将最优值和最优解进行输出。
AGSABOA的算法流程如图1所示。
图1 AGSABOA算法的流程
本文的仿真环境为:操作系统是Windows10,CPU为Intel(R) Core(TM) i5-10210U,主频率2.11 GHz,内存为16 GB,仿真软件为Matlab2018b[9]。
本文选取粒子群算法(SSA)[13]、鲸鱼优化算法(WOA)、基本蝴蝶优化算法(BOA)、融合收敛因子和黄金正弦指引机制的蝴蝶优化算法AGSABOA进行对比实验,由此验证改进策略的有效性。另外本文还进行了单一策略改进的黄金正弦指引机制的蝴蝶算法(GSABOA)与双策略改进的AGSABOA进行对比实验,为了验证混合策略改进的寻优效果更佳。最后,选取文献[4]、文献[6]中的几组数据与本文的实验结果进行对比,验证本文针对基本BOA算法的改进方法更优秀。为保证实验结果的有效性和公平性,本文将所有算法的初始化种群数均设置为30,最大迭代次数设置为500,所有算法的公有参数保持一致。BOA、GSABOA、AGSABOA的感官形态c设置为0.01,幂指数a在迭代过程从0.1迭代到0.3,切换概率p=0.8。
为验证改进算法的有效性,本文选取9个基准测试函数进行实验。表1给出本文选取测试函数的基本信息。
表1 测试函数
表2给出SSA、WOA、BOA、GSABOA、AGSABOA在每个测试函数上独立运行30次得到的结果。LABOA、IBOA的实验结果是参考其它文献所得的结果。
SSA算法具有收敛速度快,易于实现的特点,WOA算法除了具有较强收敛速度之外,其较SSA算法来说,具有较强的局部搜索能力和较高的收敛精度,所选对比算法均有较强的代表性。从表2实验结果可以明显看出,AGSABOA的寻优结果是明显优于所选对比算法的。表2给出了几个算法的最优精度值、平均精度值、精度标准差,其中最优精度值可以展示算法求解的质量,平均精度值能够反应在固定迭代次数的情况下算法能够收敛的精度,可以反应算法的收敛速度;而精度的标准差能够反应算法的鲁棒性。从表2中的实验结果可以看出函数f1、f3、f4、f5、f7、f9能够直接搜索到理论最优值,说明改进后的AGSABOA算法具有较好的寻优性能。函数f2是一种连续的、平滑的多峰函数,在求解过程中比较容易陷入局部最优值,本文的改进算法AGSABOA的收敛精度能够达到e-168,比基本BOA算法在收敛精度上高出159个数量级的精度,f6是一种复杂的爬山形函数,函数在狭长的全局极值点周围拥有很多的局部极值,在算法的迭代过程中很难跳出局部最优,改进后的AGSABOA比基本的蝴蝶优化算法在寻优精度上面提高了9个单位,该函数主要用以测试算法的收敛速度,从标准差上看,AGSABOA的波动较小,稳定性更好。f8具有很强烈的震荡性,有非常多的局部最优值,因此在算法迭代过程中很难求得最优值,本文的改进策略在求解精度上面比基本的BOA算法高出155个精度单位,说明本文的改进策略能够提高BOA算法寻优成功的概率。
表2 测试函数结果
表2(续)
另外,采用双策略改进基本的BOA算法,在表2中,本文还给出采用单一的黄金正弦算法进行改进的蝴蝶优化算法GSABOA进行的对比实验,从实验结果可以看出,在函数f5、f7、f9上GSABOA和AGSABOA都能较快收敛到全局最优值,对于函数f1,GSABOA不能收敛到最优值,但是比基本的BOA算法在平均收敛精度上面高出100个数量级;在函数f2上也提高50个数量级;在函数f3、f4高出近200个数量级;从标准差上面看,AGSABOA的精度要小于GSABOA说明双策略改进算法的鲁棒性和收敛精度更好。双策略改进的AGSABOA算法是要优于GSABOA算法的。在全局位置更新处引入收敛因子,能够提高算法的收敛精度;GSABOA的结果也是明显优于对比算法SSA、WOA、BOA,表明本文采用的黄金正弦指引机制能够促进种群个体之间的信息交流,避免算法陷入局部最优值,能够有效减少BOA算法存在的部分无效迭代,提高了算法的寻优速度。
在表2中,本文算法还与文献[4]中的LABOA、文献[6]中的IBOA中几组测试函数的实验结果进行对比,实验结果均出自参考文献之中,因为本文选取测试的函数与文献[4]和文献[6]不完全相同,所以参考文献中未涉及的测试函数,在本文表2的对比结果中未列出。从实验结果可以看出,本文的AGSABOA算法在部分测试函数上面的寻优性能是要优于LABOA和IBOA的。根据无免费午餐定理,没有任何一种算法或者改进策略能够达到最优,但是可以不断探索更优的寻优策略,因此AGSABOA算法存在的误差是可以接受的。
为了进一步验证本文改进算法的有效性,本文将给出部分测试函数的收敛曲线,如图2所示。
从图2收敛迭代曲线可以直观看出改进的AGSABOA对陷入局部最优值的性能是要优于SSA、WOA和BOA算法的。函数f3、f5、f9的收敛迭代曲线如图2(b)、图2(c)和图2(f)所示能够快速收敛到最优值,其曲线上存在多个拐点,表明改进策略能够促使算法较快的跳出局部最优值;函数f1和f7的收敛迭代曲线如图2(a)和图2(e)所示在300代左右开始迅速下降,并且随着迭代次数的增加持续下降,未出现停滞现象,表明改进算法能够弥补基本的蝴蝶优化算法在迭代后期收敛速度慢的缺陷。函数f6收敛迭代曲线如图2(d)所示,表明AGSABOA算法能够快速收敛到8.88E-16这一精度,验证本文改进策略的优化效果良好。
图2 测试函数的收敛迭代曲线
本文提出了一种融合收敛因子和黄金正弦指引机制的蝴蝶优化算法,受到鲸鱼优化算法的启发,将收敛因子融入基本BOA算法的全局位置更新处之中,能够有效地提升算法的收敛精度,将黄金正弦算法作为一种局部算子融入基本的蝴蝶优化算法之中,能够有效地加快算法跳出局部最优,减小BOA算法出现早熟的可能性。下一步的研究内容是将AGSABOA应用于约束优化问题、多目标优化和实际工程问题中,提高蝴蝶优化算法在实际问题中的应用,解决更多的NP-hard问题。