优化算法笔记（十二）烟花算法

作者: stronghorse | 来源:发表于2019-08-12 00:18 被阅读0次

1. 烟花算法简介

（以下描述，均不是学术用语，仅供大家快乐的阅读）
　　烟花算法（Firework Algorithm,FWA）是一种受烟花爆炸产生火星，并继续分裂爆炸这一过程启发而得出的算法。算法的思想简单，但具体实现复杂。算法提出时间并不长，但是已经有了不少的改进研究和较为全面的应用。
　　烟花算法中，每一个烟花的位置都代表了一个可行解。烟花的爆炸产生的火星有两种，正常的火星与特别的火星。每个火星都会爆炸产生数个正常火星，某些火星有一定的概率产生一个特别的火星。正常的火星根据当前火星的振幅随机均匀分布在该火星的周围，而特别的火星将在当前火星附近以正态分布方式产生。每次迭代产生的火星数量多于每一代应有的火星数，算法将参照火星位置的优劣，随机留下指定数量的火星，已保持火星数目的稳定。

2. 算法流程

烟花算法的主角毫无疑问就是烟花了。

　　烟花算法中每个火星有两个属性：位置以及振幅，振幅与所有火星的亮度值有关，亮度越高的火星的振幅越小，反之振幅越大。（这里亮度表示火星的适应度值，越亮表示这个位置的氧气浓度越高，适应度越好）
　　一句话总结烟花算法：较差位置大范围少量搜索，较好位置小范围大量搜索，不从众。
　　在D维解空间内每个火星的位置为。
　　在这N个火星中，在该位置上的火星的适应度值为。
　　每个火星的振幅可由下式计算得出：

$A_i=A_{max}\frac{f(X_i)-f_{min}+\xi}{\sum_{k=1}^N {(f(X_i)-f_{min})}+\xi},f_{min}=f_{best}(1)$

