模拟退火算法（Simulated Annealing，SA)是模拟物理退火求解组合问题的算法，核心是要理解Metropolis 采样算法，具有算法简单、适用范围广、可靠性高等特点。
图片来自网络
1 算法理论
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。
加温时，固体内部粒子随温升变为无序态，内能增大；
降温时，粒子逐渐趋近有序，每个温度上都达到平衡态；
常温时，粒子达到基态，内能减为最小。
图片来自网络
算法与物理退火比较如下：
| 物理退火 | 模拟算法 |
| 粒子状态 | 解 |
| 能量最低态 | 最优解 |
| 溶解过程 | 设定初温 |
| 等温过程 | Metropolis采样过程 |
| 冷却 | 控制参数的下降 |
| 能量 | 目标函数 |
Metropolis采样算法
Metropolis 采样算法是一种有效的采样法，解决的问题是从一个复杂的目标分布获取近似的样本。
系统从一个状态E1转移到另一个状态E2时，其概率为：
P=exp（-（E2-E1)/T)
如果E2<E1，系统接收此状态，否则以概率P丢弃。
2 算法流程
初始化，初始温度T、初始解状态X、每个T值的迭代次数L、K小于1并接近于1。
3 关键参数
状态产生函数
一般由产生候选解的方式和概率分布2部分组成，候选解产生方式由问题的性质决定，通常在当前状态的领域结构内以一定概率产生。
初温
初温越大，获取高质量解几率越大，P接近1，但计算时间增加。可均匀抽样一组状态，以各状态目标值的方差为初温。
退温函数
即温度更新函数，T=T*K,K=（0 1），且非常接近1。
Markov链长度L的选取
一般取100-1000。
算法停止准则
设置终止温度、设置迭代次数、最优解连续保持不变
4 仿真实例
见下篇。
