蛾群算法

❶ 优化算法笔记（二十五）飞蛾扑火算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
飞蛾扑火算法（Moth-Flame Optimization）是受飞蛾围绕火焰飞行启发而提出的算法。算法提出于2015年5月（投稿日期），虽可算作一个新算法，不过无数研究者就像飞蛾见了火一样，发表了如此之多的论文，惊了。
飞蛾扑火算法中有两种个体，飞蛾和火焰，飞蛾选择并围绕火焰以螺线方式飞行搜索，搜索完后，火焰将移动位置，以保持火焰是飞蛾和火焰群体中最优的位置。
算法的流程简单，螺线搜索在之前的鲸鱼算法中也出现过，这里会较为详细的记录记录螺线搜索的具体情况。

显然,飞蛾扑火算法中有两种角色,飞蛾与火焰。初始时飞蛾与火焰的数量均为N。为了方便查看，将飞蛾的位置表示为XM ，火焰的位置为 XF。
初始化时，会在解空间内初始化N个飞蛾与M(M=N)个火焰。在算法过程中，飞蛾将会围绕它所选择的火焰飞行，之后将这N个飞蛾与M个火焰按优劣排序，并将M个火焰移动到较优的前M个个体的位置。其中火焰的数量M会随着迭代次数的改变而不断变化，论文中阶梯递减至1。
算法的主要步骤如下：
1. 飞蛾选择火焰（将火焰分配给飞蛾）。
2. 飞蛾围绕火焰飞行。
3. 移动火焰到相应位置。
从步骤可以看出，算法中飞蛾的飞行是一种无贪心算法的操作，而火焰的移动则是一种变相的贪心操作。

初始化时，会有N个飞蛾和N个火焰（M=N）,故每只飞蛾都可以选择互不相同的火焰。随着迭代次数的递增，火焰的数量会递减。其数量根据以下公式计算得出：

其图像如下图所示：

其实就是将火焰数量M线性递减到1，由于火焰数量是正数，故图像呈阶梯状。
随着迭代次数增加，火焰数量递减，每只飞蛾无法选择互不相同的火焰，此时可以随机选择火焰或者飞蛾群体按顺序依次往后选取，类似于取模。两种方式的差别不大。

该步骤是算法的核心计算步骤。
对于飞蛾 ,它围绕火焰 飞行后到达的新位置XM_new根据以下公式计算得出：

其图像如下

而算法中的飞行轨迹应该是这样的：

取出一维看看

其中i为计算次数。

图像就是cos函数图像的变形。考虑到飞蛾与火焰之间的距离会越来越短，其飞行图像应该与上图相反，即振幅越来越小，局部搜索能力越来越强。

N只飞蛾围绕M个火焰飞行后，会到N个新位置，计算这N个新位置的适应度值，将这N个新位置与M个火焰这（N+M）个位置按优劣排序，并将其中较优的M个位置作为下一轮中火焰的位置。

其飞蛾扑火算法流程图如下：

由于飞蛾扑火算法可以说是对蚁狮算法和鲸鱼算法的结合，这里就看看算法的图像，不再做其他处理了。
适应度函数 。

实验一：

从结果看来，飞蛾扑火算法的性能稳定也优于蚁狮算法，从图像看算法收敛性不如蚁狮算法但局部搜索性能要强于蚁狮算法。
可见螺线的局部搜索能力还是强于随机游走的，不过其全局搜索要弱于随机游走。相比蚁狮算法，飞蛾扑火算法更容易陷入局部最优（其实与蚁狮差不多，只要火焰/蚁狮陷入局部最优基本完蛋，不过蚁狮数量恒定，火焰数量递减，所有火焰更容易局部最优）。

飞蛾扑火算法是根据飞蛾围绕火焰飞行的行为而提出的算法。算法的结构比较简单，与蚁狮算法类似，只是搜索步骤将随机游走替换成了螺线搜索（当然还有跟多细节上的不同，可以看看原文）。算法的局部搜索能力非常强，依靠螺线就提供了全局搜索和局部搜索能力，其全局搜索和局部搜索能力强弱由其极半径决定，算法中由b决定。不过算法缺少跳出局部最优的能力，在平滑函数中的效果非常好，在局部最优较多的函数中效果中规中矩。

