第五部分：应对不确定性与大规模问题

本部分聚焦于处理动态输入、超大规模搜索空间及实际工程中的复杂优化问题。

5.1 在线算法 (Online Algorithms)

5.1.1 在线算法

离线和在线

离线算法 (Offline Algorithm)：在计算开始前，问题的所有输入数据（整个序列）均已知。算法可以统筹全局做出最优决策。
在线算法 (Online Algorithm)：输入是以序列形式逐步到来的 ($x_1, x_2, \dots$)。算法必须在接收到每一个输入 $x_i$ 时立即做出决策，且该决策通常是不可逆的。算法无法预知未来的输入。

在线算法分析和竞争比

在线算法的分析通常被建模为在线选手 (Online Player) 与恶意对手 (Malicious Adversary) 之间的博弈：

在线选手运行在线算法。
恶意对手了解选手的算法逻辑，并精心构造一组最坏情况的输入序列，试图最大化在线选手的代价。

目标：设计一种算法，使得即使在对手最恶毒的攻击下，其表现也不会比拥有上帝视角的离线最优算法差太多。

设 $A$ 是一个在线算法，$CA(I)$ 是其在输入序列 $I$ 上的代价；$OPT$ 是离线最优算法，$C{OPT}(I)$ 是其代价。
如果存在常数 $\alpha$ 和 $b$，使得对于任意输入序列 $I$，均满足：

$C_A(I) \le \alpha \cdot C_{OPT}(I) + b$

则称算法 $A$ 是 $\alpha$-竞争的，$\alpha$ 称为竞争比。

$\alpha$ 越小，算法在最坏情况下的鲁棒性越好。
对于最小化问题，$\alpha \ge 1$。

5.1.2 经典在线问题

滑雪租赁问题

情境：计划去滑雪，但不知道天气何时变坏导致滑雪场关闭（即不知道总天数 $n$）。

租 (Rent)：每天 1 元。
买 (Buy)：一次性支付 $b$ 元。
目标：最小化总花费。

盈亏平衡算法

策略：先租 $b-1$ 天；如果第 $b$ 天还能滑，则购买滑雪板。

情况 1 ($n < b$)：一直租。代价 $CA(n) = n$，最优代价 $C{OPT}(n) = n$，比值：$1$。
情况 2 ($n \ge b$)：最坏情况发生在刚买完滑雪板后，滑雪场立即关闭（即 $n=b$），代价 $CA(n) = (b-1) + b = 2b - 1$，最优代价 $C{OPT}(n) = b$，比值：$\frac{2b-1}{b} < 2$。

盈亏平衡算法是 2-竞争 (2-Competitive) 的。

最优缓存问题

缓存容量为 $k$，主存容量为 $N$ ($N \gg k$)，输入是页面请求序列 $\sigma = $。

命中 (Page Hit)：请求页在缓存中 $\to$ 代价 0。
缺页 (Page Fault)：请求页不在缓存中 $\to$ 代价 1。
- 此时，若缓存已满，必须选择一页剔除 (Evict)，并将新页载入。
  目标：设计页面剔除策略，最小化缺页中断次数。

这个算法的离线最优是贪心算法，即选择缓存中在未来最长时间内不会被访问的那个页面。若某页未来不再被访问，则优先剔除。这个算法被称作最远将来(Farthest-in-Future, FIF)。

常见在线策略

LIFO (Last-In First-Out，后进先出)：剔除最新进入缓存的页面。
LFU (Least Frequently Used，最少频繁使用)：剔除过去被访问次数最少的页面。
FIFO (First-In First-Out，先进先出)：剔除最早进入缓存的页面
LRU (Least Recently Used，最少最近使用)：剔除距离当前时刻最久未被访问的页面

尽管 LIFO 和 LFU 在特定场景下有其逻辑，但在对抗性分析（面对恶意对手）中，它们的表现是灾难性的，竞争比无法被常数界定。
以LIFO为例：

缓存容量 $k$，当前内容 ${1, \dots, k}$，最后载入的是 $k$。
攻击序列：$k+1, k, k+1, k, \dots$
LIFO 会在 $k$ 和 $k+1$ 之间反复“抖动”，每一次请求都导致缺页。
$C{LIFO} \to \infty$（相对于 $C{OPT}=1$）。

定理：对于缓存容量为 $k$ 的系统，任何确定性在线算法 $A$ 的竞争比至少为 $k$。

假设系统共有 $k+1$ 个页面。
在每一步，对手总是请求当前不在算法 $A$ 缓存中的那个页面。
- 由于只有 $k+1$ 个页且缓存大小为 $k$，总有 1 个页在缓存外。
- 这导致算法 $A$ 每一次请求都发生缺页。对于长度为 $L$ 的序列，$C_A = L$
对于离线算法，OPT 会查看这 $k+1$ 个页中哪一个在未来最晚被请求，并剔除它。
- 在 $k+1$ 个页面的循环请求中，OPT 平均每 $k$ 次请求才需要缺页一次
  因此竞争比约等于k

LRU 策略是 $k$-竞争的

将请求序列 $\sigma$ 划分为若干阶段 $P_1, P_2, \dots$，每个阶段恰好包含 $k$ 个不同的页面。一旦请求序列中出现了第 $k+1$ 个不同的页面，当前阶段结束，新阶段开始。第 $i$ 阶段结束时的请求页与第 $i+1$ 阶段开始时的请求页必然不同。
在每个阶段 $Pi$ 内，LRU 策略最多发生 $k$ 次缺页，设总阶段数为 $N$，则 $C{LRU} \le k \cdot N$

此时的FIF算法：

每当从阶段 $Pi$ 进入 $P{i+1}$ 时，必须处理一个新的页面 $p_{new}$
在 $Pi$ 结束时，OPT 的缓存中存有 $k$ 个页。$P{i+1}$ 的第一个请求必然是 $P_i$ 中从未出现过的第 $k+1$ 个不同页，因此 OPT 在新阶段开始时必然缺页。
FIF 在每个阶段（除第一个外）至少发生 1 次缺页。$C_{OPT} \ge N - 1$。

随机在线算法和标记算法

如前所述，任何确定性在线缓存算法的竞争比至少为 $k$。为了获得更好的性能，我们引入随机性。

