《智能系统学报》：烟花算法研究进展（北京大学）

第9卷第5期 智能系统学报 Vol 9 No5 2014年10月 CAAI Transactions on Intelligent Systems Oct.2014 DOl: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- Recent advances in fireworks algorithm TAN Ying", ZHENG Shaoqiu (1. Key Laboratory of Machine Perception, Peking University, Beijing 100871, China; 2. School of Electronics Engineering and Com- ter 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 ptimization, 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- thms, 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 explosi 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 近些年,科研工作者在群体智能算法的研究中投入了大量精力,提出了许多新型算法和有效改进 方式,使得这一领域呈现出欣欣向荣的景象。关于 收稿日期:201409-05 群体智能的定义,存在许多版本,例如:G.Bemi和J 基金项目:国家自然科学基金资助项目(613519.610wang指出群体智能是由具有自组织能力的个体通 60875080) 通信作者:谭营.E-mil:ytan@ pku. edu 过组合从而表现出群体的行为的特性2

第 ９ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．５ ２０１４ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０９０１０ 烟花算法研究进展 谭营１， ２ ，郑少秋１， ２ （１．北京大学 机器感知与智能教育部重点实验室，北京 １００８７１； ２．北京大学 信息科学与技术学院，北京 １００８７１） 摘 要：烟花算法由于具有很强的优化问题求解的能力，近年来逐渐受到研究者的广泛关注。 对现有烟花算法的研 究工作进行了全面总结，主要包括烟花算法提出的背景、烟花算法的基本原理、单目标烟花算法的改进、混合算法、 多目标烟花算法、基于 ＧＰＵ 的并行烟花算法以及烟花算法在实际问题中的应用研究等。 对于单目标烟花算法及改 进算法、混合算法，文中给出了各种改进烟花算法的机制分析和对比研究，最后，给出了烟花算法的未来研究方向， 包括爆炸算子搜索机制的深入分析、烟花交互机制研究、多目标烟花算法研究、并行烟花算法研究、扩展烟花算法求 解的问题类型以及应用拓展。 关键词：群体智能；烟花算法；爆炸半径；自适应爆炸半径；动态搜索机制；多目标烟花算法；并行实现 中图分类号： ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０５⁃０５１５⁃１４ 中文引用格式：谭营，郑少秋． 烟花算法研究进展［Ｊ］． 智能系统学报， ２０１４， ９（５）： ５１５⁃５２８． 英文引用格式：ＴＡＮ Ｙｉｎｇ， ＺＨＥＮＧ Ｓｈａｏｑｉｕ． Ｒｅｃｅｎｔ ａｄｖａｎｃｅｓ ｉｎ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓ⁃ ｔｅｍｓ， ２０１４， ９（５）： ５１５⁃５２８． Ｒｅｃｅｎｔ ａｄｖａｎｃｅｓ ｉｎ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ ＴＡＮ Ｙｉｎｇ １， ２ ， ＺＨＥＮＧ Ｓｈａｏｑｉｕ １， ２ （１． Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｍａｃｈｉｎｅ Ｐｅｒｃｅｐｔｉｏｎ， Ｐｅｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １００８７１， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍ⁃ ｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｐｅｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １００８７１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ （ ＦＷＡ） ｈａｓ ｓｈｏｗｎ ｇｒｅａｔ ｓｕｃｃｅｓｓｅｓ ｉｎ ｄｅａｌｉｎｇ ｗｉｔｈ ｃｏｍｐｌｅｘ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ ａｎｄ ｈａｓ ａｔｔｒａｃｔｅｄ ａ ｇｒｅａｔ ａｍｏｕｎｔ ｏｆ ａｔｔｅｎｔｉｏｎ ｒｅｃｅｎｔｌｙ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ＦＷＡ ｗａｓ ｃｏｍｐｌｅｔｅｌｙ ａｎａｌｙｚｅｄ， Ｉｎｃｌｕｄｉｎｇ ｔｈｅ ＦＷＡ ｂａｃｋｇｒｏｕｎｄ ｅｖａｌｕａｔｉｏｎ， ｔｈｅ ｓｔｕｄｙ ｏｆ ｆｕｎｄａｍｅｎｔａｌ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ＦＷＡ， ｄｅｖｅｌｏｐｍｅｎｔｓ ｉｎ ｓｉｎｇｌｅ ｏｂｊｅｃｔｉｖｅ ＦＷＡ ｏｐｔｉｍｉｚａｔｉｏｎ， ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍｓ， ｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ， ｇｒａｐｈｉｃ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ（ＧＰＵ） ｂａｓｅｄ ｐａｒａｌｌｅｌ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ， ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎｓ ｉｎ ｐｒａｃｔｉｃｅ． Ｆｏｒ ｓｉｎｇｌｅ ｏｂｊｅｃｔｉｖｅ ＦＷＡ ａｎｄ ｉｍｐｒｏｖｅｄ ａｎｄ ｈｙｂｒｉｄ ａｌｇｏ⁃ ｒｉｔｈｍｓ， ｔｈｅ ｍｅｃｈａｎｉｓｍ ａｎａｌｙｓｉｓ ａｎｄ ｃｏｍｐａｒａｔｉｖｅ ｒｅｓｅａｒｃｈ ｏｆ ｖａｒｉｏｕｓ ｉｍｐｒｏｖｅｄ ＦＷＡｓ ａｒｅ ｇｉｖｅｎ ｉｎ ｔｈｉｓ ｐａｐｅｒ． Ｆｉｎａｌ⁃ ｌｙ， ｔｈｅ ｆｕｔｕｒｅ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎｓ ｆｏｒ ＦＷＡ ａｒｅ ｐｏｉｎｔｅｄ ｏｕｔ， ｗｈｉｃｈ ｉｎｃｌｕｄｅ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｅｘｐｌｏｓｉｏｎ ｏｐｅｒａｔｏｒ， ｓｔｕｄｙ ｏｆ ｉｎｔｅｒａｃｔｉｏｎ ｓｔｒａｔｅｇｉｅｓ ａｍｏｎｇ ｔｈｅ ｆｉｒｅｗｏｒｋｓ， ｒｅｓｅａｒｃｈ ｏｎ ｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ ａｎｄ ｐａｒａｌｌｅｌ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ， ｔｙｐｅｓ ｏｆ ｓｏｌｕｔｉｏｎｓ ｔｏ ｔｈｅ ｅｘｔｅｎｄｅｄ ＦＷＡ， ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｅｘｐａｎｓｉｏｎ． Ｋｅｙｗｏｒｄｓ：ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ； ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ； ｅｘｐｌｏｓｉｏｎ ａｍｐｌｉｔｕｄｅ； ａｄａｐｔｉｖｅ ｅｘｐｌｏｓｉｏｎ ａｍｐｌｉｔｕｄｅ； ｄｙｎａｍｉｃ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ； ｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ； ｐａｒａｌｌｅｌ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ 收稿日期：２０１４⁃０９⁃０５． 基金 项 目： 国 家 自 然 科 学 基 金 资 助 项 目 （ ６１３７５１１９、 ６１１７００５７、 ６０８７５０８０）． 通信作者：谭营． Ｅ⁃ｍａｉｌ：ｙｔａｎ＠ ｐｋｕ．ｅｄｕ．ｃｎ． 近些年，科研工作者在群体智能算法的研究中 投入了大量精力，提出了许多新型算法和有效改进 方式，使得这一领域呈现出欣欣向荣的景象。 关于 群体智能的定义，存在许多版本，例如：Ｇ． Ｂｅｎｉ 和 Ｊ． Ｗａｎｇ 指出群体智能是由具有自组织能力的个体通 过组 合 从 而 表 现 出 群 体 的 行 为 的 特 性［１⁃２］