参考文献
Mirjalili S . Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems, 2015, 89(NOV.):228-249.. 提取码：koy9
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（二十四）帝王蝶算法
下一篇 优化算法笔记（二十六）和声搜索算法

❷ 优化算法笔记（二十六）和声搜索算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
和声搜索算法（Harmony Search）是受音乐中的和声启发而提出的启发式算法，其提出（发表）年份为2001年，算是一个比较老的算法了。和声搜索算法放在现在，其性能非常一般，不过它提出了一种领域搜索的具体实现方式，可以和不同的算法融合，提高其他算法的性能。

单独看一个和声意义不大，一个和声的一个维度会根据群体中该维度的所以取值来确定其领域范围，然后再进行领域搜索。

原算法受音乐启发，所以它所解决的目标问题也是离散的问题。
和声搜索算法中的一个个体被称为和声记忆（Harmony Memory,HM），群体中和声记忆的数量为N,每个和声记忆中的音数（维度）为D。每一维的取值范围为 。

原算法中每个维度的取值范围L是一组有序的离散的值，即在指定的变量值中选取一个作为和声记忆的值。
每个和声记忆每次迭代只能变为其领域的值。
和声算法中有两种操作：1.移动到领域，2.变异到领域
其概率分别为Harmony Memory Considering Rate(HMCR)和Pitch Adjusting Rate(PAR)。
其中HMCR取值约为0.95，PAR取值约为0.10。
可以看出该算法的步骤和数值参考了遗传算法，而且两者都是为了处理离散问题。

例子如下：
和声记忆的数量为3，维度为2，其中第1维的取值范围为{A,B,C,D,E,F,G},第2维的取值为{3,4,5,6}。
第1代，三个个体的取值如下

在计算第2代时，每个个体的每一维只能去到该维度的邻域的值。
个体1_2能取到的值为(A,3) (A,4) (B,3) (B,4)
个体2_2能取到的值为(F,4)(F,5)(F,6)(G,4)(G,5)(G,6)
个体3_2能取到的值为(C,3)(C,4)(C,5)(D,3)(D,4)(D,5)(E,3)(E,4)(E,5),

图中标出了这三个个体能够到达的邻域。

变异到邻域到操作也很简单，该操作是对标了遗传算法中的变异操作。
变异到邻域操作时，该维度不会变异到当前已有的值。
如个体1_1变异第1维，由于群体中第1维的取值为{A,D,G}故该维度只能取到{B,C,E,F}。
下图中标有颜色的块出了变异操作无法到达的位置，空白位置为变异操作能够到达的位置。（如果没有空白位置呢？概率非常小，毕竟个体位置远少于解空间位置，如果出现了，不变异或者随机一个位置都行）

迭代过后，如果新的位置更好，则保留该和声记忆，并去除最差的和声记忆。
最后文章给出了判断找到的解是否是最优解的判断函数

其中Hr=HMCR,Hi会在该维度找到更好值时随着迭代次数递增。该公式的作用主要是为了判断何时去结束算法程序，不过在之前我们都是使用的最大迭代次数来结束算法程序，所有好像没多大用处。
算法的流程也挺简单的：

和声搜索的原算法是根据音乐中和声概念提出的，音符是离散的，所有算法也是离散的，对标遗传算法用于处理离散解空间问题，那么如何修改和声搜索算法使其能处理连续数值问题呢？
最关键的点是如何处理“邻域”，在连续解空间上，很难定义出一个点的领域，而且每个维度上的取值数量也是无穷的。
为和声搜索算法定义邻域也有几种思路：
1 . 将所有的个体定义为该个体的邻域，即每次随机从群体中选择一个个体，该维度移动到所选中的个体处。

