模拟退火算法的参数选择

这是一篇笔记，是对于B站up主马少平的视频（第四篇 如何用随机方法求解组合优化问题（六））的学习与记录。

算法实现需要确定的参数：

原则上初始温度越高越好，但是温度太高可能会导致求解效率下降。


【资料图】

初始温度 \(t_0\) 的选取(1)

基本原则：

“足够高”这个标准与具体的问题有关。

按照模拟退火算法，遇到好解则百分之百接受，遇到差解则按概率接受，设概率为 \(P_0\)，则有：

\[e^{-\frac{\Delta f(i,j)}{t_0}} = P_0 \approx 1\]

由此可推出：

\[t_0=\frac{\Delta f(i,j)}{\ln(P_0^{-1})}\]

这里的 \(P_0\) 需要设置为一个比较大的数，比如0.95、0.98......需要根据具体的问题做一些试验。

通过设置一个较大的 \(P_0\)，就可以计算出足够大的初始温度 \(t_0\)。

其中 \(\Delta f(i,j)\) 为状态 \(j\) 与状态 \(i\) 的指标函数差，可由随机产生的序列 \(S\) 计算

\[\begin{align*}\Delta f(i,j) &= \max\limits_{i\in S}(f(i))-\min\limits_{i\in S}(f(i)) \\\Delta f(i,j) &= \frac{\sum\limits_{i,j\in S}|f(i)-f(j)|}{|S|^2} \\\Delta f(i,j) &= \frac{\sum\limits_{i=0}^{|S|-1}|f(S(i))-f(S(i+1))|}{|S|}\end{align*}\]

\(\Delta f(i,j)\)有多种计算方式，可以是：

  1. 最大值与最小值的差；
  2. 两两做差取绝对值，再除以状态数的平方(实际上是求平均值)；
  3. 两个相邻的状态做差取绝对值，再除以状态数。

初始温度 \(t_0\) 的选取(2)

假设在 \(t_0\) 下随机地生成一个状态序列，分别用 \(m_1\) 和 \(m_2\) 表示指标函数下降的状态数和指标函数上升的状态数，\(\overline{\Delta f(i,j)}\) 表示指标函数增加的平均值。则 \(m_2\) 个状态中，被接受的个数为：

\[m_2e^{-\frac{\overline{\Delta f(i,j)}}{t_0}}\]

则有平均接受概率：

\[P_0 = \frac{m_1 + m_2 e^{-\frac{\overline{\Delta f(i,j)}}{t_0}}}{m_1 + m_2}\]

求解有：

\[t_0 = \frac{\overline{\Delta f(i,j)}}{\ln\left(\frac{m_2}{m_2P_0-m_1(1-P_0)}\right)}\]

这种选取方法与前一种方法类似，也是需要先确定一个较大的 \(P_0\)，然后计算出 \(t_0\)。

温度的下降方法

基本原则：温度下降足够缓慢。

  • “足够缓慢”这个标准与实际问题有关。

  • 也不能太缓慢，否则会使计算效率下降。

等比例下降

\[t_{k+1} = \alpha t_k \quad\quad 0 < \alpha < 1\]

\(\alpha\) 是一个需要提前确定的常数，比如：0.99或0.95......

等值下降

\[t_{k+1} = t_k - \Delta t\]

在等值下降方法中，对于 \(\Delta t\) 的选取非常重要。如果太小，对于一开始来说太慢；如果太大，对于后期来说难以收敛。

等比例下降较为常用。

每一温度下的停止准则

算法的终止原则

推荐内容