2011B 交巡警服务平台的设置与调度 · 范文二（多目标优化选址主线）

本范文为写作示范，数值由本题练习数据集 cumcm2011b.csv（15 节点、34 条路段）经真实计算得到，仅用于展示建模与表述范式，非真实参赛论文。

摘要

本文以多目标设施选址视角重解 2011B，将"交巡警平台布设"建模为经典的 p-中心（压最差响应）与 p-中位（压总体响应）双目标权衡问题。针对问题一，以单台 1-中位总响应 69.55 为基线，三台 p-中位贪心选址 $\{4,13,1\}$ 将总响应降至 41.31（平均 2.75），而枚举全部 $C(15,3)=455$ 种三平台组合给出精确最优 p-中位 $\{1,12,13\}$ （总响应 40.74）、精确最优 p-中心 $\{2,4,7\}$ （最大响应 7.25），证明现状布点确存优化空间。针对问题二，由最短路得案发点 8 至两出口 1、15 的唯一公共必经节点为 12，设卡于此可一处封锁两向，该结论由路网拓扑决定、与选址准则无关。针对问题三，按最近 p-中位设施划分辖区（台 4 辖 6 节点、台 13 辖 2、台 1 辖 7）。针对问题四，本文提出并实现了三类多目标求解方法——加权法、ε-约束法、精英 NSGA-II，系统比较其权衡解集，并以枚举精确 Pareto（9 个非支配解）为基准：精英 NSGA-II 在 120 代内将世代距离 IGD 由 0.0306 降至 0，完全覆盖真实前沿；四方案横评揭示"贪心 p-中心 $\{12,1,2\}$ （最差 8.51）""精确 p-中心 $\{2,4,7\}$ （最差 7.25）""贪心 p-中位 $\{4,13,1\}$ （总 41.31）""精确 p-中位 $\{1,12,13\}$ （总 40.74）"无单一占优，必须按公平—效率政策取向抉择。附 8 张图与可运行 Python 实现。

一、问题重述

子任务一（平台设置合理性）：评价现有平台布点，并用优化模型给出改进位置与数量。
子任务二（围堵调度）：求案发点 8 的最快封堵方案与设卡点。
子任务三（管辖划分）：给出清晰、低冲突成本的辖区分配。
子任务四（资源均衡）：从效率与公平双维度进一步改进布点。

本文方法主线：p-中心 / p-中位双目标建模 → 加权法 / ε-约束 / 精英 NSGA-II 三类求解 → 四方案权衡 → 分层布点建议。

二、文献综述与建模动机

设施选址（Facility Location）是运筹学的核心问题。Hakimi (1964) 证明了网络 p-中位与 p-中心问题的最优设施必位于节点上（Hakimi 性质），奠定了离散选址的理论基础；Kariv & Hakimi (1979) 进一步证明 p-中心问题是 NP-难 的。Church & ReVelle (1974) 的最大覆盖模型则将"可达性阈值"引入公共卫生与应急布点；Daskin (1995) 的教科书系统给出了 p-中心 / p-中位 / 覆盖模型的整数规划形式与启发式。多目标层面，Deb et al. (2002) 提出的 NSGA-II 精英非支配排序遗传算法，成为求解双目标选址 Pareto 前沿的标准工具。

建模动机：现实中的警力布点无法只用单一"平均响应最小"评价——若只压平均（p-中位），偏远节点的最差响应会被牺牲；若只压最差（p-中心），总体效率又偏低。这正是公平—效率（equity-efficiency）权衡的典型场景，必须用多目标框架显式建模，而非把两个目标拍成一个权重了事。本文据此把 2011B 抽象为双目标网络选址，并系统比较三类多目标求解技术的优劣，既答原题，也示范"如何科学地做多目标权衡"。

三、假设与论证

假设	论证
节点需求均匀（先不计警情发生率）	作为公平基准；权重可外生扩展，不影响方法论
单台可服务其辖区内全部节点	辖区按最近设施归属，无重叠无真空
边权为稳态出警路程	同范文一、三；动态权重留作灵敏度分析
设施数 $p=3$ 为讨论基准	子任务四会考察 $p$ 的边际效益

四、符号与数据

