模拟退火 模擬退火英語Simulated annealing缩写作SA是一種逼近给定函数全局最优的通用概率演算法具体来说它是一种元启发算法常用來在一定時間內尋找在一個很大搜尋空間中的近似全局最優解在有大量局部最优解时模拟退火算法可以找到全局最优解 模拟退火常用于搜索空间离散的情形如旅行推销员问题布尔可满足性问题蛋白质结构预测作业车间调度问题等对于在固定时间内找到近似全局最优优先于找到精确局部最优的问题模拟退火算法可能优于梯度下降法或分支定界等精确方法 模拟退火算法解决的问题包含多元目标函数与若干约束实践中约束可作为目标函数的一部分进行惩罚 Pincus Khachaturyan et al  KirkpatrickGelatt及Vecchi Cerny 等人先后提出过类似技术现在的模擬退火算法在年为S Kirkpatrick C D Gelatt和M P Vecchi解决旅行推销员问题所發明V Černý也在年獨立發明此演算法 模拟退火算法中的慢冷却是指在探索解空间的过程中接受较差解的概率会缓慢下降接受较差解可以更广泛地搜索全局最优解总的来说模拟退火算法的工作原理如下温度从初始值逐渐降低到每个时间步长内算法随机选择一个与当前解接近的解并根据与温度相关的概率选择更优的搜索过程中这概率会趋近于 可通过求解概率密度函数的动力方程或随机采样法进行模拟这种方法是N Metropolis et al 发表的梅特罗波利斯黑斯廷斯算法的改进版是一种生成热力学系统样本状态的蒙特卡罗方法