进化策略的方法分类

进化策略和遗传算法（GA）是进化算法（EAs）的两类重要变种。这两种主流方法的不同之处在于解的表示以及搜索和选择算子的设计。GA常使用二进制或整数编码，与此相比，ES常基于真实值编码。GA和ES之间的一个显著差别在于选择算子。在ES中，父代选择是无偏的，即，当前种群的每一个个体有着相同的概率被选择用以重组。此外，幸存者的确定性选择是ES的驱动力。不过最近几十年涌现出了许多混合方法。一方面，使用整数编码的ES被开发用于组合优化问题的求解。另一方面，也有人提出了使用ES选择模型的GA。

优化算法笔记（二十四）帝王蝶算法

粒子群算法（ParticleSwarmOptimization），又称鸟群觅食算法，是由数学家J.Kennedy和R.C.Eberhart等开发出的一种新的进化算法。它是从随机解开始触发，通过迭代寻找出其中的最优解。

粒子群算法也称粒子群优化算法（ParticleSwarmOptimization，PSO），属于群体智能优化算法，是近年来发展起来的一种新的进化算法（EvolutionaryAlgorithm，EA）。

粒子群算法原理如下：粒子群优化（ParticleSwarmOptimization，PSO)算法是1995年由美国学者Kennedy等人提出的，该算法是模拟鸟类觅食等群体智能行为的智能优化算法。在自然界中，鸟群在觅食的时候，一般存在个体和群体协同的行为。

粒子群算法（也称粒子群优化算法（particleswarmoptimization，PSO）），模拟鸟群随机搜索食物的行为。粒子群算法中，每个优化问题的潜在解都是搜索空间中的一只鸟，叫做“粒子”。