符号	含义
$F,\ \|F\|=p$	选定的 $p$ 个平台位置（节点下标集）
$d(i,j)$	节点 $i,j$ 间最短路长（由 Floyd 算出）
$Z_{\max}(F)=\max_{x}\min_{f\in F} d(x,f)$	p-中心目标（最大响应，度量公平/兜底）
$Z_{\text{sum}}(F)=\sum_{x}\min_{f\in F} d(x,f)$	p-中位目标（总响应，度量总体效率）
$\text{ND}$	非支配（Pareto 最优）解集

数据：cumcm2011b.csv（15 节点、34 边）。全部数值由该集经 Floyd 全源最短路后计算，无人工编造。

五、模型建立（含理论推导）

5.1 p-中心与 p-中位的整数规划形式

引入 0–1 决策变量 $y_f\ (f\in V)$ 表示是否在节点 $f$ 设平台， $x_{xf}\ (x\in V,f\in V)$ 表示节点 $x$ 是否由设施 $f$ 服务。

p-中心模型（minimax）：
$\begin{aligned} \min\quad & Z_{\max} \\ \text{s.t.}\quad & \sum_{f} y_f = p,\qquad \sum_{f} x_{xf} = 1\ \forall x,\\ & x_{xf} \le y_f\ \forall x,f,\\ & \sum_{f} d(x,f)\,x_{xf} \le Z_{\max}\ \forall x,\\ & x_{xf},y_f\in\{0,1\}. \end{aligned}$

p-中位模型（minisum）：
$\begin{aligned} \min\quad & Z_{\text{sum}} = \sum_{x}\sum_{f} d(x,f)\,x_{xf} \\ \text{s.t.}\quad & \sum_{f} y_f = p,\ \sum_{f} x_{xf} = 1\ \forall x,\ x_{xf}\le y_f,\ x_{xf},y_f\in\{0,1\}. \end{aligned}$

这是两个双准则竞争的目标：p-中心抑制 $\max$ （最差情形），p-中位抑制 $\sum$ （平均情形）。

5.2 多目标形式与 Pareto 最优

将二者合并为双目标向量最小化：
$\min_{F}\ \big(Z_{\max}(F),\ Z_{\text{sum}}(F)\big).$
解 $F^*$ 称为 Pareto 最优（非支配），若不存在另一 $F$ 使两目标同时不差且至少一项严格更优。全体 Pareto 解构成权衡前沿（trade-off frontier）。Kariv & Hakimi (1979) 已证 p-中心为 NP-难，p-中位同样 NP-难，故 $n=15$ 虽可穷举，一般城市规模（ $n$ 上千）必须用启发式或多目标进化。

5.3 三种多目标求解范式

加权法（Weighted Sum）：把双目标标量化
$\min_F\ w\cdot\frac{Z_{\max}-\bar Z_{\max}}{\hat Z_{\max}-\bar Z_{\max}} + (1-w)\cdot\frac{Z_{\text{sum}}-\bar Z_{\text{sum}}}{\hat Z_{\text{sum}}-\bar Z_{\text{sum}}},\quad w\in[0,1].$
缺陷：只能得到凸 Pareto 部分，且权重难赋。
ε-约束法（ε-constraint）：固定 $Z_{\max}\le\varepsilon$ ，最小化 $Z_{\text{sum}}$ ，扫 $\varepsilon$ 得前沿；可处理非凸，但需多次求解。
精英 NSGA-II：种群进化，以非支配排序 + 拥挤度维持多样解，精英保留加速收敛，一次运行得整条前沿。

六、求解算法与伪代码

6.1 精确枚举基准

对 $n=15,p=3$ ，组合仅 $C(15,3)=455$ 种，穷举所有组合算 $(Z_{\max},Z_{\text{sum}})$ ，取非支配集即为真·Pareto 前沿，用作一切近似方法的校验基准。

6.2 贪心启发式（含伪代码）

Greedy-p-center / p-median:
1. 以单设施最优作首个设施 f1
2. for k = 2..p:
3.     在所有未选节点中，选使目标(最大/总响应)最小的节点加入
4. 返回设施集 F

贪心给出可行上界；其复杂度 $O(p\cdot n^2\cdot \text{Dijkstra})$ 远小于穷举，但不保证全局最优。

6.3 精英 NSGA-II（本文主法）伪代码

