模拟退火算法[4](simulated annealing,SA)是基于Monte Carlo 迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性(即:退火过程中,固体最终达到能量最小的状态,对应于优化算法最终找到了最优解)而设计的一种智能优化算法,该算法将固体的退火过程与优化问题的求解过程有机的结合起来,因此该算法被称为模拟退火算法。

算法主要包括: 新状态产生函数、新状态接受函数、退温函数、抽样稳定准则和退火结束准则
(简称三函数两准则)。算法开始时设计一个所谓的初始温度。初始温度和上面的三函数两准则将是直接影响算法优化结果的主要环节。算法运行时是从某一较高初温开始, 结合具有概率突跳特性的Metropolis 抽样策略在解空间中随机寻找目标函数的全局最优解,伴随温度参数的不断下降重复抽样过程,最终得到问题的全局最优解。

模拟退火算法的应用很广泛在求解最大截问题,0-1背包问题,图着色问题,调度问题