具有自适应步长与协同寻优的蝙蝠烟花混合算法

莫海淼,赵志刚,曾 敏,石 静,温 泰

(广西大学 计算机与电子信息学院,南宁 530004)

1 前 言

烟花算法(Fireworks Algorithm,FWA)[1]是由Tan等人于2010年提出的,并且被广泛应用于JSP问题的求解[2]、聚类[3]、网络规划[4]、图像识别[5]、函数优化[6]等领域.

从此之后,烟花算法吸引了越来越多的学者对其进行深入的研究.通过对原始烟花算法进行深入的研究分析,并针对FWA的不足,一些研究者提出了相关的改进方法.改进烟花算法主要可以被分为两类[7],一类是在基本烟花算法的基础上进行算子的分析和改进,另一类是与其他启发式算法的混合算法的研究.第一类对烟花算法改进的工作主要有:Liu等提出一种构造型烟花算法(IFWA)[8],它引入一种新型的爆炸半径和爆炸火花数目计算方式,让拥有较好适应度值的烟花在更小的爆炸半径内产生更多的爆炸火花.Zheng等[9]人针对算子存在的缺陷提出了相应的改进策略,最终提出EFWA.文献[10]和文献[11]均是对最优的烟花个体引入了自适应的爆炸半径,并提高了算法的性能.李席广等[12]将反向学习与动态记忆反馈的思想引入烟花算法,提出了一种新的烟花算法,并得到不错的实验效果.Li 等[13]从信息利用的角度,在烟花算法中充分利用了爆炸火花的信息,并提出了 GFWA.方柳平等[14]通过嵌入一种利用历史成功信息生成两种不同的学习因子来改进dynFWA,来平衡算法的局部搜索和全局搜索能力.第二类对烟花算法改进的工作主要有:Gao 等[15]人将文化算法和烟花算法混合,改变了烟花算法中爆炸火花产生方式和选择策略,提出了CA-FWA算法.Yu等[16]人将差分演化算法的差分变异算子替换烟花算法的高斯变异算子,并提出了FWA-DM.Zhang等[17]将生物地理学优化算法的迁移算子引入烟花算法,提出了具有较强勘探能力的BBO-FWA算法.为了进一步提高标准烟花算法的性能,本文将蝙蝠算法(Bat Algorithm,BA)[18]的局部搜索机制引入到烟花算法,以协助烟花算法寻优;并利用蝙蝠种群与烟花种群的位置信息构造了新的爆炸半径,使其能够自适应地调整步长;最后,使用“精英-随机”策略选择下一代烟花,以及对全局最优个体进行高斯扰动,来保证种群的多样性,避免过快地陷入局部最优解.基于以上的思想,本文提出了蝙蝠烟花混合算法,并使用十个常用的基准函数以及五个0-1背包问题对蝙蝠烟花混合算法的性能进行测试,并与经典的蝙蝠算法、粒子群算法、烟花算法等五种算法进行对比实验.

2 混合算法

2.1 协同寻优

蝙蝠个体根据回声定位的原理,以及发出的脉冲和响度信息来判断猎物的位置来定位猎物,即当蝙蝠个体在当前最优解gbest附近进行局部搜索时,如果它所处的位置更接近猎物,则将脉冲调整变大,同时把响度调小,然后继续搜寻和定位猎物,并不断地靠近猎物.这就是蝙蝠算法局部搜索的基本原理.将蝙蝠算法的局部搜索引入烟花算法,并协助烟花算法寻优,把这个过程称作协同寻优.协同寻优是指在寻优过程中,蝙蝠种群根据蝙蝠发出的脉冲和响度在最优烟花gbest附近协助烟花种群寻优,并且加强两个种群在寻优过程中的信息交流,其主要操作是初始化一个蝙蝠种群BatX(用来存放全局最优烟花gbest附近产生的局部解),假设第i个蝙蝠个体发出的脉冲r(i)小于随机脉冲时,则对gbest进行高斯扰动之后产生一个局部解BatX(i),然后对该蝙蝠个体的位置信息BatX(i)进行评价:假如该蝙蝠个体的适应度值优于烟花种群的第i个烟花X(i),且它产生的响度A(i)大于随机生成的响度时,则该蝙蝠个体被加入烟花种群中,其操作如公式(1)和公式(2)所示.

BatX(i)=gbest*(N(0,1)+1),as r(i)

