文章插图
烟花算法
烟花算法 (Fireworks Algorithm)，缩写为 FWA，是受到夜空中烟花爆炸的启发而提出的一种群体智慧型算法 。
【烟花算法】
基本介绍中文名：烟花算法
外文名：Firework Algorithm
研究现状自从烟花算法的开创性论文由谭营教授等人于2010年发表之后，业界对烟花算法的研究逐步深入和铺开 。通过对原始烟花算法的细緻、深入的分析，针对原始烟花算法（FWA）的不足，提出了大量的改进方法，并据此发展了各种改进算法，以及与其他方法的混合方法，大大提高的原始烟花算法的性能，同时研究了烟花算法在求解不同类型最佳化问题的能力，还有大量的研究人员进行了烟花算法的套用研究，给出了一些典型的成功套用案例 。实现烟花算法开始叠代，依次利用爆炸运算元、变异运算元、映射规则和选择策略，直到达到终止条件，即满足问题的精度要求或者达到最大函式评估次数 。
文章插图
烟花算法的实现包括如下的几个步骤：1）在特定的解空间中随机产生一些烟花，每一个烟花代表解空间的一个解 。2）根据适应度函式计算每一个烟花的适应度值，并根据适应度值产生火花 。火花的个数是基于免疫学中的免疫浓度的思想来计算的，即适应度值越好的烟花产生火花的数目越多 。3）根据现实中的烟花属性并结合搜寻问题的实际情况，在烟花的辐射空间内产生火花 。（某个烟花的爆炸幅度的大小由该烟花在函式上的适应度值决定，适应度值越大，爆炸幅度越大，反之亦然） 。每一个火花代表解空间中的一个解 。为了保证种群的多样性，需要对烟花进行适当变异，如高斯变异 。4）计算种群的最优解，判定是否满足要求，如果满足则停止搜寻，没有满足则继续叠代 。叠代的初始值为此次循环得到的最好的解和选择的其他的解 。特点基本烟花算法具有如下特点：随机性、局部性、爆发性、隐并行性、多样性和瞬时性 。下面具体说明烟花算法的这些特点 。2.1 爆发性在烟花算法的一次叠代开始后，烟花在辐射範围内爆炸，会产生其他的火花 。等本次叠代结束后，烟花算法选择火花作为下一代的烟花，恢复了烟花的数目，并为下次叠代的爆发做好準备 。每一次叠代，烟花都会爆发，说明烟花算法具有爆发性 。2.2 瞬时性当一次叠代计算开始后，各个烟花依据适应度值的不同，产生不同的火花个数和爆炸幅度 。接着，烟花算法将在爆炸运算元和变异运算元的作用下产生火花 。最后，首先选出最优个体，再依据距离选择其他的个体 。这些选择出来的个体将作为下一代爆炸的烟花，其余的火花不再保留 。不保留的火花或烟花将消亡，说明烟花算法具有瞬时性 。2.3 简单性和群体智慧型算法一样，每个烟花只需要感知自身周围的信息，遵循简单的规则，完成自身的使命 。总体看来，烟花算法本身并不複杂，由简单个体组成，说明烟花算法具有简单性 。2.4 局部覆盖性在烟花算法中，所有的烟花都会在相应的爆炸幅度内产生火花 。除非超出可行域，产生的火花都局限在一定的範围内 。烟花算法的局部性特点体现了烟花算法强大的局部搜寻能力，可以用在算法运算的后期更加精细的搜寻最优解 。因此，烟花算法具有局部性 。2.5 涌现性烟花之间通过竞争与协作，群体之间表现出简单个体不具有的高度智慧型性 。烟花之间相互作用，比单个个体的行为要複杂得多，因此烟花算法具有涌现性 。2.6 分布并行性在烟花算法的每次叠代过程中，各个烟花在不同坐标範围内依次爆炸，即对不同的坐标区间进行一次搜寻，在最后会将所有的火花和烟花综合起来，进行下一代烟花的选择 。在一次叠代中，算法实质上是并行搜寻，表现出烟花算法的分布并行性 。2.7 多样性种群多样性是影响群体最佳化算法性能的关键 。群体多样性的保持，可以保证算法跳出局部极值点，从而可以收敛到全局最优点，这正是群体最佳化算法与一般最佳化算法的显着区别 。群体多样性越大，算法中的个体分布越广，找到最优值的可能越大，同时还不会明显影响算法的收敛能力 。因此，种群多样性是烟花算法的一个重要组成部分 。烟花算法的多样性主要体现下面三个方面 。2.7.1 火花个数和爆炸幅度的多样性在爆炸运算元的作用下，依据各个烟花的适应度值，其产生不同个数的火花和不同的爆炸幅度 。适应度值高的烟花产生更多的火花，爆炸幅度相对较小，而适应度值低的烟花产生更少的火花，爆炸幅度相对较大 。因此，保证了火花个数和爆炸幅度的多样性 。2.7.2 位移操作和高斯变异的多样性烟花算法有两种运算元，第一种是爆炸运算元，第二种是变异运算元 。在爆炸运算元的位移操作中，对计算出来的幅度範围，随机产生一个位移，将在选中的烟花加上这个随机位移 。在变异运算元的作用下，选中的烟花需要乘以一个满足高斯分布的随机数 。爆炸运算元与烟花的适应度值有关，变异运算元与烟花本身的坐标值有关 。两种运算元是本质上不同的，都保证了爆炸的多样性 。2.7.3 烟花的多样性通过一定的选择机制，保留下来的烟花坐标值各不相同，从而保证了烟花算法的多样性特徵 。另外，在选择策略中，距离其他火花距离更大的火花更容易被选中，也体现出烟花算法中烟花的多样性特徵 。2.8 可扩充性烟花算法中烟花和火花的数量不确定，可以依据问题的複杂度来确定 。烟花和火花的数目可多可少，增加和减少个体都能有效地求解问题，因此烟花算法具有可扩充性 。2.9 适应性烟花算法求解问题时，不要求问题具有显示表达，只要计算适应度值就能求解问题 。同时，烟花算法对问题的要求低，也能求解显示表达的问题 。因此烟花算法具有适应性 。未来发展到2018年为止，烟花算法的研究还是很初步的 。在有些方面，还是空白，在许多方面，还很肤浅，急需广大有兴趣的研究人员对其进行深入研究 。烟花算法的未来发展归纳起来，可以有下列几个方面：1、 算法的理论基础和分析 （稳定性、收敛性、收敛特性、参数灵敏度分析）2、 各种改进方法的深入研究（各种因素对烟花算法性能的影响，如何有效控制和调整 。重点是：子烟花间的协同机制建立和研究）3、 混合方法的研究4、 大数据问题的求解 （如何处理巨大数据？）5、 动态最佳化问题的求解 （最佳化目标值随时间变化的情况， 如：群体机器人的动态目标追蹤搜寻问题）6、 更广泛的套用研究