模拟退火(simulated annealing)算法是局部搜索算法的扩展，它不同于局部搜索之处是以 一定的概率选择邻域中费用值大的状态。从理论上来说，它是一个全局最优算法。模拟退火 算法最早的思想由Metropolis [1] 在 1953 年提出，Kirkpatrick[2] 在 1983 年成功地应用在组合最 优化问题。本章 3.1 节介绍模拟退火算法的思想和模型，3.2节给出马尔可夫链的基本理论， 3.3 和 3.4 节分别讨论时齐和非时齐算法的收敛性，3.5 节讨论算法实现的技术问题，最后用 示例理解它的应用。