我们采用不经意对手 (Oblivious Adversary) 模型，对手必须在算法执行前构造好整个请求序列 $I$，对手知道算法的代码，但不知道算法执行过程中的随机选择结果。

标记算法 (Marker Algorithm)通过维护页面的“标记”状态来辅助随机剔除

缓存中的每个位置（共 $k$ 个）有一个标记位，初始全为 0

对于每个请求 $r_i$
命中：若 $r_i$ 在缓存中，将其对应位置标记设为 1
缺页：若 $r_i$ 不在缓存中，检查是否存在标记为 0 的页
- 有 0 标记：在所有标记为 0 的页中，均匀随机选择一个进行剔除。将新页 $r_i$ 载入并标记为 1。
- 全 1 标记：说明当前阶段结束。将所有标记重置为 0，开始新阶段。然后按“有 0 标记”的情况处理（即随机剔除一个，载入新页并标记）。

Marker 算法对不经意对手是 $2H_k$-竞争的，其中 $H_k = 1 + 1/2 + \dots + 1/k \approx \ln k$

定义：除了最后一个阶段外，每个阶段恰好包含 $k$ 个不同的被标记页面。即每当有 $k$ 个不同页被请求后，阶段结束。

$P_i$：第 $i$ 阶段出现的所有 $k$ 个页面的集合。
新页 (New Pages)：$Ni = P_i \setminus P{i-1}$，既在当前阶段出现但上一阶段未出现的页。令 $|N_i| = n_i$。
旧页 (Old Pages)：$Oi = P_i \cap P{i-1}$，即在上一阶段也出现过的页。$|O_i| = k - n_i$。
理论上，每一阶段都会将所有缓存的标记全部标为1，并在进入下一阶段时全部置零。这一阶段结束时，缓存中包含的页面就是这一阶段中出现的所有页面。

分析第 $i$ 阶段的期望缺页数

新页 ($N_i$)：必然不在缓存中（因为上一阶段没用到，早已被剔除或从未载入）。这就贡献了 $n_i$ 次缺页。
旧页 ($O_i$)：旧页在上一阶段结束时全部包含在缓存中，但在这一阶段的进行中可能被剔除。
- 假设 $Oi$ 中的旧页在当前阶段第一次被请求的顺序为 $y_1, y_2, \dots, y{k-n_i}$
- 当请求 $y_j$ 时，已有 $n_i$ 个新页和 $j-1$ 个旧页被标记为 1。此时缓存中“未标记”的空位（即可能保留旧页的位置）还有 $k - (n_i + j - 1)$ 个、
- $y_j$ 被剔除的概率上限为 $n_i / (k - j + 1)$
- 对所有旧页求和，期望缺页数 $\le \sum{j=1}^{k-n_i} \frac{n_i}{k-j+1} = n_i (H_k - H{ni})$。
  总期望：$E[\text{Faults}_i] \le n_i + n_i(H_k - H{n_i}) \le n_i H_k$。

FIF的下界：$C_{OPT} \ge \frac{1}{2} \sum n_i$

竞争比：

$\frac{\sum n_i H_k}{\frac{1}{2} \sum n_i} = 2H_k$

5.2 现代启发式算法

当问题规模巨大且对解的精度要求不苛刻时，启发式算法是工程首选。

启发式算法利用基于经验（Experience-based）的技术寻找问题的满意解，而非绝对最优解。

具备以下特点：

经验导向：模仿自然现象（如物理退火、生物进化）或人类直觉。
近似性：通常不能保证收敛到全局最优，但实用性强。
高效性：相比精确算法（如穷举），计算时间大幅减少。
问题依赖性：通用性较弱，需针对特定问题设计。

以兔子爬山为例，一些启发式算法的思想如下所示：

局部搜索 (Local Search)：“视力不好的兔子”。采用贪心策略，每步只向周围比现在高的地方跳。
禁忌搜索 (Tabu Search)：“有记忆力的兔子”。记住走过的路并留下记号，优先探索未涉足区域，避免重复。
模拟退火 (Simulated Annealing)：“会瞬移的兔子”。在体力好（高温）时可能跳向低处（概率接受劣解），从而跳出局部陷阱。
遗传算法 (Genetic Algorithm)：“多产的兔子群”。通过优胜劣汰，海拔高的兔子繁衍后代，种群自动向高峰迁移。

5.2.1 个体算法

邻域搜索算法 NS

从一个初始解 $x$ 出发，通过定义邻域动作（如交换、插入、反转），在当前解的邻域 $N(x)$ 中寻找更好的解。

生成初始解。
在邻域中产生候选解。
贪心接受：若候选解优于当前解，则移动；否则尝试其他邻居或停止。
重复直至满足终止条件（如找不到更好的解）。

Algorithm Lin-Kernighan (LK)
输入：距离矩阵 D，初始路径 T (通常由贪心算法生成)
输出：优化后的路径 T_best

1. T_best ← T
2. improved ← true
3. while improved do
4.    improved ← false
5.    // 遍历所有节点作为搜索的起点 t1
6.    for each node t1 in T do
7.       // 选择 t1 的邻居 t2，构成第一条要断开的边 x1 = (t1, t2)
8.       for each neighbor t2 of t1 in T do
9.          // 尝试寻找能够改进路径的移动序列 (k-opt)
10.         (is_improved, new_tour) ← Execute-LK-Move(T, t1, t2)
11.         if is_improved then
12.            T ← new_tour
13.            T_best ← new_tour
14.            improved ← true
15.            goto Step 3 (一旦找到改进，立即重新开始主循环 - 贪心策略)
16.         end if
17.      end for
18.   end for
19. end while
20. return T_best

其中的Execute-LK-Move是一种变深度搜索策略，简单起见，以下使用2-opt的示例：