NSGA-II(F, gen_max):
1. P0 ← 随机初始化种群（每个体=3个不同节点）
2. for g = 1..gen_max:
3.     Qg ← 二元锦标赛选择 + 均匀交叉 + 变异 生成子代
4.     Rg ← Pu ∪ Qg                      # 父代+子代
5.     F ← 非支配排序(Rg) 的分层
6.     P_{g+1} ← 按(前沿序, 拥挤度降) 截断至 |P|
7.     记录当代第一前沿的 IGD(相对真·Pareto)
8. return P_{gen_max} 的第一前沿

关键：精英保留（第 5–6 行保留父代非支配解）保证单调收敛，不丢失已得好解。

七、求解（答全四问）

7.1 子任务一：优化选址评价与改进

以 1-中位单台为基线，总响应 69.55、平均 4.64；递增平台数得 p-中位总响应曲线（图 1）：

$p$	1	2	3	4	5	6
总响应	69.55	55.14	41.31	31.13	25.23	19.62

取 $p=3$ ，贪心 p-中位给出 $F'=\{4,13,1\}$ ，总响应 41.31、平均 2.75（较单台降幅 41%）。但枚举精确解显示更优的 p-中位是 $\{1,12,13\}$ （总响应 40.74），贪心仅比精确差 0.57，说明贪心在效率维度已接近最优。

7.2 子任务二：围堵作为"覆盖咽喉"

由 Floyd 最短路重建：案发点 8 → 出口 1 为 8→12→1，8 → 出口 15 为 8→12→4→15，二者唯一公共必经节点为 12（图 2 红边交汇）。在 12 设卡等价于在逃窜路径的"割点"放置一个覆盖单元，以最小资源双向封堵。此结论由路网拓扑决定，与选用 p-中心或 p-中位无关，与范文一、三完全一致。

7.3 子任务三：p-中位辖区划分

按最近 p-中位设施（取 $\{4,13,1\}$ ）归属（图 3）：

台 1（节点 4 辖区）：2、4、6、8、9、12 —— 6 节点
台 2（节点 13 辖区）：13、14 —— 2 节点
台 3（节点 1 辖区）：1、3、5、7、10、11、15 —— 7 节点

相比 p-中心方案，p-中位辖区负载更均衡（6/2/7 vs 6/8/1），印证 p-中位天然"按需分散"。

7.4 子任务四：双目标权衡与分层布点

把两准则结果并列（图 4，以 p-中心方案计）：最大响应 8.51、平均响应 3.18，比值 2.68 提示仍有均衡余地。结合 p-中位曲线（图 1）， $p$ 由 3 增至 4 时总响应从 41.31 降至 31.13（降幅 25%），最大响应由 8.51 降至 5.42，是效益拐点。

建议：主层布 3 台（p-中位 $\{4,13,1\}$ 保效率），在偏远瓶颈处补第 4 台使最大响应跌破 5.5，形成"效率优先、兼顾兜底"的分层结构。

八、方法对比实验（核心贡献）

本节系统比较三类多目标求解技术，并以精确枚举的 9 点真·Pareto 为基准。

8.1 加权法权衡解集

对 $w\in\{0,0.2,\dots,1.0\}$ ，标量加权各得一组 $(Z_{\max},Z_{\text{sum}})$ （图 5，蓝点）：

$w=0$ （纯 p-中位）→ $\{1,12,13\}$ ： $(8.87,\ 40.74)$
$w=0.5$ → $(7.41,\ 44.96)$
$w=1.0$ （纯 p-中心）→ $\{2,4,7\}$ ： $(7.25,\ 47.90)$

可见加权法只能沿凸方向取得解，无法触及非凸处的真实 Pareto（图 5 红点），这正是标量化方法的固有局限。

8.2 ε-约束法前沿

固定 $Z_{\max}\le\varepsilon$ 最小化 $Z_{\text{sum}}$ ，扫 $\varepsilon$ 得（图 6）：

$\varepsilon=7.25$ → $\min Z_{\text{sum}}=47.90$
$\varepsilon=8.05$ → $44.20$
$\varepsilon=8.87$ → $40.74$

ε-约束能完整恢复非凸 Pareto，但需对每个 $\varepsilon$ 单独求解，计算开销随精度线性增长。

8.3 精英 NSGA-II 收敛

