蚁群算法和退火算法的优缺点_与遗传算法相近的算法[通俗易懂]

这些优化算法都是为针对一个目标值的最大或最小的寻找，前三种算法都属于概率性原理的算法（区别于工程优化里面的梯度下降，牛顿算法等连续直接的搜索算法，可以参考我这篇文章，求多元函数极值的情况分类与对应的算法），可以避免局部最优。 而禁忌搜索算法是靠禁忌表（里面存的是前面一些次数的搜索方向和搜索步伐，可能这些步伐有局部最优解了）来限制新的搜索方向和步伐跟禁忌表里不一样，这样可以跳出这个局部最优，去更广阔的的地方搜索（不是使用的随机方式）。

群蚁算法

蚂蚁寻找食物的过程：

单只蚂蚁的行为及其简单，行为数量在10种以内，但成千上万只蚂蚁组成的蚁群却能拥有巨大的智慧，这离不开它们信息传递的方式——信息素。蚂蚁在行走过程中会释放一种称为“信息素”的物质，用来标识自己的行走路径。在寻找食物的过程中，根据信息素的浓度选择行走的方向，并最终到达食物所在的地方。信息素会随着时间的推移而逐渐挥发。在一开始的时候，由于地面上没有信息素，因此蚂蚁们的行走路径是随机的。蚂蚁们在行走的过程中会不断释放信息素，标识自己的行走路径。随着时间的推移，有若干只蚂蚁找到了食物，此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的，因此在单位时间内，短路径上的蚂蚁数量比长路径上的蚂蚁数量要多，从而蚂蚁留下的信息素浓度也就越高。这为后面的蚂蚁们提供了强有力的方向指引，越来越多的蚂蚁聚集到最短的路径上去。

什么是蚁群算法？

蚁群算法就是模拟蚂蚁寻找食物的过程，它能够求出从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。这也就是著名的旅行商问题(Traveling Saleman Problem，TSP)。主要就是解决一个组合优化的问题，比如每个段都有长度，这些段怎么组合起来使得总距离最短，不就是高中学的排列组合嘛，目标函数就是总和最小，这里用的群蚁算法就是以一定的随机概率进行组合（如果是我们自己手动一一把所有的可能性都组合出来，算出各自的总和，这样是最原本理想的做法，但是因为段数太多了，比如30段，那么组合就是30的阶乘/2，计算机可能算到爆炸，所以就希望通过一种运算量小的近似的方式求出呢，确实是可以的，那么就是群蚁算法等，而为什么需要这种概率性的搜索算法呢，因为这样才能避免直接试探性组合产生的局部最优，即跳出局部最优。除了群蚁算法，其他算法可以不呢，但是根据其算法过程知道，群蚁算法适合解决这种离散组合最大值总和的的情况，比如像求一个函数最大值这种，就不需要组合的操作了，所以用遗传算法，模拟退火算法，爬山算法，梯度下降等搜索算法才合适。

应用领域：

可以使用蚁群算法来解决分布式环境下的负载均衡调度问题。

大家感兴趣可以去具体看看参考链接给出的这篇文章的代码实现，还是挺通俗易懂的。
 

遗传算法

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。

初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

应用领域：

一元函数最大值问题。

其主要原因是遗传算法有个随机变异的方式，所以很有可能找到最高峰的那个坐标。而搜索算法（这是我以前写过的文章）只能一步一步向前搜索，这样很有可能遇到局部最优罢了。

模拟退火算法

继续考虑寻找f(x)最大值的问题，爬山算法搜索到A点时就会停止搜索，原因是A点左右的值均小于A点的值。模拟退火算法采用的解决办法是以一定的概率选择A两边的点，尽管A两边的点并不是局部最优解，这样就有一定的概率搜索到D点，从而搜索到B点，最终获得了全局最优解。上文中的一定概率来自于固体退火原理：当固体温度较高时，物质内能较大，固体内部分子运动剧烈；当温度逐渐降低时，物体内能也随之降低，分子运动趋于平稳；当固体温度降到常温时，固体内部分子运动最终平稳。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e^(-ΔE/(kT))，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。

禁忌搜索算法 

禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

又名“tabu搜索算法”为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索散发就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。

当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

主要思路

1、在搜索中，构造一个短期循环记忆表-禁忌表，禁忌表中存放刚刚进行过的 |T|（T称为禁忌表）个邻居的移动，这种移动即解的简单变化。

2、禁忌表中的移动称为禁忌移动。对于进入禁忌表中的移动， 在以后的 |T| 次循环内是禁止的，以避免回到原来的解，从而避免陷入循环。|T| 次循环后禁忌解除。

3、禁忌表是一个循环表，在搜索过程中被循环的修改，使禁忌表始终保持 |T| 个移动。

4、即使引入了禁忌表，禁忌搜索仍可能出现循环。因此，必须给定停止准则以避免出现循环。当迭代内所发现的最好解无法改进或无法离开它时，算法停止。

局部搜索算法

局部搜索算法从一个初始解开始，通过邻域动作，产生其邻居解，判断邻居解的质量，根据某种策略，来选择邻居解，重复上述过程，至到达终止条件。

针对局部邻域搜索，为了实现全局优化，可尝试的途径有：

以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；
扩大邻域搜索结构，如TSP的2opt扩展到k-opt；
多点并行搜索，如进化计算；
采用TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。
基本思想
避免在搜索过程中的循环

只进不退的原则,通过禁忌表实现

不以局部最优作为停止准则

标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域。
 

总结：遗传算法，模拟退火算法，禁忌搜索算法都是以概率选取新点或者避免重复搜索等的方式进行最优解的搜索（搜索目标函数的最值），蚁群算法主要是解决离组合优化等离散问题的最优值。

参考文献

* 10分钟搞懂蚁群算法

* 【算法】超详细的遗传算法(Genetic Algorithm)解析

* 模拟退火算法

* 禁忌搜索算法

* 禁忌搜索算法总结

今天的文章蚁群算法和退火算法的优缺点_与遗传算法相近的算法[通俗易懂]分享到此就结束了，感谢您的阅读。