模拟退火算法参数分析

时间:2024-05-20 14:10:14

模拟退火算法参数分析

一  模拟退火算法介绍


模拟退火算法是一种寻找全局最优解的优化方法,核心思想就是以一定概率接收差解,并且这个概率会随着退火温度逐渐降低。一个比较形象的比喻是:一个锅底凹凸不平有很多坑的大锅,晃动这个锅使得一个小球使其达到全局最低点。一开始晃得比较厉害,小球的变化也就比较大,在趋于全局最低的时候慢慢减小晃锅的幅度,直到最后不晃锅,小球达到全局最低。

算法流程如下(最大值问题寻优):


     模拟退火算法参数分析

   特点:与爬山法比较,最明显的特点就是,更容易跳出局部最优解,找到全局最优解。

   重点来啦,想要用好模拟退火算法,使算法收敛,了解其各个参数隐含的作用十分必要。



二  影响模拟退火算法性能的关键参数


对算法影响较大参数如下:

1退火起始、终止温度

2降温速度

3测度的计算

4状态转换

5接收差解的容忍度

6迭代次数


 

三 各关键参数对算法影响的讨论

1退火起始温度、终止温度

  

正如前面晃锅的比喻,这两个参数决定着晃锅的剧烈程度。起始温度越大,晃锅越剧烈,越容易接收差解,状态跳动随机性越大。终止温度决定着算法将要停止时,晃锅的幅度,要是算法稳定的收敛,终止温度要设置的比较低(比如,是起始温度的1000倍)。

2降温速度

 

 这个参数一般设置为0.99或0.98,越小降温越快,如果设置过小,就如同淬火一下,算法来不及充分寻优。


3测度计算

  

测度没什么好说的,就是要准。测度的计算具体问题具体分析。


4状态转换


  状态转换很重要,状态的搜索、跳转策略直接影响着算法的性能。比如根据具体的问题去分析,状态有没有边界,如果有边界的话,在状态跳转时要用边界限制。状态转换是从当前状态至下一状态,每一次跳动都是随机的,但不是完全随机的,是在一定范围内进行的跳动。那么,两个问题来了,

<1>范围怎么确定?

<2>范围确定后,状态怎么转换?

回顾一下,退火的跳动幅度是随着温度的下降逐渐降低的,因此,跳动范围须与温度建立关系,随温度下降,跳动范围减少。

这个减少可以是线性的,也可以是非线性的。

范围确定了,下一次状态的跳转可由高斯随机数生成,通过控制高斯方差就可以控制跳动范围。

状态转换完全随机会怎样?

完全随机意味着 状态开始时乱跳,温度降下来后也乱跳,这就就违背了退火算法思想。

 

5接受差解的容忍度


接受差解的容忍度由s1根据测度函数值的水平进行调节。容忍度既不能太大也不能太小。

容忍度太大了,算法啥解都接受,这个算就废了。容忍度太小了,算法不会接受差解,这样做的后果就是优化后的状态一定是局部最优的,也违背了退火算法的思想。

 

6迭代次数


迭代次数控制着算法寻优的充分程度,需根据具体问题调节。

如理解有偏差,还请指教。