Algorithm EXECUTE-2OPT-MOVE
Input: 当前路径 T，第一条要断开边的端点 t1, t2。
Output: 元组 (improved, T)，其中 improved 为布尔值。
1. x1_cost ← dist(t1, t2)
2. for 每一个节点 t3 ∈ T do
3.    // 过滤无效节点：t3 不能是 t1, t2，且构成的边不能相邻
4.    if t3 ∉ {t1, t2} and t3 is not adjacent to t1 or t2 then
5.       t4 ← next_node(t3)
6.       x2_cost ← dist(t3, t4)
7.       // 计算 2-opt 交换后的新连接成本
8.       y1_cost ← dist(t1, t3)
9.       y2_cost ← dist(t2, t4)
10.      // 计算增益：(断开的边总长) - (新连接的边总长)
11.      gain ← (x1_cost + x2_cost) - (y1_cost + y2_cost)
12.      if gain > 0 then
13.         // 执行 2-opt 反转操作：将 t2 到 t3 之间的路径段反转
14.         Reverse_Segment(T, t2, t3)
15.         return (true, T)
16.      end if
17.   end if
18. end for
19. return (false, T)

领域搜索算法与梯度下降算法相近，两者都是通过迭代改进当前解，逐步逼近局部最优解。这种算法适用于离散空间优化，而后者适用于有一阶导的连续可微函数的优化。另外，这两种算法都比较依赖初始点的选择。

变邻域搜索算法(Variable Neighborhood Search, VNS)使用多种领域结构，并在其中交替搜索。

禁忌搜索算法 TS

禁忌搜索是对局部邻域搜索的一种扩展，旨在实现全局寻优。

在搜索过程中，标记已经搜索过的局部最优解（或移动操作）为“禁忌”，在接下来的迭代中尽量避开这些禁忌对象。它允许算法接受劣解（即目标函数值变差的解），以此来跳出局部最优陷阱。

禁忌搜索算法的构成要素包括：
禁忌表 (Tabu List)：记录近期的历史移动或状态，防止搜索循环

禁忌对象：放入表中的元素，可以为状态本身、状态分量或者目标值
禁忌任期 (Tabu Tenure)：对象在表中滞留的步数
在当前解 $x$ 的邻域 $N(x)$ 中，选择不在禁忌表中的最优候选解 $s_k(x)$，即使该解的目标值比当前解差（$c(s_k(x)) > c(x)$）。

但如果某个候选解虽然在禁忌表中，但其目标值优于历史最好解（或满足特定渴望水平），则无视禁忌状态，直接接受该解。

Algorithm TABU-SEARCH
Input: 初始解 x_0，禁忌长度 L，最大迭代次数 k_max。
Output: 全局最优解 x^*。
1. x ← x_0
2. x^* ← x_0                     // 初始化全局最优解
3. T ← ∅                         // T 为禁忌表 (队列结构)
4. k ← 0
5. while k < k_max
6.    k ← k + 1
7.    BestCandidate ← null
8.    BestVal ← -∞
9.    ChosenMove ← null
10.   for 每一个候选解 y ∈ N(x) do
11.      move ← 从 x 变换到 y 的操作 (例如: Swap(i, j))
12.      is_tabu ← (move ∈ T)
13.      is_aspiration ← (f(y) > f(x^*))
14.      if (not is_tabu) or is_aspiration then
15.         // 在所有合法候选中寻找最优 (允许劣解)
16.         if f(y) > BestVal then
17.            BestCandidate ← y
18.            BestVal ← f(y)
19.            ChosenMove ← move
20.         end if
21.      end if
22.   end for
23.   if BestCandidate = null then break   //陷入死胡同，提前终止
24.   x ← BestCandidate
25.   if f(x) > f(x^*) then x^* ← x
26.   T ← T ∪ {ChosenMove}
27.   if |T| > L then
28.      从 T 中移除最早进入的移动 (FIFO)
29.   end if
30. end while
31. output x^*

主动禁忌搜索
基本 TS 的难点在于禁忌长度（Tabu Size）的设定：太短导致循环，太长限制搜索。主动 TS 通过反馈机制自动调整参数。

算法记录所有访问过的解：用于检测是否陷入长周期的循环。
如果发现当前解以前访问过（重复），说明陷入循环，将 $t$ 乘以 $N_{IN} > 1$（加强禁忌）。
如果连续多步没有重复解，说明搜索路径健康，将 $t$ 乘以 $N_{DE} < 1$（放松禁忌）。
如果解的重复次数超过阈值（$num_esc$），说明单纯调整禁忌长度无效。执行随机扰动（随机移动若干步），强行跳出当前区域。

模拟退火算法 SA

Metropolis准则
设当前状态为 $i$，能量为 $E_i$；新状态为 $j$，能量为 $E_j$。
能量差 $\Delta E = E_j - E_i$。
接受新状态 $j$ 的概率 $P$ 为：

$P = \begin{cases} 1, & \text{若 } \Delta E < 0 \text{ (能量降低，解变优)} \\ \exp(-\frac{\Delta E}{kT}), & \text{若 } \Delta E > 0 \text{ (能量升高，解变差)} \end{cases}$

粒子允许以一定概率接受劣解，从而具备跳出局部最优的能力。温度 $T$ 越高，接受劣解的概率越大。

马尔科夫链

SA 算法的随机搜索过程可以被建模为一个马尔可夫链 (Markov Chain)。

从状态 $i$ 转移到状态 $j$ 的概率 $p_{ij}$ 由两部分组成：

生成概率 (Generation Probability, $g{ij}$)：在 $i$ 的邻域中选择 $j$ 的概率。通常假设是对称的，即 $g{ij} = g_{ji}$。
接受概率 (Acceptance Probability, $a_{ij}$)：基于 Metropolis 准则。 $a_{ij}(T) = \min \left( 1, \exp \left( -\frac{f(j) - f(i)}{T} \right) \right)$ 转移概率为 $p{ij} = g{ij} \cdot a_{ij}$。

根据热力学统计物理，在温度 $T$ 下达到热平衡时，系统处于状态 $i$ 的概率遵循 Boltzmann 分布：

$P_i(T) = \frac{\exp(-E_i/T)}{\sum_{j=1}^n \exp(-E_j/T)}$

由于转移概率满足细致平衡条件：$Pi(T) p{ij} = Pj(T) p{ji}$，因此 Boltzmann 分布确实是该马尔可夫链的平稳分布。

在高温下，系统处于各个状态的概率几乎相等。算法行为近似于随机游走 (Random Walk)，进行广域搜索。
当温度趋近于 0 时，系统以概率 1 收敛于最低能量状态（全局最优解）。