516 智能系统学报 第9卷 Bonabeau、 Dorigo和 Theraulaz在《群体智能——从进展,因此,本文将对烟花算法进行了全面的综述。 自然到人工系统》书中指出群体智能是简单的个体 通过通信、协作等交互机制表现出群体智能行 1烟花算法 为。 Kennedy等指出群体智能是简单的具有信息1.1动机 处理能力的单元在交互过程中表现出简单个体不具 燃放烟花爆竹是中国传统节日尤其是除夕的 有的能够解决复杂问题的一种能力。Lim等指出项重要节日庆祝活动。在这一天,成千上万的烟花 群体智能是简单自制的代理单元展现出的集体的智爆竹在夜空中爆炸并绽放美丽的图案。通常,在市 能行为。 Krause等指出群体智能是两个或多个场上,不同价格的烟花爆炸产生不同的效果。一般 个体独立地或者部分独立地获取信息,信息的差异价格高昂(低廉)的烟花产生的火花数量比较多 通过个体的交互被组合或处理,然后产生区别于单(少),爆炸产生的火花分布的范围也较均匀(分 个个体能够产生的解决方案。总之,群体智能就散)。受到烟花在夜空中爆炸产生火花并照亮周围 是简单个体通过协作达到了拥有简单个体不具有的区域这一自然现象的启发,Tan和zhu在2010年提 问题解决能力。 出了烟花算法(FWA) 在群体智能算法的发展过程中,比较重要的里 点燃的烟花被发射到夜空中,爆炸产生火花继 程碑事件有:1987年, Craig Reynolds提出了一个使而照亮其临近的夜空,产生出一幅美丽的图案。事 用计算机模拟鸟飞行的模型;1991年, Dorigo根实上,一个优化问题的求解过程亦是如此。对于 据对自然界中蚁群觅食这一群体行为的观察研究提个最优化问题,尤其自变量是连续空间的最优化问 出了蚁群优化算法8;1995年 Kennedy和 Eberhart题,在整个解空间内,如何有效迅速地找到全局最优 根据对鸟群觅食这一群体行为的观察提出了粒子群解呢?在烟花算法中,烟花被看作为最优化问题的 优化算法。蚁群算法、粒子群优化算法发展过程解空间中一个可行解,那么烟花爆炸产生一定数量 中表现出强大的问题求解能力将群体智能的研究推火花的过程即为其搜索邻域的过程,如图1所示。 向了一个高潮,吸引了大量的科研工作者投入到群 体智能领域进行研究。 群体智能算法模拟简单个体通过协作求解复杂 问题的过程,具有以下特点0:1)组成群体的个体 通常行为、能力都较为简单,个体之间无差别;2)个 体通过协作完成复杂问题的求解,群体中无中心控 制个体。 近年来,群体智能算法的研究内容主要包括 1)已有的群体智能算法性能的提高,比如研究蚁群 优化算法、粒子群优化算法的收敛性加速策略、自适 应策略等1;2)新型群体智能算法的提出1;3) (a)单个烟花爆炸产生火花 多目标群体智能算法研究,目前大部分有影响力的 群体智能算法都有了其多目标算法的版本,例如 NSGA-II、 SPEA-IILD、 NSPSO1等;4)并行化群 体智能算法研究,比如基于图像处理单元(GPU)的 粒子群优化算法、基于GPU的烟花算法)、基 于GPU的遗传算法等;5)应用研究,尝试将群体 智能算法应用到更多更广阔的领域 自2000年以来,一系列新型群体智能算法相继 被提出。在2010年,Tan和Zhu根据对于烟花爆 炸产生火花这一自然现象的观察提出了烟花算法。 (b)优化问题搜索过程 尽管文献[21]对烟花算法的部分研究工作进行了图1真实的烟花爆炸和优化问题解搜索过程对比示意 简要总结,但是文献[21]总结的工作较为初步,尤 Fig 1 Comparison between fireworks explosion and so 其是近一年来烟花算法的研究工作取得了一些新的 lution search for optimization problem

