老周是一位经验丰富的寻宝猎人。这一天他站在一片连绵的群山前，手里只有一个能测“宝藏信号强度”的罗盘——走得越近，指针摆得越猛。任务很明确：找出整片山里信号最强的那座金矿。真正的麻烦在于三点：山多得根本数不清；雾气浓得只能看清脚边两三步；而你不可能在退休前把每寸山坡都踩一遍。老周试过的办法不止一种：有时他闭着眼只管往高处爬；有时他故意带着“温度计”，让自己忽冷忽热地乱跳；有时他干脆叫来一队帮手，大家分头探路、定期碰头交换情报。这些看似普通的登山经验，恰恰就是因果发现中“基于分数方法”最关键的工程环节——搜索策略。本文用老周的故事，讲清楚为什么要在海量因果关系中搜索最优结构、三种主流搜索算法如何工作，以及它们如何权衡探索与利用。

岗位关联

搜索策略直接决定因果结构学习的效率与质量。掌握爬山、模拟退火与遗传算法，是从事因果发现与可信 AI 工程的基本功，也是构建可审计、可干预 AI 系统的安全底座。

目录
  1. 可视化演示
  2. 搜索为何难
  3. 爬山算法
  4. 模拟退火
  5. 遗传算法
  6. 探索与利用
  7. 工程落地
  8. 效果评估
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示爬山法邻域操作寻优、模拟退火温度调度与劣解接受概率、遗传算法种群进化三代操作。

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

爬山法：贪心局部寻优 加边/删边/反转边三种邻域操作 每次选评分提升最大的操作 score(new)-score(old)>0 贪心策略

搜索为何难

老周出发前先在驿站买了一卷“全山脉地形图”。展开一看他傻了眼：地图上标注的山峰密密麻麻，而且这张图还在随心所欲地扩展——每多一个变量，就像地图多了一整条新山脉。真正的宝藏猎人知道，这辈子不可能把每座山都爬一遍。

在因果发现里，这张“山脉图”就是所有可能的因果结构集合。给定 p 个变量，每对变量之间可以连一条有向边，但要保证没有环——这样的有向无环图（DAG）数量用 Robinson 递推可以精确算出。它根本不是线性增长，而是超指数爆炸。

正因为空间太大，寻找最优结构被证明是 NP 难问题，穷举只适用于 4～5 个变量的玩具场景。实用的出路是：让评分函数担任向导，用搜索策略在巨大空间里“走一步看一步”，以有限的计算量逼近全局最优评分。搜索策略的优劣，直接决定结构学习的效率与质量。

所以老周并没有被地图吓退。他收起地图，掏出罗盘，决定用脑子而不是用脚来征服群山——先试最笨的办法。

dp=∑k=1p(−1)k+1(pk) 2k(p−k) dp−k,d0=1\displaystyle d_p = \sum_{k=1}^{p}(-1)^{k+1}\binom{p}{k}\,2^{k(p-k)}\,d_{p-k},\quad d_0 = 1
这个递推式给出 p 个节点上有向无环图的总数，让你直观感受搜索空间的爆炸速度。
  1. 组合项从 p 个节点中选出 k 个节点的组合数，相当于先从地图上圈出 k 座“候选山”，其余节点随后再处理。
    (pk)\displaystyle \binom{p}{k}
  2. 二分连接数被选出的 k 个节点与剩余 p−k 个节点之间，每条有向边可连可不连，共 k(p−k) 个边位置，带来 2 的幂。
    2k(p−k)\displaystyle 2^{k(p-k)}
  3. 容斥递推交替加减不同 k 的项并乘上规模缩小的 d(p−k)，从而去掉所有成环情形，最终得到精确的 DAG 计数。
    dp=∑k=1p(−1)k+1(pk) 2k(p−k) dp−k\displaystyle d_p = \sum_{k=1}^{p}(-1)^{k+1}\binom{p}{k}\,2^{k(p-k)}\,d_{p-k}

爬山算法