(1)

其中,i=1,2,…,popsize;N(0,1)是服从均值为0,方差为1的高斯分布函数;r(i)是第i个蝙蝠个体发出的脉冲;rand是[0,1]范围内服从均匀分布的随机数.

X(i)=BatX(i),asf(BatX(i))rand

(2)

其中,X(i)是第i个烟花所在的位置;A(i)是第i个蝙蝠发出的响度;rand是[0,1]范围内服从均匀分布的随机数.

蝙蝠种群通过发出的脉冲信息在全局最优烟花gbest附近产生一个局部解;并使用蝙蝠个体发出的响度、脉冲与所处位置的优劣来更新烟花种群.这样,蝙蝠种群与烟花种群不断地进行交互,协同寻优,而公式(1)和公式(2)相结合则加强蝙蝠种群和粒子群在寻优过程中的信息交互,协同寻优.协同寻优的操作如算法1所示.

算法1.协同寻优.

输入:蝙蝠种群的位置BatX.

输出:烟花种群的位置X和全局最优烟花个体gbest.

Begin

1. for i=1:popsize

2. if r(i)

3. 按公式(1)产生一个局部解;

4. endif

5. 越界处理;

6. 计算该局部解的适应度值f(BatX(i));

7. iff(BatX(i))rand

8. X(i)= BatX(i);

9. 更新脉冲r(i)和响度A(i);

10. endif

11. iff(BatX(i))

12. gbest = BatX(i);

13. endif

14. endfor

End

2.2 自适应步长

当烟花的爆炸火花数达到当前最大时,本文使用蝙蝠算法在最优位置附近产生局部解的位置BatX、蝙蝠发出的频率Q、烟花位置X、全局最优烟花个体gbest来构造新的爆炸半径,其具体操作如公式(3)所示.

(3)

其中,X(i)是第i个烟花的位置;BatX(i)的含义与公式(1)相同;Si是指第i个烟花个体产生的爆米花数量;Qi是指第i个蝙蝠个体产生的频率;AvgS是指此时烟花种群产生爆炸火花数量的平均值,即

(4)

其中,popsize是指烟花个体的数量.

将公式(3)代入公式(4)之后,可知:当第i个烟花个体的爆炸火花数量大于平均爆炸火花数时,则该烟花个体往全局最优附近产生的一个局部解Batx(i)靠拢;当烟花个体产生的爆炸火花数小于平均爆炸火花数时,则该烟花个体往gbest靠拢.假设此时产生爆炸火花数量最多的烟花个体也往gbest靠拢,就相当于该烟花个体没有产生位移,这样便浪费了该烟花个体的资源;若该烟花个体向gbest附近的局部解BatX(i)靠拢时,则充分发挥了该烟花个体的作用,并使它在全局最优gbest附近进行详细的局部搜索,而蝙蝠发射出随机的频率Qi,则保证了该烟花个体在gbest附近搜索的随机性.使用蝙蝠与烟花的位置信息来构造新的爆炸半径,这样便能使粒子能够自适应地调整步长.此时,烟花位移操作如下:

Xnew(i)=X(i)+R(i)

(5)

2.3 “精英-随机”策略

本文采取 “精英-随机”选择策略来选择下一代的烟花,即从烟花、烟花产生高斯变异之后的高斯烟花、烟花爆炸后产生的所有爆炸火花这三者共同组成候选集,从候选集中选取适应度值最好的个体作为下一代烟花的“精英”(仅有一个),其他popsize-1个下一代的烟花则从候选集中随机选取(可以重复选择).选择下一代烟花的具体操作为:将候选集以适应度值进行升序排序,然后选择适应度值最好的个体作为下一代的其中一个烟花,下一代其他烟花的选取则根据候选集的下标进行随机选取.

2.4 混合算法

综上所述,本文提出一种新的算法——蝙蝠烟花混合算法(the hybrid Bat and Fireworks Algorithm,BAFWA).BAFWA算法的伪代码如算法2所示.

算法2.本文蝙蝠烟花混合算法的具体过程.

输入:蝙蝠种群的位置、烟花种群的位置.

输出:蝙蝠种群更新之后的位置、烟花种群更新之后的位置、全局最优个体gbest.

Begin

1.初始化蝙蝠种群BatX、烟花种群X、最优个体gbest以及两个种群的相关参数;

2.使用蝙蝠种群协助烟花种群寻优:具体参照算法1;

