什么是模拟退火算法？

算法介绍

模拟退火算法最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于组合优化问题求解。作为求解复杂组合优化问题的一种有效方法，模拟退火算法已经在许多工程和科学领域得到广泛的应用。
模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。
模拟退火的原理也和金属退火的原理近似：可将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
在模拟退火算法中，把某类优化问题的求解过程与统计力学中的热平衡问题进行对比，通过模拟高温物体退火过程的方法，来找到优化问题的全局最优或近似全局最优解。

演算步骤

模拟退火算法新解的产生和接受可分为如下四个步骤：
1.由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
2.计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好 按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
3.判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若 Δt′<0 则接受 S′作为新的当前解 S，否则以概率 exp(-Δt′/T) 接受 S′作为新的当前解S。
4.当新解被确定接受时，用新解代替当前解，只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一次迭代。而当新解被判定为舍弃时，则在原当前解的基础上继续下一次迭代。
模拟退火算法与问题的初始状态无关，算法求得的解也与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

伪代码

s := s0; e := E(s)                           // 设定目前状态s0，其能量E(s0)
k := 0                                       // 评估次数k
while k < kmax                               // 若还有时间(评估次数k还不到kmax)
  sn := neighbour(s)                         //   随机选取一邻近状态sn
  en := E(sn)                                //   sn的能量为 E(sn)
  if random() < P(en-e, k)) then             //   决定是否移至邻近状态sn
    s := sn; e := en                         //     移至邻近状态sn
  k := k + 1                                 //   评估完成，次数k加一
return s                                     // 回传状态s

参数问题

模拟退火算法的应用广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
(1) 温度T的初始值设置问题。
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一：初始温度高，搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。
　　(2) 退火速度问题。
　　模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
　　(3) 温度下降问题。
　　温度下降问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：
T(t+1)＝k×T(t)
式中k为正的略小于1.00的常数，t为降温的次数。