算法设计与分析 · 期末复习

外观

10 智能优化算法 ​

本章对应考试中的：简答 Q18（邻域搜索、模拟退火、遗传算法的原理与比较，2020，4 分）、Q17（分支定界的前沿搜索 Frontier Search，2020，3 分）、遗传算法大题（用遗传算法求 TSP，merged，8 分）。

这一章主要出现在较新的卷子（2020 年）。题型是"阐述原理 + 比较异同"和"用遗传算法手算几轮"。

核心考点 ​

智能优化算法（metaheuristics，元启发式算法）：面向超大规模、很难求最优的优化问题的一类"启发式"方法。它们不保证找到最优解，但在实践中常能找到相当好的解。本章三种：邻域搜索、模拟退火、遗传算法。

从零开始的前置知识 ​

邻域与局部最优 ​

  • 邻域（neighborhood）：一个解通过一次"小改动"能变到的所有解的集合。例如一条 TSP 路线，交换其中两个城市的位置，就得到一个邻居。
  • 局部最优（local optimum）：在它的邻域里它最好，但在整个解空间里它不一定最好。

邻域搜索（局部搜索） ​

邻域搜索（neighborhood search / local search）：从一个初始解出发，在它的邻域里找一个更优的解，移动过去；不断重复，直到邻域里再也没有更优的解（到达局部最优）就停止。

特点：简单、快，但容易陷在局部最优出不来（因为它只肯往更好的方向走，到了局部最优就卡住）。

模拟退火 ​

模拟退火（simulated annealing, SA）：在邻域搜索的基础上，引入一个**"温度" T，并允许按概率接受比当前更差的解**，从而具备跳出局部最优的能力。接受劣解的规则叫 Metropolis 准则：设新解比当前解差了 ΔE>0（目标值变差的量），则以概率

P接受=e−ΔE/T

接受这个劣解。逐符号解释：ΔE 是变差的幅度，T 是当前温度。温度 T 高时，e−ΔE/T 接近 1，容易接受劣解（敢于到处探索）；温度逐渐降低，接受劣解的概率越来越小，最终收敛。比当前更好的解则总是接受。温度的下降速度（退火调度）影响收敛速度和最终质量。

遗传算法 ​

遗传算法（genetic algorithm, GA）：维护一个种群（一组解），用三种"遗传算子"让种群一代代进化：

  • 选择（selection）：按"适应值"（解的好坏）优胜劣汰，保留好的解。
  • 交叉（crossover）：把两个父代解的部分片段组合，产生新解（子代）。
  • 变异（mutation）：对某个解做随机小改动，维持多样性。

它靠种群的多样性 + 交叉重组进行全局搜索，能力强但参数多、收敛较慢。

三者比较（Q18 的"异同"部分） ​

  • 相同：三者都是面向难优化问题的启发式/元启发式，都不保证最优。
  • 不同：
    • 邻域搜索最基础，是单点搜索、只接受更优解，最容易陷入局部最优；
    • 模拟退火是单点搜索，但以概率接受劣解，因而能跳出局部最优；
    • 遗传算法是种群搜索，靠选择 + 交叉 + 变异获得更强的全局探索能力，但参数多、收敛慢。
  • 计算效果：通常模拟退火、遗传算法优于纯局部搜索，代价是更高的时间开销和调参成本。

逐题精解 ​

Q18 三种算法的原理与比较（2020，4 分） ​

原题：分别阐述邻域搜索、模拟退火与遗传算法的基本原理，并从算法特点与计算效果等角度比较它们的异同。

答案：

  • 邻域搜索（局部搜索）：从一个解出发，在其邻域内寻找更优解并移动过去，直到到达局部最优。简单快速，但易陷入局部最优。
  • 模拟退火：在邻域搜索基础上，用 Metropolis 准则按概率接受劣解（接受概率 e−ΔE/T 随温度 T 下降而减小），从而能跳出局部最优；温度调度影响收敛速度与解的质量。
  • 遗传算法：基于种群，用选择、交叉、变异等遗传算子并行进化多个解，靠群体多样性进行全局搜索。
  • 异同：三者都是启发式、不保证最优。邻域搜索最基础、最易陷局部最优；模拟退火以概率接受劣解获得跳出局部最优的能力（单点搜索）；遗传算法以种群 + 交叉获得更强的全局探索能力，但参数多、收敛较慢。计算效果上通常 SA、GA 优于纯局部搜索，代价是更高的时间开销与调参成本。

Q17 分支定界的前沿搜索（2020，3 分） ​

原题：分支定界算法遍历搜索树的"Frontier Search"（前沿搜索）是如何工作的？为什么会有这样一种方法？

前置：分支限界法（详见 06_回溯法与分支限界法.md）搜索时要维护一个"活结点表"，它可能膨胀得非常大。

答案：前沿搜索（Frontier Search） 只在内存中保存搜索的"前沿"（当前活结点构成的边界），而不保存已经扩展过的内部结点；当需要还原路径时，靠记录的"与父层的关系"在需要时重建。

