模拟退火算法

定义

模拟退火(Simulated Annealing)是一种通用的随机化全局优化算法,由 Kirkpatrick 等人于 1983 年提出,灵感来自固体退火过程:缓慢降温使系统趋于能量最低状态。

原理

算法从初始解出发,每步随机扰动产生邻域新解:若更优则接受;若更差,则以 exp(-Δ/T) 的概率接受,其中 Δ 为目标函数恶化量,T 为当前温度。温度按预设的退火计划逐渐降低,前期高温允许大幅探索、跳出局部最优,后期低温收敛于精细搜索。理论上降温足够慢时能以概率 1 收敛到全局最优,但实践中采用折中的降温速率。

应用

旅行商问题等组合优化、VLSI 芯片布图布线、任务调度、神经网络超参数搜索、蛋白质结构预测等难以精确求解的问题。

优缺点

实现简单、对目标函数无梯度要求;缺点是结果依赖参数调节,收敛速度与解质量之间需要权衡。