与算法笔记
‘壹’ 优化算法笔记（十二）烟花算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
烟花算法（Firework Algorithm,FWA）是一种受烟花爆炸产生火星，并继续分裂爆炸这一过程启发而得出的算法。算法的思想简单，但具体实现复杂。算法提出时间并不长，但是已经有了不少的改进研究和较为全面的应用。
烟花算法中，每一个烟花的位置都代表了一个可行解。烟花的爆炸产生的火星有两种，正常的火星与特别的火星。每个火星都会爆炸产生数个正常火星，某些火星有一定的概率产生一个特别的火星。正常的火星根据当前火星的振幅随机均匀分布在该火星的周围，而特别的火星将在当前火星附近以正态分布方式产生。每次迭代产生的火星数量多于每一代应有的火星数，算法将参照火星位置的优劣，随机留下指定数量的火星，已保持火星数目的稳定。
烟花算法的主角毫无疑问就是烟花了。
式（1）为适应度值越小越优的情况，而式（2）则是适应度值越大越优的情况。 为一个极小的值，以保证分母不为0。
每个火星产生的正常火星数量也由其适应度值来决定。
其中 表示第i个火星将要产生的正常火星数， 是产生正常火星的总数为一个常数，从式（3）,（4）可以看出适应度值越好的火星能够产生更多的正常火星，反之，火星适应度越差，能够产生的火星数越少。
由于式（3），（4）计算出的值为小数，烟花算法中使用式（5）将其转化为整数。
从式（3）和式（4）中可以看出，在每一代中将会产生出 个正常火星。产生的正常火星的位置与当前火星的振幅有关，可以从式（1），（2）看出，适应度越优的火星的振幅越小，那么它产生的正常火星将在它自己周围，而适应度越差的火星的振幅越大，它产生的正常火星将会出现在离自己较远的位置。
当前火星每次爆炸会从D维搜索空间内随机选择z维进行更新从而产生新的火星。正常火星的位置由如下公式产生。
其中z为取值1-D的均匀随机正整数，rand(-1,1)表示-1到1内的均匀随机数。从式(6)中可以看出，正常火星的位置与其振幅有直接关系，振幅越大产生的新火星距当前火星的距离约远。
每次迭代过程中，会产生m个特别的火星，即在这N个火星中随机选择m个火星，每个火星产生一个特别的火星。特别的火星的由下面的公式产生：
由上面的过程可知，在每一代中，有N个火星，将会产生出 个正常火星以及m个特别的火星。但是每一代中只能从这 个火星中选择N个火星保留至下一代。
每次会先从 个火星中选择最优的火星保留至下一代，然后再从中选择N-1个火星。选择某个火星的概率如下：
其中R(X)表示该火星距其他所有火星的距离之和，即距其它火星越远的火星，被选择保留至下一代的概率较大。
个火星，而且
,所有烟花算法每次迭代的计算复杂度要大于其他算法，这简直就是一个作弊行为。别的算法每次只搜索了N个位置，而烟花算法却搜索了 个位置。与其他优化算法对比时，其他算法的种群数量应该取 ，否则这将是一场不公正的对决。
适应度函数还是这个简单的小白鼠
实验一 ：标准烟花算法
以上数据来自原论文，现在看一看实验的图像以及实验结果。
从图像可以看出每次只选择保留了5个火星，它们的收敛速度很慢，实验结束时距离目标点还有一段距离。
看看实验结果
从实验结果可以看出，算法的性能很不稳定，而造成这一点的原因很可能是其收敛速度较慢，算法仍在收敛过程中，所以结果看上去很差。将最大迭代次数修改为100代，重新试验，其结果如下：
结果好了一些但还是难以接受，为什么烟花算法的结果不理想呢？
原因可能是保留机制（2.3节）的问题，烟花算法中保留火星的概率是根据该火星与其他火星的距离和，距离群体越大的个体被保留下的概率越大。这样做有什么好处呢？好处是火星相对分散，这是一个对抗局部最优的策略，但是，距离群体较远的个体是一个较差的个体的概率非常大，坏处就是，集中于当前最优位置的火星被保留的概率较小，算法的局部搜索能力将较弱。
实验二 . 随机选择的方式保留火星
为了加快烟花算法的收敛速度，增强局部搜索能力，我移除了标准烟花算法的选择过程，使用随机选择的方式保留火星，当然，最优个体依然会被保留至下一代。其他参数保持不变。
可以看出这次的图像相比实验一收敛速度快了不少，在迭代结束时已经相对在一个较小的区域。这次的结果也明显优于实验一。将选择过程改为随机选择后，由于较优的火星产生的较多且分布在自己周围，因此选择到这些较优的火星的概率也相对较大，算法的收敛速度相对较快。与此同时，算法跳出局部最优的能力比修改前要弱。
对于较简单的问题来说当然是随机选择收敛较快结果较好，而复杂的问题则需要更强的跳出局部最优能力。问题的关键仍然是，我们无法在一开始就知道问题的复杂程度。
实验三 .增加火星的种群数量，减少每代产生的正常火星总数
为什么要减少产生的正常火星数，这样算法搜索的次数减少了，效果不会更差吗？其实与直觉相反，减少正常火星总数，增加火星总群数，实际上是让较优的火星产生的正常火星被保留下来的概率变大了，这样也可以解决实验一中的问题，加快算法的收敛速度。
从图像中可以看出，算法在50代之前已经收敛，但是之后只在小范围内进行搜索。实验图像与之前的描述相符，收敛速度加快但是跳出局部最优能力减弱。看看实验结果，实验结果好了不少且结果更加稳定。
其实实验二与实验三，使用了不同的策略，但都达到了同样的目的——保留更多的优质火星到下一代，它们促进了局部搜索但是挤占了较劣火星的位置，削弱了种群的多样性。
每代留下的火星多了，图像看上去是不是更像烟花？
烟花算法的探究远不止如此，几年前作为一个较新的算法来学习时却已经有了大量的论文和书籍，可见大家对烟花算法已经有了较为深入的研究，而我能做的只是应用算法解决问题以及稍作改进让算法与问题的适应性更高。
烟花算法产生正常火星的过程为算法提供了搜索能力，产生特殊火星的过程和选择过程为算法提供了跳出局部最优的能力。但是个人认为选择过程与其他过程的适应性不是很好。标准的选择过程会丢失掉许多较优的个体，使之前产生的正常火星得到的成果没有保留。
烟花算法其实还有比较多的改进点，对算法产生最大的参数应该就是正常火星的总数以及振幅了。简单粗暴的改进：在每一代可以对这两个参数进行变化或者随机化，让算法的搜索能力与跳出局部最优能力在整个流程中动态变化，以均衡两种能力。
以下指标纯属个人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. 提取码：yaj0
目录
上一篇 优化算法笔记（十一）群搜索算法
下一篇 优化算法笔记（十三）鲸鱼算法
优化算法matlab实现（十二）烟花算法matlab实现
‘贰’ 优化算法笔记（十八）灰狼算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
灰狼算法（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实现
‘叁’ 机试指南与算法笔记哪个好
《算法笔记》好培明。
《算法笔记》和《王配升告道考研计算机考研机试指南》，前者详细，可以用来学习，后者比笑并较粗一点，可以拿来复盘。
《算法笔记》是一本零基础就能读懂的算法书籍，读者不需要因为自己没有语言基础而畏惧。
‘肆’ 算法设计与分析笔记之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的方法：
参考资料 ：《算法导论》
‘伍’ 优化算法笔记（一）优化算法的介绍
（以下描述，均不是学术用语，仅供大家快乐的阅读）
我们常见常用的算法有排序算法,字符串遍历算法,寻路算法等。这些算法都是为了解决特定的问题而被提出。
算法本质是一种按照固定步骤执行的过程。
优化算法也是这样一种过程，是一种根据概率按照固定步骤寻求问题的最优解的过程。与常见的排序算法、寻路算法不同的是，优化算法不具备等幂性，是一种 概率算法 。算法不断的 迭代 执行同一步骤直到结束，其流程如下图。
等幂性即 对于同样的输入，输出是相同的 。
比如图1，对于给定的鱼和给定的熊掌，我们在相同的条件下一定可以知道它们谁更重，当然，相同的条件是指鱼和熊掌处于相同的重力作用下，且不用考虑水分流失的影响。在这些给定的条件下，我们（无论是谁）都将得出相同的结论，鱼更重或者熊掌更重。我们可以认为，秤是一个等幂性的算法（工具）。
现在把问题变一变，问鱼与熊掌你更爱哪个，那么现在，这个问题，每个人的答案可能不会一样，鱼与熊掌各有所爱。说明喜爱这个算法不是一个等幂性算法。当然你可能会问，哪个更重，和更喜欢哪个这两个问题一个是客观问题，一个是主观问题，主观问题没有确切的答案的。当我们处理主观问题时，也会将其转换成客观问题，比如给喜欢鱼和喜欢熊掌的程度打个分，再去寻求答案，毕竟计算机没有感情，只认0和1（量子计算机我不认识你）。
说完了等幂性，再来说什么是概率算法。简单来说就是看脸、看人品、看运气的算法。
有一场考试，考试的内容全部取自课本，同时老师根据自己的经验给同学们划了重点，但是因为试卷并不是该老师所出，也会有考试内容不在重点之内，老师估计试卷中至少80%内容都在重点中。学霸和学渣参加了考试，学霸为了考满分所以无视重点，学渣为了pass，因此只看了重点。这样做的结果一定是score(学霸)>=score(学渣)。
当重点跟上图一样的时候，所有的内容都是重点的时候，学霸和学渣的学习策略变成了相同的策略，则score(学霸)=score(学渣)。但同时，学渣也要付出跟学霸相同的努力去学习这些内容，学渣心里苦啊。
当课本如下图时
学霸？学霸人呢，哪去了快来学习啊，不是说学习一时爽，一直学习一直爽吗，快来啊，还等什么。
这时，如果重点内容远少于书本内容时，学渣的学习策略有了优势——花费的时间和精力较少。但是同时，学渣的分数也是一个未知数，可能得到80分也可能拿到100分，分数完全取决于重点内容与题目的契合度，契合度越高，分数越高。对学渣来说，自己具体能考多少分无法由自己决定，但是好在能够知道大概的分数范围。
学霸的学习策略是一种遍历性算法，他会遍历、通读全部内容，以保证满分。
学渣的学习策略则是一种概率算法，他只会遍历、学习重点内容，但至于这些重点是不是真重点他也不知道。
与遍历算法相比，概率算法的结果具有不确定性，可能很好，也可能很差，但是会消耗更少的资源，比如时间（人生），空间（记忆）。概率算法的最大优点就是 花费较少的代价来获取最高的收益 ，在现实中体现于节省时间，使用很少的时间得到一个不与最优解相差较多的结果。
“庄子：吾生也有涯，而知也无涯；以有涯随无涯，殆矣。”的意思是：人生是有限的，但知识是无限的（没有边界的），用有限的人生追求无限的知识，是必然失败的。
生活中概率算法（思想）的应用其实比较广泛，只是我们很少去注意罢了。关于概率算法还衍生出了一些有趣的理论，比如墨菲定律和幸存者偏差，此处不再详述。
上面说到，优化算法就是不停的执行同样的策略、步骤直到结束。为什么要这样呢？因为优化算法是一种概率算法，执行一次操作就得到最优结果几乎是不可能的，重复多次取得最优的概率也会增大。
栗子又来了，要从1-10这10个数中取出一个大于9的数，只取1次，达到要求的概率为10%，取2次，达到要求的概率为19%。
可以看出取到第10次时，达到要求的概率几乎65%，取到100次时，达到要求的概率能接近100%。优化算法就是这样简单粗暴的来求解问题的吗？非也，这并不是一个恰当的例子，因为每次取数的操作之间是相互独立的，第2次取数的结果不受第1次取数结果的影响，假设前99次都没达到要求，那么再取一次达到要求的概率跟取一次达到要求的概率相同。
优化算法中，后一次的计算会依赖前一次的结果，以保证后一次的结果不会差于前一次的结果。这就不得不谈到马尔可夫链了。
由铁组成的链叫做铁链，同理可得，马尔可夫链就是马尔可夫组成的链。
言归正传, 马尔可夫链（Markov Chain, MC） ,描述的是 状态转移的过程中,当前状态转移的概率只取决于上一步的状态,与其他步的状态无关 。简单来说就是当前的结果只受上一步的结果的影响。每当我看到马尔可夫链时，我都会陷入沉思，生活中、或者历史中有太多太多与马尔可夫链相似的东西。西欧封建等级制度中“附庸的附庸不是我的附庸”与“昨天的努力决定今天的生活，今天的努力决定明天的生活”，你的下一份工作的工资大多由你当前的工资决定，这些都与马尔可夫链有异曲同工之处。
还是从1-10这10个数中取出一个大于9的数的这个例子。基于马尔可夫链的概率算法在取数时需要使当前取的数不小于上一次取的数。比如上次取到了3，那么下次只能在3-10这几个数中取，这样一来，达到目标的概率应该会显着提升。还是用数据说话。
取1次达到要求的概率仍然是
取2次内达到要求的概率为
取3次内达到要求的概率为
取4次内……太麻烦了算了不算了
可以看出基于马尔可夫链来取数时，3次内能达到要求的概率与不用马尔可夫链时取6次的概率相当。说明基于马尔可夫链的概率算法求解效率明显高于随机概率算法。那为什么不将所有的算法都基于马尔可夫链呢？原因一，其实现方式不是那么简单，例子中我们规定了取数的规则是复合马尔可夫链的，而在其他问题中我们需要建立适当的复合马尔科夫链的模型才能使用。原因二，并不是所有的问题都符合马尔科夫链条件，比如原子内电子出现的位置，女朋友为什么会生（lou）气，彩票号码的规律等，建立模型必须与问题有相似之处才能较好的解决问题。
介绍完了优化算法，再来讨论讨论优化算法的使用场景。
前面说了优化算法是一种概率算法，无法保证一定能得到最优解，故如果要求结果必须是确定、稳定的值，则无法使用优化算法求解。
例1，求城市a与城市b间的最短路线。如果结果用来修建高速、高铁，那么其结果必定是唯一确定的值，因为修路寸土寸金，必须选取最优解使花费最少。但如果结果是用来赶路，那么即使没有选到最优的路线，我们可能也不会有太大的损失。
例2，求城市a与城市b间的最短路线，即使有两条路径，路径1和路径2，它们从a到b的距离相同，我们也可以得出这两条路径均为满足条件的解。现在将问题改一下，求城市a到城市b耗时最少的线路。现在我们无法马上得出确切的答案，因为最短的线路可能并不是最快的路线，还需要考虑到天气，交通路况等因素，该问题的结果是一个动态的结果，不同的时间不同的天气我们很可能得出不同的结果。
现实生产、生活中，也有不少的场景使用的优化算法。例如我们的使用的美图软件，停车场车牌识别，人脸识别等，其底层参数可能使用了优化算法来加速参数计算，其参数的细微差别对结果的影响不太大，需要较快的得出误差范围内的参数即可；电商的推荐系统等也使用了优化算法来加速参数的训练和收敛，我们会发现每次刷新时，推给我们的商品都有几个会发生变化，而且随着我们对商品的浏览，系统推给我们的商品也会发生变化，其结果是动态变化的；打车软件的订单系统，会根据司机和客人的位置，区域等来派发司机给客人，不同的区域，不同的路况，派发的司机也是动态变化的。
综上我们可以大致总结一下推荐、不推荐使用优化算法的场景的特点。
前面说过，优化算法处理的问题都是客观的问题，如果遇到主观的问题，比如“我孰与城北徐公美”，我们需要将这个问题进行量化而转换成客观的问题，如身高——“修八尺有余”，“外貌——形貌昳丽”，自信度——“明日徐公来，孰视之，自以为不如；窥镜而自视，又弗如远甚”，转化成客观问题后我们可以得到各个解的分数，通过比较分数，我们就能知道如何取舍如何优化。这个转化过程叫做问题的建模过程，建立的问题模型实际上是一个函数，这个函数对优化算法来说是一个黑盒函数，即不需要知道其内部实现只需要给出输入，得到输出。
在优化算法中这个黑盒函数叫做 适应度函数 ， 优化算法的求解过程就是寻找适应度函数最优解的过程 ，使用优化算法时我们最大的挑战就是如何将抽象的问题建立成具体的模型，一旦合适的模型建立完成，我们就可以愉快的使用优化算法来求解问题啦。（“合适”二字谈何容易）
优化算法的大致介绍到此结束，后面我们会依次介绍常见、经典的优化算法，并探究其参数对算法性能的影响。
——2019.06.20
[目录]
[下一篇 优化算法笔记（二）优化算法的分类]
‘陆’ 优化算法笔记（二）优化算法的分类
（以下描述，均不是学术用语，仅供大家快乐的阅读）
在分类之前，我们先列举一下常见的优化算法（不然我们拿什么分类呢？）。
1遗传算法Genetic algorithm
2粒子群优化算法Particle Swarm Optimization
3差分进化算法Differential Evolution
4人工蜂群算法Artificial Bee Colony
5蚁群算法Ant Colony Optimization
6人工鱼群算法Artificial Fish Swarm Algorithm
7杜鹃搜索算法Cuckoo Search
8萤火虫算法Firefly Algorithm
9灰狼算法Grey Wolf Optimizer
10鲸鱼算法Whale Optimization Algorithm
11群搜索算法Group search optimizer
12混合蛙跳算法Shuffled Frog Leaping Algorithm
13烟花算法fireworks algorithm
14菌群优化算法Bacterial Foraging Optimization
以上优化算法是我所接触过的算法，没接触过的算法不能随便下结论，知之为知之，不知为不知。其实到目前为止优化算法可能已经有几百种了，我们不可能也不需要全面的了解所有的算法，而且优化算法之间也有较大的共性，深入研究几个之后再看其他优化算法上手速度会灰常的快。
优化算法从提出到现在不过50-60年（遗传算法1975年提出），虽种类繁多但大多较为相似，不过这也很正常，比较香蕉和人的基因相似度也有50%-60%。当然算法之间的相似度要比香蕉和人的相似度更大，毕竟人家都是优化算法，有着相同的目标，只是实现方式不同。就像条条大路通罗马，我们可以走去，可以坐汽车去，可以坐火车去，也可以坐飞机去，不管使用何种方式，我们都在去往罗马的路上，也不会说坐飞机去要比走去更好，交通工具只是一个工具，最终的方案还是要看我们的选择。
上面列举了一些常见的算法，即使你一个都没见过也没关系，后面会对它们进行详细的介绍，但是对后面的分类可能会有些许影响，不过问题不大，就先当总结看了。
再对优化算法分类之前，先介绍一下算法的模型，在笔记（一）中绘制了优化算法的流程，不过那是个较为简单的模型，此处的模型会更加复杂。上面说了优化算法有较大的相似性，这些相似性主要体现在算法的运行流程中。
优化算法的求解过程可以看做是一个群体的生存过程。
有一群原始人，他们要在野外中寻找食物，一个原始人是这个群体中的最小单元，他们的最终目标是寻找这个环境中最容易获取食物的位置，即最易存活下来的位置。每个原始人都去独自寻找食物，他们每个人每天获取食物的策略只有采集果实、制作陷阱或者守株待兔，即在一天之中他们不会改变他们的位置。在下一天他们会根据自己的策略变更自己的位置。到了某一天他们又聚在了一起，选择了他们到过的最容易获取食物的位置定居。
一群原始人=优化算法中的种群、群体；
一个原始人=优化算法中的个体；
一个原始人的位置=优化算法中个体的位置、基因等属性；
原始人变更位置=优化算法中总群的更新操作；
该位置获取食物的难易程度=优化算法中的适应度函数；
一天=优化算法中的一个迭代；
这群原始人最终的定居位置=优化算法所得的解。
优化算法的流程图如下：
对优化算法分类得有个标准，按照不同的标准分类也会得到不一样的结果。首先说一下我所使用的分类标准（动态更新，有了新的感悟再加）：
按由来分类比较好理解，就是该算法受何种现象启发而发明，本质是对现象分类。
可以看出算法根据由来可以大致分为有人类的理论创造而来，向生物学习而来，受物理现象启发。其中向生物学习而来的算法最多，其他类别由于举例有偏差，不是很准确，而且物理现象也经过人类总结，有些与人类现象相交叉，但仍将其独立出来。
类别分好了，那么为什么要这么分类呢？
当然是因为要凑字数啦，啊呸，当然是为了更好的理解学习这些算法的原理及特点。
向动物生存学习而来的算法一定是一种行之有效的方法，能够保证算法的效率和准确性，因为，如果使用该策略的动物无法存活到我们可以对其进行研究，我们也无法得知其生存策略。（而这也是一种幸存者偏差，我们只能看到行之有效的策略，但并不是我们没看到的策略都是垃圾，毕竟也发生过小行星撞地球这种小概率毁灭性事件。讲个冷笑话开cou心一shu下:一只小恐龙对他的小伙伴说，好开心，我最喜欢的那颗星星越来越亮了（完）。）但是由于生物的局限性，人们所创造出的算法也会有局限性：我们所熟知的生物都生存在三维空间，在这些环境中，影响生物生存的条件比较有限，反应到算法中就是这些算法在解决较低维度的问题时效果很好，当遇到超高维（维度>500）问题时，结果可能不容乐观，没做过实验，我也不敢乱说。
按更新过程分类相对复杂一点，主要是根据优化算法流程中更新位置操作的方式来进行分类。更新位置的操作按我的理解可大致分为两类：1.跟随最优解；2.不跟随最优解。
还是上面原始人的例子，每天他有一次去往其他位置狩猎的机会，他们采用何种方式来决定今天自己应该去哪里呢？
如果他们的策略是“跟随最优解”，那么他们选取位置的方式就是按一定的策略向群体已知的最佳狩猎位置（历史最佳）或者是当前群体中的最佳狩猎位置（今天最佳）靠近，至于是直线跑过去还是蛇皮走位绕过去，这个要看他们群体的策略。当然，他们的目的不是在最佳狩猎位置集合，他们的目的是在过去的途中看是否能发现更加好的狩猎位置，去往已经到过的狩猎地点再次狩猎是没有意义的，因为每个位置获取食物的难易程度是固定的。有了目标，大家都会朝着目标前进，总有一日，大家会在谋个位置附近相聚，相聚虽好但不利于后续的觅食容易陷入局部最优。
什么是局部最优呢？假设在当前环境中有一“桃花源”，拥有上帝视角的我们知道这个地方就是最适合原始人们生存的，但是此地入口隐蔽“山有小口，仿佛若有光”、“初极狭，才通人。”，是一个难以发现的地方。如果没有任何一个原始人到达了这里，大家向着已知的最优位置靠近时，也难以发现这个“桃源之地”，而当大家越聚越拢之后，“桃源”被发现的可能性越来越低。虽然原始人们得到了他们的解，但这并不是我们所求的“桃源”，他们聚集之后失去了寻求“桃源”的可能，这群原始人便陷入了局部最优。
如果他们的策略是“不跟随最优解”，那么他们的策略是什么呢？我也不知道，这个应该他们自己决定。毕竟“是什么”比“不是什么”的范围要小的多。总之不跟随最优解时，算法会有自己特定的步骤来更新个体的位置，有可能是随机在自己附近找，也有可能是随机向别人学习。不跟随最优解时，原始人们应该不会快速聚集到某一处，这样一来他们的选择更具多样性。
按照更新过程对上面的算法分类结果如下
可以看出上面不跟随最优解的算法只有遗传算法和差分进化算法，他们的更新策略是与进化和基因的重组有关。因此这些不跟随最优解的算法，他们大多依据进化理论更新位置（基因）我把他们叫做进化算法，而那些跟随群体最优解的算法，他们则大多依赖群体的配合协作，我把这些算法叫做群智能算法。
目前我只总结了这两种，分类方法，如果你有更加优秀的分类方法，我们可以交流一下：
目录
上一篇 优化算法笔记（一）优化算法的介绍
下一篇 优化算法笔记（三）粒子群算法（1）
‘柒’ 数据结构与算法之美笔记——散列表（上）
摘要:
我们已经知道随机访问数组元素时间复杂度只有 ，效率极高，当我们想利用数组的这个特性时就需要将元素下标与存储信息对应。例如，一个商店只有四件商品，依次编号 0 至 3，这样就可以将四件商品信息按照编号对应下标的方式存储到数组中，依据编号就可以快速从数组中找到相应商品信息。
如果一段时间之后，商店盈利并且重新进货 100 件商品，商家想对大量商品在编号上区分类别，这时陵锋颂候需要使用类别编号加顺序编号的方式标识每件商品，这种编号变得复杂，并不能直接对应数组下标，此时的商品编号又该如何对应数组下标以实现快速查找商品的功能？这时候我们可以将类别编号去除之后按照顺序编号对应数组下标，同样也能享受数组高效率随机访问的福利。这个例子中，商品编号称为“ 键 ”或“ 关键字 ”，将键转化为数组对应下标的方法就是“ 散列函数 ”或“ Hash 函数 ”，由散列函数生成的值叫做“ 散列值 ”或“ Hash 值 ”，而这样的数组就是散列表。
从散列表的原理来看，数据通过散列函数计算得到散列值是关键，这个步骤中散列函数又是其中的核心，一个散列函数需要遵守以下三个原则。
因为散列函数生成的散列值对应数组下标，而数组下标就是非负整数，所以需要满足第一个原则；两个相等的数据经过散列算法得到的散列值肯定相等，否则利用散列值在散列表中查找数据就无从谈起；至于第三个原则虽然在情理之中，却不那么容易做到，即使是被广泛运用的散列算法也会出现散列值冲突的情况，导致无法满足第三个原则。
散列函数作为散列表的核心部分，尺郑必然不能拖散列表的执行效率后腿，毕竟散列表的查询、插入和删除操作都需要经过基告散列函数，所以散列函数不能太复杂，执行效率不能太低。由于散列函数不可避免地都会出现散列冲突情况，散列函数要尽量降低散列冲突，使散列值能够均匀地分布在散列表中。
解决散列冲突主要有“ 开放寻址 ”（open addressing）和“ 链表法 ”（chaining）两类方法。
开放寻址法是指插入操作时，当生成的散列值对应槽位已经被其他数据占用，就探测空闲位置供插入使用，其中探测方法又分为“ 线性探测 ”（Linear Probing）、“ 二次探测 ”（Quadratic Probing）和“ 双重散列 ”（Double hashing）三种。
线性探测是其中较为简单的一种，这种探测方式是当遇到散列冲突的情况就顺序查找（查找到数组尾部时转向数组头部继续查找），直到查找到空槽将数据插入。当进行查找操作时，也是同样的操作，利用散列值从散列表中取出对应元素，与目标数据比对，如果不相等就继续顺序查找，直到查找到对应元素或遇到空槽为止，最坏情况下查找操作的时间复杂度可能会下降为 。
散列表除了支持插入和查找操作外，当然也支持删除操作，不过并不能将需删除的元素置为空。如果删除操作是将元素置为空的话，查找操作遇到空槽就会结束，存储在被删除元素之后的数据就可能无法正确查找到，这时的删除操作应该使用标记的方式，而不是使用将元素置空，当查找到被标识已删除的元素将继续查找，而不是就此停止。
线性探测是一次一个元素的探测，二次探测就是使用都是线性探测的二次方步长探测。例如线性探测是 ，那二次探测对应的就是 。
双重探测是当第一个散列函数冲突时使用第二个散列函数运算散列值，利用这种方式探测。例如，当 冲突时，就使用 计算散列值，如果再冲突就使用 计算散列值，依此类推。
关于散列表的空位多少使用“ 装载因子 ”（load factor）表示，装载因子满足数学关系 ，也就是说装载因子越大，散列表的空闲空间越小，散列冲突的可能性也就越大，一般我们会保持散列表有一定比例的空闲空间。
为了保持散列表一定比例的空闲空间，在装载因子到达一定阈值时需要对散列表数据进行搬移，但散列表搬移比较耗时。你可以试想下这样的步骤，在申请一个新的更大的散列表空间后，需要将旧散列表的数据重新通过散列函数生成散列值，再存储到新散列表中，想想都觉得麻烦。
散列表搬移的操作肯定会降低散列表的操作效率，那能不能对这一过程进行改进？其实可以将低效的扩容操作分摊至插入操作，当装载因子达到阈值时不一次性进行散列表搬移，而是在每次插入操作时将一个旧散列表数据搬移至新散列表，这样搬移操作的执行效率得到了提高，插入操作的时间复杂度也依然能保持 的高效。当新旧两个散列表同时存在时查询操作就要略作修改，需先在新散列表中查询，如果没有查找到目标数据再到旧散列表中查找。
当然，如果你对内存有更高效的利用要求，可以在装载因子降低至某一阈值时对散列表进行缩容处理。
除了开放寻址之外，还可以使用链表法解决散列冲突的问题。散列值对应的槽位并不直接存储数据，而是将数据存储在槽位对应的链表上，当进行查找操作时，根据散列函数计算的散列值找到对应槽位，再在槽位对应的链表上查找对应数据。
链表法操作的时间复杂度与散列表槽位和数据在槽位上的分布情况有关，假设有 n 个数据均匀分布在 m 个槽位的散列表上，那链表法的时间复杂度为 。链表法可以不用像开放寻址一样关心装载因子，但需要注意散列函数对散列值的计算，使链表结点能够尽可能均匀地分布在散列表槽位上，避免散列表退化为链表。有时黑客甚至会精心制造数据，利用散列函数制造散列冲突，使数据集中某些槽位上，造成散列表性能的极度退化。
面对这样的恶意行为散列表只能坐以待毙吗？其实不然，当槽位上的链表过长时，可以将其改造成之前学习过的跳表等，链表改造为跳表后查询的时间复杂度也只是退化为 ，依然是可以接受的范围。
链表法在存储利用上比开放寻址更加高效，不用提前申请存储空间，当有新数据时申请一个新的结点就行。而且链表法对装载因子也不那么敏感，装载因子的增高也只是意味着槽位对应的链表更长而已，链表增长也有将链表改造为跳表等结构的应对策略，所以链表法在装载因子超过 1 的情况下都可保持高效。
开放寻址不存在像链表法一样有链表过长而导致效率降低的烦恼，不过装载因子是开放寻址的晴雨表，装载因子过高会造成散列冲突机率的上升，开放寻址就需要不断探测空闲位置，算法的执行成本会不断被提高。而且在删除操作时只能将数据先标记为删除，对于频繁增删的数据效率会受到影响。
当然也可以在这种风险出现前进行散列表的动态扩容，不过这样就会出现大量空闲的存储空间，导致存储的利用效率过低，这种现象在数据量越大的情况下越明显。所以开放寻址比较适用于数据量较小的情况。
链表法对于散列冲突的处理更加灵活，同时对存储空间的利用效率也更高，但链表结点除了存储数据外还需要存储指针，如果存储数据较小指针占用的存储甚至会导致整体存储翻倍的情况，但存储数据较大时指针占用的存储也就可以忽略不计，所以链表法较适合存储数据对象较大，但频繁的增删操作不会对链表法造成明显的影响。因为这样的特点，链表法更加适合大数据量，或者数据对象较大的时候，如果数据操作频繁，那链表法更是不二之选。
散列表由数组扩展而来，使用散列函数将键计算为散列值，散列值对应数据存储的数组下标。虽然散列表的执行效率较高，但会有散列冲突的问题，可以通过开放寻址法和链表法解决此问题。
开放寻址存储利用效率较低，适用数据量较小并且增删不频繁的情况，如果数据量较大，增删频繁的情况更加适用链表法，相对之下链表法更加普适。
‘捌’ 优化算法笔记（二十六）和声搜索算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
和声搜索算法（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,仅供参考
目录
上一篇 优化算法笔记（二十五）飞蛾扑火算法
下一篇 优化算法笔记（二十七）蜉蝣算法
‘玖’ 优化算法笔记（七）差分进化算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
差分进化算法（Differential Evolution Algorithm，DE）是一种基于群体的进化算法，它模拟了群体中的个体的合作与竞争的过程。算法原理简单，控制参数少，只有交叉概率和缩放比例因子，鲁棒性强，易于实现。
差分进化算法中，每一个个体的基因表示待求问题的一个候选解。每次迭代将先进行变异操作，选择一个或多个个体的基因作为基，然后选择不同的个体的差分来构成差分基因，最后将作为基的基因与差分基因相加来得出新的个体。交叉操作将新的个体将于父代的对应个体交叉，然后进行选择操作，比较交叉后的个体与父代的对应个体，选择较优的个体保留至下一代。在迭代完成之后将选择种群中最优个体的基因作为解。
差分进化算法可以算是我所使用过的优化算法中大魔王级别的算法，虽然它每个方面都没有强到离谱，但是综合起来的效果好于大多数算法。它就像一个每个科目都能考到90分（百分制）的学生，虽然没门课都不是最优秀的，但是论综合，论总分，它有极大的概率是第一名。
在我研究优化算法的小路上，我的目标就是找到一个能打败大魔王或是能在大多数方面压制魔王的算法。
这次的主角就选魔王军吧（或者蚁王军，为了与蚁群算法区别还是叫魔王军吧），个体则称之为魔王兵。
魔王兵的能力取决于它们的基因，它们可以根据环境或者需要改变自己的基因使得自己更加强大，更方便的处理问题，问题的维度与基因维度相同。
表示第i个魔王兵在进化了第t次后的基因，该个体有D位基因。
与遗传算法同为进化算法的差分进化算法，它们的操作（算子）也都非常相似的，都是交叉，变异和选择，流程也几乎一样（遗传算法先交叉后变异，差分进化算法先变异后交叉）。
说到差分进化算法中的变异，我就想到一句论语 “三人行，必有我师焉。择其善者而从之，其不善者而改之。” ，其实这句论语已经向我们说明了差分进化算法的整个流程：
“三人行，必有我师焉”——变异，交叉。
“择其善者而从之，其不善者而改之”——选择。
差分进化算法中，当一个魔王兵变异时，它会先找来3个小伙伴，当然是随机找来3个小伙伴，避免同化。在一个小伙伴的基因上加上另外两个小伙伴基因之差作为自己的目标基因。其变异公式如下：
表示第i个魔王兵找到了编号为r1、r2和r3的三个魔王兵，当然了i、r1、r2、r3为互不相同的整数，F为缩放比例因子，通常 ，一般取F=0.5。 为第i个魔王兵交叉后的目标基因图纸，不过这是个半成品，再经过交叉后，目标基因图纸才算完成。
其实现在我们已经有了5个基因图纸了 ，接下来将进行交叉操作。由于变异操作，差分进化算法的种群中个体数至少为4，即魔王军中至少有4个小兵。
交叉操作中，魔王兵i会将目标基因图纸 进行加工得到 ，加工过程如下：
其中 。 为交叉概率，其值越大，发生交叉的概率越大，一般取 。 为{1,2,…,D}中的随机整数，其作用是保证交叉操作中至少有一维基因来自变异操作产生的基因，不能让交叉操作的努力白费。
从公式上可以看出交叉操作实际上是从变异操作得出的基因图纸上选择至少一位基因来替换自己的等位基因，得到最终的基因图纸。
选择操作相对简单，魔王兵i拿到了最终的基因图纸 ，大喊一声，进化吧，魔王兵i的基因改变了。它拿出了能力测量器fitness function,如果发现自己变强了，那么就将基因 保留到下一代，否则它选择放弃进化，让自己还原成 。
实验又来啦，还是那个实验 ，简单、易算、好画图。
实验1 ：参数如下
图中可以看出在第20代时，群体已经非常集中了，在来看看最终得出的结果。
这结果真是好到令人发指，恶魔在心中低语“把其他的优化算法都丢掉吧”。不过别往心里去，任何算法都有优缺点，天下没有免费的午餐，要想获得某种能力必须付出至少相应的代价。
实验2：
将交叉率CR设为0,即每次交叉只选择保留一位变异基因。
看看了看图，感觉跟实验1中相比没有什么变化，那我们再来看看结果。
结果总体来说比实验1好了一个数量级。为什么呢？个人感觉应该是每次只改变一位基因的局部搜索能力比改变多位基因更强。下面我们将交叉率CR设为1来看看是否是这样。
实验3：
将交叉率CR设为1,即每次交叉只选择保留一位原有基因。
实验3的图与实验1和实验2相比好像也没什么差别,只是收敛速度好像快了那么一点点。再来看看结果。
发现结果比实验2的结果还要好？那说明了实验2我得出的结论是可能是错误的，交叉率在该问题上对差分进化算法的影响不大，它们结果的差异可能只是运气的差异，毕竟是概率算法。
实验4：
将变异放缩因子设为0，即变异只与一个个体有关。
收敛速度依然很快，不过怎么感觉结果不对，而且个体收敛的路径好像遗传算法，当F=0，时，差分进化算法退化为了没有变异、选择操作的遗传算法，结果一定不会太好。
果然如此。下面我们再看看F=2时的实验。
实验5：
将变异放缩因子设为2。
实验5的图可以明显看出，群体的收敛速度要慢了许多，到第50代时，种群还未完全收敛于一点，那么在50代时其结果也不会很好，毕竟算法还未收敛就停止进化了。
结果不算很好但也算相对稳定。
通过上面5个实验，我们大致了解了差分进化算法的两个参数的作用。
交叉率CR，影响基因取自变异基因的比例，由于至少要保留一位自己的基因和变异的基因导致CR在该问题上对算法性能的影响不大（这个问题比较简单，维度较低，影响不大）。
变异放缩因子F，影响群体的收敛速度，F越大收敛速度越慢，F绝对值越小收敛速度越快，当F=0是群体之间只会交换基因，不会变异基因。
差分进化算法大魔王已经如此强大了，那么还有什么可以改进的呢？当然有下面一一道来。
方案1 .将3人行修改为5人行，以及推广到2n+1人行。
实验6：
将3人行修改为5人行，变异公式如下：
五人行的实验图看起来好像与之前并没有太大的变化，我们再来看看结果。
结果没有明显提升，反而感觉比之前的结果差了。反思一下五人行的优缺点，优点，取值范围更大，缺点，情况太多，减慢搜索速度。
可以看出算法的收敛速度比之前的变慢了一点，再看看结果。
比之前差。
差分进化算法的学习在此也告一段落。差分进化算法很强大，也很简单、简洁，算法的描述都充满了美感，不愧是大魔王。不过这里并不是结束，这只是个开始，终将找到打败大魔王的方法，让新的魔王诞生。
由于差分进化算法足够强，而文中实验的问题较为简单导致算法的改进甚至越改越差（其实我也不知道改的如何，需要大量实验验证）。在遥远的将来，也会有更加复杂的问题来检验魔王的能力，总之，后会无期。
以下指标纯属个人yy,仅供参考
目录
上一篇 优化算法笔记（六）遗传算法
下一篇 优化算法笔记（八）人工蜂群算法
优化算法matlab实现（七）差分进化算法matlab实现
‘拾’ 优化算法笔记（二十四）帝王蝶算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
上一篇记录了蝴蝶算法（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,仅供参考
目录
上一篇 优化算法笔记（二十三）蝴蝶算法
下一篇 优化算法笔记（二十五）飞蛾扑火算法