算法简介
模拟退火算法(Simulated annealing algorithm,SAA)的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减小,粒子的慢慢趋于有序,最终,当固体处于常温时,内能达到最小,此时,粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。
模拟退火算法从某一高温出发,在高温状态下计算初始解,然后以预设的邻域函数产生一个扰动量,从而得到新的状态,即模拟粒子的无序运动,比较新旧状态下的能量,即目标函数的解。如果新状态的能量小于旧状态,则状态发生转化;如果新状态的能量大于旧状态,则以一定的概率准则发生转化。当状态稳定后,便可以看作达到了当前状态的最优解,便可以开始降温,在下一个温度继续迭代,最终达到低温的稳定状态,便得到了模拟退火算法产生的结果。
算法过程
状态空间与邻域函数
状态空间也称为搜索空间,它由经过编码的可行解的集合所组成。而邻域函数应尽可能满足产生的候选解遍布全部状态空间。其通常由产生候选解的方式和候选解产生的概率分布组成。候选解一般按照某一概率密度函数对解空间进行随机采样获得,而概率分布可以为均匀分布、正态分布、指数分布等。
状态概率分布(Metropolis准则)
状态转移概率是指从一个状态转换成另一个状态的概率,模拟退火算法中一般采用Metropolis准则,具体如下:
$$f(x)=\left\lbrace\begin{array}{cll}
1 & , & E(x_{new}) < E(x_{old}) \\
exp(-\frac{E(x_{new})-E(x_{old})}{T}) & , & E(x_{new}) \ge E(x_{old})
\end{array}\right.$$
其与当前温度参数T有关,随温度的下降而减小。
冷却进度表
冷却进度表是指从某一高温状态T向低温状态冷却时的降温函数,设时刻的温度为T(t),则经典模拟退火算法的降温方式为:
$$T(t)=\frac{T_{0}}{lg(1+t)}$$
而快速模拟退火算法的降温方式为:
$$T(t)=\frac{T_{0}}{1+t}$$
其他方法不再赘述。
初始温度
一般来说,初始温度越大,获得高质量解的几率越大,但是花费的时间也会随之增加,因此,初温的确定应该同时考虑计算效率与优化质量,常用的方法包括:
1.均匀抽样一组状态,以各状态目标值的方差为初温。
2.随机产生一组状态,确定两两状态间的最大目标值差,然后根据差值,利用一定的函数确定初温,如: $T_{0}=-\frac{\Delta_{max}}{Pr}$ ,其中Pr为初始接受概率。
3.根据经验公式给出。
循环终止准则
内循环(求解循环)终止准则:
- 检验目标函数的均值是否稳定
- 连续若干步的目标值变化较小
- 按一定的步数进行抽样
外循环(降温循环)终止准则:
- 设置终止温度
- 设置外循环迭代次数
- 算法搜索到的最优值连续若干步保持不变
- 检验系统熵是否稳定
Python实现
实例函数: $f(x)=(x^{2}-5x)sin(x^2)$
1 | import numpy as np |
Reference
https://www.imooc.com/article/30160
https://baike.baidu.com/item/模拟退火算法/355508?fr=aladdin
https://blog.csdn.net/google19890102/article/details/45395257
https://www.cnblogs.com/xxhbdk/p/9192750.html