1.3　模拟退火算法

模拟退火（Simulated Annealing，SA）算法是一种基于Monte Carlo迭代求解策略的随机寻优算法，它基于物理中固体物质的退火过程与一般组合优化问题之间的相似性，其目的在于为具有NP（Non-deterministic Polynomial）复杂性的问题提供有效的近似求解算法；该算法克服了传统算法优化过程容易陷入局部极值的缺陷和对初值的依赖性。

作为一种通用的优化算法，模拟退火算法是局部搜索算法的扩展，但又与局部搜索算法不同：它以一定的概率选择邻域中目标值大的状态。从理论上来说，它是一种全局最优算法。模拟退火算法采用了许多独特的方法和技术，具有十分强大的全局搜索性能；虽然它看起来是一种盲目的搜索方法，但实际上有着明确的搜索方向。