📚 课程目录第1章课程导入与组合优化问题建模

1. 课程导入与组合优化问题建模

模拟退火算法（Simulated Annealing，SA）是一种受固体退火过程启发的随机搜索方法。它最典型的应用场景，是那些解空间离散、规模随问题增大而爆炸式增长、且难以用梯度信息引导搜索的组合优化问题。理解 SA 的定位，需要先看清它面对的问题长什么样：一个组合优化问题通常由决策变量（离散取值的安排方案）、约束条件（哪些方案合法）和目标函数（方案好坏）三部分构成。SA 不要求目标函数可导，也不要求问题具有凸性，它只要求我们能对任意一个候选解算出目标值，并能从一个解出发构造出“邻近解”。这两点正是它区别于线性规划、梯度下降等方法的根本所在。

三个典型问题的数学建模

旅行商问题（TSP）。给定 n 个城市及两两距离 d_ij，要求找一条经过每个城市恰好一次并回到起点的闭合路径，使总路程最短。决策变量可写为 0-1 矩阵 x_ij，表示是否从城市 i 直接前往城市 j；目标为最小化 Σ_iΣ_j d_ijx_ij；约束包括每个城市入度与出度均为 1，以及消除子回路。TSP 的可行解数量为 (n−1)!/2，n=20 时已超过 6×10¹⁶，穷举不可行。它的邻域操作非常自然：交换路径中两个城市的位置，或反转一段子路径（2-opt），后者能同时改变两条边的连接关系，是实践中更常用的算子。

0-1 背包问题。有 n 件物品，第 i 件重量 w_i、价值 v_i，背包容量 C。决策变量 x_i∈{0,1}，目标最大化 Σv_ix_i，约束 Σw_ix_i ≤ C。它的解空间是 2ⁿ 个 0-1 向量，但可行域被容量约束切割，邻域操作通常是翻转某一位（放入或取出），翻转后若超重则需修复——例如按价值密度贪心移除若干物品，或直接判为不可行并拒绝。背包问题的特点是“可行解稀疏”，这直接影响 SA 中邻域构造与惩罚项的设计。

作业车间调度（JSP）。有 m 台机器、n 个工件，每个工件需按固定工艺顺序在各机器上加工，各工序加工时间给定。目标是确定各机器上工序的加工顺序，使最大完工时间（makespan）最小。它的解通常编码为“工序序列”或“机器排序”，邻域操作是交换同一机器上相邻两道工序，但交换后必须检查是否破坏工艺先后约束，否则会产生不可行调度。JSP 的解空间规模约为 (n!)^m，且目标函数与解的对应关系高度非线性，属于典型的 NP-hard 问题。

复杂度分析与 SA 的定位

上述三个问题都是 NP-hard 的：TSP 的判定版本是经典的 NP 完全问题，0-1 背包是弱 NP-hard（存在伪多项式动态规划），JSP 在 m≥3 时即为强 NP-hard。这意味着不存在已知的多项式时间精确算法能对所有实例求解。面对这种局面，工程上通常有三条路线：精确算法（分支定界、整数规划）适合小规模或对最优性有硬要求的场景；启发式构造（最近邻、贪心）速度快但质量无保证；而元启发式——包括 SA、遗传算法、禁忌搜索——则在可接受时间内给出高质量近似解，是中等以上规模问题的现实选择。

SA 的独特之处在于它用概率接受准则跳出局部最优。设当前解为 s、候选解为 s′、目标差 Δ = f(s′) − f(s)（以最小化为目标）。若 Δ ≤ 0 则直接接受；若 Δ > 0 则以概率 exp(−Δ/T) 接受，其中 T 为温度参数。温度高时，劣解也有较大机会被接受，算法近似随机游走；温度逐步降低，接受劣解的概率收缩，搜索逐渐聚焦到优质区域。这一机制使 SA 对初值不敏感、实现简单、参数少，特别适合邻域结构清晰但目标函数复杂的组合问题。

建模时先明确三件事：解的编码方式、邻域算子的定义、以及不可行解的处理策略（拒绝、修复或惩罚）。这三者决定了 SA 能否高效运行，往往比温度参数本身更关键。

一个可运行的建模示例

以 10 城市 TSP 为例，用 Python 描述核心数据结构与邻域操作，便于后续章节直接扩展为完整 SA 实现。距离矩阵由坐标计算，解用城市访问序列表示，2-opt 反转一段子路径：

import random, math

cities = [(random.uniform(0,100), random.uniform(0,100)) for _ in range(10)]

def dist(a, b):
    return math.hypot(cities[a][0]-cities[b][0], cities[a][1]-cities[b][1])

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

def two_opt(tour):
    i, j = sorted(random.sample(range(len(tour)), 2))
    new = tour[:i] + tour[i:j+1][::-1] + tour[j+1:]
    return new

tour = list(range(10))
random.shuffle(tour)
print(tour_length(tour))   # 示例输出，实际值随随机种子变化

这段代码给出了建模的骨架：tour 是解，tour_length 是目标函数，two_opt 是邻域算子。运行后得到的路径长度只是一个初始值，SA 的作用就是在“接受更优解”与“以一定概率接受更差解”之间反复迭代，逐步压低这个数值。判断算法是否有效的依据，是比较多次独立运行得到的最终路径长度分布，而不是单次结果——因为 SA 是随机算法，单次运行具有偶然性。

需要强调的是，建模阶段就要考虑规模带来的影响。TSP 中 2-opt 每次只改变两条边，计算 Δ 可以做到 O(1)，无需重算整条路径；背包问题翻转一位后只需检查总重量是否越界；JSP 交换工序后只需重算受影响机器上的局部时间。这些“增量计算”技巧直接决定单次迭代的开销，也是后续实现章节要重点处理的内容。把问题建模清楚、把邻域和增量评估设计好，SA 的框架才有发挥空间。