简析半径烟花算法中爆炸半径改善

论文导读：提出的一种新的群体智能优化算法，具有卓越的优化性能，因此一经提出就引起了世界范围内的广泛关注。本文分析了烟花算法中一个重要的爆炸半径公式，指出最优烟花所产生的火花由于爆炸半径趋向于0，对算法搜索没有贡献，白白浪费了计算量。继而提出了一个改进的爆炸半径公式，实验证明，改进算法没有增加计算量，而优化效率得到了提高
摘要： 烟花算法是最近出现的一种优化算法，分析了算法中一个关键参数即爆炸半径。分析表明，由最优烟花所产生的火花由于其爆炸半径趋于0，所以在计算中几乎是无用的，而且增加了计算代价。为此，给出了一个改进的爆炸半径的算法，实验表明，改进算法在收敛速度和精度方面都优于原始算法。
关键词： 烟花算法； 爆炸半径； 群体智能； 优化算法
1006-8228（2013）01-28-02
Study on improvement of explosion radius in fireworks algorithm
Du Zhenxin
（Hanshan Normal University， chaozhou， Guangdong 521041， China）
Abstract： Fireworks algorithm is a new optimization algorithm. The fireworks algorithm is analyzed and the shortage of the crucial paramete摘自：本科毕业论文评语www.7ctime.com
r explosion radius is pointed out. The analysis manifests that because their explosion radius tends to zero， the sparks produced by the best firework are useless and the computing process is wasted. An improved explosion radius formula is proposed in the paper， and experimental results show that the improved algorithm's performance is better than the original one in convergence velocity and accuracy.
Key words： fireworks algorithm； explosion radius； swarm intelligence； optimization algorithm
0 引言
烟花算法是由Ying Tan和Yuanchun Zhu在2010年提出的一种新的群体智能优化算法，具有卓越的优化性能，因此一经提出就引起了世界范围内的广泛关注[2-3]。本文分析了烟花算法中一个重要的爆炸半径公式，指出最优烟花所产生的火花由于爆炸半径趋向于0，对算法搜索没有贡献，白白浪费了计算量。继而提出了一个改进的爆炸半径公式，实验证明，改进算法没有增加计算量，而优化效率得到了提高。
1 烟花算法的原理
烟花算法来自于对烟花爆炸过程的模拟。当烟花爆炸后，火花的散落将充满烟花周围的局部空间，爆炸产生的火花又作为新的烟花继续爆炸，从而逐步充满整个天空。把烟花爆炸过程看作搜索最优解的过程，用算法实现，如图1所示（求最小值）。
第i（i=1，2，…，n）个烟花爆炸产生的火花数目可以用式⑴表示：
⑴
式⑴中，m表示由n个烟花所产生的火花的总数目，ymax=max（f（xi））（i=1，2，…，n）表示n个烟花对应目标函数的最大值（即最坏值），ξ表示计算机所能表示的最小正常数，用于防止式⑴出现除零错误。
第i（i=1，2，…，n）个烟花爆炸的半径是：
⑵
式⑵中，表示预先设定的最大爆炸半径，ymin=min（f（xi））表示n个烟花代表的目标函数的最小值（即最好值），ξ的含义同式⑴中的ξ。
第i（i=1，2，…，n）个烟花产生火花的过程：假设待优化的目标函数是D维函数，随机选取D维中的z维坐标进行更新，则第i（i=1，2，…，n）个烟花的第j（j=1，2，…，si）个火花的第k（k=1，2，…，z）维坐标更新公式：
⑶
式⑶中的rand（-1，1）表示[-1，1]之间的随机数。上面的过程中，由n个烟花总共产生了m个火花。另外，为了增加种群多样性，按照高斯分布额外产生个火花，其中第j（j=1，2论文导读：个烟花（火花）中按照浓度原则选择新的n个火花，参与下一轮爆炸。第i（i=1，2，…，K）个烟花（火花）被选中的概率是：⑸⑹式⑸中，d（xi-xj）表示第i个烟花或火花与第j个烟花或火花之间的距离，可以是欧氏距离，也可以是适应度的差值。由式⑹看出，距离相近的烟花（火花），被选中的概率较低，这就避免了优势烟花增长过快，增加了种群
，…，）个火花的第k（k=1，2，…，z）维坐标更新如下：
⑷
式⑷中，Gaussian（1，1）是一个均值和方差都为1的服从高斯分布的随机数。
上述火花全部产生以后，在产生的总共K=n+m+个烟花（火花）中按照浓度原则选择新的n个火花，参与下一轮爆炸。第i（i=1，2，…，K）个烟花（火花）被选中的概率是：
⑸
⑹
式⑸中，d（xi-xj）表示第i个烟花或火花与第j个烟花或火花之间的距离，可以是欧氏距离，也可以是适应度的差值。由式⑹看出，距离相近的烟花（火花），被选中的概率较低，这就避免了优势烟花增长过快，增加了种群多样性。
2 算法的分析与改进

2.1 算法分析

公式⑵的主要原理是优秀的粒子爆炸的半径小，因为优秀粒子周围存在全局最优解的可能性较大，所以要给予较小的爆炸半径，加强周围的搜索。但也存在问题：对上次爆炸产生的最好烟花，带入式⑵可得：
⑺
由于ξ是一个计算机所能表示的最小常数，用于防止除零错误，例如matlab系统中，ξ一般可以设置为1e-250，分母中的远大于ξ，因此式⑺趋近于0。而由式⑴可知，最优烟花总是产生最多数量的火花。这意味着最优烟花产生的最多数量的火花的爆炸半径都是0，即原样复制了最优烟花，没有进行任何搜索，在下一轮爆炸的时候，根据式⑹，这些火花几乎都被抛弃，所以这些火花都是没有价值的，既增加了计算量，又减少了搜索的机会。

2.2 算法的改进

改进后的算法对于最优火花，爆炸半径不再参照公式⑵，而是按照公式⑻计算：
⑻
式⑻中，t是爆炸搜索的代数，T是预设的总的搜索代数，是预设的爆炸半径最小值。显然，随着爆炸代数t的增加，Ai逐渐减小，这就使得算法一开始搜索半径较大，侧重于全局搜索，后期接近找到最优值的时候减少爆炸半径，有利于在局部精细搜索。
3 实验
同样采用文献中的测试函数，测试条件保持不变，本文对新增加的参数取值10-6。实验结果见表1。
从表1中可以看出，在所有测试函数中，除了Sphere函数效果保持不变，其余测试函数在同样计算次数下，都取得了比原算法更好的结果。
4 结束语
本文分析并改进了烟花算法中的爆炸半径公式，使得每次爆炸中最优烟花不再产生无用的个体。改进后的算法在没有增加计算量的前提下，提高了搜索精度。
参考文献：
Tan Y.， Zhu Y. C..Fireworks Algorithms for Optimization[J]. Proc.of Int. Conf. on Swarm Intelligence （ICSI2010），Part II， LNCS 6145， Beijing， China， 2010.12-15（6）：355-364
张家琴.求解0/1背包问题的烟花算法研究[J].武汉工程职业技术学院学报，201

1.23（3）.

[3] 曹炬，李婷婷，贾红.带有遗传算子的烟花爆炸优化算法[J].计算机工程，2010.36（23）.