简单说说模拟退火

目录

模拟退火算法

模拟退火(simulated annualing)SA算法。

是一个随机化算法,在正常算法题中可能体现较少,在人工智能等方面应用比较广泛。

这个随机化算法非常看人品,以及参数的正确选择。

简单介绍

回顾爬山算法,在单峰函数中不断取更高值来获得最高值。

而模拟退火则是在温度递降过程中,随机跳跃范围不断减少,遇到更好解替代目前解。遇到不好的解也有一定概率P(X)去接受这个解。

\[ P(X)=\left\{ \begin{aligned} 1, X比当前解更好 \\ e^{ -\frac {dE} {kT}},X比当前解劣 \end{aligned} \right.\]

大致工作如下伪代码。

//求f(x)最大值
T = t //初始一个温度T,需要调参决定和优化
x = a //初始化一个x,函数坐标
while(T > eps)//eps为一个很小的退火结束温度,调参决定和优化
begin
	dx = rand(0, 1) * T // 随机取T之内一个偏移值
	dE = f(x) - f(x + dx) // 能量变化
	if (exp(-dE/T) > rand(0, 1)) // 如果dE大于0,偏移后变劣看概率;如果dE小于0,一定成立
		x = x + dx
	T = T * c // c为降温系数,0.95~0.999999,需要调参
end

工作流程引用经典gif
简单说说模拟退火

调参

在搜索范围大,而答案点非常小的情况下,往往得到的值并不尽人意。

而优秀参数的选取能大大提高最优解接近率。

这个参数调节非常讲究,并且需要运气。。。

所以说这种算法经常被人说玄妙,就是因为你参数调来调去很多时候你就不知道这程序怎么这么准确或者这么不准确。

优化技巧

  1. 在一个程序中,可以多做几次模拟退火。

  2. 模拟退火得到近似解之后,在小温度范围内做爬山算法微调。

  3. 分区域模拟退火,取最优解

  4. 卡时间。。。

    巧用clock()函数

上一篇:Kaggle_Data Bar Charts and Heatmaps


下一篇:CV学习笔记(二十六):NMS非极大值抑制算法