Ｂｏｎａｂｅａｕ、Ｄｏｒｉｇｏ 和 Ｔｈｅｒａｕｌａｚ 在《群体智能———从 自然到人工系统》书中指出群体智能是简单的个体 通过通 信、 协 作 等 交 互 机 制 表 现 出 群 体 智 能 行 为［３］ 。 Ｋｅｎｎｅｄｙ 等指出群体智能是简单的具有信息 处理能力的单元在交互过程中表现出简单个体不具 有的能够解决复杂问题的一种能力［４］ 。 Ｌｉｕ 等指出 群体智能是简单自制的代理单元展现出的集体的智 能行为［５］ 。 Ｋｒａｕｓｅ 等指出群体智能是两个或多个 个体独立地或者部分独立地获取信息，信息的差异 通过个体的交互被组合或处理，然后产生区别于单 个个体能够产生的解决方案［６］ 。 总之，群体智能就 是简单个体通过协作达到了拥有简单个体不具有的 问题解决能力。 在群体智能算法的发展过程中，比较重要的里 程碑事件有：１９８７ 年，Ｃｒａｉｇ Ｒｅｙｎｏｌｄｓ 提出了一个使 用计算机模拟鸟飞行的模型［７］ ；１９９１ 年，Ｄｏｒｉｇｏ 根 据对自然界中蚁群觅食这一群体行为的观察研究提 出了蚁群优化算法［８］ ；１９９５ 年 Ｋｅｎｎｅｄｙ 和 Ｅｂｅｒｈａｒｔ 根据对鸟群觅食这一群体行为的观察提出了粒子群 优化算法［９］ 。 蚁群算法、粒子群优化算法发展过程 中表现出强大的问题求解能力将群体智能的研究推 向了一个高潮，吸引了大量的科研工作者投入到群 体智能领域进行研究。 群体智能算法模拟简单个体通过协作求解复杂 问题的过程，具有以下特点［１０］ ：１）组成群体的个体 通常行为、能力都较为简单，个体之间无差别；２）个 体通过协作完成复杂问题的求解，群体中无中心控 制个体。 近年来，群体智能算法的研究内容主要包括： １）已有的群体智能算法性能的提高，比如研究蚁群 优化算法、粒子群优化算法的收敛性加速策略、自适 应策略等［１１⁃ １３］ ；２）新型群体智能算法的提出［１４］ ；３） 多目标群体智能算法研究，目前大部分有影响力的 群体智能算法都有了其多目标算法的版本，例如 ＮＳＧＡ⁃ＩＩ ［１５］ 、ＳＰＥＡ⁃ＩＩ ［１６］ 、ＮＳＰＳＯ ［１７］ 等；４） 并行化群 体智能算法研究，比如基于图像处理单元（ＧＰＵ）的 粒子群优化算法［１８］ 、基于 ＧＰＵ 的烟花算法［１９］ 、基 于 ＧＰＵ 的遗传算法［２０］等；５）应用研究，尝试将群体 智能算法应用到更多更广阔的领域。 自 ２０００ 年以来，一系列新型群体智能算法相继 被提出［１４］ 。 在 ２０１０ 年，Ｔａｎ 和 Ｚｈｕ 根据对于烟花爆 炸产生火花这一自然现象的观察提出了烟花算法。 尽管文献［２１］对烟花算法的部分研究工作进行了 简要总结，但是文献［２１］总结的工作较为初步，尤 其是近一年来烟花算法的研究工作取得了一些新的 进展，因此，本文将对烟花算法进行了全面的综述。 １ 烟花算法 １．１ 动机 燃放烟花爆竹是中国传统节日尤其是除夕的一 项重要节日庆祝活动。 在这一天，成千上万的烟花 爆竹在夜空中爆炸并绽放美丽的图案。 通常，在市 场上，不同价格的烟花爆炸产生不同的效果。 一般 价格高昂（低廉） 的烟花产生的火花数量比较多 （少），爆炸产生的火花分布的范围也较均匀（ 分 散）。 受到烟花在夜空中爆炸产生火花并照亮周围 区域这一自然现象的启发， Ｔａｎ 和 Ｚｈｕ 在 ２０１０ 年提 出了烟花算法（ＦＷＡ） ［２２］ 。 点燃的烟花被发射到夜空中，爆炸产生火花继 而照亮其临近的夜空，产生出一幅美丽的图案。 事 实上，一个优化问题的求解过程亦是如此。 对于一 个最优化问题，尤其自变量是连续空间的最优化问 题，在整个解空间内，如何有效迅速地找到全局最优 解呢？ 在烟花算法中，烟花被看作为最优化问题的 解空间中一个可行解，那么烟花爆炸产生一定数量 火花的过程即为其搜索邻域的过程，如图 １ 所示。 （ａ） 单个烟花爆炸产生火花 （ｂ） 优化问题搜索过程 图 １ 真实的烟花爆炸和优化问题解搜索过程对比示意 Ｆｉｇ．１ Ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ ｆｉｒｅｗｏｒｋｓ ｅｘｐｌｏｓｉｏｎ ａｎｄ ｓｏ⁃ ｌｕｔｉｏｎ ｓｅａｒｃｈ ｆｏｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ·５１６· 智 能 系 统 学 报 第 ９ 卷

