解析算法笔记

A. 算法设计与分析笔记之NP完备性理论

  三类问题都会涉及到多项式时间算法，我们先解决什么是多项式时间算法。
  多项式时间的算法的形式化定义是，对于规模为n的输入，在最坏情况下的运行时间是 ，其中k为某一 确定常数 。相对应的，有伪多项式时间算法，典型的0-1背包问题算法复杂度为 ，其运行时间与输入的规模相关，是伪多项式的。

  如以下表格中的都是P类问题。

  NP问题能找到多项式时间的验证算法。
  什么叫验证？例如，在哈密尔顿圈问题中，Z为图中点的一个序列。如果我们能设计一个多项式时间的判定算法，判定这个序列是否是一个哈密尔顿圈，那么称这个问题能在多项式时间内验证，序列Z是这个问题的一个证书（Certificate）。
如何证明一个问题是NP问题？

注意 ：不用证明这个问题没有多项式时间求解算法，因为P类问题是NP问题的子集，只需有证书验证过程即可。

   非形式化定义 ，如果一个NP问题和其他任早数咐何NP问题一陆纯样“不易解决”（归约），那么我们认为这一问题是NPC类问题或称之为NP完全问题。
   形式化定义 ，问题X是NP完全的，如果：

  NP问题可在多项式时间归约到NPC问题。特殊地，如果一个问题满足2，而 不一定 满足1，则称它是NP难度（NP-Hard）的。
  反过来，要证明一个问题Y是NP完全的。可以采用如下步骤：

写了这么多，我还是看不懂。就这样理解叭，P类问题是可以在多项式时间求解的问题，但大部分问题都是不能的。因此我们想用一些数据去验证它是不是这个问题的解，如果能在多项式时间验证出来，那么这个问题就是NP问题。其中，NP里最难的问题我们叫它NPC问题，但有些问题跟NPC问题差不多难，然而它又不是NP问题，就只好说它是NP难度的，也就是NP难问题（NP-Hard）。

  目的：我们希望在多项式时间内解决一个 判断 问题。
  准备：某一特定问题（A）的输入为该问题的实例。毕链例如，寻找路径（PATH）问题的实例可以是图G、G中特定的点u和v以及一个特定的整数k（是否存在u到v长度为k的路径）。
  假设有另一不同的判定问题B，已知在多项式时间解决它的算法。我们将A的任何实例 α 转化成B的具有以下特征的某个实例 β：

  这一过程就是 多项式时间归约算法 。它提供了一种在多项式时间内解决A的方法：

参考资料 ：《算法导论》

B. 优化算法笔记（十八）灰狼算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
灰狼算法（Grey Wolf Algorithm）是受灰狼群体捕猎行为启发而提出的算法。算法提出于2013年，仍是一个较新的算法。目前为止（2020）与之相关的论文也比较多，但多为算法的应用，应该仍有研究和改进的余地。
灰狼算法中，每只灰狼的位置代表了解空间中的一个可行解。群体中，占据最好位置的三只灰狼为狼王及其左右护法（卫）。在捕猎过程中这三只狼将带领着狼群蛇皮走位，抓捕猎物，直至找到猎物（最优解）。当然狼王不会一直是狼王，左右护法也是一样，每一轮走位后，会根据位置的优劣重新选出新的狼王和左右护法。狼群中的每一只灰狼会向着（也可能背向）这三只位置最优的灰狼移动一定的距离，来决定这一步自己将如何走位。简单来说， 灰狼个体会向则群体中最优的三个个体移动 。

很明显该算法的主角就是灰狼了。

设定目标灰狼为
，当前灰狼的为 ，则该灰狼向着目标灰狼移动后的位置 可以由一下公式计算得出：

灰狼群体中位置最好的三只灰狼编号为1,2,3，那么当前的灰狼i通过观察灰狼1、灰狼2和灰狼3，根据公式（1）得出的三个位置为Xi1,Xi2,Xi3。那么灰狼i将要移动到的位置可以根据以下供述计算得出：

可以看出该灰狼的目标位置是通过观察三只头狼得到的三个目标位置的所围成的区域的质心。（质心超出边界时，取值为边界值）。

灰狼算法的论文描述很多，但是其公式和流程都非常简单，主要对其参数A和C的作用效果进行了详细描述。
C主要决定了新位置相对于目标灰狼的方位，而A则决定新位置向目标靠近还是远离目标灰狼。当|A|>=1时，为远离目标，表现出更强的全局搜索能力，|A|<1时靠近目标，表现出更强的局部搜索能力。

适应度函数 。
实验一：

看看这图像和结果，效果好极了。每当我这么认为时，总会出现意想不到的转折。
修改一下最优解位置试一试， 。
实验二 ： 。

其结果比上面的实验差了不少，但我觉得这才是一个优化算法应有的搜索图像。其结果看上去较差只是因为迭代次数较少，收敛不够迅速，这既是优点也是缺点，收敛慢但是搜索更细致。
仔细分析灰狼算法的流程，它并没有向原点靠近的趋势，那只能理解为算法群体总体上向着群体的中心移动。 猜想 ：当初始化群体的中心恰好是正解时，算法的结果将会非常的好。
下面使用 ，并将灰狼的初始位置限定在（50,100）的范围内，看看实验图像是否和实验二的图像一致。

实验三 . ,初始种群取值范围为（50,100）

