具有动态方差高斯变异的蝴蝶优化算法*

张小萍, 谭欢

(1. 广西大学 计算机与电子信息学院， 广西 南宁，530004;2.中国移动通信集团广西有限公司，广西 南宁 530022)

1 引言

优化问题是工程数学中的普遍适用性问题，由于其使用的广泛性和多样性一直都是研究领域中的热点.优化的方法大致可以分为两类：确定性优化方法和随机优化方法.确定性优化方法对应用条件的要求非常严格，只能用于小规模的优化问题，对于大规模的优化问题一般使用的是随机优化方法[1].在随机优化方法中，群智能优化算法近年来得到了快速的发展，出现了许多优秀的算法，包括粒子群算法(PSO)[2]、树种算法(TSA)[3]、灰狼算法(GWO)[4]和乌鸦算法(CSA)[5]等，这些算法被广泛应用到图像分割[6]、软件工程测试数据生成[7]和SVM参数优化[8]等领域，获得了良好的效果.

蝴蝶优化算法(BOA)[9]的基本思想是模拟蝴蝶觅食的过程，该算法的参数较少，迭代过程简单易于实现，而且可以获得较高的求解精度；但蝴蝶优化算法存在收敛速度较慢，容易陷入局部最优解的问题，因此需对其进行改进，以提高算法的全局搜索能力和收敛速度.文献[10]提出的改进算法(AGSABOA)在全局位置更新处融入收敛因子并结合黄金正弦指引机制来改善迭代后期种群多样性的下降，提高全局搜索的范围.文献[11]使用cubic混沌映射初始化种群，并将粒子群算法和蝴蝶算法结合(HBOAPSO).上述算法的种群多样性和全局搜索能力都获得了提高，但仍存在迭代后期种群多样性不足和难以平衡全局搜索和局部搜索的问题，可进行进一步的优化研究.本文提出一种改进的蝴蝶优化算法，首先引入线性函数的动态切换概率来平衡全局搜索和局部搜索，然后使用方差动态变化的高斯随机数来改进局部搜索和全局搜索的公式，提高局部搜索能力的同时避免陷入局部最优解.

2 基本蝴蝶优化算法(BOA)

蝴蝶优化算法是模拟蝴蝶在觅食和求偶时行为的群智能优化算法，在该算法中每只蝴蝶都可以发出一定浓度的香味，这些香味可以被一定范围内的其他蝴蝶所感知，每只蝴蝶散发香味的浓度和适应度有关，当蝴蝶从一个位置移动到另一个位置，对应的适应度也发生改变；当蝴蝶感知到香味浓度最大蝴蝶(最优蝴蝶)的香味时，就朝最优蝴蝶的方向移动，这个阶段叫作全局搜索阶段；当感知不到比自己更浓香味时，则随机移动，这个阶段叫作局部搜索阶段.香味的计算公式为

fi=cIα;

(1)

其中，fi是其他蝴蝶对香味的感知浓度；c是感官模态因子；I是刺激强度；α是由感官模态决定的幂指数参数.

全局搜索和局部搜索通过切换概率p来控制，在全局搜索阶段，蝴蝶向最优蝴蝶g*方向移动，可表示为

(2)

在局部搜索阶段，蝴蝶进行随机移动，可表示为

(3)

3 具有动态方差高斯变异的蝴蝶优化算法(DGBOA)

针对BOA存在着收敛速度慢，寻优精度不高，容易陷入局部最优解的问题，对其进行了两点改进，一是使用线性函数的动态切换概率来取代常数切换概率，二是使用动态方差的高斯变异来改进局部搜索和全局搜索的公式.

3.1 线性函数的动态切换概率

在BOA中，切换概率p是一个常数，决定了每次迭代全局搜索和局部搜索的相对比例，是平衡算法勘探和开发能力的重要参数.对于一个优秀的寻优算法，在算法迭代初期往往需进行全局搜索，在迭代后期主要进行局部搜索，因此常数的切换概率p无法适应BOA迭代的要求，使用线性函数的动态切换概率，在迭代的不同阶段p的值是不同的，为

图1 μ=0，σ=0.5，1,2的高斯曲线Fig.1 Gaussian curve of μ=0，σ=0.5,1,2

(4)

其中，t是当前迭代次数；tmax是算法的最大迭代次数；pmax和pmin是切换概率的最大和最小值.在公式(4)中，迭代初期p(t)比较大，主要进行全局搜索以便尽快确定全局最优解的位置，提高搜索速度，在迭代后期，p(t)比较小，主要进行局部搜索以便提升算法的寻优精度.

3.2 动态方差的高斯变异

高斯概率密度函数可以表示为

(5)