第5期 谭营,等:烟花算法研究进展 为了能够有效地进行搜索,这里要求解空间中一定数量的个体作为烟花进入下一代的迭代 解的邻域有意义,同时需要保证在某一有限的范围 烟花算法具有局部搜索能力和全局搜索能力自 内解和其邻域的其他解具有相似的性质——“靠调节机制。烟花算法中每个烟花的爆炸半径和爆炸 近是一种性质”。这个要求是烟花算法应用于优火花数是不同的,适应度值差的烟花的爆炸半径较 化求解的有效性关键,因此在实际使用烟花算法求大,使其具有更大的“探索能力”——勘探性。适应 解优化问题时,在问题建模和解的编码过程中,无论度值好的烟花的爆炸半径较小,使其能够在该位置 是离散编码还是连续编码都需要满足这一个基本条周围具有更大的“挖掘能力”——开采性。此外,高 件。此外,烟花种群中各个烟花根据相对于其他烟斯变异火花的引入可以进一步增加种群的多样性。 花的适应度值进行资源分配和信息交互使得整个种文献[24]给出了一个关于烟花的爆炸半径和爆炸 群能够在全局搜索能力和局部搜索能力之间达到一火花数目对于烟花算法性能的影响的简要分析 个平衡,而且烟花的爆炸搜索机制使得单个烟花具1.3算子分析 有很强的局部爆发性。因此,烟花算法中烟花之间 不失一般性,假设待求解的优化问题形式如下 进行的资源的交互(爆炸火花数目和爆炸半径)使 Minf(x)∈R,x∈ 得烟花算法成为一种新型的群体智能算法。 式中:为解的可行域。 算法框架 使用烟花算法对优化问题(1)进行求解的目标 烟花算法的算法执行流程如图2所示。 是在可行域Ω内,寻找一点x,使得x具有全局最 初始化M个位置 小的适应度值。 在烟花算法中,爆炸算子(即爆炸产生火花操 在N个位置释放烟花 作)、变异算子(高斯变异产生火花操作)和选择策 略(即选择下一代烟花操作)是最重要的3个组成 我得 爆炸火花 部分,直接决定烟花算法的性能优劣, 高斯火花 1)爆炸算子 在可行域Ω内初始化一定数量烟花,对烟花位 是否满足 Y 置的适应度值进行评估。为了差异化不同位置的烟 终止条件 花,一般适应度值较好(即适应度值较小)的烟花能 够获取更多的资源,在较小的范围内产生更多的火 花,具有对于该烟花位置的强大的局部搜索能力 选择M个位置 结束 反之,适应度值较大的烟花只能获取相对较少的资 源,在较大的范围内产生数量较少的火花,具有一定 2烟花算法执行流程图 的全局搜索能力。 Fig 2 Flowchart of fireworks algorithm 为了达到烟花差异化的目的,即开采性和勘探 烟花算法具体包括以下几个步骤 性兼顾的目标,在烟花算法中,每个烟花的爆炸半径 每乙)在可行解空间中随机产生一定数量的烟花,和爆炸产生的火花数目是根据其相对于烟花种群中 每个烟花代表解空间中的一个可行解。 其他烟花适应度值计算得到的。对于烟花x;,其爆 2)根据优化目标函数计算每个烟花的适应度炸半径A和爆炸火花数目S的计算公式分别为 值,并据此确定烟花质量的好坏,以在不同爆炸半径 f(x)-ymin +e 下产生不同数量的火花。在烟花算法中,作者使用 A=A (2) 了两种形式的火花,分别是爆炸火花和高斯变异火 ∑((x)-y。)+E 花。其中爆炸火花主要负责对烟花邻近区域的搜 索,适应度值好的烟花在较小的邻近区域内产生较 多的火花,反之,适应度值差的烟花在较大的邻近区 ∑(ym-f(x))+s 域内产生较少的火花。相对于爆炸火花,高斯火花式中:ymn=min(f(x;)),(i=1,2,…,N)为当前烟 的引入增强了种群的多样性。 花种群中适应度最小值,y==max(f(x;)),(i=1, 3)判定是否满足终止条件。如果满足则停止2,…,N)是当前烟花种群中适应度最大值。A是 搜索,否则在爆炸火花、高斯变异火花和烟花中选择常数,用来调整爆炸半径大小,M是一常数,用来调

为了能够有效地进行搜索，这里要求解空间中 解的邻域有意义，同时需要保证在某一有限的范围 内，解和其邻域的其他解具有相似的性质———“靠 近是一种性质” ［２３］ 。 这个要求是烟花算法应用于优 化求解的有效性关键，因此在实际使用烟花算法求 解优化问题时，在问题建模和解的编码过程中，无论 是离散编码还是连续编码都需要满足这一个基本条 件。 此外，烟花种群中各个烟花根据相对于其他烟 花的适应度值进行资源分配和信息交互使得整个种 群能够在全局搜索能力和局部搜索能力之间达到一 个平衡，而且烟花的爆炸搜索机制使得单个烟花具 有很强的局部爆发性。 因此，烟花算法中烟花之间 进行的资源的交互（爆炸火花数目和爆炸半径） 使 得烟花算法成为一种新型的群体智能算法。 １．２ 算法框架 烟花算法的算法执行流程如图 ２ 所示。 图 ２ 烟花算法执行流程图 Ｆｉｇ．２ Ｆｌｏｗｃｈａｒｔ ｏｆ ｆｉｒｅｗｏｒｋｓ ａｌｇｏｒｉｔｈｍ 烟花算法具体包括以下几个步骤： １）在可行解空间中随机产生一定数量的烟花， 每个烟花代表解空间中的一个可行解。 ２）根据优化目标函数计算每个烟花的适应度 值，并据此确定烟花质量的好坏，以在不同爆炸半径 下产生不同数量的火花。 在烟花算法中，作者使用 了两种形式的火花，分别是爆炸火花和高斯变异火 花。 其中爆炸火花主要负责对烟花邻近区域的搜 索，适应度值好的烟花在较小的邻近区域内产生较 多的火花，反之，适应度值差的烟花在较大的邻近区 域内产生较少的火花。 相对于爆炸火花，高斯火花 的引入增强了种群的多样性。 ３）判定是否满足终止条件。 如果满足则停止 搜索，否则在爆炸火花、高斯变异火花和烟花中选择 一定数量的个体作为烟花进入下一代的迭代。 烟花算法具有局部搜索能力和全局搜索能力自 调节机制。 烟花算法中每个烟花的爆炸半径和爆炸 火花数是不同的，适应度值差的烟花的爆炸半径较 大，使其具有更大的“探索能力”———勘探性。 适应 度值好的烟花的爆炸半径较小，使其能够在该位置 周围具有更大的“挖掘能力”———开采性。 此外，高 斯变异火花的引入可以进一步增加种群的多样性。 文献［２４］给出了一个关于烟花的爆炸半径和爆炸 火花数目对于烟花算法性能的影响的简要分析。 １．３ 算子分析 不失一般性，假设待求解的优化问题形式如下： Ｍｉｎ ｆ（ｘ） ∈ Ｒ，ｘ ∈ Ω （１） 式中： Ω 为解的可行域。 使用烟花算法对优化问题（１）进行求解的目标 是在可行域 Ω 内，寻找一点 ｘ → ，使得 ｘ → 具有全局最 小的适应度值。 在烟花算法中，爆炸算子（即爆炸产生火花操 作）、变异算子（高斯变异产生火花操作）和选择策 略（即选择下一代烟花操作）是最重要的 ３ 个组成 部分，直接决定烟花算法的性能优劣。 １）爆炸算子 在可行域 Ω 内初始化一定数量烟花，对烟花位 置的适应度值进行评估。 为了差异化不同位置的烟 花，一般适应度值较好（即适应度值较小）的烟花能 够获取更多的资源，在较小的范围内产生更多的火 花，具有对于该烟花位置的强大的局部搜索能力。 反之，适应度值较大的烟花只能获取相对较少的资 源，在较大的范围内产生数量较少的火花，具有一定 的全局搜索能力。 为了达到烟花差异化的目的，即开采性和勘探 性兼顾的目标，在烟花算法中，每个烟花的爆炸半径 和爆炸产生的火花数目是根据其相对于烟花种群中 其他烟花适应度值计算得到的。 对于烟花 ｘｉ ，其爆 炸半径 Ａｉ 和爆炸火花数目 Ｓｉ 的计算公式分别为 Ａｉ ＝ Ａ ＾ × ｆ（ｘｉ） － ｙｍｉｎ ＋ ε ∑ Ｎ ｉ ＝ １ （ｆ（ｘｉ） － ｙｍｉｎ ） ＋ ε （２） Ｓｉ ＝ Ｍ × ｙｍａｘ － ｆ（ｘｉ） ＋ ε ∑ Ｎ ｉ ＝ １ （ｙｍａｘ － ｆ（ｘｉ）） ＋ ε （３） 式中： ｙｍｉｎ ＝ ｍｉｎ（ｆ（ｘｉ）） ，（ｉ ＝ １，２，…，Ｎ） 为当前烟 花种群中适应度最小值， ｙｍａｘ ＝ ｍａｘ（ｆ（ｘｉ）），（ｉ ＝ １， ２，…，Ｎ） 是当前烟花种群中适应度最大值。 Ａ ＾ 是一 常数，用来调整爆炸半径大小， Ｍ 是一常数，用来调 第 ５ 期 谭营，等：烟花算法研究进展 ·５１７·