这图像和结果跟实验一的不是一样的吗?这说明从实验二中得出的猜想是错误的。

从图像和结果上看，都和实验二非常相似，当解在解空间的中心时但不在原点时，算法的结果将差一些。
为什么会这样呢？从算法的流程上看，灰狼算法的各个行为都是关于头狼对称的，当最优解在原点且头狼在附近时，公式（1）将变为如下：

实验五 . ,三只头狼添加贪心算法。

从图像可以看出中心的三个点移动的频率要比其他点的移动频率低。从结果上可以看出其结果相对稳定了不少，不过差距非常的小，几乎可以认为是运气好所导致。如果所有的个体都添加贪心算法呢？显然，算法的全局搜索能力将进一步减弱，并且更容易向群体中心收敛，这并不是一个好的操作。

实验六 . ,
在实验五的基础上为狼群添加一个统一的步长，即每只狼每次向着目标狼移动的距离不能大于其步长，将其最大步长设为1，看看效果。

从图像可以看出，受到步长的约束每只狼的移动距离较小，在结束时还没有收敛，其搜索能力较强但收敛速度过慢且极易陷入局部最优。现在将最大步长设置为10（1/10解空间范围）使其搜索能力和收敛速度相对平衡，在看看效果。

从图像可以看出，算法的收敛速度快了不少，但从结果可知，相较于实验五，算法的提升并不太大。
不过这个图像有一种似曾相识的感觉，与萤火虫算法（FireFly Algorithm）差不多，仔细对比这两个算法可以发现， 灰狼算法相当于萤火虫算法的一个简化 。实验六种对灰狼算法添加步长的修改，让其离萤火虫算法更近了一步。

实验七 . ,
在实验六的基础上让最大步长随着迭代次数增加递减。

从实验七的图像可以看出，种群的收敛速度好像快了那么一点，结果也变好了不少。但是和改进后的萤火虫算法相比仍然有一定的差距。
灰狼算法在全局搜索和局部搜索上的平衡已经比较好了，尝试过对其进行改进，但是修改使搜索能力更强时，对于局部最优的函数求解效果很差，反之结果的精度较低，总体而言修改后的算法与原算法相差无几。

灰狼算法是根据灰狼群体的捕猎行动而提出的优化算法，其算法流程和步骤非常简单，数学模型也非常的优美。灰狼算法由于没有贪心算法，使得其有着较强的全局搜索能力同时参数A也控制了算法的局部搜索范围，算法的全局搜索能力和局部搜索能力比较平衡。
从算法的优化图像可以看出，灰狼算法和萤火虫算法非常的相似。可以认为，灰狼算法是对萤火虫算法的一种改进。萤火虫算法向着由于自己的个体飞行，而灰狼算法则的条件更为苛刻，向着群体前三强前进，萤火虫算法通过步长控制搜索范围，而灰狼算法则直接定义搜索范围参数A，并令A线性递减。
灰狼算法的结构简单，但也不容易改进，数次改进后只是改变了全局搜索能力和局部搜索能力的比例，综合能力并没有太大变化。
由于原点对于灰狼算法有着隐隐的吸引力，当测试函数目标值在原点时，其结果会异常的好。因此，灰狼算法的实际效果没有论文中的那么好，但也不差，算是一个中规中矩的优化算法。
参考文献
Mirjalili S , Mirjalili S M , Lewis A . Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69:46-61. 提取码：wpff

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

目录
上一篇 优化算法笔记（十七）万有引力算法
下一篇 优化算法笔记（十九）头脑风暴算法

优化算法matlab实现（十八）灰狼算法matlab实现

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

（以下描述，均不是学术用语，仅供大家快乐的阅读）
上一篇记录了蝴蝶算法（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,仅供参考

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

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

（以下描述，均不是学术用语，仅供大家快乐的阅读）
和声搜索算法（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,仅供参考

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

E. 算法笔记之博弈问题——猫和老鼠

博弈问题，需要注意，对于每个玩家，都会争取：

LeetCode913. 猫和老鼠

两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

然后，游戏在出现以下三种情形之一时结束：

如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。

题目描述比较长，但其实还是很好理解的。需要注意，每个玩家都会争取自己获胜。本题就是简单的深度优先搜素+记忆化问题了。

这里考虑的是怎么才能算平局，我们采取的方法是，如果有n个节点，到2n轮如果还没出结果，就认为可以平局了。

需要注意的是记忆化，memo[i][j][k] 代表猫在i，老鼠在j，在第k轮的结果。

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

（以下描述，均不是学术用语，仅供大家快乐的阅读）
飞蛾扑火算法（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,仅供参考

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

G. 【算法笔记】字符串匹配

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法：

主串和模式串：
在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m

我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

BF 算法的时间复杂度是 O(n*m)

等价于

比如匹配Google 和Goo 是最好时间复杂度，匹配Google 和ble是匹配失败的最好时间复杂度。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配。

看来网上很多的文章，感觉很多的都没有说清楚，这里直接复制阮一峰的内容，讲的很清晰
内容来自 http://www.ruanyifeng.com/blog/

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

因为 6 - 2 等于4，所以将搜索词向后移动4位。

因为空格与C不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

因为空格与A不匹配，继续后移一位。

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是着名的KMP 算法的 3 到 4 倍。

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）

未完待续

参考文章：
字符串匹配的Boyer-Moore算法