模拟退火算法参数分析
一 模拟退火算法介绍
模拟退火算法是一种寻找全局最优解的优化方法,核心思想就是以一定概率接收差解,并且这个概率会随着退火温度逐渐降低。一个比较形象的比喻是:一个锅底凹凸不平有很多坑的大锅,晃动这个锅使得一个小球使其达到全局最低点。一开始晃得比较厉害,小球的变化也就比较大,在趋于全局最低的时候慢慢减小晃锅的幅度,直到最后不晃锅,小球达到全局最低。
算法流程如下(最大值问题寻优):
特点:与爬山法比较,最明显的特点就是,更容易跳出局部最优解,找到全局最优解。
重点来啦,想要用好模拟退火算法,使算法收敛,了解其各个参数隐含的作用十分必要。
二 影响模拟退火算法性能的关键参数
对算法影响较大参数如下:
1退火起始、终止温度
2降温速度
3测度的计算
4状态转换
5接收差解的容忍度
6迭代次数
三 各关键参数对算法影响的讨论
1退火起始温度、终止温度
正如前面晃锅的比喻,这两个参数决定着晃锅的剧烈程度。起始温度越大,晃锅越剧烈,越容易接收差解,状态跳动随机性越大。终止温度决定着算法将要停止时,晃锅的幅度,要是算法稳定的收敛,终止温度要设置的比较低(比如,是起始温度的1000倍)。
2降温速度
这个参数一般设置为0.99或0.98,越小降温越快,如果设置过小,就如同淬火一下,算法来不及充分寻优。
3测度计算
测度没什么好说的,就是要准。测度的计算具体问题具体分析。
4状态转换
状态转换很重要,状态的搜索、跳转策略直接影响着算法的性能。比如根据具体的问题去分析,状态有没有边界,如果有边界的话,在状态跳转时要用边界限制。状态转换是从当前状态至下一状态,每一次跳动都是随机的,但不是完全随机的,是在一定范围内进行的跳动。那么,两个问题来了,
<1>范围怎么确定?
<2>范围确定后,状态怎么转换?
回顾一下,退火的跳动幅度是随着温度的下降逐渐降低的,因此,跳动范围须与温度建立关系,随温度下降,跳动范围减少。
这个减少可以是线性的,也可以是非线性的。
范围确定了,下一次状态的跳转可由高斯随机数生成,通过控制高斯方差就可以控制跳动范围。
状态转换完全随机会怎样?
完全随机意味着 状态开始时乱跳,温度降下来后也乱跳,这就就违背了退火算法思想。
5接受差解的容忍度
接受差解的容忍度由s1根据测度函数值的水平进行调节。容忍度既不能太大也不能太小。
容忍度太大了,算法啥解都接受,这个算就废了。容忍度太小了,算法不会接受差解,这样做的后果就是优化后的状态一定是局部最优的,也违背了退火算法的思想。
6迭代次数
迭代次数控制着算法寻优的充分程度,需根据具体问题调节。
如理解有偏差,还请指教。