如何用随机方法求解组合优化问题（六）-Toy模板网

这篇具有很好参考价值的文章主要介绍了如何用随机方法求解组合优化问题（六）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

模拟退火算法的参数选择

这是一篇笔记，是对于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\) 的选取非常重要。如果太小，对于一开始来说太慢；如果太大，对于后期来说难以收敛。

等比例下降较为常用。

每一温度下的停止准则

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

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

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

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

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

下面介绍一种常用的方法叫做固定长度方法，这里的“长度”是指“交换次数”。
固定长度方法文章来源地址https://www.toymoban.com/news/detail-655783.html
- 在每一个温度下，都使用相同的 \(L_k\)（即每一个温度下，都使用相同的交换次数）；
- \(L_k\) 的选取与具体的问题相关，一般与邻域的大小直接关联，通常选择为问题规模 \(n\) 的一个多项式函数。