模拟退火算法用于解决TSP问题

模拟退火
1982年，KirkPatrick将退火理念引入组合优化研究领域，提出了一种用于解决大规模组合优化问题的算法，尤其适用于NP完全组合优化问题。这一方法源于固体的退火过程，即首先将温度升高至较高水平，再缓慢降低温度（即退火），从而达到能量最低点。若快速降温（即淬火）则无法达到最低点。
模拟退火算法是一种可用于求解最小值问题或基本先前更新的学习过程（随机或确定性的）。在此过程中，每一步更新的幅度均与相应的参数成正比，这些参数起到温度的作用。类似金属退火原理，在初始阶段为了加速最小化或学习过程，温度被设定得较高，随后逐步降温以实现稳定状态。
模拟退火算法是一种用于解决大规模优化问题的随机搜索方法，其基础是优化求解过程与物理系统退火过程之间的相似性；目标函数对应于金属的内能；优化问题中的自变量组合状态空间等同于金属内能状态空间；求解过程则是寻找一个组合状态使得目标函数值最小。通过Metropolis准则并适当控制温度下降的过程来实现模拟退火操作，从而在多项式时间内完成全局优化问题的求解目标。
模拟退火算法来源于固体退火原理，即将固体加热至足够高后缓慢冷却，在加热过程中固体内部粒子随温升变得无序化、内能增加；而在缓慢冷却时粒子逐渐有序化，并在每个温度下达到平衡态；最终在常温状态下达到基态、内能降至最小值。根据Metropolis准则，在温度T时趋于平衡的概率为e-Δ