Skip to content

模拟退火算法 ​

方法速览 ​

  • 主要用途 在多峰、不可导或黑箱目标中寻找近似全局最优(本页以最大化为例,最小化只需对目标取负)。
  • 必要输入 目标函数、可行域、初始温度、冷却系数与停止条件,以及一个可复现的随机数发生器(固定 seed)。
  • 适用条件 存在多个局部最优、穷举或精确求解代价过高,且允许返回「足够好」的近似解而非严格最优证明。
  • 典型不适用情况 需要严格全局最优证明、目标函数评估极其昂贵,或问题本身可用确定性方法精确求解时。
  • 最低限度的验证方式 用独立网格搜索或枚举给出参考最优,比较慢冷却与快冷却的 best 值差异,并固定 seed 复现结果。

快速回答 ​

模拟退火(Simulated Annealing,SA)是受金属退火启发的随机全局优化算法。它用一个随迭代下降的「温度」T 控制搜索的随机程度:高温时几乎随机游走(能翻山越岭跳出局部最优),低温时几乎只接受改善(收敛到局部或全局最优)。

它的核心是一条接受准则——Metropolis 准则:改进(Δ≥0)一定接受,变差(Δ<0)以概率 exp⁡(Δ/T) 接受。正是「偶尔接受更差解」让它区别于贪婪爬山,能逃出局部最优。

关键可调参数是初始温度 t0 与冷却系数 α(0<α<1,每步 T←T⋅α)。α 越接近 1、t0 越大,冷却越慢、越可能逼近全局最优,但越耗时;冷却太快则会陷入局部最优。

从零理解 ​

金属退火的过程是:把金属加热到高温,让原子剧烈运动,然后缓慢降温。降温足够慢时,原子有充分时间排列成能量最低的晶体结构;降温太快,原子被「冻」在某个能量较低的局部排列里,形成有内应力的非晶体。

把这个过程逐项「翻译」成优化语言,就得到模拟退火:

物理退火优化中的对应
金属内部能量 E目标函数 f(x)(越小越好;最大化取 −f)
原子的某种排列一个可行解 x
温度 T随机扰动强度,也是接受劣解的尺度
高温下原子剧烈运动大步随机搜索,接受劣解的概率高
缓慢降温逐渐减小扰动、收紧接受准则
降温过快 → 非晶体(局部能量最低)快冷却 → 陷入局部最优
充分慢的退火 → 晶体(全局能量最低)慢冷却 → 逼近全局最优

所以「退火」三个字不是比喻,而是同一套数学——接受概率中的 exp 就是统计物理里的 Boltzmann 因子(见下节)。

数学原理 ​

符号定义 ​

符号含义
x当前解(本页为一维标量,多维同理)
f(x)目标函数,本页最大化
x′候选解,由当前解加一个随机扰动得到
Δ=f(x′)−f(x)候选相对当前的改进量
T温度,随迭代下降
t0初始温度
α冷却系数,0<α<1,每步 T←T⋅α

Metropolis 接受准则推导 ​

统计物理中,系统处于能量为 E 的状态的概率服从 Boltzmann 分布,正比于 exp⁡(−E/kT)。因此系统从旧态(能量 E)跳到新态(能量 E′)的相对概率为

P(E′)P(E)=exp(−E′−EkT)=exp(−ΔEkT),ΔE=E′−E.

把「能量」对应到最大化问题的「负目标」,即 E↔−f(x),则 ΔE=E′−E↔−(f(x′)−f(x))=−Δ。代入上式,新解被接受的概率(相对当前解的比值)为

P(接受)∝exp(ΔT).

把它归一化成一条确定性的接受准则:Δ≥0 时 exp⁡(Δ/T)≥1,接受概率取上限 1;Δ<0 时接受概率为 exp⁡(Δ/T)。合起来就是

P(接受)=min(1, exp⁡(Δ/T)).

这正是本页代码里 accepted = rng() < exp(delta / T)(在 Δ≥0 分支恒真)所实现的内容。

为什么接受劣解 ​

