Loading AI tools
来自维基百科，自由的百科全书
模拟退火（英语：Simulated annealing，缩写作SA）是一种逼近给定函数全局最优的通用概率演算法，具体来说，它是一种元启发算法，常用来在一定时间内，寻找在一个很大搜寻空间中的近似全局最优解。在有大量局部最优解时，模拟退火算法可以找到全局最优解。[1] 模拟退火常用于搜索空间离散的情形（如旅行推销员问题、布尔可满足性问题、蛋白质结构预测、作业车间调度问题等）。对于在固定时间内找到近似全局最优优先于找到精确局部最优的问题，模拟退火算法可能优于梯度下降法或分支定界等精确方法。
模拟退火算法解决的问题包含多元目标函数与若干约束。实践中，约束可作为目标函数的一部分进行惩罚。
Pincus (1970)、[2]Khachaturyan et al (1979,[3] 1981[4])、Kirkpatrick、Gelatt及Vecchi (1983)、Cerny (1985)等人先后提出过类似技术。[5]现在的“模拟退火”算法在1983年为S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi解决旅行推销员问题所发明[6]，V. Černý也在1985年独立发明此演算法。
模拟退火算法中的慢冷却是指在探索解空间的过程中，接受较差解的概率会缓慢下降。接受较差解可以更广泛地搜索全局最优解。总的来说，模拟退火算法的工作原理如下：温度从初始值逐渐降低到0，每个时间步长内，算法随机选择一个与当前解接近的解，并根据与温度相关的概率选择更优的。搜索过程中，这概率会趋近于1。
可通过求解概率密度函数的动力方程[7][8]或随机采样法进行模拟。[6][9]这种方法是N. Metropolis et al. (1953)发表的梅特罗波利斯-黑斯廷斯算法的改进版，是一种生成热力学系统样本状态的蒙特卡罗方法。[10]
“模拟退火”来自冶金学术语退火，是将材料加热后再经特定速率冷却的技术，目的是增大晶粒的体积，并且减少晶格中的缺陷，以改变材料的物理性质。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。
模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
可以证明，模拟退火算法所得解依概率收敛到全局最优解。
模拟退火法可用于精确算法失效的高难度计算优化问题，虽然通常只能获得全局最优的近似，但对很多实际问题已经足够。
物理系统的热力学状态s，以及要最小化的函数（类似于系统当前状态下的内能）。目标是将系统从任意初始状态带到内能尽可能小的状态。
模拟退火启发式在每一步都会考虑当前状态s的某邻态，并以概率决定是否移动到状态。概率最终引导系统进入低能状态。这步骤一般会重复进行，直到系统达到满足需求的状态，或达到预设的计算量。
解的优化包括计算问题状态的邻域，即由保守改变现状态产生的新状态。例如，在旅行推销员问题中，状态是待访问城市的排列，状态的邻域是交换任意两城市产生的排列集合。良定义的到邻态的方法称为移动，不同移动会产生不同的邻态集。
爬山算法之类启发法逐个寻找更好的邻态来移动，并在无更好邻态时停止，显然这很容易陷入局部最优。元启发算法利用解的邻域作为探索解空间的一种方式，虽然更喜欢较好的邻态，但也接受较差的邻态，以免陷入局部最优。若运行时间够长，则可以找到全局最优。
从现状态s转移到候选的新状态的概率由接受概率函数（acceptance probability function）确定，其取决于两状态的能量，以及称作温度的全局时变参数T。转移到能量更小的状态的概率更大。概率函数P在时也是正的，这可以防止算法陷入局部最优。
T趋近于0时，若，概率也要趋近于0或某正值。对足够小的T，系统会越来越倾向于“下山”（向低能值移动）而避免“上山”。时，程序将简化为贪心算法，只进行下山转移。
在模拟退火的原始描述中，时概率，即无论温度如何，程序找到下山的方法时总会下山。许多模拟退火算法的描述和实现仍将此条件作为方法定义的一部分，但这条件实际上并非必须。
P函数通常是这样选择的：当差值增加时，接受较小上山转移的概率就会比较大的更大。不过，在满足上述要求的前提下，这要求并非绝对必要。
鉴于这些特性，温度T在控制系统状态s演化方面起到关键作用，因为它对系统能量变化非常敏感。确切地说，T的大小决定着s演化敏感的“粒度”。
算法名称与灵感要求嵌入一个与温度有关的有趣特征。开始时，温度T被设为一个较大值（或无穷大），按用户指定的退火历程，每次迭代降温，但必须在一定时间预算内结束为。这样，预计系统最初会在搜索空间中包含良好解的广阔区域内游荡，忽略能量函数的微小特征；然后，向能量更低的区域漂移，最后根据梯度下降法启发式向下移动。
对任意给定的有限问题，随着退火历程延长，模拟退火算法以全局最优解终止的概率趋近于1。[11]但这理论结果并不很有用，因为确保显著成功概率的耗时通常大于暴力搜索整个解空间的耗时。[12]
寻找能量 最低的状态
s := s0; e := E(s) // 设定目前状态为 s0，其能量 E(s0)
k := 0 // 评估次数 k
while k < kmax and e > emin // 若还有时间（评估次数 k 还不到 kmax）且结果还不够好（能量 e 不够低）则：
sn := neighbour(s) // 随机选取一邻近状态 sn
en := E(sn) // sn 的能量为 E(sn)
if random() < P(e, en, temp(k/kmax)) // 决定是否移至邻近状态 sn
s := sn; e := en // 移至邻近状态 sn
k := k + 1 // 评估完成，次数 k 加一
return s // 返回状态 s
下面以自然语言解说模拟退火算法的演算步骤。
由一个产生函数从当前解产生一个位于解空间的新解，并定义一个足够大的数值作为初始温度。
迭代过程是模拟退火算法的核心步骤，分为新解的产生和接受新解两部分：
模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。
迭代过程的一般停止准则：温度T降低至某阈值时，或连续若干次迭代均未接受新解时，停止迭代，接受当前寻找的最优解为最终解。
在某个温度状态T下，当一定数量的迭代操作完成后，降低温度T，在新的温度状态下执行下一个批次的迭代操作。
将模拟退火算法用于实际问题，需要指定状态空间、能量（目标）函数E()、候选解生成器neighbour()、接受概率函数P()、退火历程temperature()以及初始温度init_temp。这些选择会对算法效率产生重大影响，遗憾的是它们的选择不适合所有问题，也没有针对特定问题找到最佳选择的通用方法。下面几节将给出一些通用指导。
模拟退火可建模为搜索图上的随机游走，其顶点是所有状态，边为候选的移动。neighbour()的基本要求是提供从初态到任何可能是全局最优态的足够短路径，这要求搜索图的直径足够小。以上面的旅行推销员问题为例，n = 20个城市的搜索空间有n! = 2,432,902,008,176,640,000（243亿亿）个状态，而每个顶点有条边（来自n选2），图直径为。
要研究模拟退火算法在特定问题上的行为，可考虑算法实施过程中各种设计选择产生的转移概率。对搜索图中的每条边，转移概率定义为现态为s时转移到的概率，取决于temperature()指定的当前温度、neighbour()生成的候选移动的顺序及接受概率函数P()（注意转移概率不是简单的，因为候选转移是以序列测试的）。
neighbour()、P()、temperature()的指定是多余的，因为实践中通常会使用相同的接受函数P()，并根据具体问题调整其他函数。
在Kirkpatrick et al.的方法中，若则接受概率函数，否则为。表面上看，这个公式是通过类比物理系统的转移来证明的；在且梅特罗波利斯-黑斯廷斯的提议分布对称时，对应梅特罗波利斯-黑斯廷斯算法。即使与梅特罗波利斯-黑斯廷斯算法中的提议分布类似的neighbour()函数不对称或根本不是概率分布，也常用于模拟退火。因此，转移概率同类似物理系统的转移概率并不对应，恒定温度T下的长期状态分布也不必同物理系统在任何温度下的热力平衡态分布有任何相似处。尽管如此，大多数模拟退火的描述都会假定原接受函数，而这种函数可能在许多模拟退火的实现中都是硬编码（hard-coded）的。
Moscato and Fontanari (1990)[13]与Dueck and Scheuer[14]分别提出，确定性更新（即不基于概率接受规则的）可加速优化，且不影响最终质量。Moscato and Fontanari通过观察“阈值更新”退火的类“比热”曲线得出结论：“在模拟退火算法中，Metropolis更新的随机性在寻找近优最小值的过程中没有发挥主要作用。”相反，他们认为“高温下成本函数景观的平滑化与冷却过程中最小值的逐步确定是模拟退火算法成功的基本要素。”后来，由于Dueck and Scheuer的命名，这种方法也称作“阈值接受法”。Franz, Hoffmann and Salamon (2001)表明，在一大类模拟成本/能量景观随机游走的算法中，确定性更新策略确实是最优策略。[15]
选择候选生成器neighbour()时，必须考虑到算法迭代几次后，现态的能量将低于随机状态。因此一般来说，生成器应偏向更接近目标状态能量的邻域。这种启发式（也是梅特罗波利斯-黑斯廷斯算法的主要原理）往往会排除“非常好”与“非常坏”的转移，不过前者通常更少见，所以启发式往往相当有效。
例如，在上述旅行商问题中，低能旅行中交换两连续城市对能量（总距离）影响不大，而交换两任意城市更可能增加能量。因此，连续交换优于随机交换，尽管后者能提供更优路径（次交换，而非次）。
启发式一个更准确的诠释是，应先尝试较大的邻态。对上述“标准”接受函数P来说，这意味着在T或更小的数量级上因此在上述旅行商问题中，可用交换两随机城市的neighbour()，并设置两城市距离超过T时不予选择。
选择候选生成器neighbour()时，还必须尽量减少能量远低于所有邻态的“深”局部最优（或相连状态集）数，这种“能量函数盆地”可能会以较高概率（与盆地中状态数大致呈正比）与较长时间（与周围状态同盆地底部的能量差大致呈指数关系）困住模拟退火算法。
一般来说设计不出既能满足这一目标，又能优先处理能量相近的候选粒子的候选发生器。另一方面，往往可对生成器进行相对简单的修改，大大提高模拟退火的效率。例如，在旅行商问题中，不难找到两条长度几乎相等的路线，使得(1) 最优、(2) 将转换为的城市交换序列要经历比二者长得多的距离、(3) 可通过翻转（颠倒顺序）一组连续的城市序列变为。此例中，就处于不同的“盆地”中，但若生成器执行随机分段翻转，则将位于同一个盆地。
模拟退火的物理类比假设冷却速率足够低，当前状态的概率分布比任意时刻都接近热力平衡。 然而，弛豫时间（relaxation time，温度变化后恢复平衡耗时）很大程度上取决于能量函数的“地形”和当前温度。模拟退火算法中，弛豫时间还以非常复杂的方式取决于候选生成器。注意所有参数通常作为黑盒函数提供给模拟退火算法。因此，理想的冷却速度无法事先确定，只能根据经验分析具体问题。自适应模拟退火算法将冷却历程同搜索进度联系起来，解决了这一问题。其他自适应法有热力学模拟退火，[16]会根据热力学定律，依两状态能量差自动调整每步的温度。
有时，从现态出发不如回到明显更优的解，这一过程称作模拟退火的重启（restarting）。为此，置s、e为sbest、ebest，然后重启退火历程。重启的决定可基于多个标准，其中值得注意的是包括基于固定步数、基于当前能量与迄今最优的能量、随机重启等等。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
