模拟退火(SA)是拿来找给定函数的近似全局最优的。一般当搜索空间是离散的时,经常使用它。模拟退火算法最初是受到金属加工时退火过程的启发来的。在真正的金属冶炼过程中,通过给金属降温,金属的形态就会固定。而在模拟退火中,我们会设置 “温度” 这个变量,来模拟这个过程。 初始时,将其设置为高,然后在算法运行时让它慢慢“冷却”。当这个变量“温度”很高时,算法会更允许接受比当前解更差的解(即高温时,金属可以改变的力度和形状可以更大)。这能够让算法不局限在之前发现的任何local optimum上。随着温度的降低,接受更差解的机会就越小,因此允许算法逐渐集中在搜索空间的一个区域,来找到近最优解。这个渐进的“冷却”过程能够让模拟退火算法在处理包含大量局部最优解的大问题时非常有效地找到接近的最优解。
Acceptance Function:
决定一个solution是否被接受的步骤如下:
- 看下一个解是否优于当前解,如果是,则无条件接受
- 如果不是,根据以下几个方面考虑要不要接受:
- 下一个解有多差?
- 当前系统的 “温度” 有多高?
数学表达式如下:
$$exp(\frac{solutionEnergy - neighborEnergy}{Temperature})$$
即:系统能量变得越小,温度越高,越会接受这个解。是否接受解根据一个随机的概率来的
算法描述如下:
- 设置温度变量初始值,随机初始化一个解
- 循环直到停止条件达到:一般为系统足够”冷却” 或 最优的解已经找到
- 通过较小地改变当前解来确定下一个解
- 决定是否跳去下一个解(用上面的Acception function)
- 降低温度,继续循环
Pseudo Code
1 | int temperature = m; |
Reference:
http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
http://mathworld.wolfram.com/SimulatedAnnealing.html