模拟退火算法
物理固体退火过程(可不了解)：
什么是退火：指对物体（指的是固体）加温至熔化，再徐徐冷却，使之凝固成规则晶体的热力学过程，简而言之，是对物体加温后再冷却的一个物理过程。
可见，物理退火过程由以下三部分组成：
（1）加温过程： 一般一个物体不是一个有规则的晶体（下图左图），于是加热，当温度足够高时，固体的规则性被彻底破坏，固体熔解为液体（下图中图），从而消除系统原先可能存在的非均匀状态，使随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程相联系，系统能量也随温度的升高而增大。
（2）等温过程。当某一温度固定后，要使系统达到热平衡态，才能进行降温，这就是“徐徐”的意思。如果降温降低很快，会出现猝火效应（对应后面讲解的局部最小值），即猝火效应是指固体只能冷凝为非均匀的亚稳态，系统能量也不会达到最小值。
由物理学知识可知，对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能到达最小值时，系统达到热平衡态。此现象保证系统在每一温度下能到达平衡态的过程。这个跟熵很类似。（熵总是往这增大的方向进行）
等温下热平衡过程可用Metropolis准则（即以概率接受新状态）进行模拟。
Metropolis准则：
假设当前状态为 $x(n)$ , 系统受到一定扰动，状态变为 $x(n+1)$,相应的系统能量由 $E(n)$ 变为 $E(n+1)$ ,定义状态 $x(n)$ 变为 $x(n+1)$ 的接受概率为 $p$ :
$$p= \begin{cases}
1 &, E(n+1) < E(n)
e^{\left(-\frac{E(n+1)-E(n)}{T}\right)} &,E(n+1) \geq E(n)
\end{cases}$$
当状态转移之后，如果能量减小了（即 $E(n+1) < E(n)$ ），那么这种转移就被接受了（以概率1发生）
当状态转移之后，如果能量增大了(即 $E(n+1) \geq E(n)$ ），那么这种转移按照概率 $p= e^{\left(-\frac{E(n+1)-E(n)}{T}\right)}$ 去接受，具体操作： 首先在区间[0,1]产生一个均匀分布的随机数$\xi$，如果 $\xi < p（此时p= e^{\left(-\frac{E(n+1)-E(n)}{T}\right)} ） $,则这种转移被接受，否则被拒绝。
（3）冷却过程，液体粒子的热运动逐渐减弱，随着温度的徐徐降低（即系统能量逐渐下降），粒子运动逐渐有序，当温度减到足够小时，液体凝固成按一定形状排列，高密度，低能量的有规则晶体（下图右图）。
对照表
| 模拟退火 | 物理退火 |
|---|---|
| 解 | 粒子状态 |
| 最优解 | 能量最低态 |
| 设定初始温度 | 熔解过程 |
| Metropolis采样过程 | 等温过程 |
| 控制参数的下降 | 冷却 |
| 目标函数 | 能量 |
模拟退火算法基本步骤与基本思想
基本思想： 其基本思想是模拟金属退火过程。
基本步骤（求 $min \ f(x)$）：
(1)明确目的，第一步是确定问题域，包括变量 $x$的个数和维度，以及目标函数 $f( \cdot )$的计算方式
(2)初始化，随机产生一个初始解 $x0$，令 $x{best } = x_0 $，并计算目标函数值$f(x0)$，同时设置初始温度$T(0)$,终止温度$T{final}$ 和温度的下降公式及相应的参数。
(3) Do while $ T(0) > T_{final} $ # 外循环
① for j = 1~ k #内循环 ， k为内循环的最大迭代次数
② 运行Metropolis算法，以一定规则在当前状态 $x{best}$ 附近产生新的状态 $x{new}$，计算 $f(x{best})$ 与 $f(x{new})$ ，并计算目标函数值得增量 $\Delta f = f(x{best}) - f(x{new})$ 。
③
- 如果$\Delta f <0$ ,则 $x{best} := x{new}$ 。
- 如果 $\Delta f > 0$ ,则计算$p = e^{ - \frac{\Delta f}{T}}$,并从0~1之间产生一个随机数$\xi$，
- 如果 $\xi < p$,则$x{best} := x{new}$，否则,$x{best} := x{best}$。
- 如果$\Delta f <0$ ,则 $x{best} := x{new}$ 。
④ End for
(4) **按温度的下降公式更新温度$T(0)$。 **
(5) End Do
(6) 输出当前最优点,计算结束。
模拟退火算法基本步骤中的关键要素
以一定规则在当前状态 $x{best}$附近产生新的状态 $x{new}$(很重要)
一般是按照某一概率密度分别函数（均匀分布、正太分布、指数分布）进行随机采样得到新的状态，如果是函数优化可以采取牛顿迭代的方法产生新的状态。
温度的下降公式 （也称冷却进度表）
指数式下降（简单式）: $T(0) := \lambda T(0)$ , 其中$\lambda<1$ ,一般取 0.8~0.99之间.
经典式（常用式）： $T(0):= \dfrac{T_0}{lg(1+t)}$
快速降温： $T(0) := \dfrac{T_0}{1+t}$
初始温度$T_0$的设置
初始温度足够高，温度下降的足够慢，能使系统达到高质量的解，但耗费时间也非常大。
应该适当权衡初始温度和温度的下降。所有模拟退火算法的解与温度有很大的关系。
内循环终止准则（常用）
（1）目标函数的值是否趋于稳定
（2） 是否达到最大迭代次数
外循环终止准则（常用）
（1）是否到达最低温度（常用）。
（2）设置外循环的最大迭代次数。
（3）外循环搜索到的最有值对应的目标函数值连续若干步保持不变。