模拟退火

引入

爬山算法

爬山算法, 即贪心算法, 在当前解得临近空间中选择一个最优解作为新的当前解. 因此, 最后得到的解是一个局部最优解, 往往不是全局最优的

模拟退火算法

模拟退火算法可以有效地解决陷入局部最优解的问题, 从而找到一个全局最优解. 模拟退火算法也是一种贪心算法, 只不过对爬山算法进行了改造, 在其基础上增加了随机因素, 即以一定的概率接受一个比当前解更差的解, 通过这个随机因素, 使得算法有可能跳出这个局部最优解.

算法

Metropoils算法

此算法是模拟退火算法的核心, 前面说道以一定的概率接受一个更差的解, 从而可能跳出局部最优, 这个概率的计算就是靠此算法.

Metropoils算法定义了一个转移概率$P$, 由状态$i$转移到状态$j$时, 接受的概率为:

$P(i,j)=\begin{cases}1, \quad f(j)\ge f(i) \\ \exp(\frac{f(i)-f(j)}{t}), \quad \text{otherwise} \end{cases}$

即当新的解表现比之前好时, 一定接受新解. 当表现不如之前时, 根据表现的差距, 以及一个退火温度计算得到一个概率, 以这个概率接受这个新解.

温度t

现实中, 冶炼固体退火的时候, 温度是要徐徐下降, 使得温度在每个阶段达到平衡, 最后趋于稳定. 模拟这种情况, 模拟退火算法中, 温度$t$需要满足以下几点:

• 初始温度较高, 保证初始阶段可以搜索到全局最优点, 如果太小, 就无法跳出局部最优解

• 温度是要一直衰减的. 温度的衰减也是有各种策略的, 一般使用线性的衰减函数, 即$t:=at$, 其中$a$一般取小于1且又很接近与1的数.

停止条件

• 温度$t$降低到某个阈值

• 连续多个解对应的表现没有变化

关键问题

模拟退火算法更像是一种思想, 通过灵活的设计, 可以应用在很多情景中. 设计时需要考虑一下几点:

• 新解产生的策略: 根据当前解的表现, 生成新解, 如使用后验概率

• 退火策略: 温度随着迭代的进行逐渐降低的策略

• 接受策略: 往往使用Metropoils算法, 也可以根据实际的情况, 进行调整

例子

甚至在TSP问题都可以使用, 可以根据上面的几个点, 对应地查看在该例子中是如何使用模拟退火算法的, 理解算法细节.

参考资料

模拟退火