1. 蝴蝶算法简介
（以下描述，均不是学术用语，仅供大家快乐的阅读）
学习蝴蝶算法时，我找到了两种蝴蝶算法,一个是Butterfly Algorithm（蝴蝶算法），另一个是Monarch butterfly optimization（帝王蝶算法）。两个算法同年提出（2015年），不知道你们说的具体是哪一个，作为一个成年人，我只能全都要了，这里先记录Butterfly Algorithm（蝴蝶算法），下一篇来记录Monarch butterfly optimization（帝王蝶算法）。
蝴蝶算法（Butterfly Algorithm）是根据蝴蝶受香味吸引飞行的行为而提出的优化算法。算法于2015年提出，效果中规中矩，不过相关的论文数量也不少了。算法的流程和结构非常简单，不过论文对算法的细节描述不够清晰，有些参数意义不明。
蝴蝶算法中，每只蝴蝶的位置代表一个可行解，每只蝴蝶的值表示该位置的香味。每只蝴蝶会向着香味浓度最高位置的蝴蝶飞行，或者向着随机选定的蝴蝶飞行。通过该行为在解空间内搜寻香味浓度最大的位置。
吐槽一下三哥的科研水平，缺少了算法的关键性描述（贪心步骤），导致开始时实验效果总是不佳。算法简称BA已经被Bat Algorithm占用，不应该重复使用BA简称蝴蝶算法，建议使用BFA（论文中Bat Algorithm 和Butterfly Algorithm都叫BA）。
2. 算法流程
蝴蝶算法中每只蝴蝶的为 ，该位置的优劣由其适应度函数F(X)计算得出。
每只蝴蝶的香味大小根据以下公式计算得出：
其中c为其组合方式（意义不明）取值为0.1，I为其香味浓度，与F(x)相关，a为香味浓度的指数，取值为0.01。
由于F的该蝴蝶散发香味的浓度，故该值不应该与F(x)有直接关联，否则对于不同的适应度函数F的取值会相差还很大，导致算法的结果不稳定。
如果I取值如下：
其意义也不太大，F的取值总是一个相对固定的值（因为a=0.01,0<I<1），约等于c的值，故在实验阶段将取F=c。
蝴蝶有两种搜索模式：
1. 全局飞行：向着香味浓度最高的蝴蝶飞行。
其实现公式如下：
其中g为全局最优的蝴蝶的位置，Levy简介参考杜鹃搜索算法。
2. 局部飞行：向着种群中随机数只蝴蝶飞行。
其实现公式如下：
其中xj,xk为种群中的随机蝴蝶（没有限制i,j,k不相等）。
每只蝴蝶飞行时有一定的几率进行全局飞行，否则将进行局部飞行，其全局飞行的概率为p,取值为0.8。
算法的流程图如下：
可以看出蝴蝶算法的流程简单，蝴蝶的飞行公式也不复杂，总体来说算是一个较为简单的算法，不过其中的一些参数没有具体描述，但也不影响我们通过实验来对其进行调优。（算法没有贪心算法步骤，应该加上，原因见下节。）
3.实验
适应度函数。
实验一：
| 值 | |
|---|---|
| 问题维度(维度) | 2 |
| 总群数量(种群数) | 20 |
| 最大迭代次数 | 50 |
| 取值范围 | （-100，100） |
| 实验次数 | 10 |
| p | 0.8 |
| c | 0.1 |
| a | 0.01 |
| Levy(x) | 0<x<1 |
| 值 | |
|---|---|
| 最优值 | 2.0280446250944513 |
| 最差值 | 1474.0189312937716 |
| 平均值 | 725.1419526667166 |
从图像上看，群体的行为确实很像一群翩翩飞舞的蝴蝶，偶尔的长距离跳动是levy飞行的结果。但是从结果来看，并不理想，结果都很差，而且从图像可以看出，群体好像在向着解空间中心附近聚集。即使增加最大迭代次数，其结果也不会有太大的提升。
从算法的流程来看，算法却少了贪心步骤，即下一个位置优于当前位置才进行移动。该算法没有这个步骤，又由于所有个体都在向着随机选择的其他个体或者最优个体靠近，所以群体会收敛于群体的中心（稍偏向最优个体），而解空间随机种群的中心的期望为解空间的中心，所有其图像会如上。
下面为个体加上贪心步骤看看效果。
实验二： 为所有个体添加贪心步骤（找到优于当前的位置才移动）
| 值 | |
|---|---|
| 问题维度(维度) | 2 |
| 总群数量(种群数) | 20 |
| 最大迭代次数 | 50 |
| 取值范围 | （-100，100） |
| 实验次数 | 10 |
| p | 0.8 |
| c | 0.1 |
| a | 0.01 |
| Levy(x) | 0<x<1 |
| 值 | |
|---|---|
| 最优值 | 7.859647143839805E-6 |
| 最差值 | 0.009767643559322189 |
| 平均值 | 0.0018503228803280754 |
图像中群体很明显的收敛到了解附近，看看结果也比之前好了不少，这可以说明，贪心步骤应该是蝴蝶算法的必要步骤。不过我还是挺喜欢实验一图像中那种翩翩飞舞的感觉，这然我觉得算法的实际行为和蝴蝶的飞行行为很像。
实验二中为所有个体都添加了贪心算法，收敛速度明显加快，下面，将选择性为某些个体的添加贪心步骤。
实验三： 只为最优个体添加贪心步骤。
| 值 | |
|---|---|
| 问题维度(维度) | 2 |
| 总群数量(种群数) | 20 |
| 最大迭代次数 | 50 |
| 取值范围 | （-100，100） |
| 实验次数 | 10 |
| p | 0.8 |
| c | 0.1 |
| a | 0.01 |
| Levy(x) | 0<x<1 |
| 值 | |
|---|---|
| 最优值 | 0.04291235218693606 |
| 最差值 | 6.479294918144142 |
| 平均值 | 1.4241355087369678 |
从图像来看，种群的收敛没有实验二中那么快，但是结果也没有实验二好，不过可以看出算法的全局搜索的时间长了不少，结合levy飞行步骤，算法跳出局部最优的能力有一定增强，但是这是牺牲了一定的局部搜索能力得来的，不过也相对均衡。
上面实验二和实验三是两个极端的情况，从单个个体贪心到全体贪心，中间还有仅全局飞行个体贪心和仅局部飞行个体贪心，其效果位于实验二和实验三之间，大同小异，不在赘述。
算法中的参数几乎没有使用，主要使用的是c，该参数用来控制蝴蝶的飞行步长，步长太大收敛较快，精度较低，步长太小收敛太慢，精度较高。
实验四： 实验二的基础上c取值1和0.01。
| 值 | |
|---|---|
| 问题维度(维度) | 2 |
| 总群数量(种群数) | 20 |
| 最大迭代次数 | 50 |
| 取值范围 | （-100，100） |
| 实验次数 | 10 |
| p | 0.8 |
| c | 1,0.01 |
| a | 0.01 |
| Levy(x) | 0<x<1 |
c=1
c=0.01
可以明显看出，参数c对算法的收敛速度有较大的影响，取值在0.01-1之间效果都可以接受，论文中给出的c=0.01是一个比较好的值，在收敛速度和搜索精度之间平衡的很不错。该参数属于可优化参数，可以让其随迭代次数递减，前期加速收敛，后期提高精度。
算法中的levy步骤其实也是一个锦上添花的步骤，仅仅提提供了跳出局部最优的能力。在该算法作者的另一篇论文中也对levy进行了替换，效果差不多。
4.总结
蝴蝶算法是根据蝴蝶被香味吸引飞行的行为提出的算法。蝴蝶拥有全局搜索和局部搜索两个主要行为，其实现和流程非常简单，算法的效果也算是中规中矩。算法中的部分参数不知其作用（水平有限没看懂其作用），不过也并没有对算法的结果产生较大影响，这也说明了该算法的鲁棒性较强。
参考文献
[Arora S , Singh S . Butterfly algorithm with Lèvy Flights for global optimization[C]// 2015 International Conference on Signal Processing, Computing and Control (ISPCC). IEEE, 2015.]
[Arora S , Singh S . An improved butterfly optimization algorithm with chaos[J]. Journal of Intelligent & Fuzzy Systems, 2017.]
以下指标纯属个人yy,仅供参考
| 指标 | 星数 |
|---|---|
| 复杂度 | ★★☆☆☆☆☆☆☆☆ |
| 收敛速度 | ★★★★★★☆☆☆☆ |
| 全局搜索 | ★★★★☆☆☆☆☆☆ |
| 局部搜索 | ★★★★☆☆☆☆☆☆ |
| 优化性能 | ★★★★☆☆☆☆☆☆ |
| 跳出局部最优 | ★★★☆☆☆☆☆☆☆ |
| 改进点 | ★★★☆☆☆☆☆☆☆ |
网友评论