其中，μ表示均值；σ表示标准方差；当μ=0，σ=0.5,1，2时函数曲线如图1所示.

显然当方差越小时，函数值集中在均值附近的概率越大，函数曲线也会越向均值靠拢，当产生高斯随机数时，计算发现μ=0,当σ=0.5时，产生的随机数在[-0.5,0.5]范围概率达到68.3%，而当σ=2时，产生随机数在[-0.5,0.5]范围概率只有19.7%.由于BOA容易陷入局部最优解，在迭代前期需要在较大的范围内进行探索以便快速定位到全局最优解，在迭代后期需要在优化精度和避免早熟而进入局部最优解之间进行平衡，因此可以利用高斯随机数中方差的变化来达到目的，在初始时设置方差比较大，使种群在一个变化范围大的区间进行搜索，在迭代后期方差逐渐变小，种群大概率在一个变化范围比较小的区间进行探索，以提高寻优的精确度，同时也有机会跳出局部最优解.设置方差的最大值σmax和最小值σmin.方差计算公式为

σ(t)=σmax-(σmax-σmin)×t/tmax;

(6)

其中，t是当前迭代次数；tmax是算法的最大迭代次数.

BOA的局部搜索公式改进为

(7)

其中normrnd(0,σ(t))表示均值为0、方差为σ(t)的随机数.

为了增加种群的多样性，全局搜索采用两种方式进行，全局搜索的公式改进为

(8)

其中pg是全局搜索两种更新方式的转换概率，是(0,1)之间的一个常数.

3.3 DGBOA算法描述

Step 1.初始化系统相关参数和种群；

Step 2.计算种群中每个个体的适应度，并使用公式(1)计算香味的浓度，然后根据适应度得到最佳蝴蝶的位置g*；

Step 3.使用公式(4)计算转换概率p(t)；

Step 4.生成一个随机数rand,若rand

Step 5.否则，使用公式(7)进行局部位置更新；

Step 6.检查更新后的位置的适应度值是否比原来更新前的值更优，如果更优，则用更新后的位置取代更新前的位置，并更新全局最优蝴蝶的位置和适应度值；

Step 7.判断是否满足结束条件，不满足就转到Step 2，否则输出全局最优解和相应的适应度，算法结束.

4 实验仿真测试结果和分析

4.1 实验环境与测试函数

实验环境为64位的Windows 7，CPU为Inter(R) Xeon(R)E5645主频双核2.4 GHz,内存8 G,仿真实验软件为MATLAB 2020b.选择了6个基准函数作为测试函数，函数的具体情况如表1所示，其中‘U’表示单峰值函数，‘M’表示多峰值函数.

表1 基准测试函数

4.2 实验参数设置和仿真结果

在实验中DGBOA设置的参数为pmax=0.8,pmin=0.3,a=0.1,c=0.01,σmax=1.5,σmin=0.4，pg=0.5,将DGBOA和HBOAPSO、AGSABOA、BOA、PSO和GWO共6种算法作对比试验，设置最大迭代次数为500次，种群中的个体数为30，在每个函数上单独运行50次，计算它们的最大值、最小值、平均值、方差和运行时间，得到的实验结果如表2所示.

表2 实验结果

从表2可以看出在使用的6个测试函数中，DGBOA在5个测试函数中都找到了理论最优解，并且在6个函数中方差为0，具有较强的稳定性.使用平均绝对误差[12](Mean Absolute Error,MAE)作为定量标准来分析6个算法，计算各算法的MAE值，HBOAPSO是1.480E-16,AGSABOA是1.320，BOA是2.233E-2,PSO是2.243E2，GWO是7.877E-1，DGBOA是1.355E-18，显然，DGBOA的MAE值是所有算法中最小的，说明引入的改进策略是有效的.

为了进一步分析DGBOA算法的有效性，图2-5给出了4个多峰值函数在6个算法下的收敛曲线.

图2 f3的收敛曲线 图3 f4的收敛曲线

图4 f5的收敛曲线 图5 f6的收敛曲线

从收敛曲线图中可以看出，PSO和BOA在f5当中无法迭代到理论最优解，PSO和GWO在f6当中无法迭代到理论最优解，AGSABOA和HBOAPSO曲线的波动在f3与f5中都比DGBOA要大，收敛到理论最优值需要更多的迭代次数，而DGBOA算法在四个函数的迭代初期就可以接近理论最优解，比其他5个算法的迭代次数要少，寻优能力更强.

通过实验数据对比可以看出，DGBOA对于所给的测试基准函数都有较好的寻优效果，具有较强的稳定性和较快的寻优能力，有效缓解BOA算法寻优精度不高，难以获得全局最优解的问题.