如何用随机方法求解组合优化问题(六)

模拟退火算法的参数选择

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

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

  • 初始温度 \(t_0\)
  • 温度 \(t\) 的衰减函数,即温度的下降方法;
  • 算法的终止准则,终止温度 \(t_f\) 或者终止条件;
  • 每个温度 \(t\) 下的马尔可夫链长度 \(L_k\),即算法的内循环次数。

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

初始温度 \(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\) 的选取非常重要。如果太小,对于一开始来说太慢;如果太大,对于后期来说难以收敛。

等比例下降较为常用。

每一温度下的停止准则

  • 在每个温度下要有足够的交换次数

    在模拟退火算法的内循环是在保持温度不变的情况下,反复地进行状态的交换。

    理论上来说,在每一个温度下都应该有足够的交换次数,这样才能保证不同状态的指标函数值都能达到一个平稳的分布状态。

    但是交换次数过多将影响计算效率,因此需要折中选择。

    一般来说问题越复杂,则交换次数应该越多。

    下面介绍一种常用的方法叫做固定长度方法,这里的“长度”是指“交换次数”。

  • 固定长度方法

    • 在每一个温度下,都使用相同的 \(L_k\)(即每一个温度下,都使用相同的交换次数);
    • \(L_k\) 的选取与具体的问题相关,一般与邻域的大小直接关联,通常选择为问题规模 \(n\) 的一个多项式函数。

算法的终止原则

  • 基本原则:温度足够低;
  • 零度法:温度小于某个给定值 \(\varepsilon>0\) 时结束;
  • 循环总控制法:温度下降次数达到给定次数 \(K\) 时结束;
  • 无变化控制法:在相邻的 \(n\) 个温度中得到的指标函数值无变化时结束。

热门相关:冉冉心动   大妆   拒嫁豪门,前妻太抢手   后福   后福