贪婪爬山只接受 Δ≥0,一旦走到一个局部最高点,任何一步都会变差,于是被卡住。接受劣解让算法有概率「往山下走一步」,从而有机会翻过山谷、登上更高的峰。

  • T 大时,exp⁡(Δ/T) 接近 1,劣解几乎照单全收 → 随机游走、充分探索;
  • T→0 时,exp⁡(Δ/T)→0,劣解几乎全被拒绝 → 退化为贪婪爬山、只收敛。

所以温度就是「敢于接受更差解」的刻度,是模拟退火区别于确定性局部搜索的根因。

冷却策略与收敛条件 ​

  • 几何冷却 T←T⋅α:最常用,本页演示所用。α 通常取 0.8–0.999。
  • 线性冷却 T←T−β:温度按固定步长下降。
  • 对数冷却 T←t0/ln⁡(1+k):理论上能保证收敛到全局最优,但降温极慢,实践中基本不直接使用。

收敛条件要分两层:理论保证需要极慢(对数)冷却,这在有限时间内不现实;实践普遍用几何冷却加足够多的迭代,得到一个「足够好」的近似解,并用独立基准(网格搜索)与固定 seed 复现来验证,而不是宣称「证明了全局最优」。

失败条件 ​

冷却太快(t0 太低或 α 太小)会让温度过早趋近 0,算法退化成贪婪爬山,从而陷入局部最优。本文「动态实验」与 Python 算例都给出了这个反例:t0=0.05, α=0.9 时,算法被卡在浅峰 3π/2(f≈−0.5),而慢冷却能找到全局峰(f≈1.076)。

动态实验 ​

模拟退火演示:最大化 f(x) = sin(x) + 0.5·sin(3x)
0π/2π3π/22π-1-0.500.51全局峰全局峰
温度 T = 2.0000(t0 = 2.00)
几何冷却 T ← T·α
f* = 1.0758迭代次数best.fx
迭代 0/1000x = 4.0000f(x) = -1.0251T = 2.0000接受率(至今)—累计接受 0

高温起点:T = t0 = 2.00,几乎随机游走——接受更差解的概率 exp(Δ/T) 接近 1,能翻山越岭跳出局部最优。

1 / 1001
左图:f(x) 曲线(紫)、已访问轨迹(浅色折线)、当前解(品牌色圆点,绿描边=接受 / 红描边=拒绝)、 历史最优(金色星形)。右列:温度条(T 随迭代下降)与最优值曲线(best.fx vs 迭代)。 两个「全局峰」虚线标记了 f(π−x)=f(x) 的两个等高全局极大值。从 x0=4.0 出发:慢冷却(默认)跳出浅峰 3π/2 到达全局峰;把 t0 调到 0.05、α 调到 0.9 会看到快冷却陷入浅峰。本演示是随机搜索轨迹: 同一 seed 可复现,不同 seed 轨迹不同。

本演示最大化 f(x)=sin⁡(x)+0.5sin⁡(3x),x∈[0,2π]。注意该函数关于 x=π/2 对称(f(π−x)=f(x)),存在两个等高的全局极大值(x≈0.70 与 x≈2.44,f≈1.0758),以及一个较浅的局部极大值(x=3π/2≈4.71,f=−0.5)。演示从 x0=4.0(浅峰左坡的深谷)出发。

参数含义:

参数范围默认作用
t00.05–52初始温度;越大初期探索越充分
α0.8–0.9990.99冷却系数;越接近 1 冷却越慢
iterations200 / 1000 / 50001000迭代次数上限
seed42 / 7 / 12342随机种子;同一 seed 轨迹可复现

慢 / 快冷却对照(与 Python 算例逐位一致,seed 42 实测):

慢冷却(收敛)快冷却(失败反例)
参数t0=2, α=0.99,2000 次t0=0.05, α=0.9,200 次
best.x2.44004.7127
best.fx1.075829−0.5000
acceptCount468(总接受率 0.234)18(总接受率 0.090)
接受更差解次数2263
高温段(前 100 步)接受率0.94—

独立网格搜索(105 等分)给出的参考最优:x\*=0.7016433033,f\*=1.0758287051(镜像峰 π−x\*≈2.4399 等高)。慢冷却落在镜像峰邻域,f 达到 1.0758286753,与网格最优只差约 10−8;快冷却则卡在 f≈−0.5,明显低于网格最优。

