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

手机

国产厂商崛起！三星为让SSD等存储涨价出大招：暂停第六代V-NAND程报价

乌克兰延长战时状态至11月！中方使馆紧急提醒！

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

2023-08-18 18:53:01 来源：博客园

模拟退火算法的参数选择

这是一篇笔记，是对于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\) 个温度中得到的指标函数值无变化时结束。

关键词：