第9卷第5期 智能系统学报 Vol.9 No.5 2014年10月 CAAI Transactions on Intelligent Systems 0ct.2014 D0:10.3969/j.issn.1673-4785.201409010 烟花算法研究进展 谭营2，郑少秋2 (1.北京大学机器感知与智能教育部重点实验室，北京100871；2.北京大学信息科学与技术学院，北京100871) 摘要：烟花算法由于具有很强的优化问题求解的能力，近年来逐渐受到研究者的广泛关注。对现有烟花算法的研 究工作进行了全面总结，主要包括烟花算法提出的背景、烟花算法的基本原理、单目标烟花算法的改进、混合算法、 多目标烟花算法、基于GPU的并行烟花算法以及烟花算法在实际问题中的应用研究等。对于单目标烟花算法及改 进算法、混合算法，文中给出了各种改进烟花算法的机制分析和对比研究，最后，给出了烟花算法的未来研究方向， 包括爆炸算子搜索机制的深入分析、烟花交互机制研究，多目标烟花算法研究、并行烟花算法研究、扩展烟花算法求 解的问题类型以及应用拓展。 关键词：群体智能：烟花算法：爆炸半径：自适应爆炸半径；动态搜索机制：多目标烟花算法；并行实现 中图分类号：TP301文献标志码：A文章编号：1673-4785(2014)05-0515-14 中文引用格式：谭营，郑少秋.烟花算法研究进展[J].智能系统学报，2014,9(5)：515-528. 英文引用格式：TAN Ying,ZHENG Shaoqiu.Recent advances in fireworks algorithm[J].CAAI Transactions on Intelligent Sys- tes,2014,9(5):515-528. Recent advances in fireworks algorithm TAN Ying'.2,ZHENG Shaoqiu'.2 (1.Key Laboratory of Machine Perception,Peking University,Beijing 100871,China;2.School of Electronics Engineering and Com- puter 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 algo- rithms,the mechanism analysis and comparative research of various improved FWAs are given in this paper.Final- ly,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. Keywords:swarm intelligence;fireworks algorithm;explosion amplitude;adaptive explosion amplitude;dynamic search strategy;multi-objective fireworks algorithm;parallel implementation 近些年，科研工作者在群体智能算法的研究中 投入了大量精力，提出了许多新型算法和有效改进 方式，使得这一领域呈现出欣欣向荣的景象。关于 收稿日期：2014-09-05. 群体智能的定义，存在许多版本，例如：G.Beni和J. 基金项目：国家自然科学基金资助项目(61375119、61170057、 Wang指出群体智能是由具有自组织能力的个体通 60875080). 通信作者：谭营.E-mail:ytan@pku.edu.cn 过组合从而表现出群体的行为的特性②)
第 ９ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．５ ２０１４ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０９０１０ 烟花算法研究进展 谭营１， ２ ，郑少秋１， ２ （１．北京大学 机器感知与智能教育部重点实验室，北京 １００８７１； ２．北京大学 信息科学与技术学院，北京 １００８７１） 摘 要：烟花算法由于具有很强的优化问题求解的能力，近年来逐渐受到研究者的广泛关注。 对现有烟花算法的研 究工作进行了全面总结，主要包括烟花算法提出的背景、烟花算法的基本原理、单目标烟花算法的改进、混合算法、 多目标烟花算法、基于 ＧＰＵ 的并行烟花算法以及烟花算法在实际问题中的应用研究等。 对于单目标烟花算法及改 进算法、混合算法，文中给出了各种改进烟花算法的机制分析和对比研究，最后，给出了烟花算法的未来研究方向， 包括爆炸算子搜索机制的深入分析、烟花交互机制研究、多目标烟花算法研究、并行烟花算法研究、扩展烟花算法求 解的问题类型以及应用拓展。 关键词：群体智能；烟花算法；爆炸半径；自适应爆炸半径；动态搜索机制；多目标烟花算法；并行实现 中图分类号： ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０５⁃０５１５⁃１４ 中文引用格式：谭营，郑少秋． 烟花算法研究进展［Ｊ］． 智能系统学报， ２０１４， ９（５）： ５１５⁃５２８． 英文引用格式：ＴＡＮ Ｙｉｎｇ， ＺＨＥＮＧ Ｓｈａｏｑｉｕ． Ｒｅｃｅｎｔ ａｄｖａｎｃｅｓ ｉｎ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓ⁃ ｔｅｍｓ， ２０１４， ９（５）： ５１５⁃５２８． Ｒｅｃｅｎｔ ａｄｖａｎｃｅｓ ｉｎ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ ＴＡＮ Ｙｉｎｇ １， ２ ， ＺＨＥＮＧ Ｓｈａｏｑｉｕ １， ２ （１． Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｍａｃｈｉｎｅ Ｐｅｒｃｅｐｔｉｏｎ， Ｐｅｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １００８７１， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍ⁃ ｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｐｅｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １００８７１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ （ ＦＷＡ） ｈａｓ ｓｈｏｗｎ ｇｒｅａｔ ｓｕｃｃｅｓｓｅｓ ｉｎ ｄｅａｌｉｎｇ ｗｉｔｈ ｃｏｍｐｌｅｘ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ ａｎｄ ｈａｓ ａｔｔｒａｃｔｅｄ ａ ｇｒｅａｔ ａｍｏｕｎｔ ｏｆ ａｔｔｅｎｔｉｏｎ ｒｅｃｅｎｔｌｙ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ＦＷＡ ｗａｓ ｃｏｍｐｌｅｔｅｌｙ ａｎａｌｙｚｅｄ， Ｉｎｃｌｕｄｉｎｇ ｔｈｅ ＦＷＡ ｂａｃｋｇｒｏｕｎｄ ｅｖａｌｕａｔｉｏｎ， ｔｈｅ ｓｔｕｄｙ ｏｆ ｆｕｎｄａｍｅｎｔａｌ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ＦＷＡ， ｄｅｖｅｌｏｐｍｅｎｔｓ ｉｎ ｓｉｎｇｌｅ ｏｂｊｅｃｔｉｖｅ ＦＷＡ ｏｐｔｉｍｉｚａｔｉｏｎ， ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍｓ， ｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ， ｇｒａｐｈｉｃ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ（ＧＰＵ） ｂａｓｅｄ ｐａｒａｌｌｅｌ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ， ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎｓ ｉｎ ｐｒａｃｔｉｃｅ． Ｆｏｒ ｓｉｎｇｌｅ ｏｂｊｅｃｔｉｖｅ ＦＷＡ ａｎｄ ｉｍｐｒｏｖｅｄ ａｎｄ ｈｙｂｒｉｄ ａｌｇｏ⁃ ｒｉｔｈｍｓ， ｔｈｅ ｍｅｃｈａｎｉｓｍ ａｎａｌｙｓｉｓ ａｎｄ ｃｏｍｐａｒａｔｉｖｅ ｒｅｓｅａｒｃｈ ｏｆ ｖａｒｉｏｕｓ ｉｍｐｒｏｖｅｄ ＦＷＡｓ ａｒｅ ｇｉｖｅｎ ｉｎ ｔｈｉｓ ｐａｐｅｒ． Ｆｉｎａｌ⁃ ｌｙ， ｔｈｅ ｆｕｔｕｒｅ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎｓ ｆｏｒ ＦＷＡ ａｒｅ ｐｏｉｎｔｅｄ ｏｕｔ， ｗｈｉｃｈ ｉｎｃｌｕｄｅ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｅｘｐｌｏｓｉｏｎ ｏｐｅｒａｔｏｒ， ｓｔｕｄｙ ｏｆ ｉｎｔｅｒａｃｔｉｏｎ ｓｔｒａｔｅｇｉｅｓ ａｍｏｎｇ ｔｈｅ ｆｉｒｅｗｏｒｋｓ， ｒｅｓｅａｒｃｈ ｏｎ ｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ ａｎｄ ｐａｒａｌｌｅｌ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ， ｔｙｐｅｓ ｏｆ ｓｏｌｕｔｉｏｎｓ ｔｏ ｔｈｅ ｅｘｔｅｎｄｅｄ ＦＷＡ， ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｅｘｐａｎｓｉｏｎ． Ｋｅｙｗｏｒｄｓ：ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ； ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ； ｅｘｐｌｏｓｉｏｎ ａｍｐｌｉｔｕｄｅ； ａｄａｐｔｉｖｅ ｅｘｐｌｏｓｉｏｎ ａｍｐｌｉｔｕｄｅ； ｄｙｎａｍｉｃ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ； ｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ； ｐａｒａｌｌｅｌ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ 收稿日期：２０１４⁃０９⁃０５． 基金 项 目： 国 家 自 然 科 学 基 金 资 助 项 目 （ ６１３７５１１９、 ６１１７００５７、 ６０８７５０８０）． 通信作者：谭营． Ｅ⁃ｍａｉｌ：ｙｔａｎ＠ ｐｋｕ．ｅｄｕ．ｃｎ． 近些年，科研工作者在群体智能算法的研究中 投入了大量精力，提出了许多新型算法和有效改进 方式，使得这一领域呈现出欣欣向荣的景象。 关于 群体智能的定义，存在许多版本，例如：Ｇ． Ｂｅｎｉ 和 Ｊ． Ｗａｎｇ 指出群体智能是由具有自组织能力的个体通 过组 合 从 而 表 现 出 群 体 的 行 为 的 特 性［１⁃２］
·516· 智能系统学报 第9卷 Bonabeau、Dorigo和Theraulaz在《群体智能一从 进展，因此，本文将对烟花算法进行了全面的综述。 自然到人工系统》书中指出群体智能是简单的个体 1烟花算法 通过通信、协作等交互机制表现出群体智能行 为[)。Kennedy等指出群体智能是简单的具有信息 1.1动机 处理能力的单元在交互过程中表现出简单个体不具 燃放烟花爆竹是中国传统节日尤其是除夕的一 有的能够解决复杂问题的一种能力)。Lu等指出 项重要节日庆祝活动。在这一天，成千上万的烟花 群体智能是简单自制的代理单元展现出的集体的智 爆竹在夜空中爆炸并绽放美丽的图案。通常，在市 能行为)。Krause等指出群体智能是两个或多个 场上，不同价格的烟花爆炸产生不同的效果。一般 个体独立地或者部分独立地获取信息，信息的差异 价格高昂（低廉）的烟花产生的火花数量比较多 通过个体的交互被组合或处理，然后产生区别于单 (少)，爆炸产生的火花分布的范围也较均匀（分 个个体能够产生的解决方案[6。总之，群体智能就 散)。受到烟花在夜空中爆炸产生火花并照亮周围 是简单个体通过协作达到了拥有简单个体不具有的 区域这一自然现象的启发，Tan和Zhu在2010年提 问题解决能力。 出了烟花算法(FWA)[]。 在群体智能算法的发展过程中，比较重要的里 点燃的烟花被发射到夜空中，爆炸产生火花继 程碑事件有：l987年，Craig Reynolds提出了一个使 而照亮其临近的夜空，产生出一幅美丽的图案。事 用计算机模拟鸟飞行的模型)1；1991年，Dogo根 实上，一个优化问题的求解过程亦是如此。对于一 据对自然界中蚁群觅食这一群体行为的观察研究提 个最优化问题，尤其自变量是连续空间的最优化问 出了蚁群优化算法[s】;I995年Kennedy和Eberhart 题，在整个解空间内，如何有效迅速地找到全局最优 根据对鸟群觅食这一群体行为的观察提出了粒子群 解呢？在烟花算法中，烟花被看作为最优化问题的 优化算法[)。蚁群算法、粒子群优化算法发展过程 解空间中一个可行解，那么烟花爆炸产生一定数量 中表现出强大的问题求解能力将群体智能的研究推 火花的过程即为其搜索邻域的过程，如图1所示。 向了一个高潮，吸引了大量的科研工作者投入到群 体智能领域进行研究。 群体智能算法模拟简单个体通过协作求解复杂 问题的过程，具有以下特点[o:1)组成群体的个体 通常行为、能力都较为简单，个体之间无差别：2)个 体通过协作完成复杂问题的求解，群体中无中心控 制个体。 近年来，群体智能算法的研究内容主要包括： 1)已有的群体智能算法性能的提高，比如研究蚁群 优化算法、粒子群优化算法的收敛性加速策略、自适 应策略等[)]：2)新型群体智能算法的提出[；3) (a)单个烟花爆炸产生火花 多目标群体智能算法研究，目前大部分有影响力的 群体智能算法都有了其多目标算法的版本，例如 NSGA-s、SPEA-I6)、NSPS0等：4)并行化群 体智能算法研究，比如基于图像处理单元(GPU)的 粒子群优化算法)、基于GPU的烟花算法)、基 于GPU的遗传算法[20]等：5)应用研究，尝试将群体 智能算法应用到更多更广阔的领域。 自2000年以来，一系列新型群体智能算法相继 被提出[)。在2010年，Tan和Zhu根据对于烟花爆 炸产生火花这一自然现象的观察提出了烟花算法。 (b)优化问题搜索过程 尽管文献[21]对烟花算法的部分研究工作进行了 图1真实的烟花爆炸和优化问题解搜索过程对比示意 简要总结，但是文献[21]总结的工作较为初步，尤 Fig.1 Comparison between fireworks explosion and so- 其是近一年来烟花算法的研究工作取得了一些新的 lution search for optimization problem
Ｂｏｎａｂｅａｕ、Ｄｏｒｉｇｏ 和 Ｔｈｅｒａｕｌａｚ 在《群体智能———从 自然到人工系统》书中指出群体智能是简单的个体 通过通 信、 协 作 等 交 互 机 制 表 现 出 群 体 智 能 行 为［３］ 。 Ｋｅｎｎｅｄｙ 等指出群体智能是简单的具有信息 处理能力的单元在交互过程中表现出简单个体不具 有的能够解决复杂问题的一种能力［４］ 。 Ｌｉｕ 等指出 群体智能是简单自制的代理单元展现出的集体的智 能行为［５］ 。 Ｋｒａｕｓｅ 等指出群体智能是两个或多个 个体独立地或者部分独立地获取信息，信息的差异 通过个体的交互被组合或处理，然后产生区别于单 个个体能够产生的解决方案［６］ 。 总之，群体智能就 是简单个体通过协作达到了拥有简单个体不具有的 问题解决能力。 在群体智能算法的发展过程中，比较重要的里 程碑事件有：１９８７ 年，Ｃｒａｉｇ Ｒｅｙｎｏｌｄｓ 提出了一个使 用计算机模拟鸟飞行的模型［７］ ；１９９１ 年，Ｄｏｒｉｇｏ 根 据对自然界中蚁群觅食这一群体行为的观察研究提 出了蚁群优化算法［８］ ；１９９５ 年 Ｋｅｎｎｅｄｙ 和 Ｅｂｅｒｈａｒｔ 根据对鸟群觅食这一群体行为的观察提出了粒子群 优化算法［９］ 。 蚁群算法、粒子群优化算法发展过程 中表现出强大的问题求解能力将群体智能的研究推 向了一个高潮，吸引了大量的科研工作者投入到群 体智能领域进行研究。 群体智能算法模拟简单个体通过协作求解复杂 问题的过程，具有以下特点［１０］ ：１）组成群体的个体 通常行为、能力都较为简单，个体之间无差别；２）个 体通过协作完成复杂问题的求解，群体中无中心控 制个体。 近年来，群体智能算法的研究内容主要包括： １）已有的群体智能算法性能的提高，比如研究蚁群 优化算法、粒子群优化算法的收敛性加速策略、自适 应策略等［１１⁃ １３］ ；２）新型群体智能算法的提出［１４］ ；３） 多目标群体智能算法研究，目前大部分有影响力的 群体智能算法都有了其多目标算法的版本，例如 ＮＳＧＡ⁃ＩＩ ［１５］ 、ＳＰＥＡ⁃ＩＩ ［１６］ 、ＮＳＰＳＯ ［１７］ 等；４） 并行化群 体智能算法研究，比如基于图像处理单元（ＧＰＵ）的 粒子群优化算法［１８］ 、基于 ＧＰＵ 的烟花算法［１９］ 、基 于 ＧＰＵ 的遗传算法［２０］等；５）应用研究，尝试将群体 智能算法应用到更多更广阔的领域。 自 ２０００ 年以来，一系列新型群体智能算法相继 被提出［１４］ 。 在 ２０１０ 年，Ｔａｎ 和 Ｚｈｕ 根据对于烟花爆 炸产生火花这一自然现象的观察提出了烟花算法。 尽管文献［２１］对烟花算法的部分研究工作进行了 简要总结，但是文献［２１］总结的工作较为初步，尤 其是近一年来烟花算法的研究工作取得了一些新的 进展，因此，本文将对烟花算法进行了全面的综述。 １ 烟花算法 １．１ 动机 燃放烟花爆竹是中国传统节日尤其是除夕的一 项重要节日庆祝活动。 在这一天，成千上万的烟花 爆竹在夜空中爆炸并绽放美丽的图案。 通常，在市 场上，不同价格的烟花爆炸产生不同的效果。 一般 价格高昂（低廉） 的烟花产生的火花数量比较多 （少），爆炸产生的火花分布的范围也较均匀（ 分 散）。 受到烟花在夜空中爆炸产生火花并照亮周围 区域这一自然现象的启发， Ｔａｎ 和 Ｚｈｕ 在 ２０１０ 年提 出了烟花算法（ＦＷＡ） ［２２］ 。 点燃的烟花被发射到夜空中，爆炸产生火花继 而照亮其临近的夜空，产生出一幅美丽的图案。 事 实上，一个优化问题的求解过程亦是如此。 对于一 个最优化问题，尤其自变量是连续空间的最优化问 题，在整个解空间内，如何有效迅速地找到全局最优 解呢？ 在烟花算法中，烟花被看作为最优化问题的 解空间中一个可行解，那么烟花爆炸产生一定数量 火花的过程即为其搜索邻域的过程，如图 １ 所示。 （ａ） 单个烟花爆炸产生火花 （ｂ） 优化问题搜索过程 图 １ 真实的烟花爆炸和优化问题解搜索过程对比示意 Ｆｉｇ．１ Ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ ｆｉｒｅｗｏｒｋｓ ｅｘｐｌｏｓｉｏｎ ａｎｄ ｓｏ⁃ ｌｕｔｉｏｎ ｓｅａｒｃｈ ｆｏｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ·５１６· 智 能 系 统 学 报 第 ９ 卷
第5期 谭营，等：烟花算法研究进展 .517. 为了能够有效地进行搜索，这里要求解空间中 一定数量的个体作为烟花进入下一代的迭代。 解的邻域有意义，同时需要保证在某一有限的范围 烟花算法具有局部搜索能力和全局搜索能力自 内，解和其邻域的其他解具有相似的性质一“靠 调节机制。烟花算法中每个烟花的爆炸半径和爆炸 近是一种性质”[2]。这个要求是烟花算法应用于优 火花数是不同的，适应度值差的烟花的爆炸半径较 化求解的有效性关键，因此在实际使用烟花算法求 大，使其具有更大的“探索能力”—勘探性。适应 解优化问题时，在问题建模和解的编码过程中，无论 度值好的烟花的爆炸半径较小，使其能够在该位置 是离散编码还是连续编码都需要满足这一个基本条 周围具有更大的“挖掘能力”一开采性。此外，高 件。此外，烟花种群中各个烟花根据相对于其他烟 斯变异火花的引入可以进一步增加种群的多样性。 花的适应度值进行资源分配和信息交互使得整个种 文献[24]给出了一个关于烟花的爆炸半径和爆炸 群能够在全局搜索能力和局部搜索能力之间达到一 火花数目对于烟花算法性能的影响的简要分析。 个平衡，而且烟花的爆炸搜索机制使得单个烟花具 1.3算子分析 有很强的局部爆发性。因此，烟花算法中烟花之间 不失一般性，假设待求解的优化问题形式如下： 进行的资源的交互（爆炸火花数目和爆炸半径）使 Min f(x)∈R,x∈2 (1) 得烟花算法成为一种新型的群体智能算法。 式中：2为解的可行域。 1.2 算法框架 使用烟花算法对优化问题(1)进行求解的目标 烟花算法的算法执行流程如图2所示。 是在可行域2内，寻找一点x,使得x具有全局最 初始化N个位置 小的适应度值。 在烟花算法中，爆炸算子（即爆炸产生火花操 在N个位置释放烟花 作)、变异算子（高斯变异产生火花操作）和选择策 略（即选择下一代烟花操作）是最重要的3个组成 获得爆炸火花 部分，直接决定烟花算法的性能优劣。 和高斯火花 1)爆炸算子 在可行域2内初始化一定数量烟花，对烟花位 置的适应度值进行评估。为了差异化不同位置的烟 是否满足 终止条件 花，一般适应度值较好（即适应度值较小）的烟花能 够获取更多的资源，在较小的范围内产生更多的火 N 花，具有对于该烟花位置的强大的局部搜索能力。 选择W个位置 结束 反之，适应度值较大的烟花只能获取相对较少的资 源，在较大的范围内产生数量较少的火花，具有一定 图2烟花算法执行流程图 的全局搜索能力。 Fig.2 Flowchart of fireworks algorithm 为了达到烟花差异化的目的，即开采性和勘探 烟花算法具体包括以下几个步骤： 性兼顾的目标，在烟花算法中，每个烟花的爆炸半径 1)在可行解空间中随机产生一定数量的烟花， 和爆炸产生的火花数目是根据其相对于烟花种群中 每个烟花代表解空间中的一个可行解。 其他烟花适应度值计算得到的。对于烟花x:,其爆 2)根据优化目标函数计算每个烟花的适应度 炸半径A,和爆炸火花数目S,的计算公式分别为 值，并据此确定烟花质量的好坏，以在不同爆炸半径 下产生不同数量的火花。在烟花算法中，作者使用 A:=A× f(x:）-ymin+e (2) 了两种形式的火花，分别是爆炸火花和高斯变异火 )-)+e 花。其中爆炸火花主要负责对烟花邻近区域的搜 索，适应度值好的烟花在较小的邻近区域内产生较 S:=M×- ymx-f(x:）+& (3) 多的火花，反之，适应度值差的烟花在较大的邻近区 -)+8 域内产生较少的火花。相对于爆炸火花，高斯火花 式中：ym=min(f(x),(i=1,2,…,N)为当前烟 的引入增强了种群的多样性。 花种群中适应度最小值，ym=max(f代x:),(i=1, 3)判定是否满足终止条件。如果满足则停止 2,…,N)是当前烟花种群中适应度最大值。A是一 搜索，否则在爆炸火花、高斯变异火花和烟花中选择 常数，用来调整爆炸半径大小，M是一常数，用来调
为了能够有效地进行搜索，这里要求解空间中 解的邻域有意义，同时需要保证在某一有限的范围 内，解和其邻域的其他解具有相似的性质———“靠 近是一种性质” ［２３］ 。 这个要求是烟花算法应用于优 化求解的有效性关键，因此在实际使用烟花算法求 解优化问题时，在问题建模和解的编码过程中，无论 是离散编码还是连续编码都需要满足这一个基本条 件。 此外，烟花种群中各个烟花根据相对于其他烟 花的适应度值进行资源分配和信息交互使得整个种 群能够在全局搜索能力和局部搜索能力之间达到一 个平衡，而且烟花的爆炸搜索机制使得单个烟花具 有很强的局部爆发性。 因此，烟花算法中烟花之间 进行的资源的交互（爆炸火花数目和爆炸半径） 使 得烟花算法成为一种新型的群体智能算法。 １．２ 算法框架 烟花算法的算法执行流程如图 ２ 所示。 图 ２ 烟花算法执行流程图 Ｆｉｇ．２ Ｆｌｏｗｃｈａｒｔ ｏｆ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ 烟花算法具体包括以下几个步骤： １）在可行解空间中随机产生一定数量的烟花， 每个烟花代表解空间中的一个可行解。 ２）根据优化目标函数计算每个烟花的适应度 值，并据此确定烟花质量的好坏，以在不同爆炸半径 下产生不同数量的火花。 在烟花算法中，作者使用 了两种形式的火花，分别是爆炸火花和高斯变异火 花。 其中爆炸火花主要负责对烟花邻近区域的搜 索，适应度值好的烟花在较小的邻近区域内产生较 多的火花，反之，适应度值差的烟花在较大的邻近区 域内产生较少的火花。 相对于爆炸火花，高斯火花 的引入增强了种群的多样性。 ３）判定是否满足终止条件。 如果满足则停止 搜索，否则在爆炸火花、高斯变异火花和烟花中选择 一定数量的个体作为烟花进入下一代的迭代。 烟花算法具有局部搜索能力和全局搜索能力自 调节机制。 烟花算法中每个烟花的爆炸半径和爆炸 火花数是不同的，适应度值差的烟花的爆炸半径较 大，使其具有更大的“探索能力”———勘探性。 适应 度值好的烟花的爆炸半径较小，使其能够在该位置 周围具有更大的“挖掘能力”———开采性。 此外，高 斯变异火花的引入可以进一步增加种群的多样性。 文献［２４］给出了一个关于烟花的爆炸半径和爆炸 火花数目对于烟花算法性能的影响的简要分析。 １．３ 算子分析 不失一般性，假设待求解的优化问题形式如下： Ｍｉｎ ｆ（ｘ） ∈ Ｒ，ｘ ∈ Ω （１） 式中： Ω 为解的可行域。 使用烟花算法对优化问题（１）进行求解的目标 是在可行域 Ω 内，寻找一点 ｘ → ，使得 ｘ → 具有全局最 小的适应度值。 在烟花算法中，爆炸算子（即爆炸产生火花操 作）、变异算子（高斯变异产生火花操作）和选择策 略（即选择下一代烟花操作）是最重要的 ３ 个组成 部分，直接决定烟花算法的性能优劣。 １）爆炸算子 在可行域 Ω 内初始化一定数量烟花，对烟花位 置的适应度值进行评估。 为了差异化不同位置的烟 花，一般适应度值较好（即适应度值较小）的烟花能 够获取更多的资源，在较小的范围内产生更多的火 花，具有对于该烟花位置的强大的局部搜索能力。 反之，适应度值较大的烟花只能获取相对较少的资 源，在较大的范围内产生数量较少的火花，具有一定 的全局搜索能力。 为了达到烟花差异化的目的，即开采性和勘探 性兼顾的目标，在烟花算法中，每个烟花的爆炸半径 和爆炸产生的火花数目是根据其相对于烟花种群中 其他烟花适应度值计算得到的。 对于烟花 ｘｉ ，其爆 炸半径 Ａｉ 和爆炸火花数目 Ｓｉ 的计算公式分别为 Ａｉ ＝ Ａ ＾ × ｆ（ｘｉ） － ｙｍｉｎ ＋ ε ∑ Ｎ ｉ ＝ １ （ｆ（ｘｉ） － ｙｍｉｎ ） ＋ ε （２） Ｓｉ ＝ Ｍ × ｙｍａｘ － ｆ（ｘｉ） ＋ ε ∑ Ｎ ｉ ＝ １ （ｙｍａｘ － ｆ（ｘｉ）） ＋ ε （３） 式中： ｙｍｉｎ ＝ ｍｉｎ（ｆ（ｘｉ）） ，（ｉ ＝ １，２，…，Ｎ） 为当前烟 花种群中适应度最小值， ｙｍａｘ ＝ ｍａｘ（ｆ（ｘｉ）），（ｉ ＝ １， ２，…，Ｎ） 是当前烟花种群中适应度最大值。 Ａ ＾ 是一 常数，用来调整爆炸半径大小， Ｍ 是一常数，用来调 第 ５ 期 谭营，等：烟花算法研究进展 ·５１７·
·518. 智能系统学报 第9卷 整产生的爆炸火花数目大小，￡是一个机器最小量， 的个体之间的距离之和。在候选者集合中，如果个 用来避免除零操作。 体密度较高，即该个体周围有很多其他候选者个体 在式(3)中，为了限制适应度值好的烟花位置 时，该个体被选择的概率会降低。 不会产生过多的爆炸火花，同时适应度值差的烟花 基于前面的叙述，烟花算法的具体执行如下： 位置不会产生过少的火花粒子，文献[22]对于产生 1)参数初始化 的火花个数进行了如下的限制： 随机在解空间初始化N个位置x:,即N个烟 S;= 花。 2)循环如下的(1)~(4)，直到满足终止条件。 round(a M),S;aM (1)/评估每个烟花适应度值，计算每个烟花 round(b*M),S;>bM,a <b 1 (4) 爆炸半径和爆炸火花数 round(S;),其他 for i=1 to N do 式中：a、b是两个常数，round(·)是根据四舍五入 计算每个烟花的适应度值f(x:); 原则的取整函数。 计算每个烟花的爆炸半径A:和产生的爆炸火 2)变异算子 花数目S:; 为了增加爆炸火花种群的多样性，烟花算法引 endfor 入了变异算子用于产生变异火花，即高斯变异火花。 (2)/产生爆炸火花 高斯变异火花产生的过程如下：首先在烟花种群中 for i 1 to N do 随机选择一个烟花x:,然后对该烟花随机选择一定 for j=1 to S;do 数量的维度进行高斯变异操作。对于烟花x:的某 x:=x:; 一个选择得到的维度k执行高斯变异操作即为 随机选择z个维度作为集合DS, x法=x法Xe (5) z=round(D×U(0,1)),D为x:的维数(U(a, 式中：e~N(1,1),N(1,1)表示均值为1，方差为 b)表示为在区间[a,b]中产生服从均匀分布的随 1的高斯分布。 机数的值)： 在爆炸算子和变异算子分别产生爆炸火花和高 计算位置偏移h=A,×U(-1,1); 斯变异火花过程中，可能产生的火花会超出可行域 for each k in DS 2的边界范围。当火花x:在维度k上超出边界，将 xk=xt十h; 通过式(6)的映射规则映射到一个新的位置。 越界检测： 元4=xB.+|x法|%(xB,k-X1B,） (6) endfor 式中：xB4、xB4为解空间在维度k上的上边界和 将x:保存到爆炸火花种群中； 下边界。 endfor 3)选择策略 endfor 为使烟花种群中优秀的信息能够传递到下一代 (3)/产生M个高斯变异火花 种群中，在产生爆炸火花和高斯变异火花后，算法会 for i=1 to Mdo 在候选者集合（包括烟花、爆炸火花和高斯变异火 花)中选择一定数量的个体作为下一代的烟花。 随机选择火花x:; 随机选择z个维度作为集合DS, 假设候选者集合为K,烟花种群大小为N。候 z=round(D×U(0,1)),D为x:的维数； 选者集合中适应度值最小的个体会被确定性地选择 计算高斯变异参数e=N(1,1)(产生矩阵为1， 到下一代作为烟花，而对剩下的N-1个烟花的选 方差为1的随机数)； 择使用轮盘赌的方法在候选者集合中进行选择。对 for each k in DS 于候选者x:,其被选择概率的计算公式为 xik=xik xe; R(x:) p(x:)= (7) 越界检测； endfor xEK R(x)=∑d(x-x)=∑‖x:-x (8) 将x保存到高斯变异火花种群中； endfor 式中：R(x:)为当前个体到候选者集合K除x:所有 (4)从烟花、爆炸火花、高斯变异火花种群中选
整产生的爆炸火花数目大小， ε 是一个机器最小量， 用来避免除零操作。 在式（３）中，为了限制适应度值好的烟花位置 不会产生过多的爆炸火花，同时适应度值差的烟花 位置不会产生过少的火花粒子，文献［２２］对于产生 的火花个数进行了如下的限制： Ｓ ＾ ｉ ＝ ｒｏｕｎｄ（ａ∗Ｍ），Ｓｉ ＜ ａＭ ｒｏｕｎｄ（ｂ∗Ｍ），Ｓｉ ＞ ｂＭ，ａ ＜ ｂ ＜ １ ｒｏｕｎｄ（Ｓｉ），其他 ì î í ï ï ïï （４） 式中： ａ、ｂ 是两个常数，ｒｏｕｎｄ（·）是根据四舍五入 原则的取整函数。 ２）变异算子 为了增加爆炸火花种群的多样性，烟花算法引 入了变异算子用于产生变异火花，即高斯变异火花。 高斯变异火花产生的过程如下：首先在烟花种群中 随机选择一个烟花 ｘｉ ，然后对该烟花随机选择一定 数量的维度进行高斯变异操作。 对于烟花 ｘｉ 的某 一个选择得到的维度 ｋ 执行高斯变异操作即为 ｘ ＾ ｉｋ ＝ ｘｉｋ × ｅ （５） 式中： ｅ ～ Ｎ（１，１） ， Ｎ（１，１） 表示均值为 １，方差为 １ 的高斯分布。 在爆炸算子和变异算子分别产生爆炸火花和高 斯变异火花过程中，可能产生的火花会超出可行域 Ω 的边界范围。 当火花 ｘｉ 在维度 ｋ 上超出边界，将 通过式（６）的映射规则映射到一个新的位置。 ｘ ＾ ｉｋ ＝ ｘＬＢ，ｋ ＋｜ ｘ ＾ ｉｋ ｜ ％（ｘＵＢ，ｋ － ｘＬＢ，ｋ） （６） 式中： ｘＵＢ，ｋ 、 ｘＬＢ，ｋ 为解空间在维度 ｋ 上的上边界和 下边界。 ３）选择策略 为使烟花种群中优秀的信息能够传递到下一代 种群中，在产生爆炸火花和高斯变异火花后，算法会 在候选者集合（包括烟花、爆炸火花和高斯变异火 花）中选择一定数量的个体作为下一代的烟花。 假设候选者集合为 Ｋ ，烟花种群大小为 Ｎ 。 候 选者集合中适应度值最小的个体会被确定性地选择 到下一代作为烟花，而对剩下的 Ｎ － １ 个烟花的选 择使用轮盘赌的方法在候选者集合中进行选择。 对 于候选者 ｘｉ ，其被选择概率的计算公式为 ｐ（ｘｉ） ＝ Ｒ（ｘｉ） ∑ｘｊ∈Ｋ ｘｊ （７） Ｒ（ｘｉ） ＝ ∑ｘｊ∈Ｋ ｄ（ｘｉ － ｘｊ） ＝ ∑ｘｊ∈Ｋ ‖ｘｉ － ｘｊ‖ （８） 式中： Ｒ（ｘｉ） 为当前个体到候选者集合 Ｋ 除 ｘｉ 所有 的个体之间的距离之和。 在候选者集合中，如果个 体密度较高，即该个体周围有很多其他候选者个体 时，该个体被选择的概率会降低。 基于前面的叙述，烟花算法的具体执行如下： １）参数初始化 随机在解空间初始化 Ｎ 个位置 ｘｉ ，即 Ｎ 个烟 花。 ２）循环如下的（１） ～ （４），直到满足终止条件。 （１） ／ ／ 评估每个烟花适应度值，计算每个烟花 爆炸半径和爆炸火花数 ｆｏｒ ｉ ＝ １ ｔｏ Ｎ ｄｏ 计算每个烟花的适应度值 ｆ（ｘｉ） ； 计算每个烟花的爆炸半径 Ａｉ 和产生的爆炸火 花数目 Ｓｉ ； ｅｎｄｆｏｒ （２） ／ ／ 产生爆炸火花 ｆｏｒ ｉ ＝ １ ｔｏ Ｎ ｄｏ ｆｏｒ ｊ ＝ １ ｔｏ Ｓｉ ｄｏ ｘ ＾ ｉ ＝ ｘｉ ； 随机选择 ｚ 个维度作为集合 ＤＳ， ｚ ＝ ｒｏｕｎｄ（Ｄ × Ｕ（０，１）） ， Ｄ 为 ｘｉ 的维数（ Ｕ（ａ， ｂ） 表示为在区间 ［ａ，ｂ］ 中产生服从均匀分布的随 机数的值）； 计算位置偏移 ｈ ＝ Ａｉ × Ｕ（ － １，１） ； ｆｏｒ ｅａｃｈ ｋ ｉｎ ＤＳ ｘ ＾ ｉｋ ＝ ｘｉｋ ＋ ｈ ； 越界检测； ｅｎｄｆｏｒ 将 ｘ ＾ ｉｋ 保存到爆炸火花种群中； ｅｎｄｆｏｒ ｅｎｄｆｏｒ （３） ／ ／ 产生 Ｍ ＾ 个高斯变异火花 ｆｏｒ ｉ ＝ １ ｔｏ Ｍ ＾ ｄｏ 随机选择火花 ｘｉ ； 随机选择 ｚ 个维度作为集合 ＤＳ， ｚ ＝ ｒｏｕｎｄ（Ｄ × Ｕ（０，１）） ， Ｄ 为 ｘｉ 的维数； 计算高斯变异参数 ｅ ＝ Ν（１，１） （产生矩阵为 １， 方差为 １ 的随机数）； ｆｏｒ ｅａｃｈ ｋ ｉｎ ＤＳ ｘ ＾ ｉｋ ＝ ｘｉｋ × ｅ ； 越界检测； ｅｎｄｆｏｒ 将 ｘ ＾ ｉｋ 保存到高斯变异火花种群中； ｅｎｄｆｏｒ （４）从烟花、爆炸火花、高斯变异火花种群中选 ·５１８· 智 能 系 统 学 报 第 ９ 卷
第5期 谭营，等：烟花算法研究进展 ·519· 择N个个体作为下一代迭代计算的烟花； 索烟花算法(dynFWA)和自适应烟花算法(AF 3)返回优化结果。 WA)。在dynFWA中，烟花爆炸半径的变化过程依 1.4与遗传算法、粒子群优化算法搜索机制比较 据烟花种群产生的火花适应度值是否发生改进（即 烟花算法相对于遗传算法和粒子群优化算法表 优化得到适应度值更优的火花)决定。在AFWA 现出了不同的搜索机制。在遗传算法中，染色体通 中，烟花的爆炸半径的确定依据当前种群适应度值 常被编码成一个优化问题的解，染色体之间通过交 最优的个体和一个特定个体之间的距离计算。这两 叉和变异操作产生新的解。在编码空间上，子代染 种方法由于采用了自适应调整爆炸半径的机制，都 色体和父代染色体具有相近的性质。粒子群优化算 大大提升了增强型烟花算法的性能。 法通过种群中的粒子间相互协作，每个粒子通过种 第2类算法改进的工作有：Zheng Y.等[3]提出 群中的全局最优信息和自身历史最优信息进行指导 使用差分演化算法和烟花算法进行混合的新型算法 搜索，进而更新粒子的位置。对于烟花算法，其主要 FWA-DE。Yu等[]用差分变异替换基本烟花算法 用于连续空间的优化问题求解，烟花算法采用爆炸 中的高斯变异，所提出的FWA-DM算法比EFWA算 搜索机制。此外，烟花之间通过交互机制来计算每 法的性能更好。Gao等[3]提出使用文化算法和烟 个烟花的爆炸半径和爆炸火花数目，使得适应度值 花算法进行混合的文化烟花算法(CA-FWA),并将 较好的烟花获取更多的资源，反之，适应度值较差的 文化烟花算法应用到滤波器的设计上，取得了相对 烟花获取较少的资源。烟花算法和遗传算法具有一 于量子粒子群优化算法(QPS0[])和自适应量子粒 些类似的地方，比如遗传算法可以通过变异概率的 子群优化算法(AQPS0])较优的性能。Zheng 大小在“编码空间”中产生一个相对于当前染色体 等]将生物地理学优化算法引入增强烟花算法，提 距离较远/近的解2]，而同样地，烟花算法可以通过 出混合算法BBO-WA,提高了烟花间的交互能力。 不同的爆炸半径大/小产生距离烟花较远/近的爆炸 2.1基于适应度函数估计的烟花算法 火花，烟花算法在迭代过程中，种群中每个烟花个体 进化计算加速策略研究是一个比较重要的研究 在一次迭代过程中会产生多个个体，而粒子群优化 方向。1999年，Takagi等36提出对于一个简单的单 算法通常只产生一个个体，烟花算法的这种爆炸机 峰优化问题求解，可以通过进化算法优化的解信息 制使得其对于烟花附近的区域的搜索更加彻底。 去估计搜索空间形状，然后对估计得到的简单曲面 2几种典型的改进烟花算法 求解其最优值位置并引入到种群中作为启发式信息 来加速搜索过程。基于此，在烟花算法中，在每一代 烟花算法自提出后就受到了诸多科研工作者的 烟花产生爆炸火花和高斯变异火花以后，Pi等[2 关注，许多改进算法相继被提出。改进烟花算法主 尝试使用当前种群的候选者集合（烟花、爆炸火花 要可以被分为两类，一类是在基本烟花算法的基础 和高斯变异火花)的位置信息和适应度值信息去估 上进行算子的分析和改进，另一类是与其他启发式 计整个搜索空间的形状，然后根据估计得到的形状 算法的混合算法的研究。 等作为启发式信息。 第一类算法改进的工作主要有：Pei等]提出 文献[26]讨论了3种不同的抽样策略：基于适 基于适应度函数估计的加速型烟花算法(AcFWA)。 应度值的抽样策略，即在候选者集合中选择k个适 AcFWA使用烟花及其产生的爆炸火花、高斯变异火 应度值最好的样本个体：基于距离的抽样策略，即在 花种群的位置信息和适应度值信息来估计搜索空间 候选者集合中选择欧式距离上离最优点位置最近的 的形状，然后使用估计的形状的最优位置作为启发 k个样本个体：随机抽样策略，即随机从候选者集合 式信息引入到当前种群进行加速搜索。山等[)提 中选择k个样本个体。对于搜索空间的估计，文献 出一种构造型烟花算法(FWA),使用了一种新型 中将D维搜索空间投影到每一个维数上面，并使用 的烟花爆炸半径和爆炸火花数目的计算方式，相对 抽样得到的样本个体在该维度上的投影位置和适应 于基本烟花算法，获得了性能上的提升。Zheng S. 度值信息依据估计模型进行形状估计。 等[]对于基本烟花算法的爆炸算子、变异算子、选 在实验中，抽样点个数被设置成3、5和10，用 择策略和映射规则等进行了细致的分析，针对烟花 于研究抽样点个数对于算法性能的影响。对于通过 算法存在的缺陷进行了逐一改进，并提出了增强型 选择有限的样本点估计其搜索空间形状这一问题， 烟花算法(EFWA)。接着，Zheng S.等[9]和i 曲面估计形状的选择十分重要。文献中使用一次最 等[0]分别提出了两种自适应半径策略一动态搜 小二乘法、二次最小二乘法来研究模型的选择对于
择 Ｎ 个个体作为下一代迭代计算的烟花； ３）返回优化结果。 １．４ 与遗传算法、粒子群优化算法搜索机制比较 烟花算法相对于遗传算法和粒子群优化算法表 现出了不同的搜索机制。 在遗传算法中，染色体通 常被编码成一个优化问题的解，染色体之间通过交 叉和变异操作产生新的解。 在编码空间上，子代染 色体和父代染色体具有相近的性质。 粒子群优化算 法通过种群中的粒子间相互协作，每个粒子通过种 群中的全局最优信息和自身历史最优信息进行指导 搜索，进而更新粒子的位置。 对于烟花算法，其主要 用于连续空间的优化问题求解，烟花算法采用爆炸 搜索机制。 此外，烟花之间通过交互机制来计算每 个烟花的爆炸半径和爆炸火花数目，使得适应度值 较好的烟花获取更多的资源，反之，适应度值较差的 烟花获取较少的资源。 烟花算法和遗传算法具有一 些类似的地方，比如遗传算法可以通过变异概率的 大小在“编码空间”中产生一个相对于当前染色体 距离较远／ 近的解［２５］ ，而同样地，烟花算法可以通过 不同的爆炸半径大／ 小产生距离烟花较远／ 近的爆炸 火花，烟花算法在迭代过程中，种群中每个烟花个体 在一次迭代过程中会产生多个个体，而粒子群优化 算法通常只产生一个个体，烟花算法的这种爆炸机 制使得其对于烟花附近的区域的搜索更加彻底。 ２ 几种典型的改进烟花算法 烟花算法自提出后就受到了诸多科研工作者的 关注，许多改进算法相继被提出。 改进烟花算法主 要可以被分为两类，一类是在基本烟花算法的基础 上进行算子的分析和改进，另一类是与其他启发式 算法的混合算法的研究。 第一类算法改进的工作主要有：Ｐｅｉ 等［２６］ 提出 基于适应度函数估计的加速型烟花算法（ＡｃＦＷＡ）。 ＡｃＦＷＡ 使用烟花及其产生的爆炸火花、高斯变异火 花种群的位置信息和适应度值信息来估计搜索空间 的形状，然后使用估计的形状的最优位置作为启发 式信息引入到当前种群进行加速搜索。 Ｌｉｕ 等［２７］提 出一种构造型烟花算法（ ＩＦＷＡ），使用了一种新型 的烟花爆炸半径和爆炸火花数目的计算方式，相对 于基本烟花算法，获得了性能上的提升。 Ｚｈｅｎｇ Ｓ． 等［２８］对于基本烟花算法的爆炸算子、变异算子、选 择策略和映射规则等进行了细致的分析，针对烟花 算法存在的缺陷进行了逐一改进，并提出了增强型 烟花 算 法 （ ＥＦＷＡ）。 接 着， Ｚｈｅｎｇ Ｓ． 等［２９］ 和 Ｌｉ 等［３０］分别提出了两种自适应半径策略———动态搜 索烟花算法 （ ｄｙｎＦＷＡ） 和自适应烟花算法 （ ＡＦ⁃ ＷＡ）。 在 ｄｙｎＦＷＡ 中，烟花爆炸半径的变化过程依 据烟花种群产生的火花适应度值是否发生改进（即 优化得到适应度值更优的火花） 决定。 在 ＡＦＷＡ 中，烟花的爆炸半径的确定依据当前种群适应度值 最优的个体和一个特定个体之间的距离计算。 这两 种方法由于采用了自适应调整爆炸半径的机制，都 大大提升了增强型烟花算法的性能。 第 ２ 类算法改进的工作有：Ｚｈｅｎｇ Ｙ．等［３１］ 提出 使用差分演化算法和烟花算法进行混合的新型算法 ＦＷＡ⁃ＤＥ。 Ｙｕ 等［３２］ 用差分变异替换基本烟花算法 中的高斯变异，所提出的 ＦＷＡ⁃ＤＭ 算法比 ＥＦＷＡ 算 法的性能更好。 Ｇａｏ 等［３３ ］ 提出使用文化算法和烟 花算法进行混合的文化烟花算法（ＣＡ⁃ＦＷＡ），并将 文化烟花算法应用到滤波器的设计上，取得了相对 于量子粒子群优化算法（ＱＰＳＯ ［３４］ ）和自适应量子粒 子群 优 化 算 法 （ ＡＱＰＳＯ ［３５］ ） 较 优 的 性 能。 Ｚｈｅｎｇ 等［３７］将生物地理学优化算法引入增强烟花算法，提 出混合算法 ＢＢＯ⁃ＦＷＡ，提高了烟花间的交互能力。 ２．１ 基于适应度函数估计的烟花算法 进化计算加速策略研究是一个比较重要的研究 方向。 １９９９ 年，Ｔａｋａｇｉ 等［３６］提出对于一个简单的单 峰优化问题求解，可以通过进化算法优化的解信息 去估计搜索空间形状，然后对估计得到的简单曲面 求解其最优值位置并引入到种群中作为启发式信息 来加速搜索过程。 基于此，在烟花算法中，在每一代 烟花产生爆炸火花和高斯变异火花以后，Ｐｅｉ 等［２６］ 尝试使用当前种群的候选者集合（烟花、爆炸火花 和高斯变异火花）的位置信息和适应度值信息去估 计整个搜索空间的形状，然后根据估计得到的形状 等作为启发式信息。 文献［２６］讨论了 ３ 种不同的抽样策略：基于适 应度值的抽样策略，即在候选者集合中选择 ｋ 个适 应度值最好的样本个体；基于距离的抽样策略，即在 候选者集合中选择欧式距离上离最优点位置最近的 ｋ 个样本个体；随机抽样策略，即随机从候选者集合 中选择 ｋ 个样本个体。 对于搜索空间的估计，文献 中将 Ｄ 维搜索空间投影到每一个维数上面，并使用 抽样得到的样本个体在该维度上的投影位置和适应 度值信息依据估计模型进行形状估计。 在实验中，抽样点个数被设置成 ３、５ 和 １０，用 于研究抽样点个数对于算法性能的影响。 对于通过 选择有限的样本点估计其搜索空间形状这一问题， 曲面估计形状的选择十分重要。 文献中使用一次最 小二乘法、二次最小二乘法来研究模型的选择对于 第 ５ 期 谭营，等：烟花算法研究进展 ·５１９·
·520· 智能系统学报 第9卷 性能的影响。 的维度上爆炸的偏置是相同的。然而，相同的偏置 2.2构造型烟花算法 将会降低局部搜索的多样性。为了解决这一问题， 在FWA中，为了差异化不同的烟花，使得适应 EFWA在每个选择的维度上使用不同的偏置值。此 度值较低的烟花拥有更多的资源，即在较小的爆炸 外，在EFWA中，爆炸维度的选择亦有不同)。 半径内产生较多数量的爆炸火花，同时使得适应度 2.3.3映射规则 值较高的烟花拥有较少的资源，即在较大的爆炸半 在WA中，当一个火花（爆炸火花或高斯变异 径内产生较少数量的爆炸火花。这两类烟花分别对 火花)在维度k上超出边界，会通过式(6)的映射规 应着局部搜索能力和全局搜索能力，基本烟花算法 则映射到一个新的位置。在很多时候，火花位置超 采用式(2)、(3)计算爆炸半径和爆炸火花数目。 出边界通常都是一个较小的值，而且通常使用的测 事实上，可以有许多种计算方法使得计算得到 试函数都是边界对称的，即 的爆炸半径和爆炸火花数目具有上面提到的这一性 XUBA =-XIB.k (11) 质。L山等2可使用烟花的适应度值的排序信息来计 式中：xBk、xB,k为解空间在维度k上的上边界和 算烟花的爆炸半径和爆炸火花数目，适应度值低的 下边界。那么，在这种情况下，超出边界的火花在维 烟花具有较小的序号，反之，适应度值较大的烟花具 度k上会被映射到一个距离原点很近的位置上。然 有较大的序号。除了改进爆炸算子，Liu等]还对 而，由于很多测试函数的最优值都在原点位置或者 高斯变异算子和选择策略进行了修改。对于高斯变 附近，因此，这种映射规则会无意地加速算法收敛， 异算子，Lu等使用了一种随机变异算子产生变异 而这种加速并不是算法的智能。 火花：对于选择策略，文中讨论了基于适应度值的轮 为了解决这一缺陷，EFWA提出使用下式作为 盘赌选择策略和随机选择策略对性能的影响。 映射规则来处理超出边界的火花。 2.3增强烟花算法 元=xB.k+U(0,1)×(xB.A-xB.4)(12) Zheng S..等[对FWA的算子进行了细致的分 式中：xk、xBk为可行区域在维度k上的上边界 析，针对FWA的缺陷进行了改进，包括最小爆炸半 和下边界。 径检测、爆炸火花产生方式、映射规则、高斯变异算 2.3.4高斯变异算子 子和选择策略，提出了增强型烟花算法(EFWA)。 在FWA中，在产生高斯变异火花时，当随机产 2.3.1最小爆炸半径检测 生e~N(1,1),的值接近于0时候，高斯变异火花 在WA中，通过对不同的烟花设置不同的爆 的计算方法如式(5)所示，位置x4会接近于0，而且 炸半径来保持全局搜索和局部搜索的平衡，使得烟 很难跳出。此外，如果产生较大的e值，通过FWA 花种群具有探索性和开采性。尽管这个想法看似可 的映射规则即式(12)使得x:可能会被映射到原点 以通过式(2)达到这一性质，然而，在使用式(2)计 位置附近。这对于最优值在原点的优化函数来说将 算爆炸半径的时候会发现适应度值最小的烟花的爆 极大地加速优化过程的收敛，而对其他最优值不在 炸半径非常小，接近于0，从而浪费了宝贵的资源。 原点或者其附近的测试函数则浪费了搜索资源。 为了解决这一缺陷，EFWA引入了最小爆炸半 为了避免这一个缺陷，EWA使用一种新型高 径检测机制。如果烟花的爆炸半径小于某一阈值， 斯变异算子，计算公式为 则将其置为该值，如式(9)： X证=x证+gX(x做一X法） (13) (Amin,,Ai,k<Amin,k A:.k= 式中：g~N(0,1),x陆为当前烟花种群中适应度函 46,其他 (9)》 数值最小的烟花的第k维度上的位置。 对于如何确定Ak,EFWA提出了使用非线性递减 2.3.5选择策略 方式： 在FWA中，选择策略是基于距离度量的，由式 Amink(t)=Ainit -Ainit -Afnlevals_max x (7)进行计算。但这种选择方式需要在每一次迭代 √(2 evals_max-t)×t (10) 过程中，计算候选者集合中任意两个个体之间的距 其中，t指当前函数评估的次数，evals_.max为最大 离，这是十分耗时的。EFWA使用一种精英随机选 函数评估次数。A、A6aml表示迭代过程中的最初和 择策略，即首先选择出候选者集合中适应度值最小 最终爆炸半径检测值。 的个体，然后，对其余的烟花的选择采用随机策略。 2.3.2爆炸火花产生方式 2.4动态搜索烟花算法和自适应烟花算法 在FWA中，烟花爆炸产生火花时在所有选择 在FWA和EFWA中，烟花算法的爆炸半径由
性能的影响。 ２．２ 构造型烟花算法 在 ＦＷＡ 中，为了差异化不同的烟花，使得适应 度值较低的烟花拥有更多的资源，即在较小的爆炸 半径内产生较多数量的爆炸火花，同时使得适应度 值较高的烟花拥有较少的资源，即在较大的爆炸半 径内产生较少数量的爆炸火花。 这两类烟花分别对 应着局部搜索能力和全局搜索能力，基本烟花算法 采用式（２）、（３）计算爆炸半径和爆炸火花数目。 事实上，可以有许多种计算方法使得计算得到 的爆炸半径和爆炸火花数目具有上面提到的这一性 质。 Ｌｉｕ 等［２７］使用烟花的适应度值的排序信息来计 算烟花的爆炸半径和爆炸火花数目，适应度值低的 烟花具有较小的序号，反之，适应度值较大的烟花具 有较大的序号。 除了改进爆炸算子，Ｌｉｕ 等［２７］ 还对 高斯变异算子和选择策略进行了修改。 对于高斯变 异算子，Ｌｉｕ 等使用了一种随机变异算子产生变异 火花；对于选择策略，文中讨论了基于适应度值的轮 盘赌选择策略和随机选择策略对性能的影响。 ２．３ 增强烟花算法 Ｚｈｅｎｇ Ｓ．等［２８］对 ＦＷＡ 的算子进行了细致的分 析，针对 ＦＷＡ 的缺陷进行了改进，包括最小爆炸半 径检测、爆炸火花产生方式、映射规则、高斯变异算 子和选择策略，提出了增强型烟花算法（ＥＦＷＡ）。 ２．３．１ 最小爆炸半径检测 在 ＦＷＡ 中，通过对不同的烟花设置不同的爆 炸半径来保持全局搜索和局部搜索的平衡，使得烟 花种群具有探索性和开采性。 尽管这个想法看似可 以通过式（２）达到这一性质，然而，在使用式（２）计 算爆炸半径的时候会发现适应度值最小的烟花的爆 炸半径非常小，接近于 ０，从而浪费了宝贵的资源。 为了解决这一缺陷，ＥＦＷＡ 引入了最小爆炸半 径检测机制。 如果烟花的爆炸半径小于某一阈值， 则将其置为该值，如式（９）： Ａｉ，ｋ ＝ Ａｍｉｎ，ｋ，Ａｉ，ｋ ＜ Ａｍｉｎ，ｋ {Ａｉ，ｋ，其他 （９） 对于如何确定 Ａｍｉｎ，ｋ ，ＥＦＷＡ 提出了使用非线性递减 方式： Ａｍｉｎ，ｋ（ｔ） ＝ Ａｉｎｉｔ － Ａｉｎｉｔ － Ａｆｉｎａｌ ｅｖａｌｓ＿ｍａｘ × （２ｅｖａｌｓ＿ｍａｘ － ｔ） × ｔ （１０） 其中， ｔ 指当前函数评估的次数， ｅｖａｌｓ＿ｍａｘ 为最大 函数评估次数。 Ａｉｎｉｔ 、 Ａｆｉｎａｌ 表示迭代过程中的最初和 最终爆炸半径检测值。 ２．３．２ 爆炸火花产生方式 在 ＦＷＡ 中，烟花爆炸产生火花时在所有选择 的维度上爆炸的偏置是相同的。 然而，相同的偏置 将会降低局部搜索的多样性。 为了解决这一问题， ＥＦＷＡ 在每个选择的维度上使用不同的偏置值。 此 外，在 ＥＦＷＡ 中，爆炸维度的选择亦有不同［２８］ 。 ２．３．３ 映射规则 在 ＦＷＡ 中，当一个火花（爆炸火花或高斯变异 火花）在维度 ｋ 上超出边界，会通过式（６）的映射规 则映射到一个新的位置。 在很多时候，火花位置超 出边界通常都是一个较小的值，而且通常使用的测 试函数都是边界对称的，即 ｘＵＢ，ｋ ＝ － ｘＬＢ，ｋ （１１） 式中： ｘＵＢ，ｋ 、 ｘＬＢ，ｋ 为解空间在维度 ｋ 上的上边界和 下边界。 那么，在这种情况下，超出边界的火花在维 度 ｋ 上会被映射到一个距离原点很近的位置上。 然 而，由于很多测试函数的最优值都在原点位置或者 附近，因此，这种映射规则会无意地加速算法收敛， 而这种加速并不是算法的智能。 为了解决这一缺陷，ＥＦＷＡ 提出使用下式作为 映射规则来处理超出边界的火花。 ｘ ＾ ｉｋ ＝ ｘＬＢ，ｋ ＋ Ｕ（０，１） × （ｘＵＢ，ｋ － ｘＬＢ，ｋ） （１２） 式中： ｘＵＢ，ｋ 、 ｘＬＢ，ｋ 为可行区域在维度 ｋ 上的上边界 和下边界。 ２．３．４ 高斯变异算子 在 ＦＷＡ 中，在产生高斯变异火花时，当随机产 生 ｅ ～ Ｎ（１，１）， 的值接近于 ０ 时候，高斯变异火花 的计算方法如式（５）所示，位置 ｘｉｋ 会接近于 ０，而且 很难跳出。 此外，如果产生较大的 ｅ 值，通过 ＦＷＡ 的映射规则即式（１２）使得 ｘｉｋ 可能会被映射到原点 位置附近。 这对于最优值在原点的优化函数来说将 极大地加速优化过程的收敛，而对其他最优值不在 原点或者其附近的测试函数则浪费了搜索资源。 为了避免这一个缺陷，ＥＦＷＡ 使用一种新型高 斯变异算子，计算公式为 ｘ ＾ ｉｋ ＝ ｘｉｋ ＋ ｇ × （ｘＢｋ － ｘｉｋ） （１３） 式中： ｇ ～ Ｎ（０，１）， ｘＢｋ 为当前烟花种群中适应度函 数值最小的烟花的第 ｋ 维度上的位置。 ２．３．５ 选择策略 在 ＦＷＡ 中，选择策略是基于距离度量的，由式 （７）进行计算。 但这种选择方式需要在每一次迭代 过程中，计算候选者集合中任意两个个体之间的距 离，这是十分耗时的。 ＥＦＷＡ 使用一种精英随机选 择策略，即首先选择出候选者集合中适应度值最小 的个体，然后，对其余的烟花的选择采用随机策略。 ２．４ 动态搜索烟花算法和自适应烟花算法 在 ＦＷＡ 和 ＥＦＷＡ 中，烟花算法的爆炸半径由 ·５２０· 智 能 系 统 学 报 第 ９ 卷
第5期 谭营，等：烟花算法研究进展 ·521· 式(2)计算的。在烟花种群中，当烟花的适应度值 的爆炸半径放大缩小机制。当烟花种群搜索得到一 较低时，该烟花所在的位置被认为是一个潜在较好 个适应度值更低的位置的时候，通常情况下有3种 的区域，应增加在该位置的搜索资源：对于一个适应 情况：1)核心烟花找到的：2)距离核心烟花位置很 度值较高的烟花，所在的位置被认为是一个潜在的 近的非核心烟花找到的：3)距离核心烟花位置不近 较差区域，应减少该位置的搜索资源。 的非核心烟花找到的。在第1种情况下，为了增大 然而，这种爆炸半径计算方法存在很多不合理 收敛速度，更快地找到解空间的全局最优位置，放大 的地方。比如在烟花种群中，可能烟花刚开始进入 爆炸半径是一种最直接有效的方法。这同样适用于 一个好的区域并对其进行搜索时，其搜索点的适应 第2种情况。在第3种情况下，找到的适应度函数 度值相对于种群中其他烟花所在的位置的适应度值 值更低的位置在下一代会被选择为核心烟花，其爆 差。在这种情况下，该点的搜索资源在下一代会被 炸半径应该重新初始化。然而，由于动态搜索策略 大大降低，以至于即使烟花进入了一个比较好的区 具有自适应调整爆炸半径的能力，而且很难有简单 域，原先的这种爆炸半径和爆炸火花数计算方法仍 有效的距离度量方式表明距离当前的核心烟花很 然可能导致烟花很难对于一个潜在的好的区域的深 远，所以为了简便，在dynFWA中，下一代核心烟花 度挖掘，即持久性开发。而且，在FWA和EFWA算 的爆炸半径仍然被放大。 法中，算法仅根据烟花的适应度值之间的差异来决 当烟花种群搜索不到一个适应度值更好的位置 定爆炸半径和爆炸火花数目，并没有考虑到优化问 的时候，dynFWA将缩小核心烟花的爆炸半径。因 题求解的过程中的启发式信息。比如，即使最优的 为缩小爆炸半径将提高找到更优位置的概率2]。 烟花达到了一个较好的区域，每次计算其爆炸半径 此外，dynFWA算法相对于EFWA和FWA算 都是根据相对于其他烟花的适应度值信息计算的， 法，去除了高斯变异算子使得其时间消耗相对较低。 但是，如果烟花需要具有强大的局部搜索能力其爆 2.4.2自适应烟花算法 炸半径可能需要降低到非常小的范围内才能够使得 自适应烟花算法(AFWA)是Li等[0]提出的另 有限的资源（即每个烟花的爆炸火花数目）下找到 一种自动调整爆炸半径大小的方法。在AFWA中， 更好的解，而仅根据烟花相对于种群中其他烟花的 候选者集合中的最优个体（下一代的烟花）会被选 适应度值计算得到的爆炸半径很难达到非常小的 择到下一代，其爆炸半径的计算方法为选择满足如 值，因此在测试函数上，FWA和EFWA往往表现出 下两个条件的个体，用最优个体和该个体之间的距 了不太好的局部搜索能力2]。 离作为最优个体下一次的爆炸半径： 2.4.1动态搜索烟花算法 1)该个体的适应度值比上代的烟花差： 基于前面的分析，Zheng S.等提出了动态搜索 2)该个体是满足条件1)的个体中距离最优个 烟花算法dynFWA[29。在dynFWA中，Zheng S.等将 体最近的。 烟花种群分为2类：核心烟花（适应度值最优的烟 理论分析表明，这种方式能够有效地根据搜索 花)和非核心烟花。核心烟花和非核心烟花的区别 的情况来自适应地调整步长：在初始阶段，这种半径 主要在于：1)核心烟花能够在较小的爆炸半径范围 能够自动根据局部区域的大小进行调整：而在局部 内产生更多的爆炸火花，进行局部搜索，而非核心烟 搜索中它又能够像dynFWA一样根据搜索的结果对 花在较大的爆炸半径范围内产生更少的爆炸火花， 步长进行放缩：最后在微调阶段，它会使半径逐渐减 进行全局搜索。2)核心烟花由于是适应度值最低 小从而找到极值点。因此，AFWA表现出了很好的 的个体，很大概率上核心烟花或者其子代会被选择 性能改善。 到下一代。这也就是为什么dynFWA算法中的动态 2.5差分演化一烟花混合算法 搜索爆炸策略应用到核心烟花上。而非核心烟花并 在文献[31]中，Zheng Y.等提出了将烟花算法 不能保证会被确定地选择到种群的下一代中。 和差分演化算法进行混合的一种新型算法(FWA- 在dynFWA中，核心烟花的爆炸半径依据动态 DE)。在基本烟花的基础上中，该算法引入了差分 搜索策略进行调整，同时其他非核心烟花仍旧依据 演化算法中的变异算子、交叉算子和选择算子。 式(2)计算。在dynFWA中，当烟花种群中找到了 FWA-DE将候选者集合（烟花、爆炸火花和高斯变 一个适应度值更低的位置，核心烟花的爆炸半径变 异火花)按照适应度值升序排列，并从前2P的候选 大，反之，核心烟花的爆炸半径变小。 者中选择P个组成集合S。选择方法是首先选择适 在dynFWA中，Zheng S.等细致分析了核心烟花 应度值最小的候选者加人到集合S中，其余P-1
式（２）计算的。 在烟花种群中，当烟花的适应度值 较低时，该烟花所在的位置被认为是一个潜在较好 的区域，应增加在该位置的搜索资源；对于一个适应 度值较高的烟花，所在的位置被认为是一个潜在的 较差区域，应减少该位置的搜索资源。 然而，这种爆炸半径计算方法存在很多不合理 的地方。 比如在烟花种群中，可能烟花刚开始进入 一个好的区域并对其进行搜索时，其搜索点的适应 度值相对于种群中其他烟花所在的位置的适应度值 差。 在这种情况下，该点的搜索资源在下一代会被 大大降低，以至于即使烟花进入了一个比较好的区 域，原先的这种爆炸半径和爆炸火花数计算方法仍 然可能导致烟花很难对于一个潜在的好的区域的深 度挖掘，即持久性开发。 而且，在 ＦＷＡ 和 ＥＦＷＡ 算 法中，算法仅根据烟花的适应度值之间的差异来决 定爆炸半径和爆炸火花数目，并没有考虑到优化问 题求解的过程中的启发式信息。 比如，即使最优的 烟花达到了一个较好的区域，每次计算其爆炸半径 都是根据相对于其他烟花的适应度值信息计算的， 但是，如果烟花需要具有强大的局部搜索能力其爆 炸半径可能需要降低到非常小的范围内才能够使得 有限的资源（即每个烟花的爆炸火花数目） 下找到 更好的解，而仅根据烟花相对于种群中其他烟花的 适应度值计算得到的爆炸半径很难达到非常小的 值，因此在测试函数上，ＦＷＡ 和 ＥＦＷＡ 往往表现出 了不太好的局部搜索能力［２８］ 。 ２．４．１ 动态搜索烟花算法 基于前面的分析，Ｚｈｅｎｇ Ｓ．等提出了动态搜索 烟花算法 ｄｙｎＦＷＡ ［２９］ 。 在 ｄｙｎＦＷＡ 中，Ｚｈｅｎｇ Ｓ．等将 烟花种群分为 ２ 类：核心烟花（适应度值最优的烟 花）和非核心烟花。 核心烟花和非核心烟花的区别 主要在于：１）核心烟花能够在较小的爆炸半径范围 内产生更多的爆炸火花，进行局部搜索，而非核心烟 花在较大的爆炸半径范围内产生更少的爆炸火花， 进行全局搜索。 ２） 核心烟花由于是适应度值最低 的个体，很大概率上核心烟花或者其子代会被选择 到下一代。 这也就是为什么 ｄｙｎＦＷＡ 算法中的动态 搜索爆炸策略应用到核心烟花上。 而非核心烟花并 不能保证会被确定地选择到种群的下一代中。 在 ｄｙｎＦＷＡ 中，核心烟花的爆炸半径依据动态 搜索策略进行调整，同时其他非核心烟花仍旧依据 式（２）计算。 在 ｄｙｎＦＷＡ 中，当烟花种群中找到了 一个适应度值更低的位置，核心烟花的爆炸半径变 大，反之，核心烟花的爆炸半径变小。 在 ｄｙｎＦＷＡ 中，Ｚｈｅｎｇ Ｓ．等细致分析了核心烟花 的爆炸半径放大缩小机制。 当烟花种群搜索得到一 个适应度值更低的位置的时候，通常情况下有 ３ 种 情况：１）核心烟花找到的；２）距离核心烟花位置很 近的非核心烟花找到的；３）距离核心烟花位置不近 的非核心烟花找到的。 在第 １ 种情况下，为了增大 收敛速度，更快地找到解空间的全局最优位置，放大 爆炸半径是一种最直接有效的方法。 这同样适用于 第 ２ 种情况。 在第 ３ 种情况下，找到的适应度函数 值更低的位置在下一代会被选择为核心烟花，其爆 炸半径应该重新初始化。 然而，由于动态搜索策略 具有自适应调整爆炸半径的能力，而且很难有简单 有效的距离度量方式表明距离当前的核心烟花很 远，所以为了简便，在 ｄｙｎＦＷＡ 中，下一代核心烟花 的爆炸半径仍然被放大。 当烟花种群搜索不到一个适应度值更好的位置 的时候，ｄｙｎＦＷＡ 将缩小核心烟花的爆炸半径。 因 为缩小爆炸半径将提高找到更优位置的概率［２９］ 。 此外，ｄｙｎＦＷＡ 算法相对于 ＥＦＷＡ 和 ＦＷＡ 算 法，去除了高斯变异算子使得其时间消耗相对较低。 ２．４．２ 自适应烟花算法 自适应烟花算法（ＡＦＷＡ）是 Ｌｉ 等［３０］ 提出的另 一种自动调整爆炸半径大小的方法。 在 ＡＦＷＡ 中， 候选者集合中的最优个体（下一代的烟花） 会被选 择到下一代，其爆炸半径的计算方法为选择满足如 下两个条件的个体，用最优个体和该个体之间的距 离作为最优个体下一次的爆炸半径： １）该个体的适应度值比上代的烟花差； ２）该个体是满足条件 １）的个体中距离最优个 体最近的。 理论分析表明，这种方式能够有效地根据搜索 的情况来自适应地调整步长：在初始阶段，这种半径 能够自动根据局部区域的大小进行调整；而在局部 搜索中它又能够像 ｄｙｎＦＷＡ 一样根据搜索的结果对 步长进行放缩；最后在微调阶段，它会使半径逐渐减 小从而找到极值点。 因此，ＡＦＷＡ 表现出了很好的 性能改善。 ２．５ 差分演化—烟花混合算法 在文献［３１］中，Ｚｈｅｎｇ Ｙ．等提出了将烟花算法 和差分演化算法进行混合的一种新型算法（ ＦＷＡ⁃ ＤＥ）。 在基本烟花的基础上中，该算法引入了差分 演化算法中的变异算子、 交叉算子和选择算子。 ＦＷＡ⁃ＤＥ 将候选者集合（烟花、爆炸火花和高斯变 异火花）按照适应度值升序排列，并从前 ２Ｐ 的候选 者中选择 Ｐ 个组成集合 Ｓ 。 选择方法是首先选择适 应度值最小的候选者加入到集合 Ｓ 中，其余 Ｐ － １ 第 ５ 期 谭营，等：烟花算法研究进展 ·５２１·
.522 智能系统学报 第9卷 个候选者的选择方式依据适应度函数值的轮盘赌选 估函数，则是这一概率较小为好。 择，对于候选者x:的选择概率计算公式为 2.8改进型单目标烟花算法性能 f(x:) 为了验证改进型烟花算法的有效性，通常，对于 p(x)= (14) 2P fx) 算法的性能验证主要是通过在测试函数集合测试算 j=1 法性能或者将改进型烟花算法和基本烟花算法应用 式中：f(x:)为当前候选者x:的适应度值。这里需 到实际优化问题，根据求解结果的质量进行验证。 要指出，这种选择方式其实是存在风险的，因为在文 在使用测试函数集合进行性能验证时，目前存在一 献中使用的测试函数的最优解都是大于零的，所以 些标准的测试函数集合，在改进型烟花算法中使用 计算得到的概率p(x:)恒为正。对于得到的集合 的主要有如下3个标准测试函数集合： S,对集合S中的每个元素执行以下的操作，使用差 CEC2005,包含25个测试函数1； 分进化策略进行迭代进化，包括变异算子、交叉算子 CEC2013,包含28个测试函数[9： 和选择算子。 CEC2014,包含30个测试函数[0」 此外，Yu等2也尝试用差分变异算子替 在测试函数集合上进行性能测试，对于不同算 换烟花算法的高斯变异算子提出了FWA-DM。在 法之间的性能比较主要有比较均值，其中也有适应 基本烟花算法执行过程中，首先在可行解空间随机 度值排名等指标90。为了验证不同算法在测试 初始化5D个烟花(D为维度)，并评估烟花的适应 函数上的差异显著性，通常使用t检验或者Wileox- 度值。烟花的爆炸半径根据式(2)计算。每个烟花 on符号秩检验，其中Wilcoxon符号秩检验不假设数 在爆炸半径内随机产出一个爆炸火花。然后，对比 据服从正态分布4)。 烟花和火花，选择适应度值较低的个体组成新种群， 最后，运用变异算子对新种群进行变异。在变异算 3多目标烟花算法 子的作用下，每个烟花将产生变异火花。对比变异 多目标优化算法自20世纪90年代发展，如今 火花和当前火花，适应度值较优的个体被选择到下 大部分有影响力的群体智能算法、进化算法都有其 一代作为烟花。算法迭代进行直到满足终止条件。 多目标算法版本，例如NSGA-I,SPEA-16] 2.6文化-烟花混合算法 NSPS0)等。相对于单目标优化算法，多目标优化 文化烟花算法(CA-FWA)是Gao等提出的一种 算法应用求解具有多个优化目标的优化问题而不是 用于数字滤波器设计的烟花算法[)。CA-FWA不 单个优化目标问题，在实际优化问题中具有更重要 同于FWA,其具有4种火花生成的方式。此外，在 的意义。在文献[44]中，Zheng Y.等基于单目标差 选择策略上，文化烟花算法的采用的选择策略是首 分演化-烟花混合算法[3)(FWA-DE)首次提出多目 先选择排名靠前的入W个烟花(N是烟花个数)，对 标烟花算法MOFWA,并将多目标烟花算法应用到 于剩下的(1-入)N个烟花的选择策略为在由x:, 油料作物生产这一实际的优化问题中。 (i=入N+1,AN+2,…,N)组成的集合中依据FWA 在将单目标群体智能算法框架移植去解决多目 算法选择策略进行选择。 标优化问题需要解决几个关键步骤：主要包括适应 2.7生物地理学优化-烟花混合算法 度值计算方法和档案维护方法。 Zhang等)将生物地理学优化(BBO)算法和 MOFWA使用的SPEA-I6]方法中的适应度值 增强烟花算法(EFWA)进行混合一BBO-FTWA,提 计算方法。在SPEA-Ⅱ方法中，对于当前种群中，无 高了烟花之间的交互能力。BBO提供了一种根据 论是支配解还是非支配解，其解的强度值是由这个 个体的适应度值，以概率将个体的某些维的值进行 解支配其他解的数目和这个解的浓度决定的。关于 交叉迁移的方法。 档案维护方法，MOFWA使用文献[45]提出的档案 在BBO中，个体的适应度值越差，其从别的个 维护方法。在档案更新过程中，首先确定支配关系， 体接受某些位置的概率越高，而把自己的某些位置 移除被支配的解，如果仍旧达到档案大小的上限则 给予别的个体的概率越低，反之亦然。在BBO- 移除距离最近的一对点中的一个。 FWA,烟花产生爆炸火花的步骤被修改成以概率p MOFOA执行流程如下：首先，初始化N个烟 进行BB0方式的迁移，以概率1-P产生爆炸火花。 花，每个烟花产生爆炸火花和高斯变异火花。然后， P如果较大，能够提升种群的多样性以及个体之间 使用产生的火花（包括爆炸火花、高斯变异火花）更 的信息交互，但是对于最优点处于狭缝中的那些评 新档案。从烟花和火花中选择一定数量的个体组成
个候选者的选择方式依据适应度函数值的轮盘赌选 择，对于候选者 ｘｉ 的选择概率计算公式为 ｐ（ｘｉ） ＝ ｆ（ｘｉ） ∑ ２Ｐ ｊ ＝ １ ｆ（ｘｊ） （１４） 式中： ｆ（ｘｉ） 为当前候选者 ｘｉ 的适应度值。 这里需 要指出，这种选择方式其实是存在风险的，因为在文 献中使用的测试函数的最优解都是大于零的，所以 计算得到的概率 ｐ（ｘｉ） 恒为正。 对于得到的集合 Ｓ ，对集合 Ｓ 中的每个元素执行以下的操作，使用差 分进化策略进行迭代进化，包括变异算子、交叉算子 和选择算子。 此外，Ｙｕ 等［３２］ 也尝试用差分变异算子替 换烟花算法的高斯变异算子提出了 ＦＷＡ⁃ＤＭ。 在 基本烟花算法执行过程中，首先在可行解空间随机 初始化 ５Ｄ 个烟花（ Ｄ 为维度），并评估烟花的适应 度值。 烟花的爆炸半径根据式（２）计算。 每个烟花 在爆炸半径内随机产出一个爆炸火花。 然后，对比 烟花和火花，选择适应度值较低的个体组成新种群， 最后，运用变异算子对新种群进行变异。 在变异算 子的作用下，每个烟花将产生变异火花。 对比变异 火花和当前火花，适应度值较优的个体被选择到下 一代作为烟花。 算法迭代进行直到满足终止条件。 ２．６ 文化⁃烟花混合算法 文化烟花算法（ＣＡ⁃ＦＷＡ）是 Ｇａｏ 等提出的一种 用于数字滤波器设计的烟花算法［３３］ 。 ＣＡ⁃ＦＷＡ 不 同于 ＦＷＡ，其具有 ４ 种火花生成的方式。 此外，在 选择策略上，文化烟花算法的采用的选择策略是首 先选择排名靠前的 λＮ 个烟花（ Ｎ 是烟花个数），对 于剩下的 （１ － λ）Ｎ 个烟花的选择策略为在由 ｘｉ， （ｉ ＝λＮ ＋ １，λＮ ＋ ２，…，Ｎ） 组成的集合中依据 ＦＷＡ 算法选择策略进行选择。 ２．７ 生物地理学优化⁃烟花混合算法 Ｚｈａｎｇ 等［３７］ 将生物地理学优化（ＢＢＯ） 算法和 增强烟花算法（ＥＦＷＡ）进行混合———ＢＢＯ⁃ＦＷＡ，提 高了烟花之间的交互能力。 ＢＢＯ 提供了一种根据 个体的适应度值，以概率将个体的某些维的值进行 交叉迁移的方法。 在 ＢＢＯ 中，个体的适应度值越差，其从别的个 体接受某些位置的概率越高，而把自己的某些位置 给予别的个体的概率越低， 反之亦然。 在 ＢＢＯ⁃ ＦＷＡ，烟花产生爆炸火花的步骤被修改成以概率 ｐ 进行 ＢＢＯ 方式的迁移，以概率 １ － ｐ 产生爆炸火花。 ｐ 如果较大，能够提升种群的多样性以及个体之间 的信息交互，但是对于最优点处于狭缝中的那些评 估函数，则是这一概率较小为好。 ２．８ 改进型单目标烟花算法性能 为了验证改进型烟花算法的有效性，通常，对于 算法的性能验证主要是通过在测试函数集合测试算 法性能或者将改进型烟花算法和基本烟花算法应用 到实际优化问题，根据求解结果的质量进行验证。 在使用测试函数集合进行性能验证时，目前存在一 些标准的测试函数集合，在改进型烟花算法中使用 的主要有如下 ３ 个标准测试函数集合： ＣＥＣ２００５，包含 ２５ 个测试函数［３８］ ； ＣＥＣ２０１３，包含 ２８ 个测试函数［３９］ ； ＣＥＣ２０１４，包含 ３０ 个测试函数［４０］ 。 在测试函数集合上进行性能测试，对于不同算 法之间的性能比较主要有比较均值，其中也有适应 度值排名等指标［３９⁃４０］ 。 为了验证不同算法在测试 函数上的差异显著性，通常使用 ｔ 检验或者 Ｗｉｌｃｏｘ⁃ ｏｎ 符号秩检验，其中 Ｗｉｌｃｏｘｏｎ 符号秩检验不假设数 据服从正态分布［４１］ 。 ３ 多目标烟花算法 多目标优化算法自 ２０ 世纪 ９０ 年代发展，如今 大部分有影响力的群体智能算法、进化算法都有其 多目 标 算 法 版 本， 例 如 ＮＳＧＡ⁃ＩＩ ［１５］ ， ＳＰＥＡ⁃ＩＩ ［１６］ ， ＮＳＰＳＯ ［１７］等。 相对于单目标优化算法，多目标优化 算法应用求解具有多个优化目标的优化问题而不是 单个优化目标问题，在实际优化问题中具有更重要 的意义。 在文献［４４］中，Ｚｈｅｎｇ Ｙ．等基于单目标差 分演化⁃烟花混合算法［３１］ （ ＦＷＡ⁃ＤＥ）首次提出多目 标烟花算法 ＭＯＦＷＡ，并将多目标烟花算法应用到 油料作物生产这一实际的优化问题中。 在将单目标群体智能算法框架移植去解决多目 标优化问题需要解决几个关键步骤：主要包括适应 度值计算方法和档案维护方法。 ＭＯＦＷＡ 使用的 ＳＰＥＡ⁃ＩＩ ［１６ ］方法中的适应度值 计算方法。 在 ＳＰＥＡ⁃ＩＩ 方法中，对于当前种群中，无 论是支配解还是非支配解，其解的强度值是由这个 解支配其他解的数目和这个解的浓度决定的。 关于 档案维护方法，ＭＯＦＷＡ 使用文献［４５］提出的档案 维护方法。 在档案更新过程中，首先确定支配关系， 移除被支配的解，如果仍旧达到档案大小的上限则 移除距离最近的一对点中的一个。 ＭＯＦＯＡ 执行流程如下：首先，初始化 Ｎ 个烟 花，每个烟花产生爆炸火花和高斯变异火花。 然后， 使用产生的火花（包括爆炸火花、高斯变异火花）更 新档案。 从烟花和火花中选择一定数量的个体组成 ·５２２· 智 能 系 统 学 报 第 ９ 卷
第5期 谭营，等：烟花算法研究进展 .523. 一个新的群体P,对于P中的每个个体分别执行变 下一代烟花算法的种群。算法迭代执行直到满足终 异算子、交叉算子和选择算子得到新的群体P'作为 止条件。 表1典型改进型烟花算法的比较 Table 1 Comparisons among typical improved FWA versions 年份 算法名称 算法改进思想与机制 性能验证 对比算法及性能 对比了CPS0[]、SPS0[4],在 11个函数组 2010 FWA 函数优化结果的均值上FWA 成测试集合 具有更优的性能 文化算法和烟花算法混合，改变了烟花 滤波器设计对比了AQPSO[和QPSO[) 2011 CA-FWA 算法中爆炸火花产生方式和选择策略 优化问题 算法，具有更优的性能 利用候选者集合中的位置信息和适应度 CEC2005前对于FWA,t检验显示改进有 2012 AcFWA 值信息估计搜索空间形状，生成精英解， 10个函数 效 引人到烟花种群作为启发式信息。 由6个函数对比了FWA、DE,对比算法 2012 FWA-DE 差分演化算法和烟花算法混合 组成的测试优化最优解的成功率，显示 集合 改进有效 根据烟花算法思想，适应度值好的烟花 在更小的爆炸半径内产生更多的爆炸火CEC2005 对比了FWA、PS0算法，在函 前 2013 IFWA 数优化结果的均值上FWA 花，FWA引入一种新型的爆炸半径和爆14个函数 具有更优的性能 炸火花数日计算方式。 对比了FWA、SPSO算法，t检 由12个函数验结果显示对于FWA算法 细致分析了烟花算法的算子，并针对算 2013 EFWA 组成的测试 改进有效，EFWA算法相对于 子存在的缺陷提出了相应的改进策略。 集合 SPS02007算法局部搜索能力 不佳 对比了EFWA算法，Wilcoxon 符号秩检验显示对EFWA算 针对适应度值最优的烟花引入了动态搜 2014 dynFWA CEC2013 法改进有效。对比了SP 索爆炸半径策略。 S02011算法，dynFWA平均 均值排名更优 对比了EFWA算法，t检验显 示对EFWA算法改进有效。 针对适应度值最优的烟花引入自适应爆 2014 AFWA CEC2013 对比了SPS02011、SPS02007 炸半径策略。 算法，AFWA平均均值排名更 优 2014 FWA-DM 差分演化算法和烟花算法混合 CEC2014 由13个函数对比了EFWA、BB0算法，在 2014 BBO-FWA 生物地理学优化算法和烟花算法混合 组成的测试函数优化结果的均值上BBO- 集合 FWA具有更优的性能 4 基于GPU的并行烟花算法 据算法规则迭代产生新的解，时间消耗较大。近些 年来，随着并行技术的不断发展，很多群体智能算 由于群体智能算法在迭代过程中需要不断地根 法，比如粒子群优化算法[)、遗传算法[6]、差分进化
一个新的群体 Ｐ ，对于 Ｐ 中的每个个体分别执行变 异算子、交叉算子和选择算子得到新的群体 Ｐ′ 作为 下一代烟花算法的种群。 算法迭代执行直到满足终 止条件。 表 １ 典型改进型烟花算法的比较 Ｔａｂｌｅ １ Ｃｏｍｐａｒｉｓｏｎｓ ａｍｏｎｇ ｔｙｐｉｃａｌ ｉｍｐｒｏｖｅｄ ＦＷＡ ｖｅｒｓｉｏｎｓ 年份 算法名称 算法改进思想与机制 性能验证 对比算法及性能 ２０１０ ＦＷＡ — １１ 个函数组 成测试集合 对比了 ＣＰＳＯ ［４２］ 、ＳＰＳＯ ［４３］ ，在 函数优化结果的均值上 ＦＷＡ 具有更优的性能 ２０１１ ＣＡ⁃ＦＷＡ 文化算法和烟花算法混合，改变了烟花 算法中爆炸火花产生方式和选择策略 滤波 器 设 计 优化问题 对比了 ＡＱＰＳＯ ［３４］和 ＱＰＳＯ ［３５］ 算法，具有更优的性能 ２０１２ ＡｃＦＷＡ 利用候选者集合中的位置信息和适应度 值信息估计搜索空间形状，生成精英解， 引入到烟花种群作为启发式信息。 ＣＥＣ２００５ 前 １０ 个函数 对于 ＦＷＡ， ｔ 检验显示改进有 效 ２０１２ ＦＷＡ⁃ＤＥ 差分演化算法和烟花算法混合 由 ６ 个 函 数 组成 的 测 试 集合 对比了 ＦＷＡ、ＤＥ，对比算法 优化最优解的成功率，显示 改进有效 ２０１３ ＩＦＷＡ 根据烟花算法思想，适应度值好的烟花 在更小的爆炸半径内产生更多的爆炸火 花，ＩＦＷＡ 引入一种新型的爆炸半径和爆 炸火花数目计算方式。 ＣＥＣ２００５ 前 １４ 个函数 对比了 ＦＷＡ、ＰＳＯ 算法，在函 数优化结果的均值上 ＩＦＷＡ 具有更优的性能 ２０１３ ＥＦＷＡ 细致分析了烟花算法的算子，并针对算 子存在的缺陷提出了相应的改进策略。 由 １２ 个函数 组成 的 测 试 集合 对比了 ＦＷＡ、ＳＰＳＯ 算法， ｔ 检 验结果显示对于 ＦＷＡ 算法 改进有效，ＥＦＷＡ 算法相对于 ＳＰＳＯ２００７ 算法局部搜索能力 不佳 ２０１４ ｄｙｎＦＷＡ 针对适应度值最优的烟花引入了动态搜 索爆炸半径策略。 ＣＥＣ２０１３ 对比了 ＥＦＷＡ 算法，Ｗｉｌｃｏｘｏｎ 符号秩检验显示对 ＥＦＷＡ 算 法 改 进 有 效。 对 比 了 ＳＰ⁃ ＳＯ２０１１ 算 法， ｄｙｎＦＷＡ 平 均 均值排名更优 ２０１４ ＡＦＷＡ 针对适应度值最优的烟花引入自适应爆 炸半径策略。 ＣＥＣ２０１３ 对比了 ＥＦＷＡ 算法， ｔ 检验显 示对 ＥＦＷＡ 算法改进有效。 对比了 ＳＰＳＯ２０１１、 ＳＰＳＯ２００７ 算法，ＡＦＷＡ 平均均值排名更 优 ２０１４ ＦＷＡ⁃ＤＭ 差分演化算法和烟花算法混合 ＣＥＣ２０１４ — ２０１４ ＢＢＯ⁃ＦＷＡ 生物地理学优化算法和烟花算法混合 由 １３ 个函数 组成 的 测 试 集合 对比了 ＥＦＷＡ、ＢＢＯ 算法，在 函数优化结果的均值上 ＢＢＯ⁃ ＦＷＡ 具有更优的性能 ４ 基于 ＧＰＵ 的并行烟花算法 由于群体智能算法在迭代过程中需要不断地根 据算法规则迭代产生新的解，时间消耗较大。 近些 年来，随着并行技术的不断发展，很多群体智能算 法，比如粒子群优化算法［９］ 、遗传算法［４６］ 、差分进化 第 ５ 期 谭营，等：烟花算法研究进展 ·５２３·
·524. 智能系统学报 第9卷 算法[)等，均有学者开始研究算法的并行版本，烟 法的NMF初始化策略和基于群体智能算法的NMF 花算法亦是如此。Ding等[12013年在FWA的基 迭代优化策略。 础上提出了基于GPU平台的并行烟花算法(GPU- 为了验证策略1的有效性，Janecek等在人工数 FWA)。 据集合上进行性能比较，当NMF计算的秩比较小的 将群体智能算法并行化的核心目标是在保证性 时候，FWA表现出了较其他算法较差的性能；当 能的基础上提高时间加速比，即并行化群体智能算 NMF计算的秩变大的时候，FWA算法的性能明显提 法和串行化群体智能算法的时间消耗对比。而提高高。为了验证策略2的有效性，Janecek等在人工数 加速比的核心策略是使得串行群体智能算法的每个据集合上进行性能比较，实验发现策略2对于NMF 步骤能够最大化地并行化，即如果串行群体智能算计算的性能改进十分明显，尤其是在秩比较低的时 法的某个步骤可以并行化则直接将该步骤并行化实候，此外，实验结果表明对于策略2不同的群体智能 现，如果串行群体智能算法的某个步骤由于存在和算法之间差异不明显。 其他地方的数据交互，则尽可能在性能不降低的情5.2图像识别 况下修改该算子，提高其并行化程度。 在图像识别领域，特征之间的距离度量方法对 为了降低FWA中烟花之间的交互，Dig等使于识别准确率的影响至关重要。在生物特征尤其是 用了一种新型的爆炸火花产生方法。在FWA中，每 线条状的生物特征提取方法中，目前基于方向编码 个烟花需要和其他烟花进行交互才能够计算出爆炸 特征提取方法效果较优。在方向性特征提取方法中 半径，但是如果每代都进行交互则并行化程度会大 典型的有竞争编码算法【60]，掌纹方向编码6]和鲁 大降低。因此，Dig等使用间隔性交互方式，即间隔 棒线方向编码2]。对于这几种特征提取方法的距 一定迭代次数后再进行交互计算烟花爆炸半径。在 离度量方法主要有汉明距离和角度距离方法。 不交互的阶段，每个烟花独立地根据现有的爆炸半 在文献[52]中，Zheng S.和Tan细致讨论了汉明 径来产生爆炸火花，在GPU-FWA中，爆炸火花数目 距离、角度距离之间的关系，据此提出了一种统一距 设置为固定值。 离作为距离度量方法。 5应用 D.=k a+kzaz h3a3 (16) 式中：k:表示特征之间具有i个方向差异的错判代 群体智能算法因其强大的问题求解能力被应用 价，a:表示特征之间具有i个方向差异的个数。 到诸多领域。FWA自提出后，很多学者尝试将其应 相对于文献[63]讨论的统计距离方法，Zheng 用到各自领域优化问题求解中。主要应用领域有方 S.和Tan指出角度距离度量方法的性能并不一定恒 程组求解[】、0/1背包问题9]、桁架结构质量最小 差于汉明距离度量方法，即k,≤k2≤k,并不一定恒 化o]非负矩阵分解(NMF)计算)、图像识别[)、 成立。为了计算得到最优的参数组，Zheng S.等使用 垃圾电子邮件检测[)、滤波器设计)、配电网重构 粒子群优化算法[]、差分演化算法[)和烟花算 优化s4、施肥问题求解4，选择性谐波消除的问 法[2进行参数优化。在3个测试集合（人工数据 题5]多个领域，取得了十分明显的应用效果。 集、掌纹数据集和手指静脉数据集)上面进行实验验 5.1非负矩阵分解 证。关于特征提取方法，文中使用了竞争编码算法、 1999年，Lee和Seung提出了著名的非负矩阵 掌纹方向编码和鲁棒线方向编码3种特征提取方 分解(NMF)算法s6)。NMF算法使用低秩、非负矩 法。实验结果表明采用群体智能优化算法进行优化 阵W、H对目标矩阵A进行近似，即A≈WH。 的距离度量方法能够显著降低EER值。 NMF是一个非线性优化函数，形式如下： 5.3滤波器设计 1 目前，有不少学者将群体智能算法应用到滤波 minw.f(W,)minw.A-W 器设计中。Gao等33]提出使用文化烟花算法CA- (15) FWA进行滤波器的设计，并对比了PSO6]、QP 式中：‖·I。表示为向量的F范数。 S03和AQPS0[]。实验结果表明，基于文化烟花 在NMF计算过程中，Janecek等提出基于群体 算法(CA-FWA)设计的数字滤波器比使用PSO、QP 智能算法（包括粒子群优化算法[9）、遗传算法[6]、鱼 S0和AQPSO设计的滤波器性能更好。 群算法[]、差分演化算法[]和烟花算法[2])的两种 5.4垃圾电子邮件检测 NMF计算优化策略[1，匆，分别为基于群体智能算 He等[s]提出使用烟花算法对基于局部免疫浓
算法［４７］等，均有学者开始研究算法的并行版本，烟 花算法亦是如此。 Ｄｉｎｇ 等［１ ９］ ２０１３ 年在 ＦＷＡ 的基 础上提出了基于 ＧＰＵ 平台的并行烟花算法（ＧＰＵ⁃ ＦＷＡ）。 将群体智能算法并行化的核心目标是在保证性 能的基础上提高时间加速比，即并行化群体智能算 法和串行化群体智能算法的时间消耗对比。 而提高 加速比的核心策略是使得串行群体智能算法的每个 步骤能够最大化地并行化，即如果串行群体智能算 法的某个步骤可以并行化则直接将该步骤并行化实 现，如果串行群体智能算法的某个步骤由于存在和 其他地方的数据交互，则尽可能在性能不降低的情 况下修改该算子，提高其并行化程度。 为了降低 ＦＷＡ 中烟花之间的交互，Ｄｉｎｇ 等使 用了一种新型的爆炸火花产生方法。 在 ＦＷＡ 中，每 个烟花需要和其他烟花进行交互才能够计算出爆炸 半径，但是如果每代都进行交互则并行化程度会大 大降低。 因此，Ｄｉｎｇ 等使用间隔性交互方式，即间隔 一定迭代次数后再进行交互计算烟花爆炸半径。 在 不交互的阶段，每个烟花独立地根据现有的爆炸半 径来产生爆炸火花，在 ＧＰＵ⁃ＦＷＡ 中，爆炸火花数目 设置为固定值。 ５ 应用 群体智能算法因其强大的问题求解能力被应用 到诸多领域。 ＦＷＡ 自提出后，很多学者尝试将其应 用到各自领域优化问题求解中。 主要应用领域有方 程组求解［４８］ 、０ ／ １ 背包问题［４９］ 、桁架结构质量最小 化［５０］ 、非负矩阵分解（ＮＭＦ）计算［５１］ 、图像识别［５２］ 、 垃圾电子邮件检测［５３］ 、滤波器设计［３３］ 、配电网重构 优化［５４］ 、施肥问题求解［４４］ ，选择性谐波消除的问 题［５５］多个领域，取得了十分明显的应用效果。 ５．１ 非负矩阵分解 １９９９ 年，Ｌｅｅ 和 Ｓｅｕｎｇ 提出了著名的非负矩阵 分解（ＮＭＦ） 算法［５６］ 。 ＮＭＦ 算法使用低秩、非负矩 阵 Ｗ 、 Ｈ 对目标矩阵 Ａ 进行近似，即 Ａ ≈ ＷＨ 。 ＮＭＦ 是一个非线性优化函数，形式如下： ｍｉｎＷ，Ｈ ｆ（Ｗ，Ｈ） ＝ ｍｉｎＷ，Ｈ １ ２ ‖Ａ － ＷＨ‖２ Ｆ （１５） 式中： ‖·‖Ｆ 表示为向量的 Ｆ 范数。 在 ＮＭＦ 计算过程中，Ｊａｎｅｃｅｋ 等提出基于群体 智能算法（包括粒子群优化算法［９］ 、遗传算法［４６］ 、鱼 群算法［５７］ 、差分演化算法［４７］和烟花算法［２２］ ）的两种 ＮＭＦ 计算优化策略［５１，５８⁃５９］ ，分别为基于群体智能算 法的 ＮＭＦ 初始化策略和基于群体智能算法的 ＮＭＦ 迭代优化策略。 为了验证策略 １ 的有效性，Ｊａｎｅｃｅｋ 等在人工数 据集合上进行性能比较，当 ＮＭＦ 计算的秩比较小的 时候， ＦＷＡ 表现出了较其他算法较差的性能；当 ＮＭＦ 计算的秩变大的时候，ＦＷＡ 算法的性能明显提 高。 为了验证策略 ２ 的有效性，Ｊａｎｅｃｅｋ 等在人工数 据集合上进行性能比较，实验发现策略 ２ 对于 ＮＭＦ 计算的性能改进十分明显，尤其是在秩比较低的时 候，此外，实验结果表明对于策略 ２ 不同的群体智能 算法之间差异不明显。 ５．２ 图像识别 在图像识别领域，特征之间的距离度量方法对 于识别准确率的影响至关重要。 在生物特征尤其是 线条状的生物特征提取方法中，目前基于方向编码 特征提取方法效果较优。 在方向性特征提取方法中 典型的有竞争编码算法［６０］ ，掌纹方向编码［６１］ 和鲁 棒线方向编码［６２］ 。 对于这几种特征提取方法的距 离度量方法主要有汉明距离和角度距离方法。 在文献［５２］中，Ｚｈｅｎｇ Ｓ．和 Ｔａｎ 细致讨论了汉明 距离、角度距离之间的关系，据此提出了一种统一距 离作为距离度量方法。 Ｄｕ ＝ ｋ１ ａ１ ＋ ｋ２ ａ２ ＋ ｋ３ ａ３ （１６） 式中： ｋｉ 表示特征之间具有 ｉ 个方向差异的错判代 价， ａｉ 表示特征之间具有 ｉ 个方向差异的个数。 相对于文献［６３］ 讨论的统计距离方法，Ｚｈｅｎｇ Ｓ．和 Ｔａｎ 指出角度距离度量方法的性能并不一定恒 差于汉明距离度量方法，即 ｋ１ ≤ ｋ２ ≤ ｋ３ 并不一定恒 成立。 为了计算得到最优的参数组，Ｚｈｅｎｇ Ｓ．等使用 粒子群优化算法［４３］ 、 差分演化算法［４７］ 和烟花算 法［２２］进行参数优化。 在 ３ 个测试集合（人工数据 集、掌纹数据集和手指静脉数据集）上面进行实验验 证。 关于特征提取方法，文中使用了竞争编码算法、 掌纹方向编码和鲁棒线方向编码 ３ 种特征提取方 法。 实验结果表明采用群体智能优化算法进行优化 的距离度量方法能够显著降低 ＥＥＲ 值。 ５．３ 滤波器设计 目前，有不少学者将群体智能算法应用到滤波 器设计中。 Ｇａｏ 等［３３］ 提出使用文化烟花算法 ＣＡ⁃ ＦＷＡ 进行滤波器的设计， 并对比了 ＰＳＯ ［６４］ 、 ＱＰ⁃ ＳＯ ［３４］和 ＡＱＰＳＯ ［３５］ 。 实验结果表明，基于文化烟花 算法（ＣＡ⁃ＦＷＡ）设计的数字滤波器比使用 ＰＳＯ、ＱＰ⁃ ＳＯ 和 ＡＱＰＳＯ 设计的滤波器性能更好。 ５．４ 垃圾电子邮件检测 Ｈｅ 等［５３］ 提出使用烟花算法对基于局部免疫浓 ·５２４· 智 能 系 统 学 报 第 ９ 卷