把 t0 调到 0.05、α 调到 0.9,就能在动画里看到快冷却如何「贪婪地」爬上浅峰 3π/2 后停下。本演示是随机搜索轨迹:同一 seed 可复现,不同 seed 轨迹不同。

代码实践 ​

完整代码 ​

下面的代码与仓库 examples/simulated_annealing.py 逐字一致,可用 python examples/simulated_annealing.py 直接运行。脚本用独立网格搜索给出参考最优,复现慢/快冷却两种行为,并用 assert 与前端 TS 测试的钉死值交叉核对(不一致即非零退出)。

py
# -*- coding: utf-8 -*-
"""模拟退火算法(最大化)—— MathModel FAQ 可运行算例。

目标函数(区间 [0, 2π],最大化):
    f(x) = sin(x) + 0.5·sin(3x)

这是一个多峰函数:由 f(π−x) = f(x) 可知它关于 x=π/2 对称,存在两个等高
的全局极大值(x≈0.70 与 x≈2.44,f≈1.0758)以及一个较浅的局部极大值
(x=3π/2≈4.71,f=−0.5)。演示要点:

  从 x0=4.0(浅峰 3π/2 左坡的一个深谷)出发:
    · 快冷却(t0=0.05, α=0.9)几乎只接受改善,贪婪爬到最近的浅峰 3π/2
      就停下(f≈−0.5)—— 陷入局部最优;
    · 慢冷却(t0=2, α=0.99)在高温段能翻过深谷,最终到达全局最高峰
      (x≈2.44,f≈1.0758)。

随机数:mulberry32(seed),与前端 TS 引擎 docs/.vitepress/theme/math/
simulatedAnnealing.ts 逐位一致(32 位无符号运算,返回 [0,1) 的 IEEE 754
双精度浮点数)。同一 seed 得到逐位相同的轨迹,不同 seed 轨迹不同。

参考最优值由独立网格搜索(区间 10^5 等分)给出,与退火算法代码路径无关。

运行方式(本机实测:Python 3.14.8 + numpy 2.5.3 + matplotlib 3.11.2):
    python examples/simulated_annealing.py

输出:控制台数值表 + docs/public/examples/simulated-annealing-demo.png
"""
import math
import sys
from pathlib import Path

import matplotlib
# Agg 用于无图形环境生成网页 PNG;NumPy 组织曲线,Metropolis 决策使用 math。
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np

plt.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei']
plt.rcParams['axes.unicode_minus'] = False

ROOT = Path(__file__).resolve().parent.parent
OUT_DIR = ROOT / 'docs' / 'public' / 'examples'

BOUNDS = (0.0, 2.0 * math.pi)
X0 = 4.0  # 演示用的固定起点:浅峰 3π/2 左坡的深谷

# 与前端 TS 测试钉死值一致(本机实测 Python 3.14.8;来源见 tests/
# simulated-annealing.test.ts 的注释与下文独立网格搜索)。
GRID_X = 0.701643303252744
GRID_FX = 1.075828705133744
SLOW_BEST_X = 2.440037527307869
SLOW_BEST_FX = 1.075828675286362
SLOW_ACCEPT = 468
SLOW_WORSE = 226
FAST_BEST_X = 4.712739312276244
FAST_BEST_FX = -0.500000214781735
FAST_ACCEPT = 18


def mulberry32(seed):
    """mulberry32 确定性 PRNG;与前端 TS 实现逐位一致。"""
    state = seed & 0xFFFFFFFF

    def next_float():
        nonlocal state
        state = (state + 0x6D2B79F5) & 0xFFFFFFFF
        # t = Math.imul(a ^ (a >>> 15), 1 | a)
        t = ((state ^ (state >> 15)) & 0xFFFFFFFF) * (state | 1) & 0xFFFFFFFF
        # t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t
        u = (t ^ (t >> 7)) & 0xFFFFFFFF
        w = u * (t | 61) & 0xFFFFFFFF
        t = (((t + w) & 0xFFFFFFFF) ^ t) & 0xFFFFFFFF
        # return ((t ^ (t >>> 14)) >>> 0) / 4294967296
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296.0

    return next_float


