贪心算法和模拟退火算法

发表于 2023-03-24 更新于 2024-09-17 分类于 Algorithm Waline：

贪心算法是比较常见的一种算法，贪心的本质是选择每一阶段的局部最优，从而达到全局最优。而模拟退火算法比较常见于人工智能当中。

这两种算法之所以放在一起考虑是因为，模拟退火算法像是加强版的贪心算法。

如果一个问题的每一步的局部最优解无法得到全局最优解，我们常规前后端程序员的算法思维想到的是动态规划。

但是对于AI开发来讲，参数可能是上亿级别的，根本没有办法动态规划，这个时候就可以尝试用模拟退火算法以一定概率跳出这个局部，去整体中找到一个更优的答案，但是，其实这种算法也不像常规算法一样，会得到一个必然的结果。

本文把两种算法放在一起进行总结和比较，看看他们分别适用于什么情况，以及如何使用。

贪心算法

什么是贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。

什么时候使用贪心算法

说实话贪心算法并没有固定的套路。

所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？

不好意思，也没有！靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

贪心算法一般步骤：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

这个四步其实过于理论化了，我们平时在做贪心类的题目很难去按照这四步去思考，真是有点“鸡肋”。

做题的时候，只要想清楚局部最优是什么，如果推导出全局最优，其实就够了。

模拟退火算法

金属退火原理

金属退火是将金属加热到一定温度，保持足够时间，然后以适宜速度冷却(通常是缓慢冷却，有时是控制冷却)的一种金属热处理工艺。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

处在低温状态时，固体中分子具有的内能很低，在原本的位置上做小范围的振动。若是将固体加热到一定温度，分子内能将会增加，热运动加剧，分子排列的无序度增加。此时再将温度缓缓降低，在每个温度都达到平衡态（即准静态过程），分子具有的能量逐渐降低，最终回归到有序排列的状态，分子内能也跟着降到最低。

模拟退火算法机制

模拟退火算法(Simulated Annealing,SA)最早的思想是由N. Metropolis等人于1953年提出。1983年,S. Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

介绍模拟退火前，还是有必要先介绍爬山算法。

爬山算法

爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如上图所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

模拟退火核心思想

模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。

模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合一定的概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。将温度T当作控制参数，目标函数值f视为内能E，而固体在某温度T时的一个状态对应一个解
，然后算法试图随着控制参数T的降低，使目标函数f(内能E)也逐渐降低，直至趋于全局最小值（退火中低温时的最低能量状态），就像金属退火过程一样。

模拟退火的数学原理

从上面我们知道，会结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，那么具体的更新解的机制是什么呢？如果新解比当前解更优，则接受新解，否则基于Metropolis准则判断是否接受新解。接受概率为：

\begin{equation} P = \begin{cases} 1 & E_{t + 1} < E_t;\\ e^{-\frac{E_{t + 1} - E_t}{kT}} & E_{t + 1} \geq E_t; \end{cases} \end{equation}

如上公式，假设当前时刻搜索的解为 $x_t$ ，对应的系统能量(目标函数)为 $E_t$ ，对搜索点施加随机扰动，产生新解 $x_{t+1}$ ，相应地，系统能量为 $E_{t+1}$ ，那么系统对搜索点从到转变的接受概率就为上公式。

即，如果新的解所对应的能量更低了，那么接受概率就为1，也就是一定接受。如果新的解对应的能量高，那么就以 $e^{-\frac{E_{t + 1} - E_t}{kT}}$ 的概率去接受这个新解，即以这个概率去跳出这个局部最优解。

这个过程就是在随机挑选x，然后去找到一个对应E最低的x出来，这里的E更加低对应于我们具体的算法就是，更加接近于我们需要的目标

这里还有一个问题，就是我们随机挑选x的时候，如何选择x每次变化的大小。

这个问题其实就是退火这两个字的由来，即温度会逐渐降低，x变化的幅度也会越来越小。

模拟退火的流程

算法实质分两层循环，在任一温度水平下，随机扰动产生新解，并计算目标函数值的变化，决定是否被接受。由于算法初始温度比较高，这样，使E增大的新解在初始时也可能被接受，因而能跳出局部极小值，然后通过缓慢地降低温度，算法就最终可能收敛到全局最优解，具体流程为：

令 $T = T_0$ ,表示开始退火的初始温度，随机产生一个初始解 $x_0$ ,并计算对应的目标函数值 $E_0$ ;
令 $T = kT$ ,其中k取值0到1之间，为温度下降速率；
对当前解 $x_t$ 施加随机扰动，在其邻域内产生一个新解 $x_{t+1}$ ，并计算对应的目标函数值 $E_{t+1}$ ,计算
$\Delta E =E_{t+1} - E_t$
若 $\Delta E < 0$ 接受新解作为当前解，否则按照概率 $e^{-\frac{\Delta E}{kT}}$ 判断是否接受新解；
在温度T下，重复L次扰动和接受过程，即执行步骤3和4；
判断温度是否达到终止温度水平，若是则终止算法，否则返回步骤2.

其中有几个需要注意的点：

初始点的选取对算法结果有一定的影响，最好是多次运行对结果进行综合判断。
在算法运行初期，温度下降快，避免接受过多的差结果。当运行时间增加，温度下降减缓，以便于更快稳定结果。
当迭代次数增加到一定次数时，结果可能已经达到稳定，但是距离算法结束还有一段时间。在设计程序时应该加入适当的输出条件，满足输出条件即可结束程序。

模拟退火的应用

模拟退火算法在VLSI设计中的应用，利用模拟退火算法进行VLSI(Very Large Scale Integration,超大规模集成电路)的最优设计，是目前模拟退火算法最成功的应用实例之一。用模拟退火算法几乎可以很好地完成所有优化的VLSI设计工作。如全局布线、布板、布局和逻辑最小化等等。
模拟退火算法可用来进行图像恢复等工作，即把一幅被污染的图像重新恢复成清晰的原图，滤掉其中被畸变的部分。因此它在图像处理方面的应用前景是广阔的。
模拟退火算法在神经网计算机中的应用。模拟退火算法具有跳出局部最优陷阱的能力。在Boltzmann机中，即使系统落入了局部最优的陷阱，经过一段时间后，它还能再跳出来，系统最终将往全局最优值的方向收敛。
在力导向布局算法中，其实也暗含模拟退火的思想。一开始所有节点随机布局，然后节点的位置收到节点之间力的作用而产生变化。位置变化相当于x变化，变化后的位置，如果节点收到的合力降低了，相当于能量E降低，我们就接受新的解，然后随着合力的降低，其实也等同于T降低，那么对位置的影响就会变小，满满的合力降低到一定阈值之下，位置变化也不大了，我们就认为算法收敛出了结果。