想象你是一位探险队长，手里只有一张等高线密密麻麻的旧地图——每一处地形都代表一种可能的因果结构，但地图上没有标记告诉你哪个山谷最深、哪里藏着救命的水源。你真正的目标，是找到整片山脉里最深的那座山谷：山谷越深，对应的因果图对观测数据的解释就越漂亮。 问题在于，山脉中假谷遍布。如果你只走“永远向下”的路——也就是贪心策略——很快就会陷进一座“看起来很深”的假谷，再也出不来。什么时候该硬着头皮翻过山脊，赌一赌山那边有更深的谷？模拟退火给出了答案：像锻造金属一样，先烧红（高温）再慢慢冷却。温度高时，探险队敢于接受“暂时变差”的路线，四处跳跃探索；温度降下来，队伍越来越谨慎，只肯小幅优化；最终停在最满意的山谷扎营。 这篇文章，就是带你跟随这支探险队，从出发、翻山到扎营复盘，完整走一遍模拟退火因果搜索的旅程——理解它为什么能跳出局部最优、如何保证找到合法因果图、实践中踩过的坑，以及怎样把它用到基因调控、数据血缘等真实场景中。

岗位关联

对 AI 从业者而言，掌握模拟退火因果搜索不只是多会一个优化算法，更是在可解释性与因果推断方向上建立“从观测数据还原真实结构”的工程能力——这是数据可信层建设与根因分析中的硬核技能。

目录
  1. 可视化演示
  2. 概念与起源
  3. 核心原理
  4. 算法流程
  5. 关键技术
  6. 工程实践
  7. 典型应用
  8. 评估与局限
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示模拟退火在因果发现中的能量景观搜索、Metropolis接受准则四种场景，以及几何冷却调度下温度与最优解的演化过程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

能量景观搜索 高温阶段：接受劣解，广泛探索状态空间 低温阶段：趋于收敛，锁定最优DAG结构 P(accept)=exp(-dE/T) 模拟退火通过概率性接受劣解跳出局部最优

概念与起源

探险队的第一课，是理解这张“地图”从哪来。冶金工匠早就知道：铁块烧得通红，再让它慢慢冷却，会比急急忙忙浇水淬火更坚韧——因为缓慢降温给了内部原子充足的时间，让它们从杂乱无章一路调整到能量最低的规则排列。物理学家把这套“先高温后缓冷”的经验提炼成模拟退火算法，探险队正是从工匠的火炉里借来了这份耐心。

放到因果发现里，“地图”就是所有可能的因果有向无环图（DAG）：每个节点是一个变量，每条有向边表示一个因到果的直接影响。我们的任务是输入观测数据（一堆样本），输出一张最可能的DAG。可问题来了——候选图的数量比星星还多：变量越多，合法DAG的数量呈超指数爆发式增长，5个变量就有约3万张图，10个变量超过 \(4\times10^{18}\) 张，穷举法当场破产。

所以探险队需要一个“深度计”来比较任意两座山谷谁更深，这就是得分函数。最常用的是贝叶斯信息准则（BIC），本质上是“拟合优度 − 复杂度惩罚”：既要求图能充分解释数据，又不允许堆砌多余的边来过度拟合。

有了深度计，探险队终于可以出发了。但地图实在太大，队伍不可能把每个山谷都走一遍——接下来要学的，就是如何在“爬山还是翻山”之间做聪明的取舍。

BIC(G;D)=log⁡P(D∣G)−d2log⁡n\mathrm{BIC}(\mathcal{G}; D) = \log P(D \mid \mathcal{G}) - \frac{d}{2}\log n
公式含义：BIC 把“数据 D 由因果图 G 生成的可能性”减去“模型复杂度惩罚”，值越大越好；它是探险队手里的深度计。
  1. 似然项数据在给定因果图下的对数似然，图越能精确复现数据的联合分布，这一项越大。
    log⁡P(D∣G)\log P(D \mid \mathcal{G})
  2. 惩罚项d 是图的参数个数，n 是样本量；边越多、参数越多，惩罚越重。
    d2log⁡n\frac{d}{2}\log n
  3. 平衡机制整体等于拟合项减惩罚项，天然偏爱“简洁而解释力强”的图。
    BIC=拟合项−惩罚项\mathrm{BIC} = \text{拟合项} - \text{惩罚项}