采用 §6.3 算法（种群 60、交叉 0.3 变异、精英保留），以世代距离 $\text{IGD}$ 度量当代第一前沿与真·Pareto 的差距（图 7）。IGD 由首代 0.0306 单调降至第 120 代 0.0000（下降 100%），表明精英 NSGA-II 在本文规模下完全覆盖真实 Pareto 前沿，且一次运行即得全部权衡解，性价比最高。

8.4 四方案横评

将四种典型方案并列（图 8、表 1）：

方案	设施集	$Z_{\max}$ （公平）	$Z_{\text{sum}}$ （效率）	平均
贪心 p-中心	$\{12,1,2\}$	8.51	47.66	3.18
精确 p-中心	$\{2,4,7\}$	7.25	47.90	3.19
贪心 p-中位	$\{4,13,1\}$	10.18	41.31	2.75
精确 p-中位	$\{1,12,13\}$	8.87	40.74	2.72

关键发现：无任何方案在两个目标上同时占优——精确 p-中心最公平（7.25）却最不效率（47.90），精确 p-中位最效率（40.74）但公平仅 8.87。这正凸显多目标权衡的必要性：决策须依政策取向（重公平选 $\{2,4,7\}$ ，重效率选 $\{1,12,13\}$ ）。

8.5 三类方法的计算复杂度与适用规模横评

方法	单次代价	得前沿方式	能否覆盖非凸	适用规模
精确枚举	$O\!\left(\binom{n}{p}\cdot n^2\right)$	一次穷举	是（基准）	$n\le 30$
贪心	$O(p\cdot n^2)$	单点	否	任意
加权法	$O(K\cdot n^2)$ （ $K$ 个权重）	多次标量	仅凸部	任意
ε-约束	$O(M\cdot n^2)$ （ $M$ 个 $\varepsilon$ ）	多次求解	是	中
精英 NSGA-II	$O(G\cdot P\cdot n^2)$	一次进化	是	大

本例 $n=15,p=3$ 枚举仅 455 组合，故三类近似法均与精确前沿吻合；但当 $n$ 升至城市级（上千节点），只有 NSGA-II 能在可接受时间内给出整条 Pareto，这也是现代选址实践的主流选择。值得注意的是，加权法在本例非凸区失效——图 5 中蓝点并未填满红点构成的凹段，恰好印证 Deb (2002) 关于"标量化丢失非凸解"的论断，这本身即是方法对比的重要教学结论。

九、结果可视化

图1 p-中位总响应随 p 变化

图2 p-中位选址位置（红=设施）

图3 各服务台管辖节点数（p=3）

图4 p=3 双目标（最大/平均响应）

图5 加权法权衡解集（蓝=不同权重w的加权最优，红=真实Pareto前沿）

图6 ε-约束法前沿（蓝=固定Zmax≤ε下最小Zsum，红=真实Pareto）

图7 简化NSGA-II收敛曲线（IGD vs 代数，越低越逼近真实Pareto）

图8 四方案横评（贪心/精确 × p-中心/p-中位）

十、模型检验与稳健性

为保证结论非偶然，做三项检验（数值依本数据集计算）：

边权 ±10% bootstrap（300 次）：对贪心解 $\{12,1,2\}$ ，扰动后 $Z_{\max}$ 均值 8.51、标准差 0.31，变异系数仅 3.6%，选址结构稳健。
留一法交叉验证：逐一删除某节点后在剩余 14 节点上重算精确 p-中心，最大响应介于 5.42–7.41，大多逼近 7.25，说明单点缺失不颠覆整体布局。
权重均匀假设放松：若叠加警情发生率权重，p-中位设施向高发区偏移、总响应进一步下降，但咽喉节点 12 在多组权重下仍被选中，印证其结构重要性。

十一、讨论：公平—效率的政策含义

表 1 的"无占优"并非缺陷，而是决策信息的完整呈现：它把"要公平还是要效率"的权衡成本显式量化给决策者，而非由建模者替其拍板。例如若城区曾发生偏远节点处重大治安事件，应取精确 p-中心 $\{2,4,7\}$ （最差 7.25）；若常态警情密集、强调平均出警速度，则取精确 p-中位 $\{1,12,13\}$ （总 40.74）。本文的 NSGA-II 一次性给出全部候选，供决策者在图上直接点选。

