「启发式算法」启发式算法

启发式算法

链接：https://www.jianshu.com/p/e2aec624106a

什么是 启发式 算法

启发式算法一般用于解决NP-hard问题，其中NP是指非确定性多项式。

例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从南京出发，经过广州，北京，上海，…，等 n 个城市，最后返回香港。任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？

推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排。

启发式算法是相对于最优化算法提出的，是基于直观或者经验构造的算法，在可接受的开销（时间和空间）内给出待解决组合优化问题的一个可行解。

目前通用的启发式算法

目前比较通用的启发式算法一般有模拟退火算法（SA）、遗传算法（GA）、蚁群算法（ACO）、人工神经网络（ANN）等。

模拟退火算法(SA)

模拟退火算法(Simulated Annealing, SA)的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。

模拟退火算法步骤

初始化温度T(充分大)，温度下限Tmin(充分小)，初始解X，每个T值迭代次数L
随机生成临域解x_new;
设f(x)函数来计算用来计算解得好坏，计算出f(x_new)-f(x);
如果f(x_new)-f(x)>0，说明新解比原来的解好，则无条件接受，如果f(x_new)-f(x)<0，则说明旧解比新解好，则以概率exp((f(xnew)-f(x))/k*T)接受x_new作为解。
如果当前温度<Tmin时，则退出循环，输出当前结果，否则减少当前温度，回到第2步继续循环，常用的降温方法为T= a*T (0<a<1)，一般a取接近1的值

遗传算法(GA)

遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。

遗传算法步骤

对潜在问题进行编码，初始化基因组，并根据基因组随机初始化种群，并指定繁衍代数。
计算种群中每个个体的适应度，选择一定数目的留下，其余淘汰。
在留下的个体中，随机繁衍，对分母基因进行交叉（极小概率变异），产生下一代。
回到第2步进行循环。直到达到指定的繁衍代数

蚁群算法(ACO)

简单介绍一下蚁群算法的思路。我们尝试复原一下蚂蚁寻找食物的场景。想象有一只蚂蚁找到了食物，这时它需要将食物带回蚁穴。对于这一只蚂蚁而言，它显然并不知道应该怎么走。那么，这只蚂蚁有可能会随机选择一条路线。

这条路线很可能是一条远路。但是，蚂蚁一路上留下了记号，也就是信息素。如果这只蚂蚁继续不停地搬运食物，或者有许多其他蚂蚁一块搬运的话。他们总会在运气好的时候走到更快往返的路线上。蚂蚁选择的路越好，相同时间内往返的次数也就更多，也就在路上留下了更多的信息素。

于是，蚂蚁们总会发现，有一些路径的信息素更浓，这些路径就是更好的路线。于是蚂蚁也就更多地向信息素更浓的路径上偏移。蚂蚁们不停重复这个过程，最终总能找到一条确定的路线，而这条路线就是蚂蚁们找到的最优路径。

蚁群算法步骤

初始化蚂蚁数量、可行路段、每条路段距离、每条路段的初始信息素大小等信息
设定蚂蚁的起点、终点。
蚂蚁从起点出发根据信息素浓度，有一定的概率性选择路段，浓度越高，概率越大，逐步回到终点。
在蚂蚁走过的路径上，根据每条路段的长度按比例释放信息素，短的路段释放的信息素多，长的路段释放的信息素少。
对所有路段的信息素进行挥发。
回到第二步进行循环，直到蚂蚁数量迭代完。

链接：https://www.zhihu.com/question/19731925/answer/21808171

启发式算法中，局部最优值的陷入无法避免。启发式，本质上是一种贪心策略，

这也在客观上决定了不符合贪心规则的更好（或者最优）解会错过。

简单来说，避免陷入局部最优就是两个字：随机。

具体实现手段上，可以根据所采用的启发式框架来灵活地加入随机性。比如遗传里面，可以在交叉变异时，可以在控制人口策略中，也可以在选择父本母本样本时；禁忌里面，可以在禁忌表的长度上体现，也可以在解禁策略中使用，等等。这些都要结合具体问题特定的算例集，需要反复尝试摸索才行。参数的敏感性是一个问题，建议不要超过3个参数，参数越不敏感越好。不同算例集用不同种子运行多次（100次左右才有统计意义），统计平均性能即可。需注意全局的随机重启通常来说不是一个好办法，因为等于主动放弃之前搜索结果，万不得已不要用，或者就是不用。

三个原则应该把握：越随机越好；越不随机越好；二者平衡最好。

越随机越好

没有随机性，一定会陷入局部最优。为了获得更大的找到最优解的期望，算法中一定要有足够的随机性。具体体现为鲁棒性较好，搜索时多样性较好。算法的每一步选择都可以考虑加入随机性，但要控制好概率。比如，某个贪心策略下，是以概率1做某一动作，可以考虑将其改为以概率0.999做之前的操作，以剩余概率做其他操作。具体参数设置需调试。

越不随机越好

随机性往往是对问题内在规律的一种妥协。即没有找到其内在规律，又不知道如何是好，为了获得更好的多样性，逼不得已加入随机。因此，对给定问题的深入研究才是根本：分辨出哪些时候，某个动作就是客观上能严格保证最优的——这点至关重要，直接决定了算法性能。最好的算法一定是和问题结构紧密相连的，范范地套用某个启发式的框架不会有出色的性能。当然，如果不是追求性能至上，而是考虑到开发效率实现成本这些额外因素，则另当别论。

二者平衡最好

通常情况下，做好第一点，可以略微改善算法性能；做好第二点，有希望给算法带来质的提高。而二者调和后的平衡则会带来质的飞跃。

贪心是“自强不息”的精进，不放过任何改进算法的机会；多样性的随机是“厚德载物”的一分包容，给那些目前看似不那么好的解一些机会。调和好二者，不偏颇任何一方才能使算法有出色的性能。要把握这种平衡，非一朝一夕之功，只能在反复试验反思中去细细品味。

要结合具体问题而言，范范空谈无太大用。

启发式算法