智能系统学报 第9卷 整产生的爆炸火花数目大小,E是一个机器最小量,的个体之间的距离之和。在候选者集合中,如果个 用来避免除零操作 体密度较高,即该个体周围有很多其他候选者个体 在式(3)中,为了限制适应度值好的烟花位置时,该个体被选择的概率会降低 不会产生过多的爆炸火花,同时适应度值差的烟花 基于前面的叙述,烟花算法的具体执行如下 位置不会产生过少的火花粒子,文献[22]对于产生 1)参数初始化 的火花个数进行了如下的限制 随机在解空间初始化N个位置x;,即N个烟 花 2)循环如下的(1)~(4),直到满足终止条件 round(a *M), s,< aM (1)/评估每个烟花适应度值,计算每个烟花 ound(b*M),S,>bM,a<b<1(4)爆炸半径和爆炸火花数 ound(S1),其他 fori=l to n do 式中:a、b是两个常数, round(·)是根据四舍五入 计算每个烟花的适应度值f(x1); 原则的取整函数。 计算每个烟花的爆炸半径A和产生的爆炸火 2)变异算子 花数目S;; 为了增加爆炸火花种群的多样性,烟花算法引 endfor 人了变异算子用于产生变异火花,即高斯变异火花 (2)∥/产生爆炸火花 高斯变异火花产生的过程如下:首先在烟花种群中 fori=l to n do 随机选择一个烟花x:,然后对该烟花随机选择一定 forj= 1 to S, do 数量的维度进行高斯变异操作。对于烟花x1的某 一个选择得到的维度k执行高斯变异操作即为 随机选择z个维度作为集合DS xa=xa×e z= round(D×U(0,1)),D为x1的维数(U(a 式中:c~N(1,1),N(1,1)表示均值为1,方差为b)表示为在区间[a,b】中产生服从均匀分布的随 1的高斯分布。 机数的值); 在爆炸算子和变异算子分别产生爆炸火花和高 计算位置偏移h=A1×U(-1,1) 斯变异火花过程中,可能产生的火花会超出可行域 for each k in ds 的边界范围。当火花x在维度k上超出边界,将 xk=x+hi 通过式(6)的映射规则映射到一个新的位置。 越界检测; )(6) 式中:xBA、x1B4为解空间在维度k上的上边界和 将x保存到爆炸火花种群中; 下边界。 3)选择策略 endoR 为使烟花种群中优秀的信息能够传递到下一代 (3)//产生M个高斯变异火花 种群中,在产生爆炸火花和高斯变异火花后,算法会 在候选者集合(包括烟花、爆炸火花和高斯变异火 I to m 花)中选择一定数量的个体作为下一代的烟花 随机选择火花x1 假设候选者集合为K,烟花种群大小为N。候 随机选择z个维度作为集合DS, 选者集合中适应度值最小的个体会被确定性地选择 z= round(D×U(0,1),D为x,的维数 计算高斯变异参数e=N(1,1)(产生矩阵为1 到下一代作为烟花,而对剩下的N-1个烟花的选 择使用轮盘赌的方法在候选者集合中进行选择。对 方差为1的随机数) for each k in ds 于候选者x;,其被选择概率的计算公式为 r=t. xe (7) 越界检测; R(x)=∑(x1-x)=∑‖x1-xⅡ(8) 将x保存到高斯变异火花种群中 式中:R(x)为当前个体到候选者集合K除x1所有 (4)从烟花、爆炸火花、高斯变异火花种群中选