def objective(x):
    """目标函数(最大化):sin(x) + 0.5·sin(3x)。"""
    return math.sin(x) + 0.5 * math.sin(3.0 * x)


def anneal(x0, t0, alpha, iterations, seed, bounds=BOUNDS):
    """模拟退火(最大化,Metropolis 准则)。返回 (trajectory, best, accept_count)。

    trajectory 为 iterations+1 个 {iteration, x, T, fx, accepted} 条目,
    与 TS 引擎逐字段对应。
    """
    a, b = bounds
    # 相对默认 2π 区间缩放候选步长,改变边界时仍按区间的相对大小扰动。
    span = (b - a) / (2.0 * math.pi)
    rng = mulberry32(seed)

    x = min(max(x0, a), b)
    T = t0
    fx = objective(x)
    # 当前状态可回落,历史最高点单独保留。第 0 帧不计入接受次数。
    best = {'x': x, 'fx': fx}
    trajectory = [{'iteration': 0, 'x': x, 'T': T, 'fx': fx, 'accepted': True}]
    accept_count = 0

    for iteration in range(1, iterations + 1):
        step = (rng() * 0.4 - 0.2) * span
        # 从当前点提出候选并夹回约束区间,再比较目标差。
        candidate = min(max(x + step, a), b)
        candidate_fx = objective(candidate)
        delta = candidate_fx - fx

        # 最大化时,非负增益直接移动;劣解才额外抽样,与网页的随机消费顺序一致。
        if delta >= 0.0:
            accepted = True
        else:
            accepted = rng() < math.exp(delta / T)

        if accepted:
            x = candidate
            fx = candidate_fx
            accept_count += 1
        # 每步均按 T ← αT 降温,保存的温度已是下一步将使用的值。
        T *= alpha
        if fx > best['fx']:
            best = {'x': x, 'fx': fx}
        trajectory.append({'iteration': iteration, 'x': x, 'T': T, 'fx': fx, 'accepted': accepted})

    return trajectory, best, accept_count


def grid_search(bounds=BOUNDS, divisions=100_000):
    """独立网格搜索参考最优值(10^5 等分),与退火代码路径无关。"""
    a, b = bounds
    best_x, best_fx = a, objective(a)
    for i in range(divisions + 1):
        x = a + (b - a) * i / divisions
        fx = objective(x)
        if fx > best_fx:
            best_x, best_fx = x, fx
    return best_x, best_fx


def count_worse_accepts(trajectory):
    """统计「接受更差解」的迭代次数(accepted 且 fx 较上一步下降)。"""
    count = 0
    for i in range(1, len(trajectory)):
        if trajectory[i]['accepted'] and trajectory[i]['fx'] < trajectory[i - 1]['fx']:
            count += 1
    return count


def high_temp_accept_rate(trajectory, window):
    """前 window 步(高温段)的接受率。"""
    # 统计第 1 步到指定步数的接受标记,排除初始化的第 0 帧。
    accepted = sum(1 for s in trajectory[1:window + 1] if s['accepted'])
    return accepted / window


def run_slow():
    print('== 慢冷却(应跳出局部最优、收敛到全局最优)==')
    # 网页快、慢预设同时改变初温、冷却系数和迭代预算,此处展示组合效果。
    t0, alpha, iterations, seed = 2.0, 0.99, 2000, 42
    traj, best, accept = anneal(X0, t0, alpha, iterations, seed)
    worse = count_worse_accepts(traj)
    hi_rate = high_temp_accept_rate(traj, 100)
    print(f'  参数: x0={X0}, t0={t0}, alpha={alpha}, iterations={iterations}, seed={seed}')
    print(f'  best.x = {best["x"]:.15f}')
    print(f'  best.fx = {best["fx"]:.15f}')
    print(f'  acceptCount = {accept}  (总接受率 {accept / iterations:.6f})')
    print(f'  接受更差解次数 = {worse}')
    print(f'  高温段(前100步)接受率 = {hi_rate:.6f}')
    return traj, best, accept, worse, hi_rate