但是，理论上要求无限满的降温才能保证系统的每一步近似为稳态（热平衡），才能最终收敛到全局最优解。通常需要设计合理的冷却进度表提供较好的近似解。

对于算法：

初始温度 ($T_0$)要求足够高，使得 $\exp(-\Delta E/T_0) \approx 1$，保证算法初期能自由探索解空间，不依赖初始解，避免过早陷入局部最优
等温过程长度要求在每个温度下的迭代次数足够多，通常设为问题规模的函数（如 $n$ 或 $n^2$）
降温策略可以选择几何降温$T{k+1} = \alpha \cdot T_k$或者算数降温$T{k+1} = T_k - \Delta T$。
终止温度要求足够低，以锁定最终解

Algorithm SIMULATED-ANNEALING
输入：初始解 s_0，初始温度 T_0，等温过程迭代次数 L，冷却系数 α (0.95 ~ 0.99)，终止温度 T_f。
输出：全局最优解 s_best。
1. s ← s_0
2. s_best ← s_0
3. T ← T_0
4. while T > T_f
5.    // 内循环：在当前温度下进行 L 次迭代以达到热平衡
6.    for k ← 1 to L
7.       s' ← GenerateNeighbor(s)      // 在邻域内生成一个新的候选解
8.       ΔE ← Cost(s') - Cost(s)       // 计算能量差（目标函数值变化）
9.       if ΔE < 0 then
10.         // 情况 A：新解更优 (能量更低)，贪心接受
11.         s ← s'
12.         if Cost(s) < Cost(s_best) then s_best ← s
13.      else
14.         // 情况 B：新解较差 (能量更高)，按概率接受
15.         p ← exp(-ΔE / T)           // Metropolis 准则
16.         r ← Random(0, 1)           // 生成 [0, 1) 之间的随机数
17.         if r < p then s ← s'       // 即使是劣解也接受，以跳出局部最优
18.      end if
19.   end for
20.   T ← α * T                        // 几何降温过程
21. end while
22. output s_best

5.2.2 群体算法

遗传算法 GA

算法模仿达尔文的生物进化论——“物竞天择，适者生存”。通过模拟生物种群的繁衍、变异和自然选择，让解群体在迭代中不断进化，最终逼近全局最优解。

生物学术语	优化问题对应	含义
个体 (Individual)	解 (Solution)	问题的某一个可行解
种群 (Population)	解集 (Set of Solutions)	一组可行解的集合，并行搜索的基础
染色体 (Chromosome)	编码 (Encoding)	解的数字化表示（如二进制串）
基因 (Gene)	特征/分量 (Feature)	解的某一特定维度或属性
适应度 (Fitness)	目标函数值 (Objective Value)	衡量解质量好坏的标准

算法每一代包含以下步骤:

种群初始化: 随机生成 $N$ 个初始个体构成第一代种群。
适应度评估：计算每个个体的适应度值 $F(x)$，适应度通常要求非负且越大越好，对于最小化问题，需进行转换（如取倒数或相反数）。
选择操作：优胜劣汰，让适应度高的个体有更多机会遗传给下一代
- 轮盘赌选择 (Roulette Wheel Selection)：个体被选中的概率与其适应度成正比。概率 $P_i = F_i / \sum F_j$
- 锦标赛选择 (Tournament Selection)：随机选取 $k$ 个个体，其中最优者胜出
- 精英保留 (Elitism)：强制将当代最优个体直接复制到下一代，防止最佳基因丢失
遗传算子：
- 交叉：按交叉概率 $P_c$（通常较大，如 0.9）选择两个父代个体，交换其部分染色体片段。
- 变异：按变异概率 $P_m$（通常极小，如 0.01~0.1）随机改变染色体上的某一位（如 0 变 1）。

以0-1 背包问题为例：给定 $n$ 个物品（价值 $p_i$，重量 $w_i$）和背包容量 $W$，选择物品子集使得总价值最大且总重量不超过 $W$。

编码：常用二进制编码 $X = (x_1, \dots, x_n)$，$x_i \in {0, 1}$

对于随机生成或交叉产生的子代可能违反重量约束，可以在适应性函数中加入惩罚项，也可以将非法解修复为合法解：

贪心修复：计算物品的性价比 $p_i/w_i$ 并降序排列；对于超重的非法解，优先保留性价比高的物品，贪心地移除性价比低的物品，直到满足约束。

Algorithm GENETIC-KNAPSACK
Input:  n 个物品的集合 (价值 p, 重量 w)，背包容量 W，
        种群大小 N_pop，最大迭代次数 MaxGen，
        交叉概率 P_c，变异概率 P_m。
Output: 全局最优解 BestSol。

1. R_order ← Sort indices by (p_i / w_i) ascending
2. Population ← Generate N_pop random binary vectors
3. for each individual S in Population do
4.    GREEDY-REPAIR(S, W, R_order)   
5.    Evaluate Fitness(S)            
6. end for
7.  BestSol ← GetBest(Population)
8.  for gen ← 1 to MaxGen do
9.     NewPop ← ∅
10.    // 精英保留策略
11.    NewPop ← NewPop ∪ {BestSol}
12.    while |NewPop| < N_pop do
13.       // 锦标赛选择
14.       Parent1 ← TournamentSelect(Population)
15.       Parent2 ← TournamentSelect(Population)
16.       // 2. 交叉 (Crossover)
17.       if Random(0, 1) < P_c then
18.          (Child1, Child2) ← OnePointCrossover(Parent1, Parent2)
19.       else
20.          (Child1, Child2) ← (Parent1, Parent2)
21.       end if
22.       Mutate(Child1, P_m)
23.       Mutate(Child2, P_m)
24.       GREEDY-REPAIR(Child1, W, R_order)
25.       GREEDY-REPAIR(Child2, W, R_order)
26.       Evaluate Fitness(Child1)
27.       Evaluate Fitness(Child2)
28.       NewPop ← NewPop ∪ {Child1, Child2}
29.    end while
30.    Population ← NewPop
31.    CurrentBest ← GetBest(Population)
32.    if Fitness(CurrentBest) > Fitness(BestSol) then BestSol ← CurrentBest
33. end for
34. output BestSol

Algorithm GREEDY-REPAIR
Input:  个体解 S (二进制向量 x_1...x_n)，背包容量 W，
        排序索引列表 R_order (性价比从小到大)。
Output: 修复后的合法解 S (原地修改)。
1. CurrentWeight ← CalculateWeight(S)
2. if CurrentWeight > W then
3.    for each index i in R_order do
4.       if S[i] == 1 then
5.          S[i] ← 0                
6.          CurrentWeight ← CurrentWeight - w_i
7.          if CurrentWeight ≤ W then break  /
8.       end if
9.    end for
10. end if

免疫算法 IA

将生物免疫系统的概念（如抗原识别、抗体克隆、免疫记忆）引入遗传算法，旨在保留原算法优良特性的前提下，抑制早熟收敛和种群退化。

算法的流程为：

初始化 (Initialization)：随机生成初始抗体种群（候选解集）。
亲和度计算 (Affinity Calculation)：评估每个抗体的质量（如计算目标函数值）。
选择与克隆 (Selection & Cloning)：
- 对优秀抗体进行复制。关键点：克隆的数量与亲和度成正比（越优秀的解，复制的副本越多）。
超变异 (Hypermutation)
- 对克隆后的抗体进行变异操作以探索局部区域，对克隆后的抗体进行变异操作以探索局部区域
抑制与多样性保持 (Suppression)
- 计算抗体间的相似度（如欧氏距离、汉明距离）,若抗体过于相似（浓度过高），则移除或抑制冗余抗体，防止同质化
- 补充随机生成的“新抗体”以维持种群多样性
免疫记忆 (Immune Memory)：将历代最优抗体存入记忆库，用于加速后续搜索或应对动态环境变化。
终止判断：达到最大迭代次数或满足精度要求。

免疫算法比遗传算法更适合用来进行多模态优化和动态环境优化。

蚁群算法 ACO

蚂蚁在寻找食物过程中会分泌为信息素。由于短路径往返时间短，单位时间内通过的蚂蚁更多，留下的信息素累积更快，从而吸引更多后续蚂蚁，最终形成信息正反馈，使整个群体集中到最短路径上。

基本蚁群算法采用人工蚂蚁的行走路线表示可行解，通过信息素交换路径信息，形成集体自催化行为寻找最优路径。

以TSP问题为例：
蚂蚁 $k$ 在 $t$ 时刻由城市 $i$ 转移到城市 $j$ 的概率 $P_{ij}^k(t)$ 定义为：

$P_{ij}^k(t) = \frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{s \in allowed_k} [\tau_{is}(t)]^\alpha \cdot [\eta_{is}]^\beta}$