核心原理

探险队走到岔路口：眼前一个小坡通往一片看起来挺深的洼地，但老队员记得远处山脊后似乎有更好看的等高线。贪心的新队员说“往下走”，可队长摇摇头——当年在山里迷路三天，就是因为只肯往下走，最后困在假谷里。他翻开笔记本，记着工匠的秘诀：状态差一点不要紧，关键看“胆子”有多大。

这个“胆子”就是温度 T。模拟退火每走一步，会在当前的DAG上做一个小改动（比如加一条边）得到候选图。如果候选图得分更高，直接接受；如果更低，也不急着拒绝，而是以某个概率接受它——这个概率由 Metropolis 准则给出。理论上，当温度按照足够慢的对数计划冷却、迭代次数趋于无穷时，算法会以概率 1 收敛到全局最优，这就是退火区别于贪心的根本底气。

就这样，探险队在烈日当空时敢翻大山（高温高接受率），太阳西斜时只肯翻小坡（低温低接受率），天色全黑后干脆不走回头路。温度这只“看不见的手”，指挥队伍从横冲直撞逐步过渡到精雕细琢。

P(接受较差解)=exp⁡(Snew−ScurT),Snew<ScurP(\text{接受较差解}) = \exp\left(\frac{S_{\text{new}} - S_{\text{cur}}}{T}\right), \qquad S_{\text{new}} < S_{\text{cur}}
公式含义：接受“变差一步”的概率由得分差与温度共同决定——差得越小、温度越高，越容易接受；这相当于探险队“愿意翻山的勇气”。
  1. 得分差候选分数减当前分数为负，说明暂时吃亏；绝对值越小，越值得冒险一试。
    ΔS=Snew−Scur<0\Delta S = S_{\mathrm{new}} - S_{\mathrm{cur}} < 0
  2. 温度归一把得分差除以当前温度 T，高温时比值接近零，低温时负得更多。
    ΔST\frac{\Delta S}{T}
  3. 指数映射exp 把比值映射到 (0,1) 区间，作为接受较差解的概率。
    exp⁡(ΔST)∈(0,1)\exp\left(\frac{\Delta S}{T}\right) \in (0, 1)

算法流程

一次完整的寻谷远征，其实有固定的剧本：清晨整装出发，白天四处试探，每隔一段时间队长宣布“降温了，步子收敛一点”，傍晚评估成果，天黑前决定是否延长旅途。探险队把这套流程叫作“算法流程”，每一步都环环相扣。

算法从一个初始DAG出发（通常选空图或随机图），然后循环执行四件事：生成邻域候选解、按 Metropolis 准则决定是否接受、内循环若干次后降温、检查终止条件。内循环保证每个温度下都充分试探，外循环负责把温度层层压低。

每当队长喊出“0.95 倍降温”，队伍的性格就沉稳一分。等温度降到阈值以下，或者连续好几轮最优解都纹丝不动，队长便宣布收工扎营——算法吐出当前最优DAG，这趟旅程画上句号。

Tk=T0⋅αk,k=0,1,2,…T_{k} = T_{0} \cdot \alpha^{k}, \qquad k = 0, 1, 2, \ldots
公式含义：第 k 个温度层的温度等于初始温度乘以衰减因子 α 的 k 次方；α 越接近 1，降温越慢，搜索越充分。
  1. 初始温度决定出发时的“胆量上限”，太大会浪费探索，太小会退化成贪心。
    T0T_0
  2. 衰减因子每次降温都乘上它，α 通常取 0.8~0.99，是调参时最重要的旋钮。
    α∈[0.8,0.99]\alpha \in [0.8, 0.99]
  3. 温度层推进k 记录已降温的轮数，相邻两轮温度之比恒为 α，呈指数下降。
    Tk+1Tk=α\frac{T_{k+1}}{T_k} = \alpha

关键技术

远征路上有条铁律：探险队必须沿着小路走，不能瞬移，更不能绕回自己走过的地方兜圈子。在因果搜索里，这条铁律对应两件事——邻域算子（小路）和 DAG 无环约束（不许兜圈子）。