3.计算爆炸火花的数量;

4.按公式(3)和公式(4)来计算爆炸半径;

5.产生爆炸火花,并按公式(5)进行位移操作;

6.越界处理;

7.产生高斯烟花;

8.用2.3小节的“精英-随机”策略来选择下一代烟花;

9.重复步骤2至步骤8,若达到终止条件(一般为达到设定的寻优精度或者达到最大的迭代次数),则停止迭代.

End

表1 基准函数
Table 1 Benchmark functions

FunNameFuntionDomainDimOptimumSpheref1(x)=∑ni=1x2i[-100,100]d300Rosenbrockf2(x)=∑ni=1[100(xi+1-xi)2+(xi-1)2][-10,10]d300Griewankf3(x)=14000∑ni=1x2i-∏ni=1cos(xii)+1[-600,600]d300Rastriginf4(x)=∑ni=1(x2i-10cos(2πxi)+10)[-5.12,5.12]d300Ackleyf5(x)=-20exp(-0.2∑ni=1x2i)-exp(1n)∑ni=1cos(2πxi)+20+e[-32,32]d300Schwefelf6(x)=∑ni=1(∑nj=1xj)2[-100,100]d300Six-HumpCamel-Backf7(x)=4x21-2.1x41+13x61+x1x2-4x22+4x42[-5,5]22-1.0316285GoldsteinPricef8(x)=[1+(x1+x2+1)2(19-14x1+3x21-14x2+6x1x2+3x22)]·[30+(2x1-3x2)2(18-32x1+12x21+48x2-36x1x2+27x22)][-2,2]223Schaffer′sF6f9(x)=sin2x21+x22-0.5[1+0.001(x21+x22)]2+0.5[-100,100]220Braninf10(x)=(x2-5.14π2x21+5πx1-6)2+10(1-18π)cosx1+10-5

3 仿真实验

3.1 测试函数

本文选用了如表1所示的10个测试函数来测试BAWFA混合算法的性能,并与蝙蝠算法BA、烟花算法FWA、标准粒子群算法[19,20](Standard Particle Swarm Optimization,SPSO)、增强烟花算法(Enhanced Fireworks Algorithm,EFWA)[9]、 自适应烟花算法(Adaptive Fireworks Algorithm,AFWA)[11]进行对比实验.

3.2 参数设置

本文对比实验的相关参数是根据相关文献的建议来进行设置的.其中,蝙蝠算法的参数设置参照文献[18];标准粒子群算法的参数设置参照文献[19,20];烟花算法的参数设置参照文献[1];增强烟花算法的参数设置参照文献[9];自适应烟花算法的参数设置参照文献[11];蝙蝠烟花混合算法的最小频率设置为0.1,最大频率设置为100,popsize设置为10,其他参数设置参照蝙蝠算法与烟花算法;六种算法的寻优精度均设置为λ=10-5,即到达寻优精度时,则标记成功寻优一次.本文对表1的测试函数做了100次独立重复实验,最大迭代次数MaxIteration=1000.

3.3 收敛性分析

对表1的10个测试函数进行测试得到最差值worst、最好值best、平均值avg、标准偏差std如表2所示;寻优成功率SR如表3所示.为了缩减篇幅,本文只给出部分的演化曲线图,如图1-图6(测试函数进化曲线的适应度值均取对数log10,即其纵坐标为log10Fitness)所示.

图1 f1寻优演化曲线Fig.1 Evolution curve of f1

由图1可知,在优化f1函数的过程中,BA、SPSO、EFWA和AFWA的收敛曲线较平缓,说明这4种算法的种群多样性较差,极易陷入局部最优解;而BAFWA的收敛曲线较陡峭,其收敛速度优于其他5种算法;在寻优过程中,BAFWA不到100次迭代,就已经寻找到最优解0(由于寻优曲线图的纵坐标是log10Fitness,而寻找到最优解0时,即Fitness=0,此时的寻优曲线在图上无法显示);而其他5种算法在迭代终止时也没有寻找到最优解0.由表2中f1的实验数据可知,在迭代结束(iteration=1000)时,BAFWA寻找到的平均解avg均优于其他5种算法,故BAFWA的收敛精度优于其他5种算法.综上可知,在f1函数的寻优过程中,BAFWA的收敛性能优于其他5种算法.

图2 f3寻优演化曲线Fig.2 Evolution curve of f3