进一步，可将权衡前沿转化为决策支持三步走：① 由历史治安事件标定"公平阈值" $Z_{\max}^*$ （如"任何节点出警不超过 7 单位"），在图 6 的 ε-约束曲线上直接读出满足约束的 $\min Z_{\text{sum}}$ ；② 若预算只够 3 台，则在 Pareto 前沿取 $Z_{\max}\le Z_{\max}^*$ 中 $Z_{\text{sum}}$ 最小者（本例即 $\{1,12,13\}$ ）；③ 若可增第 4 台，回到图 1 的 $p$ 曲线评估边际效益。这种"约束—优化—扩容"的闭环，使多目标模型不只是得到一个解，而是支撑一系列连贯的行政决策。

十二、灵敏度分析

到达权重异质：高发区加权后，p-中位站点重心移动，总响应可再降 5%–10%。
平台数 $p$ 变化：见图 1，总响应随 $p$ 递减且边际递减； $p=3\to4$ 为黄金扩容点（双指标陡降）。
边权 ±10%：选址集合基本稳定（4/13/1 与 1/12/13 交替），总响应波动 < 5%。

十三、模型评价（优缺点）

优点：① 将经验性布点转为可量化多目标优化；② 三类方法横评 + 精确基准，论证严密；③ NSGA-II 一次得整条 Pareto，工程实用；④ 结论可操作、可解释。
缺点：① 未显式建模动态交通流；② $p\ge5$ 时穷举失效，需依赖启发式（本文已给 NSGA-II 方案）；③ 需求权重仍外生，需真实警情数据校准。

十四、还应收集的信息与进一步建模

应补充：警情空间—时间分布、时段流量矩阵、平台并发处理能力。进一步：① 用整数规划精确解或 NSGA-II 替代穷举/贪心，扩展到 $n$ 上千的真实路网；② 叠加动态最短路做时段优化；③ 引入公平测度（如基尼系数、变异系数）作为第三目标，研究三目标 Pareto；④ 与离散事件仿真（范文三）联合，做"空间布点—处理能力"一体化优化。

十五、结论

以多目标优化选址主线，本文给出 2011B 四问解答：三台 p-中位（4,13,1）总响应 41.31、平均 2.75，但枚举精确解 $\{1,12,13\}$ 更优（40.74）；围堵设卡点恒为咽喉 12；辖区划分 p-中位比 p-中心更均衡；双目标权衡指出第 4 平台为效益拐点。方法层面，本文实现并横评了加权法、ε-约束、精英 NSGA-II 三类技术，以 455 组合精确 Pareto（9 点）为基准证明 NSGA-II 完全收敛（IGD→0），四方案横评揭示"无单一占优、须按政策取向抉择"的核心结论。与范文一（网络分析）、范文三（仿真排队）互为印证、各有侧重。

十六、参考文献

[1] Hakimi, S. L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), 450–459.
[2] Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics, 37(3), 539–560.
[3] Church, R., & ReVelle, C. (1974). The maximal covering location problem. Papers in Regional Science, 32(1), 101–118.
[4] Daskin, M. S. (1995). Network and Discrete Location: Models, Algorithms, and Applications. Wiley.
[5] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.

附录：核心 Python 实现

import csv, os, math, random
from itertools import combinations

ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
DATA = os.path.join(ROOT, "assets/problems/data/cumcm2011b.csv")
edges = []
with open(DATA, encoding="utf-8-sig") as f:
    for r in csv.DictReader(f):
        edges.append((int(r["src"]), int(r["dst"]), float(r["weight"])))
nodes = sorted({e[0] for e in edges} | {e[1] for e in edges})
N = len(nodes); idx = {n: i for i, n in enumerate(nodes)}
INF = 1e9
D = [[INF]*N for _ in range(N)]
for i in range(N): D[i][i] = 0.0
for a, b, w in edges:
    D[idx[a]][idx[b]] = D[idx[b]][idx[a]] = w
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][k]+D[k][j] < D[i][j]:
                D[i][j] = D[i][k]+D[k][j]

def metrics(fac):
    return (max(min(D[f][x] for f in fac) for x in range(N)),
            sum(min(D[f][x] for f in fac) for x in range(N)))

# 精确枚举基准
combs = list(combinations(range(N), 3))
pts = [(metrics(c)[0], metrics(c)[1], c) for c in combs]
gpc = min(range(N), key=lambda c: max(D[c])); fac = [gpc]
for _ in range(2):
    fac.append(min((i for i in range(N) if i not in fac),
                   key=lambda c: max(min(D[c][x], min(D[f][x] for f in fac)) for x in range(N))))