粒子群算法，也称粒子群优化算法（ParticalSwarmOptimization），缩写为PSO，是近年来发展起来的一种新的进化算法(（Evolu2tionaryAlgorithm-EA）。

粒子群算法引言粒子群优化算法(PSO)是一种进化计算技术(evolutionarycomputation)，有Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究PSO同遗传算法类似，是一种基于叠代的优化工具。

（以下描述，均不是学术用语，仅供大家快乐的阅读）

　上一篇记录了蝴蝶算法（Butterfly Algorithm），这一篇接着记录帝王蝶算法（Monarch butterfly optimization）。

　介绍之前我们先看看帝王蝶的百科，了解其特性，这将有利于我们对算法的理解和记忆。

　帝王蝶算法（Monarch butterfly optimization）是根据帝王蝶的迁徙行为提出的优化算法。帝王蝶算法也是于2015年提出，相关的论文也比较多了（这两个蝴蝶算法都有这么多人关注吗？）。其流程相对蝴蝶算法来说有点复杂，不过其论文对算法描述非常的清晰，大家可以去阅读原文。

　帝王蝶算法中，每只蝴蝶的位置代表一个可行解，蝴蝶群体将会被分布在两个大陆上，这两块大陆上的帝王蝶分别有不同的行为：1.迁徙，2适应环境。帝王蝶算法组合了这两种行为来搜索解空间中的最优位置。

帝王蝶算法中每只蝴蝶的为 ，该位置的优劣由其适应度函数F(X)计算得出。

帝王蝶群体分布在两块大陆上，分别是land1和land2上。对于一只随机帝王蝶来说，它位于land1上的概率为p,位于land2上的概率为1-p。以此可以将总群分为2个群体，论文中p取值维5/12。

　Land1上的群体的行为为迁徙，而land2上的群体的行为为适应环境。

位于land1上的群体的行为为迁徙，这部分个体在种群中的比例为p。其计算公式如下：

不同与land1上的群体，land2上的群体的行为为适应环境，其计算公式如下：

从2.2和2.3可看出，帝王蝶算法的流程也非常的简单，过程中也只有两个公式。

　可以看出，帝王蝶算法的流程和蝴蝶算法的流程几乎一模一样（废话，流程图直接copy的，当然一样），两个算法的个体都是拥有两种行为，蝴蝶算法的行为比较整体，宏观操作，新个体由2-3个个体得出，而帝王蝶算法的行为比较零散，微观操作，每一维来自一个个体。两个算法也都使用了levy飞行，考虑到两个算法竟然还是同一年的，莫非，难道……

　不过从细节来看，两个算法差异还是比较大的，不过两个算法的性能也都算是中规中矩的那种，没有特别突出的特点。

适应度函数 。

实验一 ：

从图像中可以看出，帝王蝶算法收敛的非常之快，几乎在10代以内就聚集在了目标解附近。从结果中也可以看出，10次结果中仅有一次较差，其它结果也都很接近0。效果比较好，我总觉得参数的设置不太对称，改成对称试试结果。

实验二 ：修改参数p=0.5,peri = 1,BAR=0.5,即迁徙操作两个种群各占一半维度，适应环境操作最优个体站一半维度，1/4进行levy飞行。

从结果可以看出，将参数改为对称后效果差了不少。图像我选取一副较差的图像，从图像可以看出在最后，种群收敛到了目标解外的一点。收敛的过程很像遗传算法和差分进化算法，个体的运动轨迹在一个类似十字架的图案上。但是这个适应度函数非常简单，不存在局部最优解，问题应该出在步长上。整个算法只有levy飞行那一步会产生新的位置，其他步骤都是现有位置的组合。

下面将最大步长改大试试。

实验三 ：在实验二的基础上，将S_max改为100。

结果比实验二好了不少，但精度有所下降，但是比不上实验一。最大步长设的太大会影响精度，设得太小又会让种群提前收敛。实验三中最大步长为100，最大迭代次数为50，则由最大步长影响的精度为100/(50*50)=0.04,这与实验结果相差不太多。权衡利弊，S_max的取值还是大一点的好，否则，种群未在正解附近收敛得到的结果会很差，结果会很不稳定。

实验四 ： 在实验一的基础上将S_max修改为100，与实验三比较原文其他参数是否合适。

从结果可以看出，这次的结果要好于实验三的结果，这说明原文中给出的这一系列不对称的参数效果还是好于实验二实验三中的对称参数。图像与实验三的图像类似，步长改大之后个体很容易飞出边界，然后由越界的处理方法使其留在边界上，所以在算法开始后不久就可以看到群体都停留在了边界上，不过问题不大，最终还是会收敛与正解附近。

　与实验一相比，实验四的结果差了不少，这是因为测试函数比较简单，当选用较为复杂的测试函数后，较大的步长能够提高算法的全局搜索能力，让算法的结果更加稳定。

帝王蝶算法是根据帝王蝶的迁徙行为提出的算法。位于两块大陆上的帝王蝶群体有着不同的行为，迁徙行为类似于进化算法的杂交操作，适应环境行为类似于进化算法的变异操作，不过其变异位置在当前最优个体附近。算法中的levy飞行是其变异操作的具体实现，不过由于受最大步长的影响，levy飞行的作用并不明显。帝王蝶的最大飞行步长对结果的影响较为明显，步长较小时算法的全局搜索能力较差，局部搜索能力较强，精度较高，反之，全局搜索能力较强，局部搜索能力较差，精度较低但是更加稳定。

　帝王蝶算法的参数非常奇特，按论文中所说是根据蝴蝶在各地活动的月数而设定的。虽然不是最佳参数，但也优于均匀对称的参数。有兴趣的同学可以试试怎么设置能让算法的性能达到最佳。

　接连两篇笔记记录了都是蝴蝶算法，它们的总体流程结构相差不大，一个是宏观行为，个体之间互动，一个是微观行为，维度之间互动。这两个蝴蝶算法的性能也相差不多，中规中矩，没有太亮眼的地方，而且都用了levy飞行来提供跳出局部最优的能力。不过levy作为非常规武器，不应该在原始算法中给出，其操作与levy飞行不搭且没有提供相应的能力（可能我看到的不是原始论文）。

参考文献

Monarch butterfly optimization[J]. Neural Computing and Applications, 2015, 31:1995-2014. 提取码：fg2m

Wang G G , Zhao X , Deb S . A Novel Monarch Butterfly Optimization with Greedy Strategy and Self-adaptive Crossover Operator[C]// 2015 2nd Intl. Conference on Soft Computing & Machine Intelligence (ISCMI 2015). IEEE, 2015. 提取码：9246

以下指标纯属个人yy,仅供参考

目录

上一篇 优化算法笔记（二十三）蝴蝶算法

下一篇 优化算法笔记（二十五）飞蛾扑火算法