基于分数方法：局部最优逃逸

可视化演示

展示DAG评分地形的局部最优陷阱、模拟退火概率性接受劣解的逃逸过程与多种逃逸策略的收敛对比，交互调节温度与扰动强度。

爬山搜索局限

老李最初的寻宝方法就一条原则：哪里高往哪走。他管这叫“闷头爬”，从不看后路，也不观察远景。这种诚实而固执的策略，让他在连绵的丘陵地带收获颇丰——毕竟单峰的山丘上，向上走总能到顶。可当他真正进入群山深处，地形变得复杂起来：山坡起伏不定，小峰连大峰，老李时常费了半天力气攀上一座低矮的山包，才发现自己站的位置根本望不见真正的金山。

在基于分数的因果发现中，这种“闷头爬”对应的是爬山搜索算法（Hill Climbing）。算法的操作强度极小：每一步只对当前的DAG结构施加一次单边操作——增加一条有向边、删掉一条有向边，或者反转一条边的方向。执行完操作后，用评分函数（如BIC、BDeu）对新结构打分，只有分数提升才接受这次移动，否则就试下一个邻居结构。评分函数在这里扮演着“海拔计”的角色，它告诉算法哪个因果结构更符合观测数据。

问题恰恰出在“只接受提升”这个贪心规则上。DAG结构空间的“地形”远比真实群山崎岖：结构之间的评分落差是离散的、跳跃的，无数局部峰顶散布其中。爬山算法只看得到自己邻域内一步之遥的结构，看不见远处更高的评分区域，于是常常在某个不起眼的小山包上停下脚步——这就是著名的“局部最优困境”。

老李摔了几次跟头后终于明白：光会闷头爬是不够的，他迫切需要一套“逃逸战术”，让自己从那些看似安稳的小山包上跳出去，继续寻找真正的金山。

随机重启机制

老李的第一次战略升级来自于一次偶然的教训。那天他攀上一座小山顶，发现前方是断崖，回头又是一路下坡，正绝望时，山下的向导用望远镜给他打信号：往东三公里的那座山，高得多！于是老李雇了一架直升机，将自己空投到东边的山脚下，重新开始爬。从此他悟出一个笨而有效的道理：一座山爬到头还是不行，那就多换几座山试试。

随机重启策略正是这种“换座山”思想的算法化。它彻底放弃单一路线的执念：从多个随机初始DAG结构出发，各自独立执行爬山搜索，每一次搜索都会收敛到一个（可能是局部的）最优结构。当所有搜索结束后，将这些局部最优解放在一起，挑出评分最高的DAG作为最终答案。

这种策略本质上是“用独立重复实验换概率”：单次爬山陷入局部最优的概率很高，但多次独立随机起点的爬山全部落在差的山包上的概率则指数级下降。不过它并非没有代价——每增加一次重启，计算量就线性地增加一轮完整的爬山过程。因此，重启次数 $R$ 需要在计算预算与成功率之间仔细权衡。在工程实践中，人们常常设定一个时间上限，或者当连续若干次重启的评分不再提升时，提前终止搜索。

老李的直升机策略很快就见效了：虽然每次都得重新买机票，但找到金山的概率翻了好几倍。随机重启教会他的道理是——如果一条路走不通，与其死磕，不如大大方方换一个起点，让运气站在概率这一边。

模拟退火算法

直升机虽好，但烧钱太狠。老李开始琢磨一种更省钱的替代方案：能不能不换山峰，而是允许自己先往山下走几步，绕个远路再爬上去？困难在于，他拿不准什么时候该下坡、什么时候该咬紧牙关硬着头皮往上顶。这时，一位冶炼匠给了他启发：金属在高温下原子剧烈振动，冷却过程中逐渐安顿到低能排布——如果冷却太快，原子会被锁在高能缺陷中，这就是“退火”的智慧。

模拟退火算法（Simulated Annealing）正是受金属退火过程启发而设计的。它与爬山算法的核心区别在于：当候选结构的评分比当前结构更低时，爬山算法会直接拒绝，而模拟退火则以一个受“温度”控制的概率接受它。温度高时，算法愿意接受较差的解，从而大步探索远处的地形；温度逐渐降低后，接受差解的概率变小，算法越来越专注于精细爬坡。这个过程被称为“冷却调度”。

这个想法可以提炼为一个简洁的概率公式。设当前结构为 $G_{\text{current}}$，某个邻居结构为 $G_{\text{candidate}}$，两者评分之差为 $\Delta E$；如果 $\Delta E > 0$，说明候选解更差，此时以概率 $e^{-\Delta E / T}$ 接受它。当温度 $T$ 很大时，指数趋近1，几乎什么都敢试；当 $T$ 趋近0时，概率趋近0，算法退化为贪心爬山。正是这个“偶尔向下走”的机制，让算法得以翻越评分地形的鞍部，抵达全局最高峰。

老李把温度想象成自己的“冒险值”：刚进山时精力充沛、好奇心爆棚，什么岔路都敢试；随着天色渐晚（温度降低），他变得沉稳谨慎，只走最有把握的路。最终，他总能在傍晚前抵达当天视野里最高的那座山峰——这正是模拟退火的精妙之处。