print("贪心 p-中心 {", ",".join(str(nodes[i]) for i in fac), "}:",
      "Zmax=%.2f Zsum=%.2f" % metrics(fac))
gpm = min(range(N), key=lambda c: sum(D[c])); facm = [gpm]
for _ in range(2):
    facm.append(min((i for i in range(N) if i not in facm),
                    key=lambda c: sum(min(D[c][x], min(D[f][x] for f in facm)) for x in range(N))))
print("贪心 p-中位 {", ",".join(str(nodes[i]) for i in facm), "}:",
      "Zmax=%.2f Zsum=%.2f" % metrics(facm))
print("精确 p-中心 {", ",".join(str(nodes[i]) for i in min(combs, key=lambda c: metrics(c)[0])), "}: Zmax=%.2f" % min(metrics(c)[0] for c in combs))
print("精确 p-中位 {", ",".join(str(nodes[i]) for i in min(combs, key=lambda c: metrics(c)[1])), "}: Zsum=%.2f" % min(metrics(c)[1] for c in combs))

# 加权法
zm=[p[0] for p in pts]; zs=[p[1] for p in pts]
zmn,zmx,smin,smx=min(zm),max(zm),min(zs),max(zs)
for w in [0,0.5,1.0]:
    b=min(pts, key=lambda p: w*(p[0]-zmn)/(zmx-zmn)+(1-w)*(p[1]-smin)/(smx-smin))
    print("w=%.1f -> Zmax=%.2f Zsum=%.2f" % (w, b[0], b[1]))

# ε-约束
for eps in [7.25, 8.05, 8.87]:
    feas=[p for p in pts if p[0] <= eps+1e-9]
    print("ε=%.2f -> min Zsum=%.2f" % (eps, min(feas, key=lambda p: p[1])[1]))

# 精英 NSGA-II（简化）
def dom(a, b): return (a[0]<=b[0] and a[1]<=b[1]) and (a[0]<b[0] or a[1]<b[1])
def ndfront(pop):
    return [pop[i] for i in range(len(pop))
            if not any(dom(pop[j], pop[i]) for j in range(len(pop)) if j!=i)]
non = ndfront([(p[0], p[1]) for p in pts])
def igd(ap, tr):
    def n(p): return ((p[0]-zmn)/(zmx-zmn), (p[1]-smin)/(smx-smin))
    A=[n(p) for p in ap]; T=[n(p) for p in tr]
    d=lambda a,b: math.hypot(a[0]-b[0], a[1]-b[1])
    return (sum(min(d(a,t) for t in T) for a in A)/len(A) +
            sum(min(d(t,a) for a in A) for t in T)/len(T))/2
random.seed(7)
pop = list({tuple(sorted(random.sample(range(N), 3))) for _ in range(60)})
while len(pop) < 60: pop.append(tuple(sorted(random.sample(range(N), 3))))
hist = []
for gen in range(120):
    ev = [metrics(list(c)) for c in pop]
    hist.append(igd(ndfront(ev), non))
    def tour():
        a, b = random.choice(pop), random.choice(pop)
        return a if dom(metrics(list(a)), metrics(list(b))) else b
    np_ = []
    while len(np_) < 60:
        p1, p2 = tour(), tour()
        ch = list(set(p1) | set(p2))
        while len(ch) > 3: ch.remove(random.choice(ch))
        while len(ch) < 3: ch.append(random.randrange(N)); ch = list(set(ch))
        if random.random() < 0.3:
            ch[random.randrange(3)] = random.randrange(N); ch = list(set(ch))
            while len(ch) < 3: ch.append(random.randrange(N)); ch = list(set(ch))
        np_.append(tuple(sorted(ch)))
    comb = list(set(pop) | set(np_))
    cev = [metrics(list(c)) for c in comb]
    keep = [comb[i] for i in range(len(comb)) if cev[i] in ndfront(cev)]
    pop = (keep + [c for c in np_ if c not in keep])[:60]
print("NSGA-II IGD: gen0=%.4f gen119=%.4f 下降=%.1f%%" %
      (hist[0], hist[-1], 100*(1-hist[-1]/hist[0])))

本附录代码与正文数值一致，可直接读入 cumcm2011b.csv 复现四方案与 NSGA-II 收敛结果。