融合正弦余弦算法的蝴蝶优化算法*

郑洪清,冯文健,周永权

(1.广西外国语学院信息工程学院，广西南宁 530222；2.柳州铁道职业技术学院，广西柳州 545616；3.广西民族大学人工智能学院，广西南宁 530006)

0 引言

由于群智能算法无需先验知识，无需分析数据内部规律和内在关联，只需对数据本身进行学习，自组织、自适应地完成优化问题的求解，近年来大批群智能算法被相继提出，如布谷鸟搜索算法(Cuckoo Search Algorithm,CS)[1]、樽海鞘群算法(Salp Swarm Algorithm,SSA)[2]、狼群算法(Grey Wolf Optimizer,GWO)[3]、正弦余弦算法(Sine Cosine Algorithm,SCA)[4]、鲸鱼优化算法(Whale Optimization Algorithm)[5]、花朵授粉算法(Flower Pollenation Algorithm,FPA)[6]等。这些群智能算法基本上是模拟生物的群体行为，按照某种合作方式一起求解优化问题，并在工程优化、图像处理、特征选择和机器学习等领域得到广泛应用。蝴蝶优化算法(Butterfly Optimization Algorithm,BOA)[7]是模拟自然界的蝴蝶觅食或求偶行为而衍生出的一种仿生群智能算法，已成功解决图像分割[8]、经济负荷调度[9]等问题。但基本BOA也存在收敛速度慢、计算精度差和易陷入局部最优等缺陷，许多学者提出不同改进策略。如高文欣等[10]首先引入limit阈值来限定BOA陷入局部最优次数，然后结合单纯形法和正弦余弦算法提升算法性能，但同时也增加了算法时间复杂度且其函数4求解精度较低。王依柔等[11]首先在自身认知部分引入自适应惯性权重，其次在全局最优位置引入扰动策略，在花蜜位置引入疯狂因子来平衡算法的局部与全局搜索能力，提出无限折叠迭代混沌映射的蝴蝶优化算法(SIBOA)，但该优化后的算法其精度还有待于进一步提升。宁杰琼等[12]首先利用Circle映射初始化种群，然后在局部搜索阶段利用动态切换概率，控制改进正弦余弦算法与蝴蝶优化算法的转换，并在全局和局部位置引入自适应权重系数和逐维变异策略，从而改进算法的性能，使求解的精度较高。但该算法的测试函数较少且回避了最难求解的Rosenbrock函数测试。高文欣等[13]在全局位置引入柯西分布函数，在局部位置引入自适应权重因子，并引入动态切换概率来改进算法性能，但函数Apline未达到理论最优。高文欣等[14]引入收敛因子和黄金正弦指引机制来提升算法效果，但测试函数较少，精度还有待于进一步提升。谢聪等[15]融入差分进化策略和精英策略改进算法，但算法的串联操作相应地增加了算法的时间开销。

虽然上述算法在一定程度上提高了算法性能，但仍有提升空间。本文提出一种融合正弦余弦算法的蝴蝶优化算法(Sine Cosine Algorithm and Butterfly Optimization Algorithm，SCABOA)，在BOA基础之上从以下4个方面进行改进：在蝴蝶自身认知部分引入非线性自适应因子；重新定义香味浓度计算公式；在局部搜索阶段引入改进的正弦余弦算法；为回避转换概率对算法的影响，将种群一分为二。

1 蝴蝶优化算法

蝴蝶优化算法是模拟蝴蝶觅食和繁衍行为而衍生出的一种仿生群智能算法，在BOA中每只蝴蝶都会散发出香味，蝴蝶个体能感知香味而互相吸引，香味浓度的计算公式如下：

fi=cIa，

(1)

其中，fi表示蝴蝶个体i感知香味的强度；c表示感知模态参数；I表示蝴蝶散发香味的刺激强度，其值由目标函数值决定；a表示香味吸收程度，a∈[0,1]。

当蝴蝶能感知到周围有更浓香味时便朝其聚集，此阶段称为全局搜索，其计算公式如下：

(2)

当蝴蝶未能感知周围香味时便随机移动，此阶段称为局部搜索，其计算公式如下：

(3)

2 融合正弦余弦算法的蝴蝶优化算法

2.1 非线性自适应因子

大量文献记载了引入自适应权重因子的优势，有线性的，也有非线性的，其主要目的是为了更好地平衡算法的全局搜索和局部搜索能力。这也是算法改进的一个突破口，本文首先在自身认知部分引入非线性自适应因子，使算法迭代初期在较宽范围内搜索，迭代后期在较小范围内搜索。非线性自适应因子的计算公式如下:

ω(t)=2×exp(-(4×t/Ngen)2)，

(4)

其中，exp为指数函数，Ngen为最大迭代次数。

2.2 更改香味浓度计算表达式

在BOA中，香味浓度的计算公式如式(1)所示，其值取决于感知模态参数c、香味吸收程度a和蝴蝶散发香味的刺激强度I，其中I值是由目标函数值决定，首先观察Sphere函数香味浓度变化趋势(其他函数变化曲线类似)，如图1所示。

图1 香味浓度fi变化曲线

由图1可知，在迭代过程中香味浓度值变化曲线由小变大再变小，变化的范围较小，不利于全局搜索，而且中后期曲线斜率变化较小导致收敛速度缓慢且计算精度不高。因此用变化范围较宽和斜率变化较大的自适应权重因子重新定义香味浓度计算表达式，其计算公式如下：

b=2-2×t/Ngen。

(5)

fi=2×b×r-b，

(6)