邻域算子就是“一步改动”的三种工具：加一条边、删一条边、反转一条边。每一步从当前图出发，随机挑一种工具改一下，就得到候选图。难点在于：加边时如果新边会与已有路径构成环，这个候选图就不合法——因果图里不允许“A 导致 B、B 又导致 A”的循环逻辑。因此加边前必须做环检测：从新边的终点出发，用 BFS/DFS 做祖先可达判断，看它能否绕回起点。冷却计划同样需要选择：除了指数冷却，线性冷却在需要更平滑温度变化时也很常用。

掌握了小路和铁律，队员们的每一步都走得又快又稳：改了图先问一句“有没有绕圈”，绕圈就重来；温度按计划层层下降；偶尔根据实际气温微调衰减率——这就是探险队随身携带的“装备工具箱”。

Tk=T01+c⋅kT_k = \frac{T_0}{1 + c \cdot k}
公式含义：这是线性冷却计划——温度随迭代次数 k 增加而反比例下降，分母中的常数 c 控制下降速率，适合对探索时间要求较长的任务。
  1. 分子起点T0 决定初始探索强度，与指数冷却中的含义一致。
    T0T_0
  2. 分母增长\(1+ck\) 随迭代次数线性增大，温度被逐渐压低。
    1+c⋅k1 + c \cdot k
  3. 冷却趋势当 k 趋近无穷时温度趋于 0，搜索从“大胆探索”平滑过渡到“只做改善”。
    lim⁡k→∞Tk=0\lim_{k \to \infty} T_k = 0

工程实践

光有算法还不够，出发前的装备校准往往决定远征成败。老队长每次带队都要做四件事：选深度计型号、定出发胆量、算体力消耗率、约好收队信号。对应到工程实践，就是得分函数选择、初始化策略、超参数配置与收敛判据。

先说得分函数：BIC 适合中等样本、偏爱简洁；数据量小或变量为离散时，BDeu 往往更稳健。初始化上，从空图开始最保守；如果对领域有先验知识（比如已知某些边一定存在），可以先固定再搜索。超参数方面，衰变率通常取 0.9~0.99，内循环次数设为邻域规模的数倍，并建议多次随机重启取最优，以对冲随机性。

老队长常说：装备不用最贵，匹配才是王道。同样的参数在这片山谷管用，换一片山就得重新校准——工程实践的本质，就是不断用数据反馈微调，让退火过程既走得远，又落得稳。

T0≈c⋅E[∣ΔS∣],c∈[2,10]T_0 \approx c \cdot \mathbb{E}\left[\left|\Delta S\right|\right], \qquad c \in [2, 10]
公式含义：初始温度应该是“平均一次改动带来的得分差”的 2~10 倍，让早期每步都有合理概率接受较差候选，而不是全盘接受或全盘拒绝。
  1. 差值统计量随机试几百次邻域操作，统计得分变化幅度的均值，作为温度标尺。
    E[∣ΔS∣]\mathbb{E}\left[\left|\Delta S\right|\right]
  2. 倍数调节c 取 10 偏“豪放”、探索充分但慢，取 2 偏“保守”、接近贪心，一般从 5 开始调。
    c∈[2,10]c \in [2, 10]
  3. 量级匹配原则温度与得分差同量级时接受概率才“恰到好处”，跨了好几个量级就会失效。
    T0=O(E[∣ΔS∣])T_0 = O\left(\mathbb{E}[|\Delta S|]\right)

典型应用

学会了扎营技巧，探险队终于要接真实地图的任务了。这些年，模拟退火因果搜索在好几个“凶险山谷”立下功劳，其中最著名的是基因调控图与数据血缘图。

在基因调控推断中，输入是成千上万个细胞的基因表达量矩阵，目标是恢复“哪个转录因子调控哪个靶基因”的调控网络。由于存在大量共表达干扰，相关分析会画出密密麻麻的假边；用 BIC 得分配合退火搜索，可以砍掉绝大多数冗余边，只留下得分显著优化的调控结构。这类任务的基础假设，是变量服从线性高斯结构方程模型。

从基因到数据管线，地图在变，但探险队的方法论不变：先画出变量，再定好深度计，最后让退火慢慢找到深谷。这也是为什么这套算法在因果推断框架中始终占据一席之地。

