基于差分变异算子的烟花算法*

郭京蕾,赵孝豪,郭亚军

(华中师范大学计算机学院，湖北 武汉 430079)

1 引言

优化问题广泛存在于生产、生活等实际应用问题中，即在有限的时间内找到满足特征和要求的最优或较优解决方案。烟花算法FWA(FireWorks Algorithm )[1]自提出以来，已经证明了其在处理优化问题方面的效率。因其优越的特性而受到不同领域科研工作者的关注，并在工程领域取得了广泛应用。

目前，烟花算法的研究工作主要集中在以下3个方面：(1)对烟花算法中的算子进行改进。Li等[2]提出只保留爆炸操作的骨架烟花算法，该算法具有简单易行、参数少等优点。Yu等[3]提出具有突变的动态烟花算法dynFWACM(dynamic FireWorks Algorithm with Covariance Mutation)，引入协方差变异算子，利用较好火花的信息，计算平均值和协方差矩阵，产生具有良好分布特性的变异火花，增强了局部搜索能力。Zheng等[4]提出了一种基于烟花算法的合作框架CoFFWA(Cooperative Framework for FireWorks Algorithm),提出了避免拥挤的合作策略增加全局开采能力，在CEC2013测试集上CoFFWA表现出良好性能。(2)将FWA与其他群智能算法融合生成混合型烟花算法。Tan等[5]提出在烟花算法中，加入图形图像处理器GPU技术加快优化过程，缩短算法运行时间。Zhang等[6]将生物地理学优化方法BBO(Biogeography-Based Optimization)的迁移操作引入到FWA中，以增强种群之间的信息共享，从而改善解决方案的多样性以避免过早收敛。Ma等[7]提出了一种基于小波支持向量机w-SVM(wavelet Support Vector Machine)和量子烟花QFWA(Quantum FireWorks Algorithm)的混合算法的预测组合模型。(3)应用FWA解决工业生产中的实际问题。Tuba等[8]提出利用烟花算法提取二维视网膜图像配准的刚性变换最佳参数。Bacanin等[9]提出将带约束的烟花算法用于解决投资组合优化问题。Babu等[10]提出一种提取光伏模块双二极管模型未知参数的烟花算法。

标准烟花算法将在第2节进行论述，第3节论述差分变异算子的构造、动态爆炸火花策略，提出差分变异算子的烟花算法DEFWA(FireWorks Algorithm with Differential mutant operator)，第4节进行了实验结果的分析和比较，最后进行总结。

2 标准烟花算法

为了不失一般性，优化问题可以定义为式(1)所示：

Minimizef(X)∈R,Xmin≤X≤Xmax

(1)

其中，X=[x1,x2,…,xD]表示烟花在搜索空间中的位置，D表示搜索空间的维数，f(X)表示该位置所对应的目标函数，Xmin和Xmax表示可行域空间的搜索边界。

烟花算法模拟烟花的爆炸过程，属于群体随机搜索算法，主要包含爆炸算子、高斯火花算子和选择算子。

2.1 爆炸算子

烟花算法的每个烟花根据其适应值不同，产生的火花数目不同，第i个烟花产生的爆炸火花数目si如式(2)所示：

(2)

其中，Xi为第i个烟花的位置，m表示爆炸火花总数，ymax=max(f(Xi)),i=1,2,…,n,表示n个烟花中的最大适应值，ε表示较小的正常数。

从式(2)可看出,为了平衡全局探索能力和局部开发能力，种群中具有较小适应值的烟花比具有较大适应度值的烟花能产生更多的火花。为了避免算法的早熟收敛，需要防止适应值较优烟花产生过多的火花，而质量较差的烟花产生较少甚至不能产生火花。故定义爆炸火花数目si如式(3)所示。

(3)

