模拟退火算法源于对固体退火过程的模拟，采用Metropolis准则，并用一组称为冷却进度表的参数控制算法的进程，使算法能在一定的时间内给出一个近似最优解。

1．固体的退火过程

固体退火是先将固体加热到熔化，再徐徐冷却使之凝固成规整晶体的热力学过程。整个过程由以下三部分组成。

（1）升温过程

在加热固体时，固体粒子的热运动不断增强，随着温度的升高，粒子与其平衡位置的偏离越来越大。当温度升至溶解温度后，固体的规则性被彻底破坏，固体溶解为液体，粒子排列从较有序的结晶态转变为无序的液态，这个过程称为溶解。溶解过程的目的是消除系统中原先可能存在的非均匀状态，使随后进行的冷却过程以某一平衡态为始点。

（2）平衡过程

退火过程中系统在每一温度下达到平衡态的过程遵循应用于热平衡封闭系统的热力学定律即自由能减小定律，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能达到最小时，系统达到平衡。

系统自由能是系统熵（混乱度）、能量的一种度量。温度决定着这两种因素的相对权重。在高温下，熵占统治地位，有利于变化的方向就是熵增加的方向，因而显示出粒子的无序状态；低温对应于低熵，低温下能量占统治地位，能量减少的方向有利于自发变化，因而得到有序（低熵）和低能的晶体结构。

（3）冷却过程

与升温过程相反，使系统中粒子的热运动减弱并渐趋有序，系统能量随温度降低而下降。

2．Metropolis准则

1953年，Metropolis等提出重要性采样法，用于模拟固体在恒定温度下达到热平衡的过程。其基本思想是从物理系统倾向于能量较低的状态，而热运动又妨碍它准确落入最低态的基本思想出发，采样时着重取那些具有重要贡献的状态，则可以较快地达到较好的结果。

设以粒子相对位置表征的初始状态i作为固体的当前状态，该状态的能量是E_i。然后用摄动装置使随机选取的某个粒子的位移随机地产生一个微小变化，得到一个新状态j，其能量是E_j。如果E_j＜E_i，则该新状态就作为“重要”的状态，如果E_j＞E_i，则考虑到热运动的影响，该状态是否为“重要”状态，要依据固体处于该状态的概率来判断，即

其中，T为热力学温度；k为玻耳兹曼常数。因此，p∈［0，1］越大，则状态是重要状态的概率就越大。若新状态j是重要状态，就以i取代成为当前状态，否则仍以i为当前状态。再重复以上新状态的产生过程。在大量迁移（固体状态的变换称为迁移）后，系统趋于能量较低的平衡状态，固体状态的概率分布趋于吉布斯正则分布：

其中，Z为一常数。

以上接受新状态的准则称为Metropolis准则，相应的算法称为Metropolis算法。