Xj=∑i∈Pa(j)wijXi+εj,εj∼N(0,σj2)X_j = \sum_{i \in \mathrm{Pa}(j)} w_{ij} X_i + \varepsilon_j, \qquad \varepsilon_j \sim \mathcal{N}(0, \sigma_j^2)
公式含义：每个变量的值由它的因果父节点线性叠加生成，再加上独立噪声；这是 BIC 得分计算的基础假设，也规定了数据生成方向的“因果律”。
  1. 父节点集Pa(j) 是所有直接导致 Xj 的变量，正是 DAG 中有向边指向 j 的那些节点。
    Pa(j)={ i∣i→j∈G }\mathrm{Pa}(j) = \{\, i \mid i \to j \in \mathcal{G} \,\}
  2. 路径系数wij 表示从 Xi 到 Xj 的因果强度，得分回归阶段会估计它。
    wijw_{ij}
  3. 独立噪声εj 服从零均值正态分布，保证剩余方差可以作为拟合残差评估节点的解释程度。
    εj∼N(0,σj2)\varepsilon_j \sim \mathcal{N}(0, \sigma_j^2)

评估与局限

旅程结束，队长要复盘：我们找到的山谷到底是不是最深的那一个？这需要一张“标准答案地图”——在模拟实验中，我们事先知道真实因果图，于是可以精确度量算法找到的图跟真图差多远。比起贪心队员永远向下走、困在假谷里交出一张错误百出的图，退火队伍愿意绕远路，通常能得到结构差异更小的答案。

最常用的度量叫结构汉明距离（SHD）：逐边比较学习图与真实图，凡是“多了的边、少了的边、方向反了的边”都算一次差异，加总就是 SHD。SHD 为 0 说明完美还原。

复盘也暴露了探险队的短板：搜到的图可能与真图得分难分伯仲——马尔可夫等价类在图谱上无法用观测数据区分方向；超指数搜索空间让大变量集跑得很慢；随机性导致每次运行结果略有差异。队长把这些写进探险日志：山外有山，但只要清楚地图的边界，每一次远征都离真相更近一步。

SHD(G^,G∗)=∣E(G^)⊕E(G∗)∣\mathrm{SHD}(\hat{\mathcal{G}}, \mathcal{G}^{*}) = \left| E(\hat{\mathcal{G}}) \oplus E(\mathcal{G}^{*}) \right|
公式含义：两张图的边集合做对称差——只存在于其中一张图的边全部数出来，就是 SHD；数值越小，算法还原得越准。
  1. 学习图模拟退火输出的候选 DAG，就是我们找到的“山谷”。
    G^\hat{\mathcal{G}}
  2. 真实图数据生成时使用的真实因果结构，只有实验环境下才拿得到。
    G∗\mathcal{G}^{*}
  3. 对称差把多边、缺边、反向边统一折算成“只属于其中一张图”的边数。
    E(G^)⊕E(G∗)E(\hat{\mathcal{G}}) \oplus E(\mathcal{G}^{*})

AI 应用场景

基因调控网络推断

阶段：数据建模与因果发现

解决的问题：传统共表达分析只能给出“相关对”，无法判断谁调控谁；全基因组候选边多达数百万条，人工标注根本不可行。模拟退火在 BIC 得分驱动下，直接从表达矩阵搜出简洁 DAG，给出可解释的“调控方向”。

具体案例：某癌症研究团队对 500 例肿瘤样本的 30 个转录因子表达谱运行模拟退火因果搜索，输出含 21 条边的调控 DAG；其中一条“TF-A → 靶基因 B”的边被后续 siRNA 敲低实验验证，成为候选药物靶点。整个过程从数据到候选网络仅数小时。

数据血缘与异常根因定位

阶段：数据治理与可观测性归因

解决的问题：指标异常时，人工沿血缘反查上游链路，常常“查一路、猜一路”，慢且容易漏。把字段血缘关系压缩成候选边集合，用模拟退火搜索“最能解释异常指标变动的源头节点”，把经验排查变成可复现的因果归因。

具体案例：某互联网数据平台核心指标“日活”骤降12%，团队将 200 个相关调度任务与字段作为节点，用模拟退火因果搜索在分钟级定位到三天前上游一张表 join 键被误改；修复后指标恢复，MTTR 从 4 小时降到 25 分钟。

营销渠道归因分析

阶段：用户行为因果建模

解决的问题：多渠道投放中“曝光→点击→转化”存在大量伪相关，末次点击归因会系统性高估收尾渠道；用 DAG 搜索学习各渠道对转化的真实驱动路径，避免预算错配。