def run_fast():
    print('== 快冷却(应陷入局部最优)==')
    t0, alpha, iterations, seed = 0.05, 0.9, 200, 42
    traj, best, accept = anneal(X0, t0, alpha, iterations, seed)
    worse = count_worse_accepts(traj)
    print(f'  参数: x0={X0}, t0={t0}, alpha={alpha}, iterations={iterations}, seed={seed}')
    print(f'  best.x = {best["x"]:.15f}')
    print(f'  best.fx = {best["fx"]:.15f}')
    print(f'  acceptCount = {accept}  (总接受率 {accept / iterations:.6f})')
    print(f'  接受更差解次数 = {worse}')
    return traj, best, accept


def run_seeds():
    print('== 不同 seed 对比(同一慢冷却参数,轨迹不同)==')
    t0, alpha, iterations = 2.0, 0.99, 1000
    rows = []
    for seed in (42, 7, 123):
        traj, best, accept = anneal(X0, t0, alpha, iterations, seed)
        final = traj[-1]
        print(f'  seed={seed}: best.x={best["x"]:.12f}, best.fx={best["fx"]:.12f}, '
              f'final.x={final["x"]:.12f}, final.fx={final["fx"]:.12f}')
        rows.append((seed, best, final, traj))
    return rows


def make_figure(slow, fast, grid_x, grid_fx):
    OUT_DIR.mkdir(parents=True, exist_ok=True)
    xs = np.linspace(BOUNDS[0], BOUNDS[1], 600)
    ys = np.array([objective(float(x)) for x in xs])

    fig, axes = plt.subplots(2, 2, figsize=(11.5, 7.0), dpi=110)

    # 上排把接受后的状态连在剖面上;星形标出各轨迹访问到的最高点。
    for ax, (label, traj, color) in zip(
            axes[0], [('慢冷却 t0=2, α=0.99(收敛)', slow, '#1f8a4c'),
                      ('快冷却 t0=0.05, α=0.9(陷入局部最优)', fast, '#c0392b')]):
        ax.plot(xs, ys, color='#5d42bc', lw=1.6, zorder=1, label='f(x)')
        tx = [s['x'] for s in traj]
        ty = [s['fx'] for s in traj]
        ax.plot(tx, ty, color=color, lw=0.9, alpha=0.5, zorder=2, label='轨迹')
        ax.scatter([traj[0]['x']], [traj[0]['fx']], color=color, s=28, zorder=3, label='起点 x0')
        best = max(traj, key=lambda s: s['fx'])
        ax.scatter([best['x']], [best['fx']], marker='*', color=color, s=180, zorder=4,
                   label=f"best f={best['fx']:.3f}")
        ax.axvline(grid_x, color='#b07d2b', lw=1, ls='--', zorder=1,
                   label=f'网格最优 x={grid_x:.4f}')
        ax.axvline(math.pi - grid_x, color='#b07d2b', lw=1, ls=':', zorder=1,
                   label=f'镜像峰 x={math.pi - grid_x:.4f}')
        ax.set_xlabel('x')
        ax.set_ylabel('f(x)')
        ax.set_title(label)
        ax.set_xlim(BOUNDS)
        ax.set_ylim(-1.7, 1.7)
        ax.grid(alpha=0.25)
        ax.legend(frameon=False, fontsize=8, loc='lower right')

    ax = axes[1, 0]
    for label, traj, color in [('慢冷却', slow, '#1f8a4c'), ('快冷却', fast, '#c0392b')]:
        ks = np.arange(len(traj))
        Ts = np.array([s['T'] for s in traj])
        ax.plot(ks, Ts, color=color, lw=1.6, label=label)
    # 对数纵轴可以显示跨多个数量级的温度并比较几何降温斜率。
    ax.set_yscale('log')
    ax.set_xlabel('迭代次数')
    ax.set_ylabel('温度 T')
    ax.set_title('几何冷却 T ← T·α')
    ax.grid(alpha=0.25, which='both')
    ax.legend(frameon=False, fontsize=8)

    ax = axes[1, 1]
    for label, traj, color in [('慢冷却', slow, '#1f8a4c'), ('快冷却', fast, '#c0392b')]:
        # 历史最大值只会持平或提高;当前目标仍可能因接受劣解而下降。
        bests, running = [], -math.inf
        for s in traj:
            running = max(running, s['fx'])
            bests.append(running)
        ax.plot(np.arange(len(traj)), bests, color=color, lw=1.6, label=label)
    ax.axhline(grid_fx, color='#b07d2b', lw=1, ls='--', label=f'网格最优 {grid_fx:.4f}')
    ax.set_xlabel('迭代次数')
    ax.set_ylabel('best.fx(至今最优)')
    ax.set_title('最优值曲线(best-so-far)')
    ax.set_ylim(-0.6, 1.3)
    ax.grid(alpha=0.25)
    ax.legend(frameon=False, fontsize=8)

    fig.tight_layout()
    fig.savefig(OUT_DIR / 'simulated-annealing-demo.png')
    plt.close(fig)
    print(f'== 绘图已保存到 {OUT_DIR / "simulated-annealing-demo.png"} ==')