整产生的爆炸火花数目大小， ε 是一个机器最小量， 用来避免除零操作。 在式（３）中，为了限制适应度值好的烟花位置 不会产生过多的爆炸火花，同时适应度值差的烟花 位置不会产生过少的火花粒子，文献［２２］对于产生 的火花个数进行了如下的限制： Ｓ ＾ ｉ ＝ ｒｏｕｎｄ（ａ∗Ｍ），Ｓｉ ＜ ａＭ ｒｏｕｎｄ（ｂ∗Ｍ），Ｓｉ ＞ ｂＭ，ａ ＜ ｂ ＜ １ ｒｏｕｎｄ（Ｓｉ），其他 ì î í ï ï ïï （４） 式中： ａ、ｂ 是两个常数，ｒｏｕｎｄ（·）是根据四舍五入 原则的取整函数。 ２）变异算子 为了增加爆炸火花种群的多样性，烟花算法引 入了变异算子用于产生变异火花，即高斯变异火花。 高斯变异火花产生的过程如下：首先在烟花种群中 随机选择一个烟花 ｘｉ ，然后对该烟花随机选择一定 数量的维度进行高斯变异操作。 对于烟花 ｘｉ 的某 一个选择得到的维度 ｋ 执行高斯变异操作即为 ｘ ＾ ｉｋ ＝ ｘｉｋ × ｅ （５） 式中： ｅ ～ Ｎ（１，１） ， Ｎ（１，１） 表示均值为 １，方差为 １ 的高斯分布。 在爆炸算子和变异算子分别产生爆炸火花和高 斯变异火花过程中，可能产生的火花会超出可行域 Ω 的边界范围。 当火花 ｘｉ 在维度 ｋ 上超出边界，将 通过式（６）的映射规则映射到一个新的位置。 ｘ ＾ ｉｋ ＝ ｘＬＢ，ｋ ＋｜ ｘ ＾ ｉｋ ｜ ％（ｘＵＢ，ｋ － ｘＬＢ，ｋ） （６） 式中： ｘＵＢ，ｋ 、 ｘＬＢ，ｋ 为解空间在维度 ｋ 上的上边界和 下边界。 ３）选择策略 为使烟花种群中优秀的信息能够传递到下一代 种群中，在产生爆炸火花和高斯变异火花后，算法会 在候选者集合（包括烟花、爆炸火花和高斯变异火 花）中选择一定数量的个体作为下一代的烟花。 假设候选者集合为 Ｋ ，烟花种群大小为 Ｎ 。 候 选者集合中适应度值最小的个体会被确定性地选择 到下一代作为烟花，而对剩下的 Ｎ － １ 个烟花的选 择使用轮盘赌的方法在候选者集合中进行选择。 对 于候选者 ｘｉ ，其被选择概率的计算公式为 ｐ（ｘｉ） ＝ Ｒ（ｘｉ） ∑ｘｊ∈Ｋ ｘｊ （７） Ｒ（ｘｉ） ＝ ∑ｘｊ∈Ｋ ｄ（ｘｉ － ｘｊ） ＝ ∑ｘｊ∈Ｋ ‖ｘｉ － ｘｊ‖ （８） 式中： Ｒ（ｘｉ） 为当前个体到候选者集合 Ｋ 除 ｘｉ 所有 的个体之间的距离之和。 在候选者集合中，如果个 体密度较高，即该个体周围有很多其他候选者个体 时，该个体被选择的概率会降低。 基于前面的叙述，烟花算法的具体执行如下： １）参数初始化 随机在解空间初始化 Ｎ 个位置 ｘｉ ，即 Ｎ 个烟 花。 ２）循环如下的（１） ～ （４），直到满足终止条件。 （１） ／ ／ 评估每个烟花适应度值，计算每个烟花 爆炸半径和爆炸火花数 ｆｏｒ ｉ ＝ １ ｔｏ Ｎ ｄｏ 计算每个烟花的适应度值 ｆ（ｘｉ） ； 计算每个烟花的爆炸半径 Ａｉ 和产生的爆炸火 花数目 Ｓｉ ； ｅｎｄｆｏｒ （２） ／ ／ 产生爆炸火花 ｆｏｒ ｉ ＝ １ ｔｏ Ｎ ｄｏ ｆｏｒ ｊ ＝ １ ｔｏ Ｓｉ ｄｏ ｘ ＾ ｉ ＝ ｘｉ ； 随机选择 ｚ 个维度作为集合 ＤＳ， ｚ ＝ ｒｏｕｎｄ（Ｄ × Ｕ（０，１）） ， Ｄ 为 ｘｉ 的维数（ Ｕ（ａ， ｂ） 表示为在区间 ［ａ，ｂ］ 中产生服从均匀分布的随 机数的值）； 计算位置偏移 ｈ ＝ Ａｉ × Ｕ（ － １，１） ； ｆｏｒ ｅａｃｈ ｋ ｉｎ ＤＳ ｘ ＾ ｉｋ ＝ ｘｉｋ ＋ ｈ ； 越界检测； ｅｎｄｆｏｒ 将 ｘ ＾ ｉｋ 保存到爆炸火花种群中； ｅｎｄｆｏｒ ｅｎｄｆｏｒ （３） ／ ／ 产生 Ｍ ＾ 个高斯变异火花 ｆｏｒ ｉ ＝ １ ｔｏ Ｍ ＾ ｄｏ 随机选择火花 ｘｉ ； 随机选择 ｚ 个维度作为集合 ＤＳ， ｚ ＝ ｒｏｕｎｄ（Ｄ × Ｕ（０，１）） ， Ｄ 为 ｘｉ 的维数； 计算高斯变异参数 ｅ ＝ Ν（１，１） （产生矩阵为 １， 方差为 １ 的随机数）； ｆｏｒ ｅａｃｈ ｋ ｉｎ ＤＳ ｘ ＾ ｉｋ ＝ ｘｉｋ × ｅ ； 越界检测； ｅｎｄｆｏｒ 将 ｘ ＾ ｉｋ 保存到高斯变异火花种群中； ｅｎｄｆｏｒ （４）从烟花、爆炸火花、高斯变异火花种群中选 ·５１８· 智 能 系 统 学 报 第 ９ 卷