动机：分支限界 / 最优搜索的活结点表可能呈指数级膨胀，把已扩展的内部结点全存下来会耗尽内存。前沿搜索只留边界，可以大幅降低空间占用，使大规模实例在有限内存下也能求解。

遗传算法求 TSP（merged，8 分） ​

原题：推销员从城市 v1 出发，访问 v2,…,v6 各一次后回到 v1，各城市间距离由矩阵 D 给出，求总行程最短的路线。要求用遗传算法求解，写出求解过程（每轮填计算表，注释解释交叉切点、非法编码修复、变异策略），输出历史最佳个体。要求：顺序编码（v1 固定第一位）；目标函数 = 路线长度；种群规模 4；双切点交叉（个体 1 与 2 交叉、3 与 4 交叉，随机两切点，非法则修复）；每轮任选 1 个个体变异；选择策略 = 把遗传前后种群一起按适应值排序取最好的 4 个；执行 2 轮，输出历史最佳。

前置：怎么把一条路线编码。 用顺序编码：把城市访问顺序写成一串数字，v1 固定在第一位。例如编码 123456 表示路线 v1→v2→v3→v4→v5→v6→v1。适应值取路线总长度（这是最小化问题，长度越小越好）。

双切点交叉怎么做、为什么要修复。 双切点交叉 是随机选两个切点，把两个父代在两切点之间的那一段互换。但因为编码必须是 v2∼v6 的一个排列（每个城市出现且仅出现一次），直接互换中段常会造成某些城市重复、另一些缺失——这就是"非法编码"，必须修复。

一个具体的交叉 + 修复例子：

  • 父代 P1 = 1 2 3 4 5 6，父代 P2 = 1 5 4 6 3 2（首位 v1 不参与交叉）。
  • 两个切点取在第 2 位之后、第 4 位之后，中段是第 3、4 位。P1 中段 = 3 4，P2 中段 = 6 ... 这里取 P2 第 3、4 位 = 4 6。
  • 把 P1 的中段换成 P2 的中段：子代 = 1 2 | 4 6 | 5 6，出现了两个 6、缺了 3，非法。
  • 修复方法（按映射恢复）：建立两个被交换中段的对应关系（P1 段 3 4 与 P2 段 4 6 逐位对应：3↔4、4↔6）。对中段以外发生重复的位置，按这个映射替换：把多出来的 6 顺着映射 6→4→3 换成缺失的 3。修复后子代 = 1 2 4 6 5 3，成为合法排列。

变异策略：每轮任选 1 个个体，随机交换它的某两位基因（即交换路线中两个城市的位置），以维持多样性。例如把 1 2 4 6 5 3 的第 3、5 位交换得到 1 5 4 6 2 3。

选择策略：把"本轮交叉变异前的 4 个个体"和"交叉变异产生的新个体"合在一起，按适应值（路线长度，越小越好）排序，挑出最好的 4 个作为下一代种群。同时记录"历史最佳个体"。

结果（按原卷手算）：两轮之后，历史最佳个体为 126543，即路线 v1→v2→v6→v5→v4→v3→v1，其适应值（总路程） 为

10+21+12+10+4+23=80.

（上式各项依次是 v1v2, v2v6, v6v5, v5v4, v4v3, v3v1 的距离。）

答题要点：每一轮列一张表，写出"当前种群的编码及其适应值 → 双切点交叉（注明切点与中段）→ 非法编码的映射修复 → 变异（注明换了哪两位）→ 合并父子代按适应值排序保留最优 4 个"，最后输出历史最佳 126543、适应值 80。

高频陷阱 / 易错点小结 ​

  1. 模拟退火接受劣解的概率是 e−ΔE/T，温度越高越敢接受；这是它能跳出局部最优的关键，别和邻域搜索混为一谈。
  2. 三者都不保证最优（都是启发式），比较时务必点出"邻域搜索易陷局部最优、SA 能跳出、GA 种群全局搜索"。
  3. 遗传算法的非法编码必须修复：双切点交叉换中段会产生重复城市，用映射关系修复；这是大题的采分注释点。
  4. 前沿搜索的目的是省内存（只存活结点边界），别答成"省时间"。
  5. TSP 是最小化问题，遗传算法里适应值取路线长度时是"越小越好"，排序保留时别选错方向。

自测清单 ​

  • [ ] 分别用一两句话说清邻域搜索、模拟退火、遗传算法的原理。
  • [ ] 写出模拟退火接受劣解的概率公式 e−ΔE/T 并解释温度的作用。
  • [ ] 说清三者的异同（都不保证最优 + 各自特点）。
  • [ ] 解释前沿搜索怎么工作、为什么能省内存。
  • [ ] 说清遗传算法 TSP 的流程（编码 / 适应值 / 双切点交叉 / 修复 / 变异 / 选择），并给出最佳 126543、适应值 80。
赣ICP备2026014065号-1