$\tau_{ij}(t)$：边 $(i, j)$ 上的残留信息量。
$\eta{ij} = 1/d{ij}$：启发式因子，反映由 $i$ 转移到 $j$ 的期望程度。
$\alpha, \beta$：分别为信息启发因子和期望启发因子，反映了信息素与距离的相对重要程度。
$allowed_k$：蚂蚁 $k$ 下一步允许选择的城市集合。

信息素更新更新公式：

$\tau_{ij}(t+n) = (1-\rho) \tau_{ij}(t) + \Delta \tau_{ij}$

$\rho \in [0, 1)$：信息素挥发系数
$\Delta \tau{ij} = \sum{k=1}^m \Delta \tau_{ij}^k$：本轮全体蚂蚁在路径 $(i, j)$ 上留下的信息素增量

常见的更新策略

蚁周模型 (Ant-Cycle Model)：利用整体信息，在蚂蚁完成一个循环后更新路径信息素。释放量 $\Delta \tau_{ij}^k = Q/L_k$
蚁量模型 (Ant-Quantity Model)：利用局部信息，蚂蚁每走一步更新一次。释放量 $\Delta \tau{ij}^k = Q/d{ij}$。

Algorithm ANT-COLONY-OPTIMIZATION-TSP
输入：城市坐标或距离矩阵 D，蚂蚁数量 m，最大迭代次数 Gen_max，
      信息启发因子 α，期望启发因子 β，挥发系数 ρ，信息素强度 Q。
输出：全局最优路径 BestTour 及其长度 BestLength。

1. 初始化所有边 (i, j) 上的初始信息素 τ_{ij} 为一常数 (如 1.0)
2. BestLength ← ∞
3. BestTour ← ∅
4. k_gen ← 0
5. while k_gen < Gen_max
6.    k_gen ← k_gen + 1
7.    for k ← 1 to m
8.       随机选择一个起始城市放入蚂蚁 k 的禁忌表 tabu_k 中
9.    end for
10.   // 蚂蚁构建路径 (逐步移动直至走完所有城市)
11.   for step ← 1 to n - 1    
12.      for k ← 1 to m
13.         i ← 蚂蚁 k 当前所在城市
14.         根据状态转移概率 P_{ij}^k(t) 选择下一个城市 j:
15.         将城市 j 加入 tabu_k，更新当前城市为 j
16.      end for
17.   end for
18.   // 计算并更新本轮最优解
19.   for k ← 1 to m
20.      L_k ← 蚂蚁 k 经过的路径总长度
21.      if L_k < BestLength then
22.         BestLength ← L_k
23.         BestTour ← tabu_k
24.      end if
25.   end for
26.   // 息素更新 (基于蚁周模型)
27.   for 每一条边 (i, j) in E do
28.      τ_{ij} ← (1 - ρ) * τ_{ij}
29.   end for
30.   for k ← 1 to m
31.      Δτ_k ← Q / L_k
32.      for 每一条属于 tabu_k 的边 (i, j) do
33.         τ_{ij} ← τ_{ij} + Δτ_k
34.      end for
35.   end for
36.   for k ← 1 to m do tabu_k ← ∅
37. end while
38. output BestTour, BestLength

粒子群优化算法 PSO

设想一群鸟在随机搜索食物，区域内只有一块食物，鸟儿不知道食物位置，但知道当前离食物有多远（通过适值函数评估）。寻找食物的最优策略是搜寻目前离食物最近的鸟的周围区域。