第5期 谭营,等:烟花算法研究进展 519 择N个个体作为下一代迭代计算的烟花 索烟花算法( dynFWA)和自适应烟花算法(AF 3)返回优化结果 WA)。在 dynFWA中,烟花爆炸半径的变化过程依 1.4与遗传算法、粒子群优化算法搜索机制比较据烟花种群产生的火花适应度值是否发生改进(即 烟花算法相对于遗传算法和粒子群优化算法表优化得到适应度值更优的火花)决定。在AFWA 现出了不同的搜索机制。在遗传算法中,染色体通中,烟花的爆炸半径的确定依据当前种群适应度值 常被编码成一个优化问题的解,染色体之间通过交最优的个体和一个特定个体之间的距离计算。这两 叉和变异操作产生新的解。在编码空间上,子代染种方法由于采用了自适应调整爆炸半径的机制,都 色体和父代染色体具有相近的性质。粒子群优化算大大提升了增强型烟花算法的性能。 法通过种群中的粒子间相互协作,每个粒子通过种 第2类算法改进的工作有: Zheng Y.等提出 群中的全局最优信息和自身历史最优信息进行指导使用差分演化算法和烟花算法进行混合的新型算法 搜索,进而更新粒子的位置。对于烟花算法,其主要FWA-DE。Yu等12用差分变异替换基本烟花算法 用于连续空间的优化问题求解,烟花算法采用爆炸中的高斯变异,所提出的FWA-DM算法比EFWA算 搜索机制。此外,烟花之间通过交互机制来计算每法的性能更好。Gao等[3]提出使用文化算法和烟 个烟花的爆炸半径和爆炸火花数目,使得适应度值花算法进行混合的文化烟花算法(CA-FWA),并将 较好的烟花获取更多的资源,反之,适应度值较差的文化烟花算法应用到滤波器的设计上,取得了相对 烟花获取较少的资源。烟花算法和遗传算法具有 于量子粒子群优化算法(QPS1)和自适应量子粒 些类似的地方,比如遗传算法可以通过变异概率的子群优化算法(AQPS03)较优的性能。 Zheng 大小在“编码空间”中产生一个相对于当前染色体等{将生物地理学优化算法引入增强烟花算法,提 距离较远/近的解,而同样地,烟花算法可以通过出混合算法 BBO-FWA,提高了烟花间的交互能力 不同的爆炸半径大/小产生距离烟花较远/近的爆炸21基于适应度函数估计的烟花算法 火花,烟花算法在迭代过程中,种群中每个烟花个体 进化计算加速策略研究是一个比较重要的研究 在一次迭代过程中会产生多个个体,而粒子群优化方向。1990年, Takagi等提出对于一个简单的单 算法通常只产生一个个体,烟花算法的这种爆炸机峰优化问题求解,可以通过进化算法优化的解信息 制使得其对于烟花附近的区域的搜索更加彻底。 去估计搜索空间形状,然后对估计得到的简单曲面 2几种典型的改进烟花算法 求解其最优值位置并引入到种群中作为启发式信息 来加速搜索过程。基于此,在烟花算法中,在每一代 烟花算法自提出后就受到了诸多科研工作者的烟花产生爆炸火花和高斯变异火花以后,Pei等 关注,许多改进算法相继被提出。改进烟花算法主尝试使用当前种群的候选者集合(烟花、爆炸火花 要可以被分为两类,一类是在基本烟花算法的基础和高斯变异火花)的位置信息和适应度值信息去估 上进行算子的分析和改进,另一类是与其他启发式计整个搜索空间的形状,然后根据估计得到的形状 算法的混合算法的研究。 等作为启发式信息。 第一类算法改进的工作主要有:Pei等21提出 文献[26]讨论了3种不同的抽样策略:基于适 基于适应度函数估计的加速型烟花算法( ACFWA)。应度值的抽样策略,即在候选者集合中选择k个适 AcFWA使用烟花及其产生的爆炸火花、高斯变异火应度值最好的样本个体;基于距离的抽样策略,即在 花种群的位置信息和适应度值信息来估计搜索空间候选者集合中选择欧式距离上离最优点位置最近的 的形状,然后使用估计的形状的最优位置作为启发k个样本个体;随机抽样策略,即随机从候选者集合 式信息引入到当前种群进行加速搜索。Liu等2提中选择k个样本个体。对于搜索空间的估计,文献 出一种构造型烟花算法(HFWA),使用了一种新型中将D维搜索空间投影到每一个维数上面,并使用 的烟花爆炸半径和爆炸火花数目的计算方式,相对抽样得到的样本个体在该维度上的投影位置和适应 于基本烟花算法,获得了性能上的提升。 Zheng s.度值信息依据估计模型进行形状估计。 等]对于基本烟花算法的爆炸算子、变异算子、选 在实验中,抽样点个数被设置成3、5和10,用 择策略和映射规则等进行了细致的分析,针对烟花于研究抽样点个数对于算法性能的影响。对于通过 算法存在的缺陷进行了逐一改进,并提出了增强型选择有限的样本点估计其搜索空间形状这一问题 烟花算法(EFWA)。接着, Zheng S.等{和Ii曲面估计形状的选择十分重要。文献中使用一次最 等分别提出了两种自适应半径策略——动态搜小二乘法、二次最小二乘法来研究模型的选择对于

择 Ｎ 个个体作为下一代迭代计算的烟花； ３）返回优化结果。 １．４ 与遗传算法、粒子群优化算法搜索机制比较 烟花算法相对于遗传算法和粒子群优化算法表 现出了不同的搜索机制。 在遗传算法中，染色体通 常被编码成一个优化问题的解，染色体之间通过交 叉和变异操作产生新的解。 在编码空间上，子代染 色体和父代染色体具有相近的性质。 粒子群优化算 法通过种群中的粒子间相互协作，每个粒子通过种 群中的全局最优信息和自身历史最优信息进行指导 搜索，进而更新粒子的位置。 对于烟花算法，其主要 用于连续空间的优化问题求解，烟花算法采用爆炸 搜索机制。 此外，烟花之间通过交互机制来计算每 个烟花的爆炸半径和爆炸火花数目，使得适应度值 较好的烟花获取更多的资源，反之，适应度值较差的 烟花获取较少的资源。 烟花算法和遗传算法具有一 些类似的地方，比如遗传算法可以通过变异概率的 大小在“编码空间”中产生一个相对于当前染色体 距离较远／ 近的解［２５］ ，而同样地，烟花算法可以通过 不同的爆炸半径大／ 小产生距离烟花较远／ 近的爆炸 火花，烟花算法在迭代过程中，种群中每个烟花个体 在一次迭代过程中会产生多个个体，而粒子群优化 算法通常只产生一个个体，烟花算法的这种爆炸机 制使得其对于烟花附近的区域的搜索更加彻底。 ２ 几种典型的改进烟花算法 烟花算法自提出后就受到了诸多科研工作者的 关注，许多改进算法相继被提出。 改进烟花算法主 要可以被分为两类，一类是在基本烟花算法的基础 上进行算子的分析和改进，另一类是与其他启发式 算法的混合算法的研究。 第一类算法改进的工作主要有：Ｐｅｉ 等［２６］ 提出 基于适应度函数估计的加速型烟花算法（ＡｃＦＷＡ）。 ＡｃＦＷＡ 使用烟花及其产生的爆炸火花、高斯变异火 花种群的位置信息和适应度值信息来估计搜索空间 的形状，然后使用估计的形状的最优位置作为启发 式信息引入到当前种群进行加速搜索。 Ｌｉｕ 等［２７］提 出一种构造型烟花算法（ ＩＦＷＡ），使用了一种新型 的烟花爆炸半径和爆炸火花数目的计算方式，相对 于基本烟花算法，获得了性能上的提升。 Ｚｈｅｎｇ Ｓ． 等［２８］对于基本烟花算法的爆炸算子、变异算子、选 择策略和映射规则等进行了细致的分析，针对烟花 算法存在的缺陷进行了逐一改进，并提出了增强型 烟花 算 法 （ ＥＦＷＡ）。 接 着， Ｚｈｅｎｇ Ｓ． 等［２９］ 和 Ｌｉ 等［３０］分别提出了两种自适应半径策略———动态搜 索烟花算法 （ ｄｙｎＦＷＡ） 和自适应烟花算法 （ ＡＦ⁃ ＷＡ）。 在 ｄｙｎＦＷＡ 中，烟花爆炸半径的变化过程依 据烟花种群产生的火花适应度值是否发生改进（即 优化得到适应度值更优的火花） 决定。 在 ＡＦＷＡ 中，烟花的爆炸半径的确定依据当前种群适应度值 最优的个体和一个特定个体之间的距离计算。 这两 种方法由于采用了自适应调整爆炸半径的机制，都 大大提升了增强型烟花算法的性能。 第 ２ 类算法改进的工作有：Ｚｈｅｎｇ Ｙ．等［３１］ 提出 使用差分演化算法和烟花算法进行混合的新型算法 ＦＷＡ⁃ＤＥ。 Ｙｕ 等［３２］ 用差分变异替换基本烟花算法 中的高斯变异，所提出的 ＦＷＡ⁃ＤＭ 算法比 ＥＦＷＡ 算 法的性能更好。 Ｇａｏ 等［３３ ］ 提出使用文化算法和烟 花算法进行混合的文化烟花算法（ＣＡ⁃ＦＷＡ），并将 文化烟花算法应用到滤波器的设计上，取得了相对 于量子粒子群优化算法（ＱＰＳＯ ［３４］ ）和自适应量子粒 子群 优 化 算 法 （ ＡＱＰＳＯ ［３５］ ） 较 优 的 性 能。 Ｚｈｅｎｇ 等［３７］将生物地理学优化算法引入增强烟花算法，提 出混合算法 ＢＢＯ⁃ＦＷＡ，提高了烟花间的交互能力。 ２．１ 基于适应度函数估计的烟花算法 进化计算加速策略研究是一个比较重要的研究 方向。 １９９９ 年，Ｔａｋａｇｉ 等［３６］提出对于一个简单的单 峰优化问题求解，可以通过进化算法优化的解信息 去估计搜索空间形状，然后对估计得到的简单曲面 求解其最优值位置并引入到种群中作为启发式信息 来加速搜索过程。 基于此，在烟花算法中，在每一代 烟花产生爆炸火花和高斯变异火花以后，Ｐｅｉ 等［２６］ 尝试使用当前种群的候选者集合（烟花、爆炸火花 和高斯变异火花）的位置信息和适应度值信息去估 计整个搜索空间的形状，然后根据估计得到的形状 等作为启发式信息。 文献［２６］讨论了 ３ 种不同的抽样策略：基于适 应度值的抽样策略，即在候选者集合中选择 ｋ 个适 应度值最好的样本个体；基于距离的抽样策略，即在 候选者集合中选择欧式距离上离最优点位置最近的 ｋ 个样本个体；随机抽样策略，即随机从候选者集合 中选择 ｋ 个样本个体。 对于搜索空间的估计，文献 中将 Ｄ 维搜索空间投影到每一个维数上面，并使用 抽样得到的样本个体在该维度上的投影位置和适应 度值信息依据估计模型进行形状估计。 在实验中，抽样点个数被设置成 ３、５ 和 １０，用 于研究抽样点个数对于算法性能的影响。 对于通过 选择有限的样本点估计其搜索空间形状这一问题， 曲面估计形状的选择十分重要。 文献中使用一次最 小二乘法、二次最小二乘法来研究模型的选择对于 第 ５ 期 谭营，等：烟花算法研究进展 ·５１９·