具体案例：某电商团队对 60 个渠道的曝光与转化序列做模拟退火因果搜索，识别出两个“陪跑”渠道并去重投放，预算向因果路径上的核心渠道倾斜后 ROI 提升 18%。

Python 演示

python101 行
# 模拟退火因果搜索:从观测数据中学习因果DAGimport numpy as npfrom copy import deepcopyfrom collections import deque def make_data(n, true_edges, N=1500, noise=0.6):    B = np.zeros((n, n))    for i, j, w in true_edges:        B[j, i] = w    X = np.zeros((N, n))    for j in range(n):        pa = np.nonzero(B[j])[0]        if len(pa):            X[:, j] = X[:, pa] @ B[j, pa] + noise * np.random.randn(N)        else:            X[:, j] = noise * np.random.randn(N)    return X, B def bic(X, B):    N, n = X.shape    rss = 0.0    for j in range(n):        pa = np.nonzero(B[j])[0]        if len(pa):            coef, *_ = np.linalg.lstsq(X[:, pa], X[:, j], rcond=None)            resid = X[:, j] - X[:, pa] @ coef        else:            resid = X[:, j] - X[:, j].mean()        rss += float(resid @ resid)    k = int(np.count_nonzero(B))    return N * np.log(rss / N) + (k + n) * np.log(N) def reachable(B, start):    n = len(B)    seen = [False] * n    seen[start] = True    q = deque([start])    while q:        u = q.popleft()        for v in np.nonzero(B[:, u])[0]:            if not seen[v]:                seen[v] = True                q.append(v)    return seen def neighbour(B):    n = len(B)    for _ in range(50):        B2 = deepcopy(B)        i, j = np.random.randint(0, n, size=2)        if i == j:            continue        op = np.random.randint(3)        if op == 0 and B[j, i] == 0:            if not reachable(B2, j)[i]:                B2[j, i] = np.random.uniform(0.3, 0.8)                return B2        elif op == 1 and B[j, i] != 0:            B2[j, i] = 0.0            return B2        elif op == 2 and B[j, i] != 0:            B2[j, i] = 0.0            B2[i, j] = np.random.uniform(0.3, 0.8)            return B2    return deepcopy(B) def simulated_annealing(X, T0=8.0, T_min=0.05, alpha=0.92, inner=40, seed=7):    np.random.seed(seed)    n = X.shape[1]    cur = np.zeros((n, n))    best = cur.copy()    best_score = cur_score = bic(X, cur)    T = T0    while T > T_min:        for _ in range(inner):            nxt = neighbour(cur)            nxt_score = bic(X, nxt)            delta = cur_score - nxt_score            if delta > 0 or np.random.rand() < np.exp(delta / T):                cur, cur_score = nxt, nxt_score                if cur_score < best_score:                    best, best_score = cur.copy(), cur_score        T *= alpha    return best def shd(B_true, B_est):    n = len(B_true)    diff = 0    for j in range(n):        for i in range(n):            if i != j:                diff += int((B_true[j, i] != 0) != (B_est[j, i] != 0))    return diff if __name__ == "__main__":    true_edges = [(0, 1, 0.8), (0, 2, 0.6), (1, 3, 0.7), (2, 4, 0.5), (3, 4, 0.4)]    X, B_true = make_data(5, true_edges)    B_est = simulated_annealing(X, seed=7)    print("真实DAG边数:", int(np.count_nonzero(B_true)))    print("学习DAG边数:", int(np.count_nonzero(B_est)))    print("SHD:", shd(B_true, B_est))
目的：完整实现“生成线性高斯数据 → BIC 得分 → 邻域生成 → Metropolis 接受 → 指数降温”的模拟退火因果搜索，并输出学习图与真实图的结构汉明距离。
  1. X[:, j] = X[:, pa] @ B[j, pa] + noise * np.random.randn(N)按父节点线性组合再加噪声，生成符合因果方向的观测数据。
  2. coef, *_ = np.linalg.lstsq(X[:, pa], X[:, j], rcond=None)用最小二乘回归估计父节点到子节点的因果强度。
  3. N * np.log(rss / N) + (k + n) * np.log(N)BIC 得分：拟合残差项加上复杂度惩罚，越小越优。
  4. for v in np.nonzero(B[:, u])[0]:沿有向边做 BFS，收集从 start 出发可达的所有节点。
  5. if not reachable(B2, j)[i]:只有 j 不能到达 i 时才允许加边 i→j，保证无环。
  6. B2[i, j] = np.random.uniform(0.3, 0.8)反转边方向并赋新权重，构成第三种邻域算子。
  7. np.random.rand() < np.exp(delta / T)Metropolis 准则：得分差越小、温度越高，越容易接受较差候选。
  8. T *= alpha每个温度层内循环结束后按衰减因子降温，逐步收敛。
  9. diff += int((B_true[j, i] != 0) != (B_est[j, i] != 0))边存在性不一致即计入 SHD 一次差异。