老周的第一招最简单：闭眼向上爬。站定一处，向左迈一步试试信号，向右迈一步试试信号，哪边强就往哪边走，反复循环。这个方法上路快、不费脑子，但老周很快发现——他常常停在半山腰的小土包上，看得见远处的大金山，却下不去。

在 DAG 空间里，“迈一步”被定义为一次邻域操作：加一条边、删一条边或反转一条边的方向，同时保证结果仍是无环图。从某个初始图出发，爬山算法每次遍历全部邻域，选择评分最优的那个图作为下一步。

爬山算法是一种纯粹的贪心（利用）策略：它只看一步之内的信息，从不“战略性撤退”。因此它对初始解非常敏感——起点不同，终点天差地别。工程上常用“随机重启”缓解：随机生成多个初始图分别爬山，取其中评分最优的结果。

老周管这个叫“近视登山法”：快是真快，但经常白忙一场。于是他在口袋里揣了一把骰子——爬完一趟不满意，就掷骰子换一座山重新爬，这便是随机重启的朴素智慧。

G←arg⁡min⁡G′∈N(G)S(G′),直到min⁡G′∈N(G)S(G′)≥S(G)\displaystyle G \leftarrow \arg\min_{G' \in \mathcal{N}(G)} S(G'), \quad \text{直到} \quad \min_{G' \in \mathcal{N}(G)} S(G') \ge S(G)
这条更新规则说明爬山只认“眼下最优”，一旦邻域内没有更好的图就立刻停下——这就是它容易陷入局部峰的原因。
  1. 邻域集合与当前图仅相差一条边的所有合法 DAG 的集合，相当于老周一步能踩到的左右两个点位。
    N(G)={ G′∣G′ 与 G 只差一次邻域操作 }\displaystyle \mathcal{N}(G) = \{\, G' \mid G' \text{ 与 } G \text{ 只差一次邻域操作} \,\}
  2. 贪心更新在当前一步能到的地方里挑评分最低的图作为新位置，只比一步，绝不前瞻。
    G←arg⁡min⁡G′∈N(G)S(G′)\displaystyle G \leftarrow \arg\min_{G' \in \mathcal{N}(G)} S(G')
  3. 停止条件当所有邻域评分都不低于当前评分，说明已经站在“一步视野”内的最低点，算法终止。
    min⁡G′∈N(G)S(G′)≥S(G)\displaystyle \min_{G' \in \mathcal{N}(G)} S(G') \ge S(G)

模拟退火

第二次进山，老周学乖了。他给自己装了一支“神奇温度计”：出门时体温很高，脚步发飘，经常放着眼前的上坡不走，反而往谷底乱窜；等太阳落山，体温降下来，他的步伐越来越稳，最终稳稳当当地停在了最大金山上。

这个灵感来自冶金工艺：金属在高温下原子剧烈运动、结构无序；缓慢冷却后，原子才排列成能量最低的晶体。模拟退火把“温度”做成一个参数 T，用接受概率控制搜索的随机性。

每一轮，算法随机生成一个邻域图 G′。若 G′ 评分更好则直接接受；若更差，则以概率 exp(−ΔS/T) 接受，其中 ΔS 是两者评分差。温度按调度（通常指数衰减）逐渐降低，随机跳跃越来越少，最终收敛到爬山式精细搜索。

老周的经验是：把温度当成“好奇心”来管理——年轻时满世界乱跑，成熟后专心挖宝。这正是探索与利用平衡的最美体现。