def main() -> None:
    print('== 环境 ==')
    print(f'  Python {sys.version.split()[0]}')
    print(f'  numpy {np.__version__}, matplotlib {matplotlib.__version__}')
    grid_x, grid_fx = grid_search()
    print('== 独立网格搜索(10^5 等分)==')
    print(f'  网格最优 x = {grid_x:.15f}')
    print(f'  网格最优 fx = {grid_fx:.15f}')
    print(f'  镜像峰(π − x)fx = {objective(math.pi - grid_x):.15f}(与网格最优等高,函数关于 π/2 对称)')
    slow_traj, slow_best, slow_accept, slow_worse, slow_hi = run_slow()
    fast_traj, fast_best, fast_accept = run_fast()
    run_seeds()
    make_figure(slow_traj, fast_traj, grid_x, grid_fx)

    # —— 与前端 TS 测试钉死值一致(容差 1e-9;acceptCount 为整数应精确相等)——
    print('== 与 TS 测试钉死值交叉核对 ==')
    assert abs(grid_fx - GRID_FX) < 1e-9, '网格最优 fx 与 TS 钉死值不一致'
    assert abs(grid_x - GRID_X) < 1e-9, '网格最优 x 与 TS 钉死值不一致'
    assert abs(slow_best['fx'] - SLOW_BEST_FX) < 1e-9, '慢冷却 best.fx 与 TS 钉死值不一致'
    assert abs(slow_best['x'] - SLOW_BEST_X) < 1e-9, '慢冷却 best.x 与 TS 钉死值不一致'
    assert slow_accept == SLOW_ACCEPT, '慢冷却 acceptCount 与 TS 钉死值不一致'
    assert slow_worse == SLOW_WORSE, '慢冷却接受更差解次数与 TS 钉死值不一致'
    assert abs(fast_best['fx'] - FAST_BEST_FX) < 1e-9, '快冷却 best.fx 与 TS 钉死值不一致'
    assert abs(fast_best['x'] - FAST_BEST_X) < 1e-9, '快冷却 best.x 与 TS 钉死值不一致'
    assert fast_accept == FAST_ACCEPT, '快冷却 acceptCount 与 TS 钉死值不一致'
    print('  全部交叉核对通过')
    print('== 全部断言通过 ==')


if __name__ == '__main__':
    main()

运行方式 ​

bash
cd mathmodel-faq
pip install -r examples/requirements.txt   # numpy / matplotlib(本算例仅用这两个)
python examples/simulated_annealing.py

依赖列表见仓库 examples/requirements.txt(本算例只用 numpy 与 matplotlib)。本机实测环境:Python 3.14.8、numpy 2.5.3、matplotlib 3.11.2。脚本不联网、不用付费 API;任何一条断言失败都会以非零退出码退出。

输出结果(本机实际运行) ​

text
== 环境 ==
  Python 3.14.8
  numpy 2.5.3, matplotlib 3.11.2
== 独立网格搜索(10^5 等分)==
  网格最优 x = 0.701643303252744
  网格最优 fx = 1.075828705133744
  镜像峰(π − x)fx = 1.075828705133744(与网格最优等高,函数关于 π/2 对称)
== 慢冷却(应跳出局部最优、收敛到全局最优)==
  参数: x0=4.0, t0=2.0, alpha=0.99, iterations=2000, seed=42
  best.x = 2.440037527307869
  best.fx = 1.075828675286362
  acceptCount = 468  (总接受率 0.234000)
  接受更差解次数 = 226
  高温段(前100步)接受率 = 0.940000
