模拟退火（Simulated Annealing, SA）
模拟退火源于固体退火过程（加热再缓慢冷却以降低缺陷）。在组合/连续优化中，Kirkpatrick 等将其用于以可控概率接受变差的邻域移动，从而跳出局部最优。属于单点、基于邻域的元启发式，见 元启发式总览。
接受准则与降温的作用
在固定 下，用 Metropolis 思想（记 ，最小化）：
- ：总接受。
- ：以概率 接受，从而仍有机会朝劣向走一步、跨出谷口。
温度对探索程度的影响可概括为：
- 大： 小，接受劣解的意愿强，搜索偏全局。
- 小：几乎只在不升高目标时移动，偏局部抛光。
降温：按时间表降低 （如 、，或分档表、分段常数）。注意：
- 降得过快：过早近似贪心，易被困。
- 过慢：同温步数大，总计算量高。
- 常在同温下做若干内层步，到「充分搅拌」或步数上界再降温。
邻域与解编码： 的邻域 与具体实例绑定；要足以在可行解之间连通、且从 中抽样或枚举候选时， 的求值在工程上可承受。
主循环（最小化示意）
以目标函数 在邻域内搜索（最小化；若最大化，可对 讨论，或把「劣」改为「不增目标真值侧」的对应叙述）。
▶ 模拟退火主循环（单解、邻域搜索）
1. 初始化
生成初始解 s（随机或经简单启发式），记当前最优解 s⋆ ← s。设初温 T ← T₀>0，并选定降温表与每温度下的内层步数/迭代次数。
2. 同温内迭代
在温度 T 下，重复若干内层步，直到内层步数上限或同温收敛判据；每一步：
- 由邻域算子自 s 生成候选解 s′；
- 计算 Δ = f(s′) − f(s)；
- 若 Δ ≤ 0，令 s ← s′；
- 若 Δ>0，以概率 min(1, exp(−Δ/T)) 令 s ← s′，否则保持 s；
- 若 f(s)<f(s⋆)（严格改进），更新 s⋆ ← s。
3. 降温
按预设计划更新 T（如 T ← αT，标量 α∈(0,1)），或按时间表降温。
4. 终止
若 T 低于阈值、或达到总迭代/时间/无改进步数，则停；输出 s⋆。