模拟退火算法的参数选择
这是一篇笔记，是对于B站up主马少平的视频（第四篇 如何用随机方法求解组合优化问题（六））的学习与记录。
算法实现需要确定的参数：
- 初始温度 (t_0)；
- 温度 (t) 的衰减函数，即温度的下降方法；
- 算法的终止准则，终止温度 (t_f) 或者终止条件；
- 每个温度 (t) 下的马尔可夫链长度 (L_k)，即算法的内循环次数。
原则上初始温度越高越好，但是温度太高可能会导致求解效率下降。
初始温度 (t_0) 的选取(1)
基本原则：
- 足够高的初始温度，使系统可以等概率处于任何一个状态；
“足够高”这个标准与具体的问题有关。
按照模拟退火算法，遇到好解则百分之百接受，遇到差解则按概率接受，设概率为 (P_0)，则有：
]
由此可推出：
]
这里的 (P_0) 需要设置为一个比较大的数，比如0.95、0.98……需要根据具体的问题做一些试验。
通过设置一个较大的 (P_0)，就可以计算出足够大的初始温度 (t_0)。
其中 (Delta f(i,j)) 为状态 (j) 与状态 (i) 的指标函数差，可由随机产生的序列 (S) 计算
Delta f(i,j) &= maxlimits_{iin S}(f(i))-minlimits_{iin S}(f(i)) \
Delta f(i,j) &= frac{sumlimits_{i,jin S}|f(i)-f(j)|}{|S|^2} \
Delta f(i,j) &= frac{sumlimits_{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) 个状态中，被接受的个数为：
]
则有平均接受概率：
]
求解有：
{
overline{Delta f(i,j)}
}
{
lnleft(frac{m_2}{m_2P_0-m_1(1-P_0)}right)
}
]
这种选取方法与前一种方法类似，也是需要先确定一个较大的 (P_0)，然后计算出 (t_0)。
温度的下降方法
基本原则：温度下降足够缓慢。
“足够缓慢”这个标准与实际问题有关。
也不能太缓慢，否则会使计算效率下降。
等比例下降
(alpha) 是一个需要提前确定的常数，比如：0.99或0.95……
等值下降
]
在等值下降方法中，对于 (Delta t) 的选取非常重要。如果太小，对于一开始来说太慢；如果太大，对于后期来说难以收敛。
等比例下降较为常用。
每一温度下的停止准则
-
在每个温度下要有足够的交换次数
在模拟退火算法的内循环是在保持温度不变的情况下，反复地进行状态的交换。
理论上来说，在每一个温度下都应该有足够的交换次数，这样才能保证不同状态的指标函数值都能达到一个平稳的分布状态。
但是交换次数过多将影响计算效率，因此需要折中选择。
一般来说问题越复杂，则交换次数应该越多。
下面介绍一种常用的方法叫做固定长度方法，这里的“长度”是指“交换次数”。
-
固定长度方法
- 在每一个温度下，都使用相同的 (L_k)（即每一个温度下，都使用相同的交换次数）；
- (L_k) 的选取与具体的问题相关，一般与邻域的大小直接关联，通常选择为问题规模 (n) 的一个多项式函数。
算法的终止原则
- 基本原则：温度足够低；
- 零度法：温度小于某个给定值 (varepsilon>0) 时结束；
- 循环总控制法：温度下降次数达到给定次数 (K) 时结束；
- 无变化控制法：在相邻的 (n) 个温度中得到的指标函数值无变化时结束。
机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
