3. 邻域结构与状态生成

模拟退火算法能否在组合优化问题上真正发挥作用，很大程度上不取决于降温表设计得多精细，而取决于邻域结构定义得是否合理。邻域结构规定了"从当前解出发，下一步可以走到哪些解"，它同时决定了搜索空间的连通性、单步计算代价以及算法跳出局部最优的能力。本节围绕交换、插入、反转三类最常用的邻域算子展开，分析它们的适用问题、实现方式，以及邻域规模对搜索效率的定量影响。

邻域的本质：一个解到一组解的映射

设组合优化问题的可行解集合为 S，当前解为 x ∈ S。邻域结构是一个映射 N: S → 2^S，N(x) 称为 x 的邻域，其中的元素称为 x 的邻居。模拟退火在每一步从 N(x) 中按某种规则产生候选解 x'，计算目标函数差值 Δf = f(x') − f(x)，再依据 Metropolis 准则决定是否接受。因此邻域定义包含两个层面：一是"允许哪些变换"，即算子的类型；二是"如何从邻域中取点"，即随机采样还是全邻域枚举。这两点共同决定了算法的行为。

需要强调的是，邻域必须保证可行解之间的连通性：从任意可行解出发，经过有限次邻域移动能够到达任意其他可行解。否则搜索会被限制在可行解空间的一个子集内，再好的降温策略也无法弥补。

三类基础邻域算子

交换（Swap）：选取解中两个位置 i、j，交换其上的元素。对于排列型问题（如旅行商问题 TSP、二次分配问题 QAP），交换对应"把城市 i 和城市 j 在访问序列中的位置对调"。交换算子保持元素多重集不变，天然满足排列约束，实现代价极低，是排列类问题最常用的算子之一。其缺点是单步扰动幅度小，在解空间中移动缓慢。

插入（Insertion / Relocate）：把位置 i 上的元素取出，插入到位置 j 之前或之后，其余元素顺次平移。插入可以看作一次"移位"，其扰动幅度介于交换与反转之间。在车辆路径问题（VRP）中，插入算子常被解释为"把某个客户从一条路径移到另一条路径的某个位置"，因此它天然适合跨路径调整，是 VRP 邻域设计的核心算子。

反转（2-opt / Reversal）：选取区间 [i, j]，将区间内的元素顺序完全颠倒。对 TSP 而言，反转对应删除两条边 (i−1, i)、(j, j+1) 并重新连接为 (i−1, j)、(i, j+1)，这正是经典的 2-opt 移动。反转的几何意义明确，能够一次性消除路径中的交叉，因此在欧氏 TSP 上收敛速度快。但反转会改变区间内所有元素的前后关系，对带方向约束或时间窗约束的问题可能破坏可行性，需要额外的可行性检查。

邻域规模对搜索效率的影响

邻域规模直接决定单步迭代的计算量。以长度为 n 的排列为例，交换与反转的邻域大小均为 n(n−1)/2，插入为 n(n−1)，三者都是 O(n²) 量级。若每一步都枚举整个邻域并取最优，单步代价为 O(n²) 次目标函数评估；当 n = 1000 时，单步就需要约 5×10⁵ 次评估，而模拟退火通常需要数万到数十万步迭代，总代价将不可接受。因此工程上普遍采用随机采样邻域：每步随机生成一个（或少量）邻居，单步代价降为 O(1) 次评估加一次 Δf 增量计算。

但邻域并非越大越好，也非越小越好。邻域过小（例如只允许相邻位置交换），解空间连通性差，搜索容易在局部区域内反复打转，表现为目标函数长时间停滞；邻域过大，单步扰动剧烈，接受率下降，算法退化为随机游走。实践中常用的折中是混合邻域：以较高概率使用小幅度算子（如相邻交换）做精细搜索，以较低概率使用大幅度算子（如随机反转）做全局跳跃。

另一个关键点是 Δf 的增量计算。对 TSP 的 2-opt 反转，只有两条边被删除、两条边被新增，Δf 可在 O(1) 时间内算出，无需重算整条路径长度。对交换算子，若目标函数是路径总长度，则只有与 i、j 相邻的四条边受影响，同样可 O(1) 更新。能否写出增量公式，往往比邻域大小更能决定算法的实际速度。下面给出一个可运行的交换算子增量计算示例（Python，示例数据为假设）：

import random, math

def tour_length(tour, dist):
    return sum(dist[tour[i]][tour[(i+1) % len(tour)]] for i in range(len(tour)))

def swap_delta(tour, i, j, dist):
    """交换 tour[i] 与 tour[j] 后路径长度的变化量，O(1)"""
    n = len(tour)
    a, b = tour[i], tour[j]
    pa, na = tour[(i-1) % n], tour[(i+1) % n]
    pb, nb = tour[(j-1) % n], tour[(j+1) % n]
    if abs(i - j) == 1 or abs(i - j) == n - 1:   # 相邻情形需单独处理
        return 0.0
    old = dist[pa][a] + dist[a][na] + dist[pb][b] + dist[b][nb]
    new = dist[pa][b] + dist[b][na] + dist[pb][a] + dist[a][nb]
    return new - old

# 示例：n=8 的随机距离矩阵，验证增量公式与全量重算一致
random.seed(7)
n = 8
pts = [(random.random(), random.random()) for _ in range(n)]
dist = [[math.dist(pts[u], pts[v]) for v in range(n)] for u in range(n)]
tour = list(range(n))
i, j = 1, 5
delta = swap_delta(tour, i, j, dist)
new_tour = tour.copy(); new_tour[i], new_tour[j] = new_tour[j], new_tour[i]
print(round(delta, 6), round(tour_length(new_tour, dist) - tour_length(tour, dist), 6))
# 两值应相等，说明增量公式正确

这段代码的价值在于：它把"邻域移动"与"目标函数评估"解耦。只要增量公式正确，就可以在 O(1) 时间内判断一个邻居的优劣，从而支撑大规模随机采样。实际实现时务必用全量重算做一次交叉验证，尤其是相邻位置交换这类边界情形，容易因重复计算边而得到错误增量。

邻域设计中的可行性约束

对带约束的问题，邻域算子必须与约束协同设计。以带时间窗的 VRP 为例，插入算子把客户从路径 r₁ 移到路径 r₂ 时，需要检查 r₂ 上插入位置前后两个客户的时间窗是否仍然满足，以及 r₁ 删除该客户后是否仍满足载重与时间窗。若检查失败，该邻居应被直接丢弃并重新采样，而不是接受后再修复。这种"先判可行、再算 Δf"的顺序能显著减少无效计算。