b表示随迭代次数变化参数，则蝴蝶全局搜索公式更改为

(7)

2.3 正弦余弦算法指引机制

正弦余弦算法于2016年由澳大利亚学者Mirjalili[4]提出，该算法利用正余弦函数的周期性和振荡性趋于全局最优，算法中自适应参数能较好地平衡算法的全局搜索和局部开发。计算公式如下：

(8)

其中，r1等于式(5)，r2∈[0,2π]之间的随机数，r3,r4∈[0,1]之间的随机数。

高文欣等[10]和宁杰琼等[12]也使用正弦余弦算法来改进BOA，高文欣等[10]在算法迭代后期让所有蝴蝶个体执行正弦余弦算法，本质上实行算法的串联操作，但在一定程度上增加了算法的时间开销；宁杰琼等[12]在局部搜索过程中以一定概率将正弦余弦算法与基本BOA的局部搜索公式共同寻优。而本文的操作方式与其不同，首先使用非线性自适应因子式(4)替换式(8)中r1，然后用正弦余弦算法替换基本BOA的局部搜索公式，更好地平衡正弦余弦算法的全局搜索和局部勘探能力。因此改进后的正弦余弦算法公式如下：

(9)

2.4 SCABOA的伪代码

输入：种群规模n、函数名称和最大迭代次数。

①在边界范围内随机产生种群，并计算此时最优解和最优值

②Whilet

③计算式(4)和式(5)

④Fori=1∶n

⑤计算式(6)

⑥Ifi≤n/2

⑦执行式(7)

⑧Else

⑨Forj=1∶dim

⑩执行式(9)

输出：最优值和最优解

3 仿真实验与结果

为检验SCABOA的性能，选取19个基准函数进行测试，函数的具体表达式、维度、取值范围和理论值最优值如表1所示。实验环境为Matlab2016a和Windows10，机器主频为2.60 GHz ，内存为8 GB。

表1 基准函数

利用SCABOA对19个基准函数进行求解，并与基本BOA、SCA、SSA、GWO和CS算法进行对比，以验证SCABOA的效果。参数设置：种群规模为30，最大迭代次数为500，其余参数设置与原论文相同。为避免偶然性，每种算法在Matlab2016a软件中独立运行30次，计算每个函数的平均值Mean和方差Std，结果如表2所示，表中“-”表示文献未对相关函数进行测试，表中的加粗字体为所有实验中的最佳结果。

表2 基准函数的实验结果

由表2第3-8列可知，SCABOA求解的19个基准函数测试中，有8个函数(f1-f4、f8、f9、f11和f19)的平均计算结果达到理论最优值，完全胜出BOA、SCA、SSA、GWO和CS算法。未达到理论最优值的11个函数中，有4个函数f15-f18比BOA、SCA、SSA、GWO和CS算法的平均计算结果稍差且差别较小以外,另外7个函数的平均计算结果精度高出比较算法十几个数量级。尤其值得一提的是Rosenbrock函数，该函数理论最优值位于一个平滑、狭长的抛物线形山谷中，由于函数为优化算法提供的信息非常有限，使得众多算法求解其最优值变得十分困难，如BOA、SCA、SSA、GWO和CS算法求解的平均值从个位数到百位数不等，而SCABOA算法求解的平均值竟达到1×10-16，与理论最优值更为接近。可见，改进的SCABOA算法计算精度更高。

为直观展示SCABOA的收敛速度和寻优精度，给出部分函数前100代的收敛曲线图。从图2-7可知，SCABOA收敛曲线位于图形最下方，收敛速度最快,且计算精度最高。

图2 f4函数收敛曲线

与高文欣等[10,14]的改进蝴蝶优化算法进行比较，其测试函数部分与本文相同，求解结果相同部分未列出(具体数据可参考文献)，挑选求解结果不同的函数进行比较。如高文欣等[10]的f4即本文中的f12，高文欣等[10]求解的平均值精度仅为10-7，而本文算法求解的平均精度高达10-19，高出12个数量级;如高文欣等[14]使用的f2即本文中的f2，高文欣等[14]求解的平均值精度仅为1.36e-81，而本文算法求解的平均精度达到理论值。再与王依柔等[11]的算法(SIBOA)进行比较，由于本文中19个测试函数全部包含王依柔等[11]使用的测试函数，故将其结果列于表2，王依柔等[11]使用的种群规模为40，最大迭代次数为1 000。比较结果：函数f9-f11的计算结果相同，f7的计算结果略次于王依柔等[11]，函数f1-f4均优于王依柔等[11]；本文算法在种群规模为30和最大迭代次数为500的情况下，总体效果依然优于王依柔等[11]的算法，可见本文算法的优越性。

图3 f5函数收敛曲线

图4 f6函数收敛曲线

图5 f8函数收敛曲线

图6 f9函数收敛曲线

图7 f10函数收敛曲线

4 结束语

本文在BOA基础之上引入非线性自适应因子、重新定义香味浓度计算公式，嵌入正弦余弦算法，提出一种融合正弦余弦算法的改进蝴蝶优化算法(SCABOA)。比较实验结果可知，SCABOA算法性能表现优越，这与文章第2部分的改进策略分析相吻合：①通过在自身认知部分引入非线性自适应因子，使得算法迭代初期在较宽范围内搜索，而迭代后期在较窄范围搜索；②设计变化范围较宽和斜率变化较大的香味浓度计算公式；③在后半个种群中利用正弦余弦算法替换基本BOA的随机搜索，使得算法搜索更具有目标性。这3种策略的合力结果使得SCABOA算法具有更好的全局搜索和局部搜索能力。