Simulated Annealing
固体退火的过程：
- 溶解：温度上升，粒子脱离平衡，最终从有序变为完全无序。
- 退火：温度下降，粒子逐渐停留在不同状态，从无序向有序发展。温度很低时，以一定结构排列。
1. Metropolis准则
（温度一定，）从状态 \(i\) 转移到状态 \(j\) 的准则：
- 若 \(E(j) \le E(i)\) ，转移。
- 若 \(E(j) > E(i)\) ，则转移的概率： \(P(i \rightarrow j) = \exp({E(i) - E(j) \over KT}) \in (0, 1)\) 。
在给定温度下，进行足够多次状态转移后，系统将达到热平衡。
2. 算法框架
达到最小能量状态的三个条件：
- 初始温度足够高；
- 每个温度下进行充分的状态转移；
- 温度 T 的下降足够缓慢。
- 随机选择一个解 \(i\) ；序号 \(k = 0\) ，初始温度 \(t_0 = T_{\max}\) ；
- 判断是否满足「结束条件」；若满足，结束；若不满足：
- 如果在该温度下达到了「平衡条件」，降温到 \(t_{k+1}\) ；
- 如果没到平衡条件：
- 随机选择 \(j \in N(i)\) （邻域）；
- 如果 \(f(j) < f(i)\) ，则转移到 \(j\) ；（ \(\Delta f = f(j) - f(i)\) ）
- 否则，按概率 \(P(i \rightarrow j) = \exp({f(i) - f(j) \over t}) = \exp({-\Delta f \over t}) \in (0, 1)\) 转移；
- 回到判断「平衡条件」的一步；
3. 参数选取
3.1 起始温度
一个合适的初始温度，应保证平稳分布中每一个状态的概率基本相等。
3.2 温度下降
等比例下降；
其它衰减函数；
3.3 平衡条件
每一温度下，何时认为已到达平衡而停止转移？
- 根据温度固定长度法；
- 某温度下转移次数达到阈值后才停止；
3.4 结束条件
- 阈值法；
- 固定降温次数法；
- 无变化控制法：指标函数值已无变化；
Last update:
June 4, 2021
Authors: