如何用随机方法求解组合优化问题(六)
模拟退火算法的参数选择
这是一篇笔记,是对于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)\)有多种计算方式,可以是:
- 最大值与最小值的差;
- 两两做差取绝对值,再除以状态数的平方(实际上是求平均值);
- 两个相邻的状态做差取绝对值,再除以状态数。
初始温度 \(t_0\) 的选取(2)
假设在 \(t_0\) 下随机地生成一个状态序列,分别用 \(m_1\) 和 \(m_2\) 表示指标函数下降的状态数和指标函数上升的状态数,\(\overline{\Delta f(i,j)}\) 表示指标函数增加的平均值。则 \(m_2\) 个状态中,被接受的个数为:
则有平均接受概率:
求解有:
这种选取方法与前一种方法类似,也是需要先确定一个较大的 \(P_0\),然后计算出 \(t_0\)。
温度的下降方法
基本原则:温度下降足够缓慢。
“足够缓慢”这个标准与实际问题有关。
也不能太缓慢,否则会使计算效率下降。
等比例下降
\(\alpha\) 是一个需要提前确定的常数,比如:0.99或0.95......
等值下降
在等值下降方法中,对于 \(\Delta t\) 的选取非常重要。如果太小,对于一开始来说太慢;如果太大,对于后期来说难以收敛。
等比例下降较为常用。
每一温度下的停止准则
-
在每个温度下要有足够的交换次数
在模拟退火算法的内循环是在保持温度不变的情况下,反复地进行状态的交换。
理论上来说,在每一个温度下都应该有足够的交换次数,这样才能保证不同状态的指标函数值都能达到一个平稳的分布状态。
但是交换次数过多将影响计算效率,因此需要折中选择。
一般来说问题越复杂,则交换次数应该越多。
下面介绍一种常用的方法叫做固定长度方法,这里的“长度”是指“交换次数”。
-
固定长度方法
- 在每一个温度下,都使用相同的 \(L_k\)(即每一个温度下,都使用相同的交换次数);
- \(L_k\) 的选取与具体的问题相关,一般与邻域的大小直接关联,通常选择为问题规模 \(n\) 的一个多项式函数。
算法的终止原则
- 基本原则:温度足够低;
- 零度法:温度小于某个给定值 \(\varepsilon>0\) 时结束;
- 循环总控制法:温度下降次数达到给定次数 \(K\) 时结束;
- 无变化控制法:在相邻的 \(n\) 个温度中得到的指标函数值无变化时结束。
热门相关:冉冉心动 大妆 拒嫁豪门,前妻太抢手 后福 后福