由图2、图3、图5和图6可知,在优化函数f3、f4、f6和f9的过程中,在迭代结束之后BAFWA和FWA都寻找到最优解,其他四种算法没有寻找到最优解且在寻优后期陷入局部最优解;在迭代次数相同时,BAFWA的收敛速度和收敛精度均优于其他5种算法.由表2中f3、f4、f6和f9的实验数据可知,在迭代结束时,BAFWA和FWA寻找到的平均解均相同,且优于其他4种算法.综上可知,在f3、f4、f6和f9的寻优过程中,BAFWA的收敛性能均优于其他5种算法.

图3 f4寻优演化曲线Fig.3 Evolution curve of f4

图4 f5寻优演化曲线Fig.4 Evolution curve of f5

由图4可知:在优化f5函数的过程中,在迭代结束之后6种算法均没有寻找到最优解;在寻优前期,迭代次数相同时,BAFWA的收敛速度和收敛精度均优于其他5种算法.由表2中f5的实验数据可知,在迭代结束后,BAFWA和FWA寻找到的平均解均相同,且优于其他4种算法.综上可知,在f5函数的寻优过程中,BAFWA的收敛性能均优于其他5种算法.

图5 f6寻优演化曲线Fig.5 Evolution curve of f6

由表2中f2的实验数据可知:在迭代结束之后,6种算法均没有寻找到最优解,但是BAFWA寻找到的平均解avg优于其他5种算法.

图6 f9寻优演化曲线Fig.6 Evolution curve of f9

由表2中f7的实验数据可知:在迭代结束之后,BAFWA寻找到的平均解avg劣于SPSO、AFWA、EFWA,却不亚于其他3种算法.

由表2中f8的实验数据可知:在迭代结束之后,BAFWA寻找到的平均解avg与SPSO、AFWA、EFWA相同,并且优于其他2种算法.

由表2中f10的实验数据可知:在迭代结束之后,BAFWA寻找到的平均解avg优于FWA,却劣于其他4种算法.

3.4 鲁棒性分析

标准偏差的大小反映了算法鲁棒性的好坏,即标准偏差越小,则算法的鲁棒性越好;反之,则算法的鲁棒性越差.

由表2的实验数据std可知,在f1、f3、f4、f5和f9寻优过程中,BAFWA和FWA的鲁棒性一样好(在f5的寻优过程中,虽然EFWA的鲁棒性与BAFWA相同,但它的平均解avg劣于BAFWA),且均优于其他4种算法;在f2的寻优过程中,BAFWA的鲁棒性优于其他5种算法;在f6的寻优过程中,BAFWA和SPSO的鲁棒性一样好,且均优于其他4种算法;在f7的寻优过程中,BAFWA的鲁棒性优于BA、FWA,却劣于其他3种算法;在f8的寻优过程中,BAFWA的鲁棒性优于BA、FWA、EFWA,却劣于其他2种算法;在f10的寻优过程中,BAFWA的鲁棒性优于FWA,却劣于其他4种算法.因此,综上所述,在十个基准函数的寻优过程中,BAFWA的鲁棒性总体较好.

表2 十种基准函数的四种算法比较
Table 2 Comparison of four algorithms for ten benchmark functions

3.5 寻优成功率分析

表3 十个基准函数的寻优成功率
Table 3 Success rate(%)for ten benchmark functions

由表3可知,将寻优精度设置为λ=10-5,则在迭代结束后,6种算法在f2和f10的寻优成功率均为0%,而BAFWA在剩余其他8个基准函数的寻优成功率均为100%;FWA寻优成功率为100%的只有6个基准函数;BA、SPSO、EFWA和AFWA的整体寻优成功率稍差.因此,在十个基准函数的寻优过程中,BAFWA总体的寻优成功率优于其他五种算法.

综上所述,本文提出的混合算法比其他五种算法具有更好的优化性能源自以下几个方面:

1)烟花算法引入了蝙蝠算法的局部搜索机制.蝙蝠算法具有极强的局部搜索能力,并且利用蝙蝠算法在全局最优个体gbest附近进行详细的局部搜索,以提高种群的收敛性能.

2)利用蝙蝠种群和烟花种群的位置信息构造新的爆炸半径,新的爆炸半径不仅继承了两个种群的信息,而且能够自适应地调整步长.