$A_i=A_{max}\frac{f_{max}-f(X_i)+\xi}{\sum_{k=1}^N {(f_{max}-f(X_i)}+\xi},f_{max}=f_{best}(2)$

式（1）为适应度值越小越优的情况，而式（2）则是适应度值越大越优的情况。 $\xi$ 为一个极小的值，以保证分母不为0。
　　每个火星产生的正常火星数量也由其适应度值来决定。

$S_i=S_{max}\frac{f(X_i)-f_{min}+\xi}{\sum_{k=1}^N {(f(X_i)-f_{min})}+\xi},f_{max}=f_{best}(4)$
$S_i=S_{max}\frac{f_{max}-f(X_i)+\xi}{\sum_{k=1}^N {(f_{max}-f(X_i)}+\xi},f_{min}=f_{best}(3)$
　　其中 $S_{i}$ 表示第i个火星将要产生的正常火星数， $S_{all}$ 是产生正常火星的总数为一个常数，从式（3）,（4）可以看出适应度值越好的火星能够产生更多的正常火星，反之，火星适应度越差，能够产生的火星数越少。
　　由于式（3），（4）计算出的值为小数，烟花算法中使用式（5）将其转化为整数。
$S_i= \begin{cases} round(a*S_{all}),S_i<a*S_{all} \\ round(b*S_{all}),S_i>b*S_{all} ,a<b<1 \\ round(S_{i}),a*S_{all} \leq S_i\leq b*S_{all} ,a<b<1 \\ \end{cases} (5)$

2.1产生正常火星

从式（3）和式（4）中可以看出，在每一代中将会产生出 $S_{all}$ 个正常火星。产生的正常火星的位置与当前火星的振幅有关，可以从式（1），（2）看出，适应度越优的火星的振幅越小，那么它产生的正常火星将在它自己周围，而适应度越差的火星的振幅越大，它产生的正常火星将会出现在离自己较远的位置。
　　当前火星每次爆炸会从D维搜索空间内随机选择z维进行更新从而产生新的火星。正常火星的位置由如下公式产生。
$X_{i,j}^{k+1}= \begin{cases} A_i*rand(-1,1)+X_{i,j}^k,j\in \{ d_1,d_2,...,d_z \} ,1\leq z\leq d \\ X_{i,j}^k,j\notin \{ d_1,d_2,...,d_z \} \\ \end{cases} (6)$
　　其中z为取值1-D的均匀随机正整数，rand(-1,1)表示-1到1内的均匀随机数。从式(6)中可以看出，正常火星的位置与其振幅有直接关系，振幅越大产生的新火星距当前火星的距离约远。

2.2产生特别的火星

每次迭代过程中，会产生m个特别的火星，即在这N个火星中随机选择m个火星，每个火星产生一个特别的火星。特别的火星的由下面的公式产生：

$X_{i,j}^{k+1}= \begin{cases} randGauss(1,1)*X_{i,j}^k,j\in \{ d_1,d_2,...,d_z \} ,1\leq z\leq d \\ X_{i,j}^k,j\notin \{ d_1,d_2,...,d_z \} \\ \end{cases}$

2.3选择火星保留至下一代

由上面的过程可知，在每一代中，有N个火星，将会产生出 $S_{all}$ 个正常火星以及m个特别的火星。但是每一代中只能从这 $S_{all}+m+N$ 个火星中选择N个火星保留至下一代。
　　每次会先从 $S_{all}+m+N$ 个火星中选择最优的火星保留至下一代，然后再从中选择N-1个火星。选择某个火星的概率如下：
$p{(X_i)}=\frac{R(X_i)}{\sum_{k=1}^{S_{all}+m+N} R(X_k)},(8)$
$R{(X_i)}=\sum_{j} R(X_j),(9)$
　　其中R(X)表示该火星距其他所有火星的距离之和，即距其它火星越远的火星，被选择保留至下一代的概率较大。

　　我们可以看出每次迭代将会产生个火星，而且 ,所有烟花算法每次迭代的计算复杂度要大于其他算法，这简直就是一个作弊行为。别的算法每次只搜索了N个位置，而烟花算法却搜索了个位置。与其他优化算法对比时，其他算法的种群数量应该取，否则这将是一场不公正的对决。

3. 实验

适应度函数还是这个简单的小白鼠 $f(x_1,x_2)=(x_1-a)^2+(x_2-b)^2$
　　实验一：标准烟花算法

参数	值
问题维度(维度)	2
总群数量(种群数)	5
搜索次数(最大迭代次数)	50
正常火星总数	50
特殊火星总数	5
最大振幅	40
a	0.04
b	0.8
取值范围	（-100，100）
实验次数	10

以上数据来自原论文，现在看一看实验的图像以及实验结果。

　　从图像可以看出每次只选择保留了5个火星，它们的收敛速度很慢，实验结束时距离目标点还有一段距离。
　　看看实验结果

	值
最优值	0.022692463372312247
最差值	167.19952396163455
平均值	63.0846567422328

从实验结果可以看出，算法的性能很不稳定，而造成这一点的原因很可能是其收敛速度较慢，算法仍在收敛过程中，所以结果看上去很差。将最大迭代次数修改为100代，重新试验，其结果如下：

	值
最优值	0.5907841378178312
最差值	23.15339514719529
平均值	8.084264146431835

结果好了一些但还是难以接受，为什么烟花算法的结果不理想呢？
　　原因可能是保留机制（2.3节）的问题，烟花算法中保留火星的概率是根据该火星与其他火星的距离和，距离群体越大的个体被保留下的概率越大。这样做有什么好处呢？好处是火星相对分散，这是一个对抗局部最优的策略，但是，距离群体较远的个体是一个较差的个体的概率非常大，坏处就是，集中于当前最优位置的火星被保留的概率较小，算法的局部搜索能力将较弱。
　　实验二. 随机选择的方式保留火星
　　为了加快烟花算法的收敛速度，增强局部搜索能力，我移除了标准烟花算法的选择过程，使用随机选择的方式保留火星，当然，最优个体依然会被保留至下一代。其他参数保持不变。

	值
最优值	4.385708842088968E-6
最差值	0.10829929389283147
平均值	0.011556512043944553

可以看出这次的图像相比实验一收敛速度快了不少，在迭代结束时已经相对在一个较小的区域。这次的结果也明显优于实验一。将选择过程改为随机选择后，由于较优的火星产生的较多且分布在自己周围，因此选择到这些较优的火星的概率也相对较大，算法的收敛速度相对较快。与此同时，算法跳出局部最优的能力比修改前要弱。
　　对于较简单的问题来说当然是随机选择收敛较快结果较好，而复杂的问题则需要更强的跳出局部最优能力。问题的关键仍然是，我们无法在一开始就知道问题的复杂程度。
　　实验三.增加火星的种群数量，减少每代产生的正常火星总数
　　为什么要减少产生的正常火星数，这样算法搜索的次数减少了，效果不会更差吗？其实与直觉相反，减少正常火星总数，增加火星总群数，实际上是让较优的火星产生的正常火星被保留下来的概率变大了，这样也可以解决实验一中的问题，加快算法的收敛速度。

参数	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	100
正常火星总数	25
特殊火星总数	5
最大振幅	40
a	0.04
b	0.8
取值范围	（-100，100）
实验次数	10

	值
最优值	3.87503385060335E-4
最差值	0.004336798262838349
平均值	0.0021856519021473896

从图像中可以看出，算法在50代之前已经收敛，但是之后只在小范围内进行搜索。实验图像与之前的描述相符，收敛速度加快但是跳出局部最优能力减弱。看看实验结果，实验结果好了不少且结果更加稳定。
　　其实实验二与实验三，使用了不同的策略，但都达到了同样的目的——保留更多的优质火星到下一代，它们促进了局部搜索但是挤占了较劣火星的位置，削弱了种群的多样性。
每代留下的火星多了，图像看上去是不是更像烟花？

4. 总结

烟花算法的探究远不止如此，几年前作为一个较新的算法来学习时却已经有了大量的论文和书籍，可见大家对烟花算法已经有了较为深入的研究，而我能做的只是应用算法解决问题以及稍作改进让算法与问题的适应性更高。
　　烟花算法产生正常火星的过程为算法提供了搜索能力，产生特殊火星的过程和选择过程为算法提供了跳出局部最优的能力。但是个人认为选择过程与其他过程的适应性不是很好。标准的选择过程会丢失掉许多较优的个体，使之前产生的正常火星得到的成果没有保留。
　　烟花算法其实还有比较多的改进点，对算法产生最大的参数应该就是正常火星的总数以及振幅了。简单粗暴的改进：在每一代可以对这两个参数进行变化或者随机化，让算法的搜索能力与跳出局部最优能力在整个流程中动态变化，以均衡两种能力。
　　以下指标纯属个人yy,仅供参考

指标	星数
复杂度	★★★★★★★☆☆☆
收敛速度	★★★☆☆☆☆☆☆☆
全局搜索	★★★★★★★★☆☆
局部搜索	★★★☆☆☆☆☆☆☆
优化性能	★★★★☆☆☆☆☆☆
跳出局部最优	★★★★★★★☆☆☆
改进点	★★★★★★★★☆☆

参考文献
Tan Y , Zhu Y . Fireworks Algorithm for Optimization[C]// Advances in Swarm Intelligence, First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings, Part I. Springer-Verlag, 2010.
上一篇优化算法笔记（十一）群搜索算法
 下一篇优化算法笔记（十三）鲸鱼算法

优化算法笔记（十二）烟花算法

1. 烟花算法简介

2. 算法流程

2.1产生正常火星

2.2产生特别的火星

2.3选择火星保留至下一代

3. 实验

4. 总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

和大叔走大数据应用之路