PSO 将问题的每一个可行解看作解空间中的一个“粒子”。粒子在 $D$ 维空间中以一定的速度飞翔，其位置随迭代动态变化。

第 $i$ 个粒子的位置：$x_{id}^k$，代表当前的候选解。
第 $i$ 个粒子的速度：$v_{id}^k$，决定飞行的方向和距离。
个体极值 ($pbesti$)：$p{id}^k$，粒子 $i$ 自身搜索到的历史最好点。
全局极值 ($gbest$)：$p_{gd}^k$，群体内（或邻域内）所有粒子所经过的历史最好点。

演化方程

速度更新方程
- $\xi, \eta$ 为 $[0, 1]$ 上的独立随机变量。
- $c_1, c_2$ 为加速因子 (Learning Factors)，调节向个体最优和群体最优靠近的步长
位置更新方程 $x_{id}^{k+1} = x_{id}^k + v_{id}^{k+1}$

算法每一步都根据演化方程维护所有粒子状态，直至终止。

5.3 综述：最短路径问题的多维视角 (Review: Shortest Path)

本节以“最短路径”为线索，串联全课算法思想。

5.3.1 问题描述

单源最短路径问题：在一个连通的有向无环图（或一般图）中，每条边带有非负权重（距离）。给定起点（源点）和终点，目标是找到一条路径，使得该路径上所有边的权重之和最小。

给定一个有向加权图 $G = (V, E, W)$

顶点集 (Vertex Set)：$V = {v_1, v_2, \dots, v_n}$，表示网络中的所有节点。
边集 (Edge Set)：$E \subseteq V \times V$，其中每条边 $e = (u, v)$ 表示从节点 $u$ 到节点 $v$ 的直接路径。
权重函数 (Weight Function)：$w: E \rightarrow \mathbb{R}_{\geq 0}$。对于每一条边 $(u, v) \in E$，有一个非负实数权重 $w(u, v)$，代表物理距离、时间或成本。

路径定义 (Path Definition)：定义一条从起点 $s$ 到终点 $d$ 的路径 $P$ 为顶点的序列：

$P = (v_0, v_1, v_2, \dots, v_k)$

其中：$v0 = s$，$v_k = d$。对于所有的 $0 \leq i < k$，满足 $(v_i, v{i+1}) \in E$。

目标函数 (Objective Function)定义路径 $P$ 的总成本 $C(P)$ 为该路径上所有边权重的累加和：

$C(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})$

我们的目标是寻找一条最优路径 $P^*$，使得：

$C(P^*) = \min \{ C(P) \mid P \text{ 是从 } s \text{ 到 } d \text{ 的可行路径} \}$

算法名称	时间复杂度 (Time Complexity)	空间复杂度 (Space Complexity)	备注 (Remarks)
蛮力/穷举法 (Brute Force)	$O(V \cdot V!)$	$O(V)$	尝试所有全排列，仅适用于极小规模图。
图的 BFS (广度优先)	$O(V!)$	$O(V \cdot V!)$	允许顶点重复访问以穷尽路径，内存消耗极高。
图的 DFS (深度优先)	$O(V!)$	$O(V)$	允许重复访问。内存消耗较少，但搜索时间极长。
回溯法 (Backtracking)	$O(V!)$ (最坏情况)	$O(V)$	引入可行性剪枝。对 DAG 或稀疏图效率显著提升。
分支定界法 (Branch & Bound)	$O(V!)$ (最坏情况)	$O(V^2)$ 或更多	基于 BFS + 最优性剪枝（如当前路径已超已知最短则舍弃）。
动态规划 (DP)	$O(V+E)$	$O(V)$	仅适用于有向无环图 (DAG)，利用拓扑序计算。
Dijkstra 算法	$O(V^2)$	$O(V)$	贪心策略。使用斐波那契堆可优化至 $O(E + V \log V)$。
Floyd-Warshall 算法	$O(V^3)$	$O(V^2)$	解决任意两点间的最短路径，而非单源。

5.3.2 穷举法

基础的穷举法列出全排列路径，对于$n$个节点的列表，总共有：

$1+\sum_{i = 1}^{n-2}\left(\prod_{j = 1}^{i}(x-j)\right) = O(n!)$

种排列。对于每一种排列，需要$O(n)$的时间复杂度验证是否可行和计算权重。因此，这种算法的时间复杂度为$O(n\cdot n!)$

这种算法的伪代码可以写作：

Algorithm EXHAUSTIVESEARCH(V,s,d，E,W)
Input: 顶点集V，起点s，终点d，权重矩阵W，。
Output：最短路径P_m

V_mid <- V / {s,d}
P_m <- ∅
w_m <- infinity

for i <- 1 to |V_mid| do
    Cur_P = {s} ∪ sub_P ∪ {d}
    Cur_w = 0
    isValid = true
    for 子排列 Sub_P in V_mid的所有i个元素的排列 do
        for i <- 0 to |Sub_P| do
            if (Cur_P(i),Cur_P(i+1)) in E then
                Cur_w <- Cur_w + W(u,v)
            else
                isValid = false
                break
            end if
        end for
        if isValid and Cur_w < W_m then
            P_m <- Cur_P
            w_m <- Cur_w
        end if
    end for
end for
output P_m,w_m

5.3.3 广度优先搜索 BFS

广度搜索都能保证搜索到的路径一定是合法的。

从起点开始进行广度优先搜索，并维护一个储存(u,d)（顶点和到达该顶点的代价）的队列
每一步搜索从队列中取出$(u, d)$，遍历 $u$ 的所有邻居 $v$，对于每一个邻居，构造新状态 $(v, d + w(u, v))$ 并入队
如果 $v$ 是终点 $G$，且当前路径长度 $d + w(u, v)$ 小于已记录的全局最短距离 $dist_min$，则更新 $dist_min$，对于此节点，不再加入新节点到队列。
当队列空时，或已经计算的元素数大于$\frac{n^n-1}{n-1}$（n层的n叉完全树的总节点数）时截止计算（事实上，因为图是无环的，总计算书不会超过这个值）。