常见误区

误区听说模拟退火是全局优化算法，就认为它每次运行都会给出真实因果结构，只要跑得足够久。

正解模拟退火只有理论上的概率收敛保证——需要迭代次数趋于无穷、温度按足够慢的计划冷却等理想条件。实际中有限迭代、随机初始化、冷却过快都可能停在次优图。应对办法是多次随机重启取最优，并配合后验分析判断解的稳定性，而不是把单次结果当作“标准答案”。

为何常见：教材强调“全局优化”能力，却很少强调前提条件；加上“退火”这个名字自带科学光环，容易被过度信任。

误区温度越高探索越充分，那把 T0 设成 100 甚至更大，反正最后会降温，总没问题。

正解T0 过大时 exp(ΔS/T)≈1，算法前几千步几乎完全随机游走，白白浪费计算资源；而且需要配合更多迭代轮数，否则根本到不了低温区就被迫终止。经验做法是先随机试几百次邻域操作，统计 |ΔS| 的均值，再取它的 2~10 倍作为 T0。

为何常见：直观上“温度高=探索多”没错，但忽略了探索要“有效”——像爬山一样，白费体力的乱走没有意义。

误区算法输出的得分最优 DAG，就是真实的因果结构，可以直接拿去写报告、做决策。

正解同一得分下可能存在多个马尔可夫等价类图（如 X→Y 与 X←Y 对观测数据不可区分），BIC 本身也只是有限样本下的估计，可能带偏差。正确的做法是把搜索出来的图当作“与数据一致的候选因果结构”，再结合干预实验、时间先后或领域知识打破等价类，才能谈因果方向。

为何常见：把“统计拟合最好”等同为“因果为真”，混淆了统计模型与因果模型——这是因果推断领域最普遍的认知误区。

误区反正有得分函数把关，加边生成环也没关系，跑起来再说。

正解DAG 是因果图的基本约束，带环的“因果图”没有因果解释，而且回归与得分计算在循环结构下会出现数值问题。每加一条边之前，都必须从终点做祖先可达判断（BFS/DFS），确认起点不在终点的祖先集合里。

为何常见：初学时把搜索当作“黑盒优化”，忽略了搜索空间内部的合法结构约束——工具书里一句话带过，实战时最容易漏。

面试题

Q1. 模拟退火算法的思想最早来源于哪种物理过程？

单选题 · easy

  • A.金属加热后缓慢冷却结晶← 正确答案
  • B.液体在真空中快速沸腾
  • C.晶体在高温下瞬间熔融
  • D.气体在管道内绝热膨胀

答案：A。金属退火把材料加热到高温再缓慢冷却，原子从无序逐步排列到低能稳定态；模拟退火借用的正是“缓慢降温才能到达全局最优”这一物理直觉。沸腾、熔融和绝热膨胀都没有“缓慢结晶”的结构对应。

Q2. 在模拟退火中，Metropolis 准则的核心作用是什么？

单选题 · easy

  • A.以一定概率接受较差解以便跳出局部最优← 正确答案
  • B.无条件接受出现的每一个较差候选解
  • C.拒绝所有新候选解以保证结果稳定
  • D.只接受当前得分更高的候选解

答案：A。Metropolis 准则用 exp(ΔS/T) 的概率接受“暂时更差”的解：高温时几乎照单全收，低温时几乎全拒。这让搜索既能留在好区域，又有机会翻山。无条件接受或全盘拒绝，都会让退火退化为纯随机或贪心算法。

Q3. 当温度趋近于无穷大时，接受任意较差解的概率趋近于什么？