禁忌搜索策略

有了随机重启和模拟退火，老李的寻宝事业蒸蒸日上，但他又发现一个新毛病：有时明明已经走过了某条死路，却总是不自觉地绕回来，在山脚下反复打转。为了治这个“原地转圈”的毛病，老李买了一本探险笔记，每走过一段坡路就记上一笔，并给自己立规矩：最近三天走的路，坚决不回头走。这笔记让他的探索路线多了几分“记性”。

禁忌搜索算法（Tabu Search）的核心思想正是这样一本“探险笔记”。它把最近执行过的操作记录在一张禁忌表中——比如刚才在节点A到节点B之间添加了一条边，那么在接下来的若干次迭代中，“删除A到B的边”这一操作会被暂时禁用，如图中所示，从而防止搜索立即退回刚才的状态。这种有记忆的搜索路径，迫使算法不断开拓新的邻域，而不是在一个小区域里来回摆动。

禁忌表的核心是“禁忌期限”（tenure）：一个操作被禁多久。期限太短，记忆形同虚设；期限太长，又可能错失良机。因此，禁忌搜索还配备了一条“特效规则”（aspiration criterion）：如果某个被禁的操作事实上能带来比历史最佳评分更高的结构，那么破例允许多次，就像老李发现笔记上那条“死路”其实藏着一道暗门通向金矿时，果断打破自己的规矩。真正的智慧不是机械守规矩，而是知道何时该守、何时该破。

老李的探险笔记越记越厚，但他发现真正管用的不是笔记本身，而是他给自己立下的规矩和偶尔破例的判断力。禁忌搜索让他明白：好的探索者不但要有勇气走新路，还要有记性不去重复踩坑。

遗传算法探索

单打独斗的日子终于结束了。老李发现，自己的经验再丰富，也敌不过十个队员各自带着不同的观察。于是他召集了一支探险队，让大家分头进山，各自画出自己眼中的“藏宝图”。回到营地后，队员们把地图摊在桌上互相拼接：你看到了东坡的溪流，我认出了西岭的峭壁，两张图一交叉，一条全新的路线浮现出来。

遗传算法（Genetic Algorithm）就是把老李的探险队搬进了计算机。候选的DAG结构不再是一个个体，而是一整个“种群”。每个个体由邻接矩阵结构编码，评分函数则化身“适应度函数”——适应度高的个体有更大的概率被选中，作为“父本”“母本”参与进化。三种遗传算子驱动着种群演化：选择（按适应度高低配比父本）、交叉（交换两个DAG的部分边集，生成子代结构）、变异（随机增删几条边引入新鲜性）。

这里有一个关键细节：基于分数的因果发现中，适应度函数往往不能只看评分。一个边数过多的DAG即使拟合得再好，也可能过拟合数据。因此，人们在适应度中引入稀疏性惩罚项——评分越高越好，边数越多越糟，$\lambda$ 就是平衡两者的旋钮。这样一来，遗传算法不仅是在搜索评分高的结构，更是在搜索“评分又高、结构又简约”的DAG。经过一代又一代的进化，整个种群像老李的探险队一样，把散布在群山各处的线索一点点拼成完整的金山地图。

探险队的经验在代际之间不断积累和重组。老李最终发现，最优的路线不是某个队员独自找到的，而是整个群体在前人的肩膀上协同进化出来的——遗传算法的魅力正在于此。

扰动平衡之道

四个战术学完，老李坐在山腰上复盘，突然悟出一个通了天的大道理：随机重启是“大扰动”——直接换座山；模拟退火是“温度扰动”——概率性下坡；禁忌搜索是“记忆扰动”——制造有方向的绕路；遗传算法是“种群扰动”——靠多样性持续撞出新的可能性。它们形式各异，本质却完全一致：在搜索过程中，恰到好处地注入噪声，打破已经稳定的局面，让探索的触角伸向未知区域。

在机器学习中，这个道理被称作“探索与利用的权衡”。探索（Exploration）是敢闯未知区域，利用（Exploitation）是深挖当前最优区域。如果只探索不利用，算法就成了乱撞的没头苍蝇；如果只利用不探索，就回到爬山算法的老路，困于局部最优。所有逃逸策略本质上都是在动态调整这两者的比例，而它们共同遵守一条经验规律：搜索前期多探索，尽可能覆盖广阔的结构空间；搜索后期多利用，把已有高分结构打磨到极致。

这条规律可以形式化为“探索强度随搜索进程衰减”的模型。初期扰动强度大，算法像是手持强光手电在黑暗中扫视整片山谷；随着迭代进行，探索强度指数下降，手电光束逐渐收窄，最终汇聚到当前最优解的精细邻域上。成功率与稳定性往往是一对矛盾：扰动太强，结果稳定但可能永远飘在随机搜索附近；扰动太弱，稳定性高却很容易再次陷入局部最优。优秀的算法设计，就是在刀刃上寻找那个让成功率和稳定性同时令人满意的平衡点。

