文章快速检索 高级检索

1. 北京大学 机器感知与智能教育部重点实验室，北京 100871;
2. 北京大学 信息科学与技术学院, 北京 100871

TAN Ying1,2, ZHENG Shaoqiu1,2
1. Key Laboratory of Machine Perception, Peking University, Beijing 100871, China ;
2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Abstract: Fireworks algorithm (FWA) has shown great successes in dealing with complex optimization problems and has attracted a great amount of attention recently. In this paper, FWA was completely analyzed, Including the FWA background evaluation, the study of fundamental principles of FWA, developments in single objective FWA optimization, hybrid algorithms, multi-objective fireworks algorithm, graphic processing unit(GPU) based parallel fireworks algorithm, and their applications in practice. For single objective FWA and improved and hybrid algorithms, the mechanism analysis and comparative research of various improved FWAs are given in this paper. Finally, the future research directions for FWA are pointed out, which include the analysis of explosion operator, study of interaction strategies among the fireworks, research on multi-objective fireworks algorithm and parallel fireworks algorithm, types of solutions to the extended FWA, and application expansion.
Key words: swarm intelligence     fireworks algorithm     explosion amplitude     adaptive explosion amplitude     dynamic search strategy     multi-objective fireworks algorithm     parallel implementation

1 烟花算法 1.1 动机

 图 1 真实的烟花爆炸和优化问题解搜索过程对比示意 Fig. 1 Comparison between fireworks explosion and solution search for optimization problem

1.2 算法框架

 图 2 烟花算法执行流程图 Fig. 2 Flowchart of fireworks algorithm

1)在可行解空间中随机产生一定数量的烟花，每个烟花代表解空间中的一个可行解。

2)根据优化目标函数计算每个烟花的适应度值，并据此确定烟花质量的好坏，以在不同爆炸半径下产生不同数量的火花。在烟花算法中，作者使用了两种形式的火花，分别是爆炸火花和高斯变异火花。其中爆炸火花主要负责对烟花邻近区域的搜索，适应度值好的烟花在较小的邻近区域内产生较多的火花，反之，适应度值差的烟花在较大的邻近区域内产生较少的火花。相对于爆炸火花，高斯火花的引入增强了种群的多样性。

3)判定是否满足终止条件。如果满足则停止搜索，否则在爆炸火花、高斯变异火花和烟花中选择一定数量的个体作为烟花进入下一代的迭代。

1.3 算子分析

 (1)

1)爆炸算子

 (2)
 (3)

 (4)

2)变异算子

 (5)

 (6)

3)选择策略

 (7)
 (8)

1)参数初始化

2)循环如下的(1)~(4)，直到满足终止条件。

(1)//评估每个烟花适应度值，计算每个烟花爆炸半径和爆炸火花数

fori=1 to N do

endfor

(2)//产生爆炸火花

for i=1 to N do

for j=1 to Si do

z=round(D×U(0, 1))，Dxi的维数(U(a, b)表示为在区间[a, b]中产生服从均匀分布的随机数的值)；

 计算位置偏移 ; (1)

for each kin DS

 ； (2)

endfor

endfor

endfor

(3)//产生 个高斯变异火花

for i =1 to do

z=round(D×U(0, 1))，Dxi的维数；

for each kin DS

 (3)

endfor

endfor

(4)从烟花、爆炸火花、高斯变异火花种群中选择N个个体作为下一代迭代计算的烟花；

3)返回优化结果。

1.4 与遗传算法、粒子群优化算法搜索机制比较

2 几种典型的改进烟花算法

2.1 基于适应度函数估计的烟花算法

2.2 构造型烟花算法

2.3 增强烟花算法

Zheng S.等[28]对FWA的算子进行了细致的分析，针对FWA的缺陷进行了改进，包括最小爆炸半径检测、爆炸火花产生方式、映射规则、高斯变异算子和选择策略，提出了增强型烟花算法(EFWA)。

2.3.1 最小爆炸半径检测

 (9)

 (10)

2.3.2 爆炸火花产生方式

2.3.3 映射规则

 (11)

 (12)

(式中：xUB, kxLB, k为可行区域在维度k上的上边界和下边界。

2.3.4 高斯变异算子

 (13)

2.3.5 选择策略

2.4 动态搜索烟花算法和自适应烟花算法

2.4.1 动态搜索烟花算法

2.4.2 自适应烟花算法

1)该个体的适应度值比上代的烟花差；

2)该个体是满足条件1)的个体中距离最优个体最近的。

2.5 差分演化—烟花混合算法

 (14)

2.6 文化-烟花混合算法

2.7 生物地理学优化-烟花混合算法

Zhang等[37]将生物地理学优化(BBO)算法和增强烟花算法(EFWA)进行混合——BBO-FWA，提高了烟花之间的交互能力。BBO提供了一种根据个体的适应度值，以概率将个体的某些维的值进行交叉迁移的方法。

2.8 改进型单目标烟花算法性能

CEC2005，包含25个测试函数[38]

CEC2013，包含28个测试函数[39]

CEC2014，包含30个测试函数[40]

3 多目标烟花算法

MOFWA使用的SPEA-II[16]方法中的适应度值计算方法。在SPEA-II方法中，对于当前种群中，无论是支配解还是非支配解，其解的强度值是由这个解支配其他解的数目和这个解的浓度决定的。关于档案维护方法，MOFWA使用文献[45]提出的档案维护方法。在档案更新过程中，首先确定支配关系，移除被支配的解，如果仍旧达到档案大小的上限则移除距离最近的一对点中的一个。

