如何用随机方法求解组合优化问题（六）
模拟退火算法的参数选择
这是一篇笔记，是对于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)\)有多种计算方式，可以是：
- 最大值与最小值的差；
- 两两做差取绝对值，再除以状态数的平方(实际上是求平均值)；
- 两个相邻的状态做差取绝对值，再除以状态数。
初始温度 \(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\) 个温度中得到的指标函数值无变化时结束。
关键词：
相关文章
精彩推送
