模拟退火

模拟退火（simulated annealing）是一类随机搜索方法：总是接受不增大代价的候选，并以随温度降低而减小的概率接受上坡候选。短期内允许变差，是为了有机会离开局部谷底。温度和降温规则属于算法参数；有限次降温搜索通常只给出找到的最好方案。

越过小山的可复算轨迹

设状态为 $0,1,2,3,4$，相邻状态才能互换，代价分别为 $E=(0,2,1,3,-1)$。状态零相对于邻居一是局部最小点，但真正最低代价在四。只接受下降的局部搜索会停在零。

在温度 $T>0$ 下，对候选y与当前x，记 $\Delta =E(y)-E(x)$，接受概率为 $$a_T(x,y)=min\{1,e^{-\Delta /T}\}.$$ 代价与温度必须使用一致尺度，指数才无量纲。对上坡高度二，温度二时概率为 $e^{-1}\approx 0.367879$，温度二分之一时只有 $e^{-4}\approx 0.018316$。

按正文指定试步可走过两处高地；最好值到最后才改善。

固定温度二，考虑四次向右提议，配对的均匀随机数依次为0.2、0.4、0.1、0.9。第一步0到1上坡二，0.2小于 $e^{-1}$，接受；第二步1到2下降一，接受；第三步2到3上坡二，0.1小于 $e^{-1}$，接受；最后3到4下降四，接受。当前代价为 $0,2,1,3,-1$，保存的最好代价却为 $0,0,0,0,-1$。它们是两个不同的状态量。

固定温度时的平衡含义

在有限状态集上，假设提议概率对称 $q(x,y)=q(y,x)$。定义 ${\pi }_T(x)=e^{-E(x)/T}/Z_T$，其中 $Z_T=\sum _z{e}^{-E(z)/T}$。对不同状态有 $${\pi }_T(x)q(x,y)a_T(x,y)=\frac{q(x,y)}{Z_T}min\{e^{-E(x)/T},e^{-E(y)/T}\},$$ 交换x、y右侧不变，故满足细致平衡，对称求和证明π为平稳分布。在提议图连通并有适当自环等条件下，可进一步讨论固定温度链的收敛。若提议不对称，简单的指数接受式一般需要修正，不能直接沿用此证明。

固定同一上坡高度，只改变温度；两标点对应正文数值。

令最低代价为 $E_{\ast }$，任何非最优状态的相对权重含 $e^{-(E-E_{\ast })/T}$，当温度趋零时趋零。因此固定温度的平衡分布在低温时集中到最小状态；这不等于任意快的时间变温算法都来得及达到那些平衡分布。早期就降到很低温可能把链冻结在局部谷底。

降温变式与实现

把上述四次试步的温度改为二分之一，第一步的0.2大于 $e^{-4}$，便会拒绝，后续轨迹随之改变。变式仅考察第一步，答案是仍停在零，保存的最好值仍为零。不同种子、提议邻域、每个温度的混合次数都会影响有限预算结果，不能由降温曲线本身宣布全局最优。

下例为复算而显式输入温度、左右提议及对应均匀数；普通随机运行可由独立随机数生成这些输入。左右各半概率，越界提议留在原处，使边界处仍保持对称提议。函数返回每次试步、接受情况和历史最好状态，不改写代价与试步数据。每次常数成本，K步历史占 $O(K)$；更复杂邻域需另计生成和评价成本。

Python 3

import math

def anneal_trace(energies, initial, temperatures, draws):
    E = tuple(map(float,energies))
    if not 0 <= initial < len(E) or len(temperatures) != len(draws):
        raise ValueError("invalid state or trajectory lengths")
    x,best,trace = int(initial),int(initial),[]
    for T,(direction,u) in zip(temperatures,draws):
        if T <= 0 or direction not in (-1,1) or not 0 <= u < 1:
            raise ValueError("invalid temperature or draw")
        y = x+direction
        if not 0 <= y < len(E):
            y = x
        delta = E[y]-E[x]
        probability = 1.0 if delta <= 0 else math.exp(-delta/T)
        accept = u < probability
        old = x
        if accept:
            x = y
        if E[x] < E[best]:
            best = x
        trace.append((old,y,probability,accept,x,E[x],best,E[best]))
    return trace

draws = [(1,.2),(1,.4),(1,.1),(1,.9)]
for row in anneal_trace([0,2,1,3,-1],0,[2]*4,draws):
    print(row)
assert anneal_trace([0,2,1,3,-1],0,[.5],draws[:1])[-1][4] == 0