MOFOA执行流程如下：首先，初始化N个烟花，每个烟花产生爆炸火花和高斯变异火花。然后，使用产生的火花(包括爆炸火花、高斯变异火花)更新档案。从烟花和火花中选择一定数量的个体组成一个新的群体P，对于P中的每个个体分别执行变异算子、交叉算子和选择算子得到新的群体P′作为下一代烟花算法的种群。算法迭代执行直到满足终止条件。

 年份 算法名称 算法改进思想与机制 性能验证 对比算法及性能 2010 FWA — 11个函数组成测试集合 对比了CPSO[42]、SPSO[43]，在函数优化结果的均值上FWA具有更优的性能 2011 CA-FWA 文化算法和烟花算法混合，改变了烟花算法中爆炸火花产生方式和选择策略 滤波器设计优化问题 对比了AQPSO[34]和QPSO[35]算法，具有更优的性能 2012 AcFWA 利用候选者集合中的位置信息和适应度值信息估计搜索空间形状，生成精英解，引入到烟花种群作为启发式信息。 CEC2005前10个函数 对于FWA，t检验显示改进有效 2012 FWA-DE 差分演化算法和烟花算法混合 由6个函数组成的测试集合 对比了FWA、DE，对比算法优化最优解的成功率，显示改进有效 2013 IFWA 根据烟花算法思想，适应度值好的烟花在更小的爆炸半径内产生更多的爆炸火花，IFWA引入一种新型的爆炸半径和爆炸火花数目计算方式。 CEC2005前14个函数 对比了FWA、PSO算法，在函数优化结果的均值上IFWA具有更优的性能 2013 EFWA 细致分析了烟花算法的算子，并针对算子存在的缺陷提出了相应的改进策略。 由12个函数组成的测试集合 对比了FWA、SPSO算法，t检验结果显示对于FWA算法改进有效，EFWA算法相对于SPSO2007算法局部搜索能力不佳 2014 dynFWA 针对适应度值最优的烟花引入了动态搜索爆炸半径策略。 CEC2013 对比了EFWA算法，Wilcoxon符号秩检验显示对EFWA算法改进有效。对比了SP-SO2011算法，dynFWA平均均值排名更优 2014 AFWA 针对适应度值最优的烟花引入自适应爆炸半径策略。 CEC2013 对比了EFWA算法，t检验显示对EFWA算法改进有效。对比了SPSO2011、SPSO2007算法，AFWA平均均值排名更优 2014 FWA-DM 差分演化算法和烟花算法混合 CEC2014 — 2014 BBO-FWA 生物地理学优化算法和烟花算法混合 由13个函数组成的测试集合 对比了EFWA、BBO算法，在函数优化结果的均值上BBO-FWA具有更优的性能

4 基于GPU的并行烟花算法

5 应用

5.1 非负矩阵分解

1999年，Lee和Seung提出了著名的非负矩阵分解(NMF)算法[56]。NMF算法使用低秩、非负矩阵WH对目标矩阵A进行近似，即AWH。NMF是一个非线性优化函数，形式如下：

 (15)

5.2 图像识别

 (16)

5.3 滤波器设计

5.4 垃圾电子邮件检测

He等[53]提出使用烟花算法对基于局部免疫浓度特征提取方法和支持向量机分类方法进行垃圾电子邮件检测模型中的参数进行优化。实验结果表明，基于烟花算法优化得到的模型可以获得更高的准确率和F值，展示了烟花算法的优化能力。

5.5 施肥问题

5.6 配电网方案重构

Mohamed和Knowsalya[54]提出使用烟花算法进行配电网方案的优化计算。在配电网优化问题中，优化目标为尽量减少电量损耗同时使得电压偏差尽量低。在该优化问题中，解被编码为开转换向量。

6 未来发展方向

1)爆炸算子搜索机制的深入分析。烟花算法相对于其他典型的群体智能算法，如粒子群优化算法等，展现了一种新型的爆炸搜索机制，具有爆发性。怎样更好地将这种爆炸搜索机制应用到其他群体智能算法或应用问题建模求解上有待更深入的研究。

2)烟花交互机制研究。在烟花算法中，算法通过适应度值进行交互，包括爆炸火花数目和爆炸半径的计算。然而，dynFWA和AFWA的提出表明目前这种交互机制不是十分有效。dynFWA和AFWA算法性能的提升主要归结于适应度值最优的烟花的局部搜索能力加强，而种群中的烟花之间的交互机制并没有变化。因此，更有效的烟花交互机制亟待研究。

3)多目标烟花算法研究。目前，对于烟花算法的多目标研究工作并不多，而且在标准多目标测试集合上与其他典型多目标进化计算方法的比较还没有系统地开展。此外，烟花算法不同于其他群体智能算法，其典型爆炸搜索机制会使得烟花在其周围区域产生大量的爆炸火花，因此，需要研究和烟花算法契合的档案维护策略、适应度值计算方法等。

4)并行烟花算法研究。目前，对于并行化烟花算法的研究工作仅限于基本烟花算法，而烟花算法改进工作不断涌现，不同的改进算法对于并行化的研究工作提出了不同的要求。因此，对于特定的性能优异的烟花算法的并行化仍需投入精力。

5)扩展烟花算法求解的问题类型，使得烟花算法能够求解包括动态优化问题、约束优化问题、离散优化问题、自变量为离散连续混合变量的优化问题。因此，怎样依据连续烟花算法思想提出有效的求解不同类型优化问题的新型烟花算法是非常重要的。

6)应用拓展。将烟花算法应用到更广阔的领域，研究和挖掘烟花算法相对于其他群体智能算法所特有的在解决某些问题的自身固有优势。

7 结束语

DOI: 10.3969/j.issn.1673-4785.201409010

0

#### 文章信息

TAN Ying, ZHENG Shaoqiu