老李的金矿最终找到了。他总结说：四门手艺没有哪一招是万能的，关键是把它们融会贯通，在对的时间用对强度的扰动。这座山爬不上去了？换座山重新来；前面的路不确定？留一丝冒险的余温；同样的坑踩过了？记下来别再踩；一个人搜不动了？带上队伍一起探索。所谓局部最优逃逸，说到底，就是一门“何时该打破安稳、何时该守住成果”的平衡艺术。

AI 应用场景

Python 演示

import numpy as np def random_dag(n):    perm = np.random.permutation(n)    adj = np.zeros((n, n))    for i in range(n):        for j in range(i + 1, n):            if np.random.rand() < 0.3:                adj[perm[i], perm[j]] = 1    return adj def is_dag(adj):    n = adj.shape[0]    indeg = adj.sum(axis=0)    q = [i for i in range(n) if indeg[i] == 0]    cnt = 0    while q:        i = q.pop()        cnt += 1        for j in range(n):            if adj[i, j] > 0:                indeg[j] -= 1                if indeg[j] == 0:                    q.append(j)    return cnt == n def score(adj, data):    n = adj.shape[0]    rss = 0.0    for j in range(n):        parents = np.where(adj[:, j] > 0)[0]        if len(parents) == 0:            rss += (data[:, j] ** 2).sum()        else:            x = np.column_stack([np.ones(len(data)), data[:, parents]])            beta, _, _, _ = np.linalg.lstsq(x, data[:, j], rcond=None)            resid = data[:, j] - x @ beta            rss += (resid ** 2).sum()    return -(rss + 0.5 * adj.sum()) def neighbors(adj):    n = adj.shape[0]    res = []    for i in range(n):        for j in range(n):            if i == j:                continue            if adj[i, j] == 0:                cand = adj.copy()                cand[i, j] = 1                if is_dag(cand):                    res.append(cand)            else:                cand = adj.copy()                cand[i, j] = 0                res.append(cand)    return res def hill_climb(adj, data, max_steps=60):    best_adj = adj.copy()    best_s = score(adj, data)    for _ in range(max_steps):        improved = False        for cand in neighbors(best_adj):            s = score(cand, data)            if s > best_s:                best_s = s                best_adj = cand                improved = True        if not improved:            break    return best_adj, best_s def random_restart(n, data, restarts=8):    best_adj, best_s = None, -np.inf    for _ in range(restarts):        adj = random_dag(n)        adj, s = hill_climb(adj, data)        if s > best_s:            best_s = s            best_adj = adj    return best_adj, best_s def simulated_annealing(adj, data, steps=300, T0=1.0):    cur_adj = adj.copy()    cur_s = score(adj, data)    best_adj, best_s = cur_adj.copy(), cur_s    for t in range(steps):        T = T0 * (1.0 - t / steps)        nbrs = neighbors(cur_adj)        cand = nbrs[np.random.randint(len(nbrs))]        cand_s = score(cand, data)        if cand_s > cur_s or np.random.rand() < np.exp((cand_s - cur_s) / max(T, 1e-6)):            cur_adj, cur_s = cand, cand_s        if cur_s > best_s:            best_s = cur_s            best_adj = cur_adj.copy()    return best_adj, best_s if __name__ == "__main__":    np.random.seed(42)    n = 4    data = np.zeros((200, n))    data[:, 0] = np.random.randn(200)    for j in range(1, n):        data[:, j] = 0.8 * data[:, j - 1] + 0.2 * np.random.randn(200)     init = random_dag(n)    hc_adj, hc_s = hill_climb(init.copy(), data)    rr_adj, rr_s = random_restart(n, data, restarts=8)    sa_adj, sa_s = simulated_annealing(init.copy(), data)     print("爬山算法评分: %.2f" % hc_s)    print("随机重启评分: %.2f" % rr_s)    print("模拟退火评分: %.2f" % sa_s)    print("爬山边数=%d, 重启边数=%d, 退火边数=%d"          % (hc_adj.sum(), rr_adj.sum(), sa_adj.sum()))

1. def is_dag(adj)通过拓扑排序判断邻接矩阵是否构成有向无环图，保证每一步搜索都停留在合法的因果结构空间。
2. def score(adj, data)实现简化版BIC评分：对每个变量用其父节点做线性回归，累加残差平方和，再减去边数惩罚。
3. def neighbors(adj)生成所有“单边操作”邻居：增边或删边，同时用 is_dag 过滤掉成环的非法结构。
4. if s > best_s:爬山算法的贪心核心：只有评分更高才接受邻居，这一步正是导致局部最优的根源。
5. def random_restart(n, data, restarts=8)用8个随机初始DAG分别爬山，再选出评分最高的结果，实现“换座山重新爬”。
6. T = T0 * (1.0 - t / steps)模拟退火的线性冷却调度：温度从T0递减到接近0，控制整个搜索过程的冒险程度。
7. np.exp((cand_s - cur_s) / max(T, 1e-6))当候选解更差时，以此概率接受它；这正是模拟退火能从局部最优“逃逸”的数学开关。

常见误区

面试题