其中，a和b表示限制种群大小范围的常数参数(a

在种群中具有较小适应度值的烟花比具有较大适应度值的烟花具有更小的爆炸幅度。所以定义每个烟花的爆炸幅度Ai如式(4)所示:

(4)

算法1爆炸算子

z=round(D·rand(0,1));

计算爆炸幅度Ai并计算h:h=Ai·rand(-1,1);

end if

end for

2.2 高斯变异算子

算法2高斯变异算子

z=round(D·rand(0,1));

计算高斯爆炸系数：e=Gaussian(1,1);

end if

end for

2.3 选择算子

R(Xi)=∑j∈Qd(Xi,Xj)=∑j∈Q‖Xi-Xj‖

(5)

其中，Q表示烟花和火花所有当前位置的集合。

个体的选择概率如式(6)所示：

(6)

在计算距离时，可以使用包括欧几里德距离、曼哈顿距离、基于角度的距离等距离测量方法进行测量，在传统烟花算法中采用的是欧几里德距离。

3 差分变异算子的烟花算法(DEFWA)

3.1 差分变异算子

在传统的DE(Differential Evolution)差分算子中：“best/1”“current-to-best/1”“best/2”能够加速向最优值附近收敛；“rand/1”“rand/2”能够增加种群多样性。为了有效平衡全局搜索能力和收敛速度，本文采用“current-to-rand/1”变异算子，如式(7)所示：

(7)

通过二项式杂交方法，如式(8)所示,生成差分变异火花。

(8)

其中，k=1,2,…,D,krand是分布在[1,D]的随机数,CR为杂交概率。

算法3“current-to-rand/1”差分变异算子

按式(7)生成V；

fork=1 toDdo

end if

end for

利用“current-to-rand/1”差分变异算子取代烟花算法的高斯变异算子，可通过成对的差分向量信息，有效地将群体中多个个体信息与当前粒子结合，增强种群的多样性。

3.2 动态爆炸火花策略

(9)

3.3 DEFWA算法流程

算法4DEFWA算法

随机初始化n个烟花并评价适应值;

while stop criteria等于false do

for 每一个烟花的位置Xido

根据式(2)和式(4)计算每一个烟花的火花数si和爆炸范围Ai;

根据算法1产生爆炸火花;

end for

随机选择一个烟花Xi;

根据算法3产生差分变异火花;

end for

评价爆炸火花和差分变异火花;

选出最优个体，保存到下一代；

根据式(9)设置最优烟花的爆炸个数；

根据式(6)从烟花和火花中选择其他n-1个个体保存到下一代;

end while

4 差分变异的混合烟花算法

4.1 测试函数

选取文献[13]的12个函数作为测试集，其中包括单峰函数、多峰函数等多种类型，表1列出了测试函数的序号、名称、维数、搜索范围、最优位置和最优值。

各函数将在每个维度中产生移位，移位量大小为0.7*(Xmax-Xmin)/2。

4.2 爆炸火花个数参数选取

在算法中，爆炸火花的个数将影响到算法的勘探与开采能力，因此将DEFWA爆炸火花总数m分别设置为25,50,75,100，a=0.04,b=0.8,即smin=a·m，smax=b·m。DEFWA算法在表1的12个30维测试函数上独立运行30次，得到的平均值与方差如表2所示。

Table 1 Test functions表1 测试函数

从表2可看出，当m=50时，相比其他3种取值，在12个函数上均取得了最好均值。在后续的实验中将爆炸火花数设置为50。

4.3 算法对比

将DEFWA算法与FWA[1]和3种经典改进型烟花算法(EFWA[12]、dynFWA[13]、GFWA(Guided FireWorks Algorithm)[14])在表1的12个30维测试函数上，独立运行30次，迭代次数为3.0*105，得到的平均值与方差如表3所示。在实验中DEFWA参数设置如下：烟花个数为5，爆炸火花数m=50，差分变异火花数为5，杂交概率CR在集合{0.1,0.2,1.0}中随机取值，F在集合{0.6,0.8,1.0}中随机取值。

在12个测试问题中，FWA算法在函数f8、f9上取得了最优均值，EFWA算法在函数f8、f9、f10上取得了最优均值，dynFWA算法在9个函数(f1、f2、f3、f4、f8、f9、f10、f11、f12)上取得了最优均值，GFWA算法在函数f6、f8上取得了最优均值，DEFWA算法在9个函数(f1、f2、f5、f7、f8、f9、f10、f11、f12)上取得了最优均值。根据表3的实验结果，对算法进行了Friedman检验，结果如表4所示。

Table 2 Experiment result of the different number on explosion sparks表2 爆炸火花数实验结果

Table 3 Experiment results of FWA, EFWA, dynFWA, GFWA and DEFWA表3 FWA、EFWA、dynFWA、GFWA、DEFWA算法实验结果

DEFWA、FWA、EFWA、dynFWA、GFWA在函数f1、f3、f5、f7、f9、f11上的收敛曲线如图1所示。

Table 4 Friedman testing result表4 Friedman检验结果

Figure 1 Convergence curve of algorithms图1 算法收敛曲线图

图1中，在函数f1上仅有FWA未搜索到全局最优值，DEFWA和dynFWA的收敛过程相似，但在整个过程中DEFWA的收敛速度快，GFWA在搜索早期收敛速度较快，但中后期明显减慢。在函数f3的收敛图中，DEFWA搜索到了最小值，其它几种对比算法都未能达到。在函数f5中，依旧只有DEFWA搜索到了最小值，其它4种对比算法均出现了后期收敛性能不足的缺点。在函数f7收敛图中，DEFWA搜索到了最小值，其它4种对比算法也同样出现后期收敛性能不足的弊端，同时dynFWA陷入了局部最优。在函数f9收敛图中，DEFWA和其他4种对比算法均能在搜索早期较快地收敛。在函数f11收敛图中，DEFWA后期收敛速度快并且搜索到最小值，dynFWA性能次之，其中GFWA在搜索初期明显好于其他算法，但搜索的后期则陷入局部最优。

5 结束语

本文将差分变异算子和动态爆炸火花策略加入了烟花算法中，为了增强种群的多样性提出了差分变异算子的DEFWA算法，为了加快收敛速度，对最佳烟花采用了动态火花爆炸策略。在标准测试集上，将DEFWA算法与FWA和3个改进型的FWA(EFWA、dynFWA、GFWA)进行了实验对比，结果表明DEFWA在寻优的精度和速度方面优于对比算法。