== 快冷却(应陷入局部最优)==
  参数: x0=4.0, t0=0.05, alpha=0.9, iterations=200, seed=42
  best.x = 4.712739312276244
  best.fx = -0.500000214781735
  acceptCount = 18  (总接受率 0.090000)
  接受更差解次数 = 3
== 不同 seed 对比(同一慢冷却参数,轨迹不同)==
  seed=42: best.x=2.439661223348, best.fx=1.075828557721, final.x=2.436615372263, final.fx=1.075804093926
  seed=7: best.x=2.439855546504, best.fx=1.075828698318, final.x=2.438016263302, final.fx=1.075820538982
  seed=123: best.x=2.439749387093, best.fx=1.075828642650, final.x=2.439357976243, final.fx=1.075827997560
== 绘图已保存到 …docs\public\examples\simulated-annealing-demo.png ==
== 与 TS 测试钉死值交叉核对 ==
  全部交叉核对通过
== 全部断言通过 ==

结果图 ​

模拟退火慢/快冷却对照:f(x) 曲线、轨迹、best-so-far 与温度曲线

关键参数 ​

参数含义本算例取值与效果
t0(初始温度)决定初期接受劣解的程度2 → 慢冷却跳出局部最优;0.05 → 快冷却陷入
α(冷却系数)每步温度乘子,越接近 1 冷却越慢0.99 收敛;0.9 过快
iterations迭代上限2000 足够收敛;200 时快冷却早已卡住
seed随机种子,固定后轨迹可复现42 / 7 / 123 得到不同轨迹

常见错误 ​

  • 冷却太快:t0 太小或 α 太小会让算法退化成贪婪爬山、陷入局部最优。先做慢/快对照,确认结果对冷却速度的敏感度(优化算法无法收敛怎么办)。
  • 随机不设种子:不固定 seed 时每次运行轨迹不同、结果不可复现。固定 seed 并记录进报告(代码能够运行,但结果无法复现怎么办、多次运行得到不同结果怎么办)。
  • 把随机轨迹当确定性结论:单次运行的 best 值是随机变量的实现,不是严格最优。应固定 seed 重复多次或报告多次运行的分布,并用独立基准(网格搜索/枚举)核对。
  • 宣称「证明了全局最优」:几何冷却没有全局最优的理论保证;除非使用(极慢的)对数冷却并达到理论条件,否则只能说「近似全局最优」。

专业速查 ​

假设 ​

假设说明
邻域可达从任意解经过有限次扰动能到达全局最优附近
目标可评估每次候选都要能计算 f(x),且评估代价可接受
温度能持续下降采用几何/线性/对数冷却时 T 逐步趋近 0
随机源足够随机用可复现的确定性 PRNG(固定 seed)比系统随机更利于复现

参数 ​

参数建议
t0足够高,使初期接受率接近 1;可从高到低试
α0.8–0.999;越接近 1 越慢越稳
扰动尺度与变量尺度匹配;本算例为 U(−0.2,0.2)⋅(b−a)/(2π)
停止条件固定迭代次数,或温度低于阈值 / 若干步无改进

复杂度与优缺点 ​

维度内容
时间复杂度O(iterations×每次评估代价)
空间复杂度只存当前解为 O(1);若保留全轨迹为 O(iterations)
优点实现简单、易跳出局部最优、对目标函数几乎无光滑性要求、可并行多次启动
缺点无全局最优保证、对冷却参数敏感、目标昂贵时耗时、高维时扰动设计更难

指标 ​

指标说明
best.fx运行中记录到的最优目标值,是最终交付的「解」
acceptCount / 接受率被接受候选的比例;高温段应高、低温段应低
接受更差解次数衡量「探索性」;为 0 说明已退化为贪婪爬山
温度曲线确认 T 单调下降(几何冷却)

高频问题(FAQ) ​

问题回答
为什么接受更差的解?为了翻过山谷、跳出局部最优,接受概率 exp⁡(Δ/T) 由温度控制
如何选 t0 和 α?t0 高到初期接受率接近 1;α 从 0.95 起调,越接近 1 越慢越稳
模拟退火一定能找到全局最优吗?不能保证;理论保证需要极慢(对数)冷却,实践中只求近似
最小化问题怎么用?对目标取负(或把 Δ 与接受准则的符号反过来)
和蒙特卡洛、爬山法什么关系?接受准则来自 Boltzmann 分布;接受劣解是相对贪婪爬山的关键区别