其中D,E,F分别为AB,AC,BC的中点，A,B,C三个和声记忆的邻域将由DEF这三个点及解空间边界决定，此时的邻域比思路2中的更小，也不会出现重叠部分。
当某一维度的两个领域值相等时，上述（二维）的邻域（面）将会退化成邻域（线），可能会导致该维度快速收敛到该值，故此时需要忽略重复值，将邻域重新展开（成为面）。
在连续算法中，当满足HCMR条件时，算法将根据上面的色块在邻域中随机选择一个值；当满足PAR条件时，由于无法剔除指定值，简单起见，直接移动到随机的和声记忆的该维度。
后续的实验由于是求解连续函数最值，故会选择上述连续算法中的三种思路来进行。

适应度函数 。
实验一 ： 思路一

从图像可以看出，思路一的策略与遗传算法非常的相似，移动路线类似于十字架，最终也收敛到了正解附近。前期搜索主要靠邻域移动，后期移动则是靠变异。

从结果也可以看出与遗传算法的差距不大，算法不是很稳定，其策略是飞到相邻的和声记忆上，所以跨越度比较大，精度全靠变异。

实验二 ： 思路二

从图像中可以看出，种群的搜索路径不在像实验一中那样直来直去的十字路径，收敛的速度也慢了不少，但是仍能在正解附近收敛。

从结果中可以看出，思路二的结果好了不少，同时也更加稳定（误，运气好，之前实验出现过不好的结果，没能重现）。该思路的邻域搜索面积会更大，且个体之间的邻域存在重叠部分，故会有可能收敛于不好的位置，不过概率也较小。

实验三 ： 思路三

图像逐渐贪吃蛇化！前期的图像与思路一相似，后期的图像有点类似遗传算法，可能是邻域的面积逐渐缩小成了长条状所致，不过最终“贪吃蛇”还是吃到了食物。

结果可以看出，思路三的稳定性不太行，当全部个体收敛到了一点后会开始进行思路一的替换操作，但无论如何替换都是相同的值，难以找到更优的位置，于是会出现一个较差的结果。这里也可以增加范围随机来跳出局部最优。

和声搜索算法是根据和声乐理知识提出的算法。由于音符是离散的值，算法也对标了遗传算法，故原算法也是针对离散问题提出的。在解决连续性问题时，需要对其邻域概念进行扩展和修改，最终的效果与遗传算法相差不大。
在现在看来，和声搜索算法的效果属实一般，对于其的针对性研究也不太多，该算法主要提出了其不同于遗传算法的遍历解空间的方式。所以在很多论文中都能看到用和声搜索算法与其他算法融合来进行改进的例子。
与遗传算法相比，和声搜索算法的邻域概念，将遗传算法的基因由线扩展到了面上。这一点有点类似于SVM和卷积神经网络的关系，不过，遗传算法和和声搜索算法的差别并没有那么大，只是搜索方式不同罢了。
参考文献
Geem Z W , Kim J H , Loganathan G V . A New Heuristic Optimization Algorithm: Harmony Search[J]. Simulation, 2001, 2(2):60-68. 提取码：4udl
Omran M , Mahdavi M . Global-best harmony search[J]. Applied Mathematics and Computation, 2008, 198(2):643-656. 提取码：pk3s

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

目录
上一篇 优化算法笔记（二十五）飞蛾扑火算法
下一篇 优化算法笔记（二十七）蜉蝣算法

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

（以下描述，均不是学术用语，仅供大家快乐的阅读）
上一篇记录了蝴蝶算法（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可看出，帝王蝶算法的流程也非常的简单，过程中也只有两个公式。

可以看出，帝王蝶算法的流程和蝴蝶算法的流程几乎一模一样（废话，流程图直接的，当然一样），两个算法的个体都是拥有两种行为，蝴蝶算法的行为比较整体，宏观操作，新个体由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,仅供参考

目录
上一篇 优化算法笔记（二十三）蝴蝶算法
下一篇 优化算法笔记（二十五）飞蛾扑火算法