模拟退火算法
引入
将固体加温至充分高，再让其缓慢降温。升温时，固体内部的粒子随升温变为无序且活跃的状态，内能增大；降温时，粒子趋于惰性有序，在每个温度都达到平衡的状态，最后在常温时达到基态，内能降为最小。
这个降温的过程也就是退火。受此物理背景的启发，结合统计的知识，模拟退火算法的思想逐渐产生。
理论基础
固体退火的物理过程和统计性质：
-
加温：随温度升高，粒子能量增高，与平衡位置的距离增大；
-
等温：温度升至熔化温度，固体的规则性质被打破，成为液体，粒子可以自由运动和重新排序，消除系统中原先存在的非均匀状态；
-
冷却：随着温度的下降，粒子能量减弱，运动减小，粒子最终进入平衡状态，固化为具有最小能量的晶体。
温度$t$下，分子停留在某一状态$r$满足Bolztmann概率分布：
$$
P\left\lbrace \bar{E}=E\left( r \right) \right\rbrace =\frac{1}{z\left( t \right)}\exp \left( -\frac{E\left( r \right)}{kt} \right)
$$
其中：
-
$E\left( r \right)$：状态$r$的能量；
-
$k$：物理学中的波尔兹曼常数；
-
$t$：材料温度
-
$E$：分子能量的一个随机变量；
-
$z(t)$：概率分布的标准化因子；
-
$D_0$：最低能量状态的个数；
-
$D$：状态空间中状态的个数.
基本思想
根据统计的理论，状态迁移准则(Metropolis抽样稳定性条件)
$$
\exp \left( \frac{E_i-E_j}{kt} \right) \ge random\left( 0,1 \right)
$$
若新状态$j$的能量满足条件，则被用来代替原状态$i$。
高温下，可以接受能量差较大的新状态，也即允许在可行域内做出更多的尝试，接受目标函数值的暂时劣化，以跳出局部最优解的寻找。
低温下，只接受能量差较小的新状态，即在降温的终点，少做尝试，寻找局部最优。
由某一较高的初始温度开始，利用上式在求解域内随机搜索采样，随着温度不断降低，使系统的能量达到最低状态，即相当于能量函数的全局最优解。
算法基本步骤
设求解优化问题$\min\text{.\ }f\left( x \right) \ x\in R^n$
内循环终止条件：
-
规定产生有限个候选解；
-
在连续若干步候选解的目标函数值变化很小；
-
目标函数值的均值已相当稳定。
外循环终止条件：
-
设置一个终止温度$t_e$；
-
规定外循环的最大迭代次数$k_{max}$；
-
算法在每个$t_k$值搜索到的最优解的值在若干次迭代内保持不变。
在模拟退火算法中应注意以下问题：（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。（2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续 m 次的转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定为一个较小的值Te ，或连续几个温度下转换过程没有使状态发生变化算法就结束。（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。
概述
从算法来看，模拟退火算法就像是改良圈算法的一个改进，改良圈算法只能获得一个局部的最优解，而模拟退火算法则是在其基础上，受固体退火的过程和统计性质的启发，引入了温度的变量，让可行解在高温阶段作出更多尝试、跳出寻找局部最优，而在低温阶段降低活性转而去找局部最优。