P(接受较差解)=exp⁡ ⁣(−S(G′)−S(G)T),S(G′)>S(G)\displaystyle P(\text{接受较差解}) = \exp\!\left(-\frac{S(G') - S(G)}{T}\right), \quad S(G') > S(G)
差得越多越难被接受，温度越低也越难被接受——“退火”的精髓在于把随机性当作可调度的资源。
  1. 代价差值新图与当前图的评分差，代表这次“下坡”要损失多少信号强度。
    ΔS=S(G′)−S(G)>0\displaystyle \Delta S = S(G') - S(G) > 0
  2. 温度参数T 越大，指数负值的绝对值越小，接受概率越大；T 越接近 0，概率越接近 0。
    lim⁡T→0+exp⁡ ⁣(−ΔST)=0\displaystyle \lim_{T \to 0^{+}} \exp\!\left(-\frac{\Delta S}{T}\right) = 0
  3. 指数映射指数函数把任意正代价压缩到 (0,1) 区间，成为可比较的概率值。
    e−x=1ex∈(0,1],x≥0\displaystyle e^{-x} = \frac{1}{e^{x}} \in (0,1], \quad x \ge 0

遗传算法

一个人的力量终究有限。第三次寻宝，老周摇来一支二十人的寻宝队。大家从不同山口进山，每隔几天集合一次，把两两的路线图各取一半拼成新路线分给新人；偶尔有人心血来潮拐进一条从没走过的沟谷。几轮下来，整支队伍奇迹般聚到了最大的金矿上。

遗传算法把每个候选 DAG 看成一个“个体”，一组个体构成“种群”。个体优劣由适应度函数衡量：在我们的问题里，评分越低（BIC 越小）适应度越高，就像藏宝图越接近真实金矿越有价值。

每一代，算法按适应度比例选择若干“父母”，通过交叉把两个父代图的边结构混合生成子代，再以一定概率变异（随机执行一次邻域操作）。子代构成新一代种群，替代旧种群，如此迭代直到评分收敛——相当于让一队老周同时进化。

老周发现，遗传算法最妙的地方是“共享”：一个人的迷路信息，通过交叉能变成全队的财富；变异又保证了队伍不会过早统一到同一条错误路线上。

P(个体 i 被选中)=fi∑j=1Nfj,fi=−BIC(Gi)\displaystyle P(\text{个体 } i \text{ 被选中}) = \frac{f_i}{\displaystyle\sum_{j=1}^{N} f_j}, \quad f_i = -\mathrm{BIC}(G_i)
适应度越高，被选为父母的机会越大；负号让“评分越低越好”变成“适应度越高越好”。
  1. 适应度转换用负 BIC 作为适应度，评分越低适应度越高，天然满足“择优”方向。
    fi=−BIC(Gi)\displaystyle f_i = -\mathrm{BIC}(G_i)
  2. 归一化分母把种群所有个体的适应度求和，让每个概率落在 0～1 之间。
    ∑j=1Nfj\displaystyle \sum_{j=1}^{N} f_j
  3. 比例选择个体 i 的适应度占全种群的比例即其被选中概率，数值越大越容易当“父母”。
    Pi=fi∑j=1Nfj\displaystyle P_{i} = \frac{f_i}{\sum_{j=1}^{N} f_j}

探索与利用

寻宝队内部分成了两派：激进派主张多去没标记过的新山脉碰运气，保守派主张守住当前信号最强的山头死磕到底。老周当了和事佬：前期让大家放开了探索，后期统一收网深挖——顺序不能反。

这是搜索算法的“第一性矛盾”：探索（exploration）去未去之处获取新信息，利用（exploitation）在已知最优处深耕获利。纯探索像无头苍蝇，纯利用像井底之蛙。三种算法的性格差异，本质就是它们对这对矛盾的不同取舍。

爬山纯利用不探索；遗传算法用变异维持少量探索；模拟退火则是把“探索权重”做成随时间衰减的调度表——温度就是那个旋钮。

老周把这套时间表贴在营地里：白天探路，傍晚挖宝。道理朴素——先有广度，才有深度。

Tk=αk T0,0<α<1\displaystyle T_k = \alpha^{k}\,T_{0}, \qquad 0 < \alpha < 1
指数降温相当于给探索设定“截止日期”：前期高温海量探索，后期低温专心利用。
  1. 初始温度T₀ 决定开局探索的猛烈程度，类似寻宝队出发时愿意跑多远。
    T0>0\displaystyle T_0 > 0
  2. 衰减因子α 略小于 1，每轮都乘一次，温度呈指数衰减。
    αk=α×α×⋯×α⏟k 次\displaystyle \alpha^{k} = \underbrace{\alpha \times \alpha \times \cdots \times \alpha}_{k \text{ 次}}
  3. 迭代步数k 越大温度越低，调度曲线从“燥热”平滑滑向“冷静”。
    Tk=Tk−1⋅α\displaystyle T_k = T_{k-1} \cdot \alpha

工程落地

理论讲得再好，寻宝队长还要管三件杂事：从哪出发、何时收工、带多少干粮。老周的装备清单，就是搜索算法的工程配置单。

初始解最常见的选择是空图（没有任何边），实现简单且无偏；如果领域专家能给出若干先验边，塞进初始图会让搜索少走很多弯路。停止条件通常是“评分改善小于阈值 ε”或者“达到最大迭代次数 t_max”。

复杂度上，爬山每轮要扫描 O(p²) 个邻域并逐一评分，p 稍大就非常昂贵。工程上常用随机采样邻域子集代替全量扫描，或限制每次只评估少量候选；退火的迭代次数、初始温度和降温系数，遗传的种群大小、交叉变异概率，都需要按数据规模做折中。

老周的忠告：装备不是越贵越好。参数调得太激进，再好的算法也会在超指数空间里迷路；调得太保守，又和爬山没有区别。

停止判定：∣S(Gt+1)−S(Gt)∣<ε或t≥tmax⁡\displaystyle \text{停止判定：}\quad |S(G_{t+1}) - S(G_t)| < \varepsilon \quad \text{或} \quad t \ge t_{\max}
这条停止规则把“差不多行了”写成了可执行的代码：评分连续两轮几乎不动就收工，时间到也收工。
  1. 评分变化量相邻两轮评分差的绝对值，波动很小说明搜索已趋于稳定。
    ∣S(Gt+1)−S(Gt)∣\displaystyle |S(G_{t+1}) - S(G_t)|
  2. 收敛阈值ε 越小搜索越久、结果越精细，等于“信号不再增强就认定到顶”。
    ε>0\displaystyle \varepsilon > 0
  3. 迭代上限t_max 是兜底护栏，防止算法在超指数空间里空转到天荒地老。
    tmax⁡∈N+\displaystyle t_{\max} \in \mathbb{N}_{+}

效果评估

满载而归的老周没有急着庆祝。他翻出一张官方发布的“标准藏宝图”——那是用人工合成数据造的已知因果结构——将自己的路线图叠上去逐格比对：哪些边找错了，错了几条，来回跑十次结果稳不稳定。

在合成数据上，真实 DAG G* 是已知的，因此可以量化学习结果与真值的差距。最常用的指标是 SHD（结构汉明距离）：统计两张图的邻接矩阵中不一致的元素个数，0 表示完全恢复。

工程上还会做多次随机初始化，观察 SHD 的方差——稳定地小才是可靠的。在 AI 安全视角下，这一步尤其关键：因果图一错，下游的归因、干预与解释全盘皆错；搜索质量划定了系统“可被信任”的安全边界。

老周把评估结果写进行囊笔记，也写进了团队的规矩：没有经过 SHD 和稳定性检验的因果图，一律不准用于下游决策。这是寻宝人的底线，也是 AI 的安全线。

SHD(G,G∗)=∑i=1p∑j=1p1 ⁣[ Aij≠Aij∗ ]\displaystyle \mathrm{SHD}(G, G^{*}) = \sum_{i=1}^{p}\sum_{j=1}^{p} \mathbb{1}\!\left[\,A_{ij} \ne A^{*}_{ij}\,\right]
SHD 就是“数一数两幅藏宝图有几个格子画得不一样”，是衡量结构学习精度的标尺。
  1. 邻接矩阵元素A(i,j) 取 1 表示存在边 i→j，取 0 表示不存在，是因果图的数字化形态。
    Aij∈{0,1}\displaystyle A_{ij} \in \{0, 1\}
  2. 指示函数方括号内条件成立时计 1，否则计 0，用于标记“这一格两幅图是否不同”。
    1[ Aij≠Aij∗ ]\displaystyle \mathbb{1}[\,A_{ij} \ne A^{*}_{ij}\,]
  3. 双重求和遍历所有有序节点对，把不一致的格子全部累加，得到结构总误差。
    ∑i=1p∑j=1p(⋅)\displaystyle \sum_{i=1}^{p}\sum_{j=1}^{p} (\cdot)

AI 应用场景

场景一：金融风控中的逾期归因

阶段：因果发现（模型结构学习）

解决的问题：传统风控模型只输出“谁可能逾期”的预测分，却说不清“为什么”。分析师手工画因果图既慢又主观。用基于分数的搜索自动学习变量间因果 DAG，能让逾期率的关键驱动因素一目了然。就像老周用罗盘定位金矿，搜索算法用评分函数定位真正的风险源头。

具体案例：某消费金融公司收集用户收入、负债比、征信查询次数、历史逾期等 12 个特征，用模拟退火搜索 BIC 评分最优的因果图，锁定了“负债比→逾期率”的直接因果边，并据此设计还款提醒策略，逾期率下降 18%。

场景二：大模型可解释与安全审计

阶段：模型审计与归因分析

解决的问题：大模型回答“正确但不知道哪条推理链出了问题”，出现幻觉时难以追责。用因果结构搜索刻画模型内部概念依赖，定位幻觉的传播路径。

具体案例：安全团队对客服大模型的 2000 条错误回复做因果归因：以“输入摘要话题、检索上下文、注意力权重、输出置信度、是否幻觉”为节点，用遗传算法搜索因果图，发现“注意力漂移→输出置信度虚高→幻觉”的传导链，为模型修复提供了证据。

场景三：生物基因调控网络重建

阶段：结构化因果学习

解决的问题：基因表达数据维度高、真实调控结构未知，手工建模不现实；搜索算法需要在海量候选 DAG 中逼近最优网络。

具体案例：团队对 3000 个细胞样本、20 个关键基因的表达数据，用带随机重启的爬山算法学习调控网络，三天内得到与文献高度吻合的 15 条关键边，其中 12 条已被实验验证。

Python 演示

python139 行
import randomimport numpy as np  def has_cycle(adj):    # DFS 三色标记判断有向图是否含环    p = adj.shape[0]    color = [0] * p     def dfs(u):        color[u] = 1        for v in range(p):            if adj[u, v] and (color[v] == 1 or (color[v] == 0 and dfs(v))):                return True        color[u] = 2        return False     return any(dfs(i) for i in range(p) if color[i] == 0)  def bic_score(X, adj):    # BIC 评分，越低越好：对每个变量回归其父变量    n, p = X.shape    total = 0.0    for j in range(p):        pa = [i for i in range(p) if adj[i, j] == 1]        if pa:            mat = np.column_stack([X[:, i] for i in pa] + [np.ones(n)])            beta, _, _, _ = np.linalg.lstsq(mat, X[:, j], rcond=None)            pred = mat @ beta            k = len(pa) + 1        else:            pred = np.full(n, X[:, j].mean())            k = 1        rss = float(np.sum((X[:, j] - pred) ** 2))        total += n * np.log(max(rss / n, 1e-9)) + k * np.log(n)    return total  def neighbors(adj):    # 枚举所有单边邻域操作：加边、删边、反边    p = adj.shape[0]    for i in range(p):        for j in range(p):            if i == j:                continue            if adj[i, j] == 1:                na = adj.copy()                na[i, j] = 0                yield 'remove', i, j, na            else:                na = adj.copy()                na[i, j] = 1                if not has_cycle(na):                    yield 'add', i, j, na                if adj[j, i] == 1:                    nb = adj.copy()                    nb[j, i] = 0                    nb[i, j] = 1                    if not has_cycle(nb):                        yield 'reverse', i, j, nb  def hill_climbing(X, max_iter=60):    adj = np.zeros((X.shape[1], X.shape[1]), dtype=int)    score = bic_score(X, adj)    for _ in range(max_iter):        cand = min(neighbors(adj), key=lambda c: bic_score(X, c[3]))        new_score = bic_score(X, cand[3])        if new_score >= score - 1e-9:            break        adj, score = cand[3], new_score    return adj  def simulated_annealing(X, max_iter=120, t0=3.0, cooling=0.97):    adj = np.zeros((X.shape[1], X.shape[1]), dtype=int)    score = bic_score(X, adj)    best_adj = adj.copy()    best_score = score    t = t0    for _ in range(max_iter):        cand = random.choice(list(neighbors(adj)))[3]        new_score = bic_score(X, cand)        dc = new_score - score        if dc < 0 or random.random() < np.exp(-dc / t):            adj = cand            score = new_score            if score < best_score:                best_adj = adj.copy()                best_score = score        t *= cooling    return best_adj  def random_dag(p):    # 按随机拓扑序生成一个随机 DAG    adj = np.zeros((p, p), dtype=int)    order = list(range(p))    random.shuffle(order)    for x in range(p):        for y in range(x + 1, p):            if random.random() < 0.5:                adj[order[x], order[y]] = 1    return adj  def genetic_algorithm(X, pop=10, gen=20, rate=0.3):    p = X.shape[1]    pool = [random_dag(p) for _ in range(pop)]    for _ in range(gen):        pool = sorted(pool, key=lambda a: bic_score(X, a))[:pop // 2 + 1]        while len(pool) < pop:            a, b = random.sample(pool, 2)            child = np.zeros((p, p), dtype=int)            for i in range(p):                for j in range(p):                    if i != j:                        child[i, j] = a[i, j] if random.random() < 0.5 else b[i, j]            if random.random() < rate:                child = random.choice(list(neighbors(child)))[3]            if has_cycle(child):                child = np.zeros((p, p), dtype=int)            pool.append(child)    return min(pool, key=lambda a: bic_score(X, a))  if __name__ == '__main__':    random.seed(7)    np.random.seed(7)    n = 300    x1 = np.random.randn(n)    x3 = np.random.randn(n)    x2 = 0.8 * x1 + 0.7 * x3 + np.random.randn(n) * 0.5    X = np.column_stack([x1, x2, x3])    true_adj = np.array([[0, 1, 0], [0, 0, 0], [0, 1, 0]])    for name, fn in [('爬山', hill_climbing), ('退火', simulated_annealing), ('遗传', genetic_algorithm)]:        adj_out = fn(X)        print(name, 'SHD =', int(np.sum(adj_out != true_adj)), ' BIC =', round(bic_score(X, adj_out), 2))
目的：用 BIC 作为评分函数，在合成数据上分别运行爬山、模拟退火和遗传算法来学习因果 DAG，并用 SHD 指标对比学习结果与真实结构。
  1. total += n * np.log(max(rss / n, 1e-9)) + k * np.log(n)BIC 的拟合与惩罚两项：数据拟合越好残差越小，但每多一条父边就多付 k·ln n 的“复杂度税”，防止搜索傻乎乎地乱加边。
  2. if adj[u, v] and (color[v] == 1 or (color[v] == 0 and dfs(v))):三色 DFS 发现环就返回 True，保证邻域生成时只放行合法 DAG，相当于“山路必须不绕圈”。
  3. yield 'add', i, j, na生成器逐个吐出加边、删边、反边操作，这是三种算法共同的“一步”。
  4. cand = min(neighbors(adj), key=lambda c: bic_score(X, c[3]))爬山在前后左右一步内挑评分最低的图，纯利用不探索。
  5. if dc < 0 or random.random() < np.exp(-dc / t):退火接受准则：更好直接走，更差按概率走，温度 t 越大概率越小。
  6. pool = sorted(pool, key=lambda a: bic_score(X, a))[:pop // 2 + 1]遗传算法每代先按评分排序，只留最优秀的一半当父母，优胜劣汰。
  7. child[i, j] = a[i, j] if random.random() < 0.5 else b[i, j]交叉：逐格随机继承两个父图的边，拼出“混血”藏宝图。
  8. if has_cycle(child): child = np.zeros((p, p), dtype=int)变异后的孩子若成环就退回空图，保证种群始终合法。

常见误区

误区初学者认为爬山算法从任意起点出发都能找到最好的因果结构，跑一次看到评分不再下降，就当作最终答案，完全不管起点是什么。

正解爬山只看一步内的评分，非常容易停在评分函数的局部峰。工程上必须配合随机重启、多起点运行，或用模拟退火、遗传算法这类带随机性的方法，才能以更高概率逼近全局最优。老周的经验是：一座山爬不放心，多爬几座才踏实。

为何常见：人脑直觉认为“不断变好=最终最好”，忽略了每一步选择都受限于当前一步的视野。

误区以为退火接受较差解等于完全不讲道理地随机跳，和无脑随机搜索没什么区别，评分再差也会被接受。

正解接受差解的概率由 exp(−ΔS/T) 精确控制：ΔS 越大越难接受、T 越低也越难接受，且温度按调度平滑下降，探索期之后自然收敛到精细利用。这种“可控的随机”是它与纯随机搜索的关键区别。

为何常见：只看到“接受差解”四个字，忽略了背后的指数概率公式和降温调度共同形成的约束。

误区觉得遗传算法只要适应度函数写得对，种群大小、交叉概率、变异概率随便设置都能得到好结果。

正解种群太小，交叉很快失去多样性，算法退化成反复复制同一对父母；变异率过低则难以引入新结构。必须搭配足够大的种群和恰当的变异率，才能维持“探索”所需的基因多样性。

为何常见：把“进化”想得太神奇，忽略多样性维持机制才是遗传算法的发动机。

误区认为一旦评分函数收敛、分数不再下降，学习得到的结构就必然等于真实因果关系，可以直接用于下游分析。

正解基于分数的搜索只能找到“在评分意义下最优”的图，且同一评分可能对应多个 Markov 等价图；还要通过效果评估（如 SHD、多次运行的稳定性）和领域知识交叉验证，才能谈因果解释。

为何常见：把“数学上的最优”与“事实上的正确”划等号，忽略了观测数据本身的信息边界。

误区认为模拟退火温度越高、探索越多，效果就一定越好，于是一上来就设一个极大的初始温度。

正解温度过高意味着连评分极差的解都频繁接受，搜索在空间里乱撞，浪费大量迭代也难以落稳到峰顶。需要和降温速率配合：先高温粗探、再低温精爬，探索与利用要按时间表分配。

为何常见：只看到探索的收益，忘了探索的代价是牺牲利用，二者必须权衡。

面试题

Q1. 关于候选 DAG 数量随变量数的增长规律，下列说法正确的是？

单选题 · easy

  • A.随变量数线性增长
  • B.随变量数多项式增长
  • C.随变量数超指数增长← 正确答案
  • D.与变量数量完全无关

答案：C。候选 DAG 数量满足 Robinson 递推：p=5 时约 29281 种，p=10 时约 4.2×10¹⁸ 种，呈超指数爆炸。就像老周面前的山多到永远不可能逐峰踩遍，穷举注定不现实。

Q2. 爬山算法在某处停止，所有邻域操作都无法再降低评分，这说明？

单选题 · easy

  • A.一定发现了全局最优结构
  • B.可能陷入了局部最优← 正确答案
  • C.评分函数出现了严重错误
  • D.数据中一定存在较多噪声

答案：B。爬山只比较一步可达的邻域，评分不再改善只说明“眼前一寸内没有更好的图”；远处可能还有评分更低的全局峰。所以老周会换起点重爬几次，而不是就此收工。

Q3. 以下哪项不属于基于分数搜索的典型邻域操作？

单选题 · easy

  • A.增加一条有向边
  • B.删除一条有向边
  • C.反转一条有向边
  • D.把 DAG 变成无向图← 正确答案

答案：D。加边、删边、反边是三种标准邻域操作，且必须保持无环；把 DAG 变成无向图改变了问题定义，不再是“在 DAG 空间中走一步”，因此不属于典型的单步邻域操作。

Q4. 模拟退火中，某较差候选解的接受概率公式是？

单选题 · mid

  • A.exp(+ΔS/T)
  • B.exp(−ΔS/T)← 正确答案
  • C.1 − ΔS/T
  • D.ΔS/T

答案：B。接受概率等于 exp(−ΔS/T)，其中 ΔS 是新解与当前解的评分差（正数）。代价越大概率越小、温度越低概率越小，恰是“高温敢下坡、低温稳爬坡”这一直觉的数学表达。

Q5. 当温度 T 趋近于 0 时，模拟退火的行为最接近下列哪种？

单选题 · mid

  • A.完全随机搜索
  • B.爬山式贪心上升← 正确答案
  • C.遗传算法的交叉
  • D.穷举全部候选图

答案：B。T→0 时 exp(−ΔS/T)→0，几乎不再接受较差解，只接受评分更优的移动——这与爬山算法完全一致。这也解释了为什么退火是“先探索后利用”的平滑版本。

Q6. 遗传算法中，有助于维持种群多样性的机制有哪些？

多选题 · mid

  • A.交叉组合父母边结构← 正确答案
  • B.变异随机增删反边← 正确答案
  • C.适应度高的个体被选中
  • D.迭代一定次数后停止

答案：AB。交叉产生边结构的新组合、变异注入随机扰动，两者都在制造多样性；适应度选择反而是“优胜劣汰”，会压缩多样性；停止条件只控制运行时长，与多样性无关。

Q7. 在探索与利用的权衡中，模拟退火实现平滑过渡靠的是？

单选题 · mid

  • A.逐渐增大变异概率
  • B.温度随迭代指数下降← 正确答案
  • C.不断扩充邻域范围
  • D.每次从空图重新开始

答案：B。T_k = α^k × T₀ 使温度指数下降，前期接受差解概率高（多探索），后期只接受改善（多利用），实现从粗到细的自然过渡，这正是老周“白天探路、傍晚挖宝”的时间表。

Q8. 关于 SHD 指标，下列说法正确的是？

单选题 · hard

  • A.值越大说明结构越接近真实图
  • B.为 0 时学习图与真值邻接矩阵完全一致← 正确答案
  • C.SHD 一定随迭代次数单调下降
  • D.SHD 只能用于无向图比较

答案：B。SHD 统计两个邻接矩阵中不一致的元素个数，越小越好；为 0 表示结构完全一致。但它在 Markov 等价图上可能区分不出方向差异，所以还要结合稳定性测试与领域知识。

Q9. 关于爬山算法与模拟退火的对比，下列说法正确的有？

多选题 · hard

  • A.爬山较易陷入局部最优← 正确答案
  • B.退火靠接受差解跳出局部峰← 正确答案
  • C.爬山得到的评分必然更低
  • D.两者都靠邻域操作生成候选← 正确答案

答案：ABD。C 错误——退火往往得到不差于爬山的解；A、B、D 正确：爬山只用利用、退火加了探索，但两者都在“加边、删边、反边且保持无环”的邻域上移动。

Q10. 关于随机重启爬山的说法，正确的有？

多选题 · extreme

  • A.从多个随机初始图开始搜索← 正确答案
  • B.多次运行会使总耗时成倍增加← 正确答案
  • C.必然找到全局最优的因果图
  • D.提高跳出坏局部峰的概率← 正确答案

答案：ABD。随机重启本质是用多次独立爬山的计算换取更可靠的全局逼近，总时间约为重启动次数倍的叠加；它只是提高概率，不能保证找到全局最优，故 C 错。这正是老周“多爬几座山”策略的科学版本。