烟花算法研究改进综述

北京信息科技大学计算机学院 崔光松

1.带有遗传因子的烟花算法(GAFEO)

随着人工智能的快速发展，越来越多的机器人具有了和人类一样的能力，为了让机器人更加智能，不断有科学家对相关算法进行改进。带有遗传因子的烟花算法是基于烟花算法改进的一种算法。该算法在烟花算法[1]中融入了遗传算法思想，与原算法相比在寻优能力和寻优精度等方面具有较高性能。GAFEO算法主要在原算法里添加了爆点分析、智能分布式搜索以及生物学中的种间更替思想。爆点分析[2]的引入主要解决了在爆点范围较大的情况下，爆炸产生的目标发生聚集而产生不相关搜索影响算法搜寻效率的问题；智能分布式搜索的引入主要解决了因爆炸瞬间产生局部和全局分层现象而降低搜索精度的问题；生物学中的种间更替思想的引入主要优化改善了原算法仅在当前爆点区域内搜索而错失其他区域最优解的缺点，让其在搜索完本区域最优解的同时凭借超强的扰动能力在相邻或其他区域再次搜寻最有解，然后将最终的搜寻结果进行分析比对，得出最最终最优解。这些改进有效改善了原算法停留在部分最优、弱化部分搜索、缺乏智能分析等不足。

2.改进的动态搜索烟花算法

改进的动态搜索烟花算法在原算法中加入了智能因子，在不断搜索过程中，该算法能够向已搜索出来的最优解进行学习，然后根据学习结果改变自身的方向以及搜寻精度，进而合理分配部分搜索和全局搜索的力度。改进后的算法主要改善优化了原算法过快收敛、搜索精度差、最优解不唯一等问题。此外改进的算法融入了特征分析策略，使得在寻找最优解的过程中算法可以将具有相同特征的因子有效结合，进而缩短搜寻最优解的时间。由于在搜寻过程中会产生很多特征，改进后的算法会对这些特征进行分析，通过具有这些特征的因子的数量的多少以及这些因子所占的权重决定哪些特征是有效的特征，分析出有效特征后再将无效特征剔除然后重复比对分析有效特征进而得出最优解，这样做的目的一来将距离爆点较远的因为考虑在内，二来在分析搜寻的初始阶段就将无效因子剔除在外，防止浪费过多时间影响搜寻效率。

3.二进制反向学习烟花算法[3]

二进制反向学习烟花算法引入01数学符号，将一些在搜索过程中的最优分析离散化，进而解决求解效率低下或者根本求解不出最优解的问题。一般情况下，最优解是通过对随机节的不断提炼筛选获得的，而分析提炼随机解的过程是寻找最优解中最耗时的过程，主要原因是，一旦算法沿着某一依据一直分析下去，可能因为一开始的方向就是错误的，不管之后采用多么精确的算法，多么智能的分析策略，多难以得出最优解。二进制反向学习烟花算法就很好的解决的这个弊病，当算法沿着某一反向在规定时间内依旧无法得出我们预期的最优解时，算法将同时分析当前方向的反方向的随机解，并且赋予反方向的随机解以更大的权重，这样就能有效避免算法一直沿着某一错误的方向继续下去。因为一旦算法的方向错误，不管是继续下去还是反方向回去都是费时费力的，继续分析下去肯定是 无果而终，返回起始点则更是耗时的操作，本算法则不让其回到起始位置，而是从其相反方向与当前方向并行分析，这样总能在有限时间内找到最优解。

4.双种群烟花算法

我们都知道在烟花爆炸之后，其收敛速度是非常慢的，如果不认为的干扰，这是不利于我们寻找最优解的。双种群烟花算法用两个种群同时并发运行的方式有效解决了原烟花算法易陷入部分最优解、收敛周期长等问题。该算法的主要思路是在烟花演化过程中，算法一方面执行爬山因素，同时在另一方面还执行协作因素，爬山因素主要是加强在烟花高斯变异过程中局部搜索能力，协助因素则是减弱由于局部搜索能力加强所带来的负面效应。并行执行不但增加了算法对随机解的选择能力，同时由于并行算法相当于两个单一算法的融合，其将爆炸算子、协作因素、特征选择、随机解分析同时多方面执行，使得最优解的得出更加高效，此外由于收敛速度加快，所得出的最优解也不再是局部最优解，而是全局最优解。

5.引入惯性权重的烟花算法

引入惯性权重的烟花算法的提出主要是为了寻找全局最优解，因为原有算法会因为各种因素的影响而陷入局部最优解。该算法融入了一种带有权重的惯性量，该惯性量随着烟花变异次数的 增加而成递减趋势。该算法在每次分析随机解的过程中都保留了上一次的分析记录，通过对前面的分析记录的比对，来进一步确定当前所获得的最优解是否为真正的最优解。这样做的好处一来避免了无用的搜索分析，二来使得所得到的最优解得到有效验证。

[1]Tan Y,Zhu Y.Fireworks algorithm for optimization[J].Tan Y,Shi YuHui,et al.Advances in swarm intelligence[C].Springer Berlin Heidelberg,2010:355-364.

[2]Hsieh Sheng-Ta,Sun Tung-Ying,Liu Changcheng.Potential Offspring Production Strategies:An Improved Genetic Algorithm for Global Numerrical Optimizatioin[J].Expert Systems with Applications,2006,36(8):11088-11098.

[3]吴虎胜,张凤鸣,战仁军,等.利用改进的二进制狼群算法求解多维背包问题[J].系统工程与技术,2015,37(5):1084-1091.