Algorithm BFS
w_m <- infinity
Queue <- empty queue
Queue.enqueue((s,0))
while Queue is not empty:
    (v,w_curr) <- Queue.dequeue()
    for each edge (u,v) in E do
        w_new <- w_curr+w(u,v)
        if v == d then
            if w_new < w_m then
                w_m = w_new
            end if
        else
            Queue.enqueue((v,w_new))
        end if
    end for
end while
output w_m

注意以上伪代码展示的算法没有将路径加入队列元素中。

算法的时间复杂度为$O(n!)$，相当于不需要检查可行性的枚举法。

算法的空间复杂度，如果需要储存路径，为$O(n\cdot n!)$

5.3.4 深度优先搜索&回溯法

深度优先搜索策略：

从起点开始进行深度搜索，并维护一个储存(u,d)的栈
其余部分与广度搜索策略基本完全相似

使用深度优先搜索可以将路径额外储存在一个长度为$n$的列表中，动态维护列表。为了保证能够正确回溯，需要使用递归方式来进行深度优先搜索。

Algorithm DFS
    p_m <- empty list [n]
    p_curr <- empty list [n]
    w_m <- infinity

    DFS(s,0)
    output w_m,p_m

Procedure DFS(u,w_curr)
    p_curr.append(u)
    if u = d then
        if w_curr < w_m then
            w_m <- w_curr
            p_m <- p_curr.copy()
        end if
    else
        for each edge (u, v) ∈ E do
            w_new <- w_curr + w(u, v)
            if w_new < w_m then
                DFS(v,w_new)
            end if
        end for
    end if
    p_curr.pop()

这种方法不改变时间复杂度，但是将空间复杂度降低到线性。

为了进一步优化性能，可以引入剪枝的思想，即当当前分支的w_curr已经超过w_m时，直接回溯。

5.3.5 分支定界法

这是一个最小化问题，因此v_m可以直接作为上界。我们寻找一种分支下界（可能能达到的最小值）的计算方法。

考虑算法结构，从s出发，s的所有邻域节点v都是可能的下个分支。一种可能的下界确定法：

预计计算整个图中，除去起点所有节点的最小进入权重，也就是对于任意节点w，所有(x,w)的最大权重。
对于邻域v，其下界为已选路径权重（对于当前情况就是w(s,v)）+未选节点最小权重和
也就是贪心最小边下界

相同问题的下界确定法是v到终点的欧几里得距离或者哈密顿距离，但是问题没有相关约束，因此不能使用。

除此之外还可以想到，可以为每个顶点维护一个最短路径状态，即从原点到该顶点的已知端点距离。如果当前路径的这一项大于已知最短距离，则直接放弃该分支。

数据结构方面，我们使用优先队列，这是一种出列优先级最大的元素的队列。

Algorithm BB
输入：图 G=(V, E)，起点 s，终点 d，下界函数 LB(u)。
输出：最短距离 d_m，最短路径p_m

d_m <- ∞
PQ <- empty priority queue
PQ.push( (s, 0, emptylist, LB([s])) )
p_m <- empty List
Shorted_path <- empty Map
for vertex in V do
    Shorted_path.put((vertex,∞))
Shorted_path[s] <- 0

while PQ is not empty do
    (u, curr_w,curr_path, curr_bound) ← PQ.pop_min()
    // 两种剪枝可能
    if curr_w > Shorted_path[u] then
        continue
    else
        Shorted_path[u] = curr_w
    end if
    if curr_bound >= d_m then
        continue
    end if

    for each neighbor v of u do
        new_w <- curr_w + w(u,v)
        new_path = curr_path.append(v)
        if v = d then
            if new_w < d_m then
                d_m <- new_w
                p_m <- new_path
        else
            new_bound <- LB(new_path )+curr_w
            if new_bound > d_m then
                continue
            end if
            PQ.enqueue((v,new_w,new_path,new_bound))
        end if
    end for
end while
output d_m,p_m

这种算法的时间和空间复杂度都依赖于优先队列的大小$E$，分别为$O(|E| \log |V|)$和$O(|E| \cdot |V|)$，这种算法的最坏时间和空间复杂度与广度搜索相同（甚至因为使用了优先队列而更差）。

5.3.6 动态规划

该问题与各种分割问题，比如矩阵最少乘法问题相似。有递归式：

$T(i,j) = min_{k\in i到j的中间节点集}(T(i,k)+T(k,j))$

问题主要在于中间节点集合如何求取。一种可行的设想是对节点进行拓扑排序

使得如果图中存在边 $(u, v)$，则在排序结果中 $u$ 必须出现在 $v$ 之前。

直接写出自定而上的伪代码：

Algorithm DP

T <- double-dim List [n,n] initial with infinity
D <- TopologicalSort(s) // 为了方便，假定D[i]返回的是排序后i对应的位置
for i <- 0 to n do
    T[i,i] = 0

Check(s,d)//假定s、d为对应节点的编号

Procedure Check(i,j)

if D[i]>D[j] then
    return infinity //理论上不会进入这一步

if T[i,j] is not inifinity then
    return T[i,j]

if (i,j) in E then
    base_length = w(i,j)
else
    base_length = infinity
end if

for each k that D[k] < D[j] and D[i] < D[k] do
    possible_length = Check(i,k)+Check(k,j)
    if possible_length < base_length then
        base_length = possible_length
    end if
end for
T[i,j] <- base_length
return T[i,j]

其中TopologicalSort是我们讨论过的tanh算法，不断寻找并移除那些不依赖任何其他节点的节点。

Algorithm TOPOLOGICAL-SORT
1.  L ← empty list                  // 用于存储最终的拓扑序列
2.  S ← empty queue (或 stack)      // 存储所有入度为 0 的节点
3.  InDegree ← Map {v: 0 for v in V} // 初始化入度表
4.  // 1. 统计每个节点的入度 (In-degree)
5.  for each edge (u, v) ∈ E do
6.      InDegree[v] ← InDegree[v] + 1
7.  end for
8.  // 2. 将所有初始入度为 0 的节点加入集合 S
9.  for each vertex v in V do
10.     if InDegree[v] == 0 then
11.         S.push(v)
12.     end if
13. end for
14. // 3. 主循环：不断移除入度为 0 的节点
15. while S is not empty do
16.     u ← S.pop()
17.     L.append(u)                 // 将 u 加入拓扑序列
18.     // 遍历从 u 出发的所有边 (u, v)
19.     for each neighbor v of u do
20.         InDegree[v] ← InDegree[v] - 1  // “移除”边 (u, v)
21.         // 如果 v 的入度变为 0，说明它依赖的所有前驱都已处理
22.         if InDegree[v] == 0 then
23.             S.push(v)
24.         end if
25.     end for
26. end while
27. // 4. 环路检测
28. if |L| < |V| then
29.     return Error (图中有环，不存在拓扑序)
30. else
31.     return L
32. end if