3)“精英-随机”策略和高斯扰动,使种群在寻优过程中保持多样性,避免过快地陷入局部最优解.

4)蝙蝠种群和烟花种群协同寻优,并且加强了两个种群之间的信息交互,也能提高混合算法的收敛性能.

4 算法应用

4.1 0-1背包问题

背包问题是一个典型的NP完全问题.为了进一步验证本文提出的算法的有效性,本文将其应用于求解0-1背包问题(Knapsack Problem,KP).0-1背包问题的数学模型如下:

(6)

(7)

其中,n 为物品的数量,第i个物品拥有的价值和体积分别为pi和vi,背包的最大体积限制用Vmax表示,自变量xi用来表征物品的状态,有 0 和 1 两个数值可选.当xi的值为1时,表示该物品i已经被装入包中,反之,如没有装入包中,xi取值为0.每个物品最多被装入背包一次,只能全部装入,不允许部分装入.

0-1背包问题是具有复杂约束的最大化问题,对于这些约束,采用外部罚函数法进行处理.同时,将最大化问题转化为最小化问题,将f(x)转化为-f(x).这样,0-1背包问题就转化为:

(8)

4.2 混合算法离散化设计

由于0-1背包问题是离散问题,因此,需要将烟花个体和蝙蝠个体的位置进行离散化处理,其具体操作如下:

(9)

其中,x′(i,j)是第i个个体第j维所在离散化处理之前的位置信息,x(i,j)是第i个个体的第j维所在离散化处理之后的位置信息.

混合算法求解0-1背包问题的伪代码参照算法1和算法2,但是在计算个体的适应度值之前,需要对其所在的位置进行离散化处理(参照公式(9)).

4.3 对比实验

其他5种对比算法(BA、SPSO、FWA、EFWA、AFWA)的离散化处理操作具体如下:

(10)

在算法比较的过程中,选用了5个0-1背包问题[21],具体如表4所示.

表4 五个常见的背包问题
Table 4 Five common knapsack problems

问题dimf∗参数f11435w=(6,5,9,7)Vmax=20p=(9,11,13,15)f12423w=(2,4,6,7)Vmax=11p=(6,10,12,13)f131052w=(30,25,20,18,17,11,5,2,1,1)Vmax=60p=(20,18,17,15,15,10,5,3,1,1)f147107w=(31,10,20,19,4,3,6)Vmax=50p=(70,20,39,37,7,5,10)f155130w=(15,20,17,8,31)Vmax=80p=(33,24,36,37,12)

4.4 实验结果与分析

在求解0-1背包问题的过程中,设置最大的迭代次数为500,其他参数设置则参照3.2小节,并且进行50次独立重复实验,其对比实验结果如表5所示.根据表5的实验结果:由max可知,6种算法均能寻找到最优解f*;由方差std可知,在求解5个0-1背包问题的过程中,BAFWA的鲁棒性不亚于其他5种算法;由寻优成功率SR可知,BAFWA的总体寻优成功率不亚于其他五种算法.因此,综上可知,BAFWA算法在求解表4的0-1背包问题的整体性能不亚于其他五种算法.

表5 5个背包问题的对比实验结果
Table 5 Comparation results of 5 knapsack problems

algfmaxavgminstdSR(%)BAf113535350100SPSO3535350100FWA3532.82243.055E+0052AFWA3535350100EFWA3535350100BAFWA3535350100BAf122323230100SPSO2323230100FWA2322.74196.642E-0180AFWA2323230100EFWA2323230100BAFWA2323230100BAf135251.98511.141E-0198SPSO5251.44497.866E-0160FWA5246.94383.644E+006AFWA5252520100EFWA5252520100BAFWA5252520100BAf141071071070100SPSO107104.98933.133E+0050FWA107100.96746.960E+0034AFWA1071071070100EFWA1071071070100BAFWA1071071070100BAf151301301300100SPSO130129.341093.390E+0096FWA130109.8721.446E+0120AFWA1301301300100EFWA1301301300100BAFWA1301301300100

5 结 论

从本文的仿真对比实验中,可以得出这样的结论:在求解本文仿真实验中的相关问题时,相比其他五种对比算法,本文提出的蝙蝠烟花混合算法具有相对更快的收敛速度,更高的收敛精度以及更好的鲁棒性.在未来的工作中,将对蝙蝠烟花混合算法进行更深入的理论研究,并将其运用到更多的具体工程实践中.