---
title: "退火与副本交换"
description: "从已有收缩树出发，用模拟退火探索不同结构，或在多个温度之间交换搜索状态。"
eyebrow: "寻路算法"
---

## 局部改变收缩树 {#tree-neighborhood}

模拟退火（simulated annealing）和副本交换（parallel tempering / replica exchange）都从已有完整路径出发。局部更新改变树中几个节点的组合方式，不执行数组计算。

```diagram
tree-rotation
a、c、d 可以各自代表一棵子树。旋转改变它们的组合方式，不改变它们各自的内部结构。
```

这些方法允许暂时接受代价更高的状态，同时单独保留历史最佳路径。

## 模拟退火 {#annealing}

温度较高时，更容易接受较差的候选；随着温度降低，搜索更倾向于保留改善。对能量增量 $\Delta E$，Metropolis 接受概率为：

$$
p=\min\left(1,\exp\left[-\beta\Delta E\right]\right).
$$

$\beta$ 为逆温度。这个式子用于 `treesa_path` 时，能量为 $E=\log_2 J$，其中 $J$ 是[完整路径的优化目标](/docs/path-metrics#definition)。`anneal_path` 则按相对目标变化与相对温度计算接受概率，不能直接套用同一组温度参数。

```pseudocode
current = 初始树
best = 初始树
按温度序列搜索:
    重复尝试局部更新:
        candidate = 对 current 做一次局部旋转
        按该方法的 Metropolis 准则决定是否接受 candidate
        若接受，则 current = candidate
        若 current 足够改善 best，则 best = current
return best
```

`anneal_path` 运行一条链；`anneal_paths` 从同一起点并行运行多条独立链；`treesa_path` 使用逐渐增加的逆温度，在每个温度下遍历树。它们都返回一条最佳路径。

## 副本交换 {#tempering}

多个副本分别在不同温度下搜索。每轮局部搜索完成后，尝试交换相邻温度的状态。与独立运行多条退火链相比，多了这一步状态交换。

```diagram
parallel-tempering
温度位置不变，交换的是树状态。图中 P、Q 接受交换，R、S 保持原位。
```

```pseudocode
用起始路径初始化不同温度的副本
重复各轮搜索，直到达到轮数或停止条件:
    各副本并行执行本轮局部搜索
    尝试交换相邻温度的副本状态
    更新历史最佳路径
return 历史最佳路径与最佳起始路径中较好的一条
```

各副本内的旋转按相对目标变化决定是否接受；相邻副本之间的交换则使用 $E_i=\ln J_i$、$\beta_i=1/T_i$，交换概率为：

$$
p_{\mathrm{swap}}=
\min\left(1,\exp\left[(\beta_i-\beta_j)(E_i-E_j)\right]\right).
$$

`temper_path` 从同一路径初始化各副本；`temper_paths` 可用多条路径初始化。副本数不等于返回路径数，两个函数都只返回一条路径。

## 接口与局部重构 {#selection}

| 方法 | 接口 |
| --- | --- |
| 模拟退火 | `anneal_path`、`anneal_paths` |
| 按逆温度遍历树 | `treesa_path` |
| 副本交换 | `temper_path`、`temper_paths` |

完整参数、温度定义和停止设置见 [Rust API](/docs/rust-api#tree-search)。这些方法保留最佳输入作为备选，但不保证全局最优。

### 周期性子树重构 {#reconfiguration}

副本交换的局部搜索还可以周期性调用[子树重构](/docs/reconfiguration)。它直接求解一个局部小网络，与一次树旋转不同。