这种算法的时间复杂度很高，对于表中的每个元素，都需要一个关于k的循环处理。在稠密图情况下，这个步骤可能是O(n)的时间复杂度，因此，总的时间复杂度来到了O(n^3)。

这个算法为什么会复杂那么多呢？这个算法，如其的递归形式，实际上可以计算任意两点间的最短路径，并没有使用到起点和终点唯一的约束。

实际上，这个算法已经与Floyd-Warshall算法复杂度相同，因此不如直接使用Floyd-Warshall算法。区别仅在于中间节点集合如何求取的问题。

现在使用拓扑排序是在有向无环图假设下，限制了k的规模，使得T[i,k]和T[k,j]一定已经得到计算（或者说T[i,k]和T[k,j]的计算不依赖于T[i,j]的计算）。Floyd-Warshall算法则将T在逻辑上拓展为三维：T[i,j,k]，在计算时状态转移方程变化为：

$dp[k][i][j] = \min(dp[k-1][i][j], \quad dp[k-1][i][k] + dp[k-1][k][j])$

也就是k被放在最外环运行：

Algorithm FLOYD-WARSHALL
1. D ← W 的拷贝
2. // k 在最外层！这是动态规划“阶段”的体现。
3. for k ← 1 to n do
4.    for i ← 1 to n do
5.       for j ← 1 to n do
6.          if D[i][k] + D[k][j] < D[i][j] then
7.             D[i][j] ← D[i][k] + D[k][j]
8.          end if
9.       end for
10.   end for
11. end for
12. 
13. output D

伪代码中可以看到，虽然形式上T被拓展为三维数组，当实际操作中只需要使用2维数组。很巧妙的算法。

重新考虑这个动规问题的阶段的定义。从起点开始，我们可以定义每增加一个节点是一个状态。此时的递归公式转换为：

$T[v] = \min(T[u] + w(u, v))$

变成了一个线性的动规问题。

Algorithm DP-SHORTEST-PATH-DAG
输入：有向无环图 G=(V, E)，起点 s，终点 d。
输出：最短距离 dist[d]。

1.  // 1. 预处理：拓扑排序 (确保计算 v 时，其所有前驱节点已计算完成)
2.  L ← TopologicalSort(G) 
3.  
4.  // 2. 初始化状态数组
5.  dist ← Map {v: ∞ for v in V}
6.  dist[s] ← 0
7.  parent ← Map {v: null for v in V} // 用于回溯路径
8.  
9.  // 3. 状态转移 (自底向上/线性扫描)
10. for each node u in L (从起点 s 所在的顺序开始) do
11.    if dist[u] < ∞ then
12.       for each neighbor v of u do
13.          // 核心转移方程：dist[v] = min(dist[v], dist[u] + w(u, v))
14.          if dist[u] + w(u, v) < dist[v] then
15.             dist[v] ← dist[u] + w(u, v)
16.             parent[v] ← u
17.          end if
18.       end for
19.    end if
20. end for
21. 
22. // 4. 重构路径
23. p_m ← ReconstructPath(parent, d)
24. output dist[d], p_m

在这个动规中，实际上维护了从起点到每个节点的可能的最近信息。这种算法的时间复杂度取决于拓扑排序，为$O(E+V)$

这个算法是有向无环图 (DAG) 的最优解法。

5.3.7 贪心算法

Dijkstra 算法

这是非负权单源图最短路路径的最优解，在这个图中，目前离起点最近的那个未访问节点，不可能通过绕路变得更近，也就是说，当准备计算离起点地n进的起点时，只有比它更近的节点可能会影响计算。

流程：

在这个图中，目前离起点最近的那个未访问节点，不可能通过绕路变得更近
从堆中弹出距离最小的节点 $u$
将 $u$ 标记为“已确定”（后续不再处理）
遍历 $u$ 的邻居 $v$。如果 $dist[u] + w(u, v) < dist[v]$，则更新 $dist[v]$ 并将 $v$ 压入堆（或更新堆中 $v$ 的优先级）。

这种算法的时间复杂度为O(ElogV)，即遍历边、最优队列每次维护的代价是logV

大规模图预处理：收缩层次结构

节点重要性排序 (Node Ordering)给图中的每一个节点 $v$ 赋予一个等级 $Rank(v)$：

试探性地移除节点 $v$，计算需要增加多少条“捷径”边，减去 $v$ 原本的边数。需要增加的捷径越少，说明 $v$ 越不重要（越处于死角），应该越先被移除

节点收缩，按照 Rank 从低到高，依次“收缩”（移除）节点。
假设我们要移除节点 $v$：

找到所有能到达 $v$ 的邻居 $U = {u_1, u_2, \dots}$
找到所有从 $v$ 出发的邻居 $W = {w_1, w_2, \dots}$
对于每一对 $(u, w)$，原本有一条路径 $u \to v \to w$。我们必须检查：在不经过 $v$ 的情况下，是否还存在另一条比 $u \to v \to w$ 更短或相等的路径
- 如果存在：说明 $v$ 对这条路不重要，直接删掉 $v$
- 如果不存在：说明 $v$ 是必经之路。为了保持图的连通性和距离正确性，我们必须在 $u$ 和 $w$ 之间添加一条人工边，其权重为 $w(u,v) + w(v,w)$

查询变为双向 Dijkstra 搜索

从起点 $s$ 出发，只走 $Rank(neighbor) > Rank(current)$ 的边
从终点 $t$ 出发，只走 $Rank(neighbor) > Rank(current)$ 的反向边
两个搜索会在某个最高等级的节点 $v{top}$ 相遇，最短路径长度 = $\min(dist{fwd}[v] + dist_{bwd}[v])$。