双语言实验 ​

继续最大化 f(x)=sin⁡x+0.5sin⁡(3x),区间是 [0,2π]。为了单独观察冷却速度的影响,两组都从 x=4、初温 0.5 开始,共运行 700 步。候选步长统一从 [−0.25,0.25] 取,越界裁剪。两组使用相同的整数递推种子,每轮都取两个数,一个生成候选步长,一个用于判断是否接受。这样,拒绝分支也不会造成两组随机流错位。

接受概率如何随冷却改变 ​

同一个使目标值下降 0.1 的候选,在温度为 0.5 时接受概率约为 e−0.2=0.819,温度降到 0.05 时变为 e−2=0.135。代码先计算新候选与当前解的差 Δ。若候选较差,比较 log⁡u 与 Δ/T,它与 u<exp⁡(Δ/T) 等价,也避免直接计算很小的指数。最佳值另存,所以曲线中的当前值可以下降,历史最佳值只能不变或上升。冷却发生在每轮接受判断之后,更新 Tt+1=αTt。

运行原理实现 ​

下载 Python 源码 · 下载 MATLAB 源码

  • Python 环境安装 python -m pip install numpy matplotlib 后,在下载目录运行 python mmf_simulated_annealing.py。
  • MATLAB 在下载目录运行 result = mmf_simulated_annealing(),用基础数值和绘图函数,无需工具箱。

固定提议序列与随机阈值,演示退火可接受较差的当前状态,同时单独保存最优历史。第一步以约 0.368 的概率接受上坡,第三步拒绝上坡。

最简版依赖 Python:无第三方依赖。MATLAB:基础功能,无需额外工具箱。

在源码所在目录运行 python mmf_min_simulated_annealing.py

py
import json
from math import exp

current, best = 0, 0
temperatures = [1, .5, .25]
proposals = [1, 0, 2]
uniforms = [.2, .9, .3]
accepted = []
probabilities = []
for proposal, temperature, threshold in zip(proposals, temperatures, uniforms):
    # 目标是 x²。下坡概率为 1,上坡概率随温度降低而减小。
    change = proposal ** 2 - current ** 2
    probability = exp(-max(change, 0) / temperature)
    probabilities.append(probability)
    take = threshold < probability
    accepted.append(take)
    if take:
        current = proposal
        if current ** 2 < best ** 2:
            best = current
assert accepted == [True, True, False] and best == 0
result = {"probabilities": probabilities, "accepted": accepted, "best_position": best, "final_position": current}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))
下载当前源码

Python 用行记录并在运行结束后转成数组,MATLAB 预先分配“步数加一 × 四列”的轨迹矩阵。初始化行分别位于索引 0 和 1。两种输出的第一、第二项依次对应 α=0.995 与 0.92。先逐项核对总接受次数和劣解接受次数,再比较最终温度和历史最佳目标值。两幅曲线图分别展示温度随步数下降和历史最佳怎样累计。有限网格参考约 1.075829,目标峰的对称性意味着两个位置可以具有同样的高值。MATLAB 的 simulannealbnd 需要 Global Optimization Toolbox,也采用最小化接口;默认候选分布、接受和再退火策略与本课原理实现不同。 MathWorks 全局优化求解器

参数练习 ​

保持初温、起点、种子和预算固定。只比较 α=0.995 与 0.92 的劣解接受次数和最佳目标值。在图上找出当前值和历史最佳分开的时刻。

参考答案

原理实验中两个系数分别接受了 207 次和 14 次严格劣解。较慢的一组到达 f≈1.075828 的高值区,较快的一组停在 f≈−0.500000 的局部峰附近。慢冷却组即使找到高点,后来也可以接受稍低的当前值,因此最终位置可以与历史最佳位置不同。这个对照固定了一个种子,换种子后两组可能都到达高值区,或都没有到达。比较两种冷却策略的可靠性需要多次重复并报告达到目标区的比例。

关联文章 ​

MathModel FAQ · 数学建模知识库