单选题 · easy

  • A.概率趋近于零
  • B.概率趋近于一半
  • C.概率趋近于一← 正确答案
  • D.概率等于得分差

答案：C。接受概率 P=exp(ΔS/T)，其中 ΔS≤0。当 T→∞ 时，指数内的负分数趋近于 0，exp(0)=1，所以差解几乎全被接受。温度越高“容忍度”越高，这正是高温期大范围探索的数学来源。

Q4. 5 个变量的因果图搜索空间有多大？

单选题 · mid

  • A.大约25种可能图
  • B.大约3万种可能图← 正确答案
  • C.大约300万种可能图
  • D.搜索空间为无穷多

答案：B。5 个变量的合法 DAG 共有 29281 个，约 3 万。随着变量数增长，DAG 数量呈超指数增长，10 个变量时超过 4×10^18。这正是需要用模拟退火等启发式搜索而非穷举的原因。

Q5. BIC 得分中的 (d/2)log n 惩罚项主要作用是什么？

单选题 · mid

  • A.奖励结构更稠密的因果图
  • B.提升模型对噪声数据的拟合
  • C.对参数过多的复杂模型施加惩罚← 正确答案
  • D.加速模拟退火的降温进程

答案：C。BIC=拟合似然−复杂度惩罚，惩罚项随参数个数 d 增加而增大，避免“边越多越好”的过拟合。贪心搜索往往因偏好稠密图而留下冗余边，惩罚项正是为平衡拟合度与简洁性而设计。

Q6. 算法卡在局部最优解反复震荡时，更合理的调参方向是什么？

单选题 · mid

  • A.直接降低初始退火温度
  • B.增大衰减因子让降温更快
  • C.提高初始温度并放慢降温← 正确答案
  • D.缩短每个温度层内循环步数

答案：C。卡在局部最优说明“翻山”能力不足或探索时间不够。提高 T0 让早期接受概率更大，放慢降温（α 更接近 1）等于给足翻山与回落的时间。降低温度或加快降温只会更早锁定在当前山谷。

Q7. 给 DAG 添加新边 i→j 之前，正确的成环检测方法是哪种？

单选题 · hard

  • A.判断 j 沿当前有向边能否到达 i← 正确答案
  • B.判断 i 沿当前有向边能否到达 j
  • C.判断图中是否存在孤立节点
  • D.判断图的总边数是否达到上限

答案：A。加边 i→j 会成环，当且仅当图中已存在 j 到 i 的路径，因此从 j 出发做 BFS/DFS 祖先可达判断即可。判断 i 能否到 j 保证的是“反向加边”的安全性，与当前操作恰好相反。

Q8. 下列哪些属于模拟退火因果搜索的邻域算子？

多选题 · mid

  • A.添加一条候选因果边← 正确答案
  • B.删除一条已有因果边← 正确答案
  • C.反转一条因果边的方向← 正确答案
  • D.交换两个随机节点的位置

答案：ABC。DAG 邻域通常由加边、删边、反转边三种基本操作构成，覆盖局部结构的所有“一步改动”。交换节点位置改变的是变量命名而非图结构，不属于合法的邻域操作。

Q9. 模拟退火因果搜索的输出与真实因果图不一致，可能的原因有哪些？

多选题 · hard

  • A.迭代次数不足，尚未充分收敛← 正确答案
  • B.数据噪声使得分函数偏好偏移← 正确答案
  • C.马尔可夫等价类在观测数据下不可区分← 正确答案
  • D.得分函数公式本身存在必然错误

答案：ABC。有限迭代会停在次优谷；有限样本噪声会让 BIC 的最优点偏离真图；等价类图（如 X→Y 与 X←Y）对观测数据不可区分，任何基于得分的搜索都选不出唯一真图。标准 BIC 定义并不存在“必然错误”的问题。

Q10. 冷却计划 Tk=T0·α^k 中 α=0.95，退火 100 轮后温度约为初始温度的多少？

单选题 · mid

  • A.大约剩余95%
  • B.大约剩余0.6%← 正确答案
  • C.大约剩余50%
  • D.大约剩余5%

答案：B。0.95^100≈e^{100·ln0.95}≈e^{−5.13}≈0.006，即约 0.6%。这说明指数冷却比直觉“快”得多：看似温和的 0.95，一百轮之后几乎耗尽探索能力，因此 α 的微小调整会显著改变搜索行为。