遗传算法

遗传算法（Genetic Algorithm, GA）是模拟达尔文"物竞天择、适者生存"进化过程的元启发式全局优化算法。它不需要目标函数可导、不需要凸性，只要"能给每个候选解打分"就能工作，因此可以求解精确算法难以处理的 NP-hard 组合优化问题与复杂多峰连续优化问题。本文从原理、适用场景、评价指标、可视化图表到可运行代码（手写实现 + scipy 对照），完整梳理遗传算法的竞赛实战用法。

一、算法含义

1.1 通俗理解（进化论隐喻）

遗传算法的全部思想来自一句话：把"找最优解"当成"养一群生物，让它们一代代进化"。对照关系如下：

生物进化	遗传算法	本文实例中的对应
种群（一群生物）	候选解集合（$N$ 条染色体）	100 个背包方案 / 100 个二维点
个体	一条染色体（一个解）	一个 0-1 串 / 一个二维向量
基因	染色体上的每一位	第 $i$ 件物品取不取 / $x_1$ 的取值
适应度（生存能力）	适应度函数值 $f(x)$	背包总价值 / Rastrigin 函数值
自然选择	选择算子（好的多留后代）	轮盘赌 / 锦标赛
交配繁殖	交叉算子（交换基因片段）	单点 / 两点 / 均匀 / 算术交叉
基因突变	变异算子（随机翻动基因）	0/1 翻转 / 高斯扰动
世代更替	迭代（代数 $g = 0, 1, \dots, G-1$）	300 代 / 200 代

算法"进化"的过程：随机生成 $N$ 个解 → 给每个解打分 → 分数高的更可能被选中做"父母" → 父母的基因片段交叉重组、再随机突变，生出下一代 → 如此往复。平均适应度逐代上升，历史最好的个体被保留下来，最终输出历史最优解。

两个关键直觉：

1. 全局搜索靠种群：GA 不是从一个点出发爬山，而是 $N$ 个点并行"撒网"搜索；交叉算子让好解的"积木块"（building block，优秀基因片段）相互组合，能跨越大范围找到全局最优区域；
2. 只要求能打分：适应度函数可以是一段仿真、一个黑盒评分函数、甚至人工评分——这是 GA 与梯度类方法（要求可导）、精确算法（要求问题有特殊结构）最大的不同。

1.2 编码（解的表示）

遗传算法操作的对象是染色体，所以第一件事是把"解"翻译成染色体，这一步叫编码。本文涉及两种最常用的编码：

（1）二进制编码：染色体是一个 0-1 串，长度 $L$ 等于决策变量（基因）个数。0-1 背包问题天然契合——第 $i$ 位表示第 $i$ 件物品是否放入背包：

$\underbrace{1\ 0\ 1\ 1\ 0\ \cdots\ 1}_{L \text{ 位，每位一个基因}} \quad \Longleftrightarrow \quad \text{选第 } 1,3,4,\dots,L \text{ 件物品}$

二进制编码的优点：交叉、变异算子极简单；适合组合优化（选/不选、开/关、建/不建）。缺点：表示连续变量时有量化误差（精度受串长限制），且存在"海明悬崖"——两个数值上相邻的解（如 0111 与 1000）在基因上差异很大，一步变异很难互相到达。

（2）实数编码：染色体直接就是浮点向量 $x \in \mathbb{R}^d$，一个基因一个实数分量。适合连续优化问题（如求 Rastrigin 函数最小值）。优点：精度高、没有编码/解码误差、交叉变异算子同样简单（见 1.5、1.6 节）。

此外还有排列编码（染色体是 1~n 的一个排列，用于 TSP 旅行商问题）、整数编码（每位取有限个整数，用于调度、选址）等，思想相同：先设计解的表示，再设计算子。

1.3 初始种群与适应度函数

初始种群：随机生成 $N$ 条染色体（二进制编码逐位随机取 0/1；实数编码在取值范围 $[a_i, b_i]$ 内均匀采样），构成第 0 代种群 $P(0)$。初始种群要求尽量"撒得开"，覆盖整个搜索空间。

适应度函数 $f(x)$：给每个解打分的函数，算法内部统一按"越大越好"处理：

• 最大化问题：直接取目标函数，$f(x) = g(x)$；
• 最小化问题：取相反数 $f(x) = -g(x)$，或取倒数/平移（本文 Rastrigin 实例用相反数）；
• 带约束问题：用罚函数法把约束惩罚并入适应度。0-1 背包问题（$\max \sum v_i x_i$，$\text{s.t. } \sum w_i x_i \le W$）的适应度写为：

$f(x) = \sum_{i=1}^{n} v_i x_i \;-\; \lambda \cdot \max\!\left(0,\ \sum_{i=1}^{n} w_i x_i - W\right)$

其中 $\lambda > 0$ 是惩罚系数，表示"超重 1 单位扣掉多少价值"。$\lambda$ 太小则最优个体可能不可行，太大则可行域内的适应度差异被抹平——它是 GA 最需要小心设置的量之一（本文 7.4 节专门讨论）。本文代码还区分了选择口径（罚函数值）与报告口径（可行个体的真实目标值），保证论文中报告的数字都是真实可行的指标。

1.4 选择（轮盘赌 / 锦标赛）

选择模拟"适者生存"：适应度高的个体以更高概率成为父代、留下后代。两种最常用方案：

（1）轮盘赌选择（Roulette Wheel Selection）：每个个体被选中的概率与其适应度成正比——想象一个轮盘，每个个体占的面积与 $f_i$ 成正比，转动轮盘选父代：

$P(\text{选中个体 } i) = \frac{f_i}{\sum_{j=1}^{N} f_j}, \quad \text{要求 } f_i \geq 0$

要求适应度非负：若 $f$ 可能为负（如最小化问题取负后），先做平移 $f_i' = f_i - \min_j f_j$ 再按比例抽取。轮盘赌的缺点：进化后期种群趋同时，选择压力消失，容易出现"超级个体"霸占轮盘导致早熟收敛。

（2）锦标赛选择（Tournament Selection）：随机抽 $k$ 个个体（锦标赛规模），适应度最高的胜出作为父代。把种群按适应度从低到高排序，排名为 $r$（$r = 1$ 最差，$r = N$ 最好）的个体在一轮锦标赛中被选中的概率为：

$P(r) = \frac{r^k - (r-1)^k}{N^k}$

最好个体一轮被选中的概率约为 $k/N$。$k$ 越大选择压力越大（$k = N$ 退化为"只选最好的"）；$k = 2$ 最常用。锦标赛优点：不要求适应度非负、选择压力可通过 $k$ 调节，鲁棒性好，本文 Rastrigin 实例即用它。

1.5 交叉（单点 / 两点 / 均匀 / 算术）

交叉模拟"繁殖"：一对父代以概率 $p_c$ 交换基因片段，产生两个子代（未触发交叉时子代原样复制父代）。以父代 $x = 10110|1011$、$y = 01001|1101$（竖线为切点）为例：

• 单点交叉：随机选一个切点 $c$，交换切点之后的基因段：子代 $10110|1101$ 与 $01001|1011$；
• 两点交叉：随机选两个切点 $a < b$，交换中间段 $[a, b)$；
• 均匀交叉：每个基因位独立地以 0.5 概率互换——父代基因"逐位对半分"，破坏性最强；
• 算术交叉（实数编码）：子代是父代的凸组合（加轻微外推的 BLX-α 版）：

$c_1 = \alpha\, x + (1-\alpha)\, y, \qquad c_2 = (1-\alpha)\, x + \alpha\, y, \qquad \alpha \sim U(-0.25,\ 1.25)$

交叉是 GA 的主搜索动力：它把两个好解的基因模块重新组合，期望得到更好的解。

1.6 变异

变异模拟"基因突变"：子代每个基因位以概率 $p_m$ 发生随机改动，防止种群陷入局部最优、并恢复交叉过程中丢失的基因：

• 二进制编码：按位翻转，$x_i \leftarrow 1 - x_i$（0 变 1、1 变 0）；
• 实数编码：高斯扰动，$x_i \leftarrow x_i + \varepsilon$，$\varepsilon \sim N(0, \sigma^2)$，扰动后裁剪回取值范围 $[a_i, b_i]$（$\sigma$ 常取取值范围宽度的 0.05~0.2 倍）。

注意变异率的量纲：二进制编码 $p_m$ 是每个基因位的翻转概率（取 $0.001 \sim 0.1$，可用 $p_m \approx 1/L$ 起步）；实数编码 $p_m$ 是每个分量发生扰动的概率（常取 $0.05 \sim 0.2$）。$p_m$ 过大会把搜索变成"随机乱撞"，过小则丧失跳出局部最优的能力——本文 3.6 节的参数敏感性实验将定量展示这一点。

1.7 精英保留策略

精英保留（Elitism）：每代把适应度最高的 $e$ 个个体（精英）原样复制进下一代，不参与选择、交叉、变异。它保证历史最优不丢失：

$f_{\text{best}}(g+1) \geq f_{\text{best}}(g), \quad \text{其中 } f_{\text{best}}(g) = \max_{x \in P(g)} f(x)$

有了精英保留，历史最优适应度随代数单调不减（这是判断代码写没写对的快速检验：收敛曲线的最优线必须只升不降）。$e$ 通常取 1~5；$e$ 过大（如超过种群 10%）会显著加速早熟收敛。

1.8 算法流程（伪代码）

输入：适应度函数 f(·)，种群规模 N，交叉率 pc，变异率 pm，
     最大代数 G，精英个数 e，选择方式
输出：历史最优个体 x* 及其适应度 f*

1. 随机初始化种群 P(0) = {x_1, x_2, ..., x_N}        // 随机撒点
2. for g = 0, 1, ..., G-1:                            // 逐代进化
   (a) 计算每个个体适应度 f(x_i), i = 1..N           // 打分
   (b) 记录指标：历史最优 f_best(g)、平均适应度 f̄(g)  // 3.1/3.2 节
   (c) 精英保留：适应度最高的 e 个个体原样进入 P(g+1)
   (d) 生成其余 N − e 个子代（重复至补满）：
       - 选择：轮盘赌 / 锦标赛，从 P(g) 中抽两个父代
       - 交叉：以概率 pc 交叉产生两个子代（否则复制父代）
       - 变异：每个子代以概率 pm 逐基因变异
   (e) P(g+1) = 精英 + 新子代
3. 返回历史最优 x* = argmax f_best(G−1) 与 f* = f_best(G−1)

1.9 参数

参数	符号	典型取值	作用	取值过大	取值过小
种群规模	$N$	50 ~ 200	并行搜索的广度	计算量线性上升	多样性不足、易早熟
交叉率	$p_c$	0.6 ~ 0.9	基因重组的强度	破坏已形成的好模式	进化停滞
变异率	$p_m$	二进制 0.0010.1；实数 0.050.2	保持多样性、跳出局部最优	退化为随机搜索	早熟收敛
最大代数	$G$	100 ~ 1000	停止条件	浪费时间	未收敛就停
精英个数	$e$	1 ~ 5	保住历史最优	早熟风险上升	最优解可能丢失
锦标赛规模	$k$	2 ~ 5	选择压力	多样性快速丧失	接近随机选择
罚函数系数	$\lambda$	依问题而定	约束惩罚强度	可行域内差异被抹平	最优解不可行

1.10 优缺点

优点：

• 全局搜索能力强：种群并行搜索 + 交叉重组 + 变异扰动，不易陷入局部最优，适合多峰、非凸问题；
• 几乎无数学要求：不需要梯度、不需要凸性、不需要问题有特殊结构，只要求能定义适应度；
• 通用性好：一套框架（初始化、选择、交叉、变异、精英）换个编码与适应度就能解完全不同的问题；
• 天然并行：种群内个体适应度可并行评估（大规模问题可以多进程/多机加速）；
• 结果是一批近似最优解（末代种群），必要时可从中再挑选次优备选方案。

缺点：

• 不保证全局最优：理论上要"种群无限大、代数无限多"才以概率 1 收敛，实际只能得到近似解（本文背包实例约 1% 误差）；
• 随机性：每次运行结果不同，必须多次运行报告统计指标（3.4 节）；
• 收敛较慢：比梯度法、单纯形法慢一到两个数量级，大规模问题计算量可观；
• 参数多、需调参：$N$、$p_c$、$p_m$、$G$、$e$ 都影响性能，且没有放之四海皆准的默认值；
• 编码与适应度设计影响大：差的编码（海明悬崖）、差的罚函数（系数不当）会显著劣化甚至搞垮算法。

二、何时使用（适用场景与条件）

2.1 适用场景

1. NP-hard 组合优化问题：0-1 背包、TSP（旅行商）、VRP（车辆路径）、作业车间调度、装箱、选址、最大覆盖。这类问题规模一大，精确算法（分支定界、割平面）计算量指数爆炸，GA 用"多项式时间换近似解"：规模 $n = 40$ 的 0-1 背包有 $2^{40} \approx 10^{12}$ 种方案无法穷举，而本文 GA 用约 0.4 秒就给出了误差不到 1% 的方案。
2. 复杂连续多峰优化：Rastrigin、Ackley、Griewank 等测试函数以及现实中大量非凸目标（分片费率、带噪声的测量模型）。目标函数多局部极小、可能不可微，梯度法一动就"陷进坑里"，实数编码 GA（以及 PSO、差分进化）是这类问题的主力。
3. 黑盒优化：适应度来自仿真软件（如 MATLAB/Simulink 联合仿真）、第三方评分接口、甚至人工打分，没有梯度也没有解析表达式。GA 只需"输入解、输出分"。
4. 混合变量优化：决策变量同时含 0-1（建不建）、整数（台数）、连续（尺寸）——二进制与实数基因可以拼在同一条染色体上，混合编码即可。
5. 多目标优化：用 GA 的多目标变体（NSGA-II，见第八节）一次求出一组帕累托最优解。
6. 竞赛常见题目：
   • 调度类：车间排产、机场登机口/出租车调度、考试排考（排列编码）；
   • 路径类：TSP、无人机巡检路径、外卖配送路线（排列/优先权编码）；
   • 资源分配类：预算分配、仓库选址、传感器布点（0-1 编码）；
   • 参数寻优类：模型权重、PID 参数、超参数整定（实数编码）。

2.2 使用前提（建模前检查清单）

检查项	具体要求	检查手段
能定义适应度	任何候选解都能给出一个分数（约束可用罚函数并入）	写出 $f(x)$ 表达式或评分流程
解可编码	解能表示成 0-1 串 / 实数向量 / 排列 / 整数串	画"解 ↔ 染色体"对照表
规模匹配	决策变量几十到几千；评估预算 $N \times G$ 次可承受	估算单次评估耗时 × N × G
允许近似解	不要求证明全局最优，gap 可接受（用 3.5 节指标量化）	明确"多少误差可以接受"
有时间调参	$N$、$p_c$、$p_m$ 需实验确定（3.6 节敏感性模板）	预留一组参数扫描实验
能多次运行	随机算法需要多次运行统计（3.4 节）	预留 $M \ge 10$ 次运行时间
有对照基准	小规模用精确解（milp/枚举）；大规模用文献最优值或其他启发式	3.5 节 gap 需要参照值

竞赛提示：以上检查不必全部完美通过，但至少把"为什么用 GA、编码怎么设计、参数怎么选的、误差多大"四条在论文里写清楚，评审会认为你的模型是"经过论证的"，而不是"套了个高大上名字"。

2.3 不适用 / 慎用的情形

1. 小规模且要求精确最优：40 件以下的 0-1 背包、几十个城市的 TSP，直接调用精确求解器（scipy 的 milp、分支定界、动态规划）又快又准。GA 的定位是"大规模下的近似解"，小问题用它属于杀鸡用牛刀、还得不到最优。
2. 存在多项式精确算法的问题：最小生成树（Prim/Kruskal）、最短路（Dijkstra）、指派问题（匈牙利算法）等有特殊结构的问题，GA 纯属浪费。
3. 单次评估极其昂贵且无法并行：一次仿真要几分钟甚至几小时时，$N \times G$ 次评估（本文就是 $100 \times 300 = 3$ 万次）完全不可承受。此时应改用贝叶斯优化、代理模型（用少量评估拟合目标再优化）。
4. 实时性要求苛刻：毫秒级决策场景（实时调度、在线控制）来不及进化几十代，应考虑贪心、规则或离线训练好的策略。
5. 强约束、可行性难维持的问题：交叉/变异后的子代经常不可行、修复算子又难设计时，构造式算法（如蚁群算法边构造边满足约束）往往更省心。
6. 光滑凸的连续优化：目标可导且凸时，梯度法/牛顿法既快又保证最优，GA 属于"能算但没必要"。

2.4 与其他智能优化算法的对比与选择

算法	搜索机制	擅长问题	相对 GA 的优势	相对 GA 的劣势	竞赛选择建议
遗传算法 GA	种群 + 选择/交叉/变异	通用：组合 + 连续、可扩展多目标	——	参数多、计算量大	组合优化与"既要又要"的题目
粒子群 PSO	粒子按速度-位置公式飞行	连续多峰优化	收敛快、参数少（$w,c_1,c_2$）、实现最短	组合问题需离散化改造、易早熟	连续问题优先试 PSO（本系列第 11 篇）
模拟退火 SA	单解 + 温度退火、Metropolis 准则接受劣解	中小规模组合优化	参数少、理论上有渐近收敛到全局最优的保证	单点串行搜索慢、无种群并行性	小规模组合、想要"收敛理论依据"
蚁群算法 ACO	信息素正反馈 + 逐条构造解	TSP / 路径 / 调度类	与图、路径问题天然契合；边构造边满足约束，无需罚函数	信息素参数（$\alpha,\beta,\rho$）敏感、易停滞	路径/分配类题目（本系列第 13 篇）

选择原则（竞赛实战）：先看问题形态——连续多峰先试 PSO（简单）或 GA 实数编码（更稳）；0-1 组合（背包、选址）用 GA 二进制编码；路径/图类用 ACO；中小规模组合且想报"理论收敛性"用 SA。GA 的最大优势是通用 + 可扩展：组合连续混编、多目标（NSGA-II）、动态问题都能在一个框架里改出来，因此是竞赛里最"保险"的智能优化武器。

三、算法指标

下面每个指标都给出：中文名、公式、方向（越大/越小越好）、如何解读，并在解读中用本文两个实例（40 件物品 0-1 背包、2D Rastrigin）的真实运行结果做示例。符号定义见第五节。

3.1 历史最优适应度（History Best Fitness）

$f_{\text{best}}(g) = \max_{0 \le g' \le g}\ \max_{x \in P(g')}\ f(x), \qquad f^* = f_{\text{best}}(G-1)$

• 方向：最大化问题越大越好；最小化问题统一转成"越大越好"口径后再看；
• 解读：$f^*$ 是算法交付给评委的结果指标——整个进化过程中出现过的最好解的分数。注意它是"历史最优"而不是"末代最优"：精英保留保证 $f_{\text{best}}(g)$ 随 $g$ 单调不减，末代种群里的最好解可能反而不如历史最优（本文代码按历史最优返回，因此不会"把最好的解进化丢了"）。背包实例 $f^* = 1614.0$（可行总价值）；Rastrigin 实例 $f^* = 0.0000$（理论全局最优为 0，打印精度内已命中）。

3.2 每代平均适应度（Mean Fitness per Generation）

$\bar{f}(g) = \frac{1}{N} \sum_{x \in P(g)} f(x)$

• 方向：越大越好（整体水平越高说明种群越"健康"）；
• 解读：反映种群整体的进化状况，与"只有最优个体在进步"区分开。两个用途：
  1. 进化幅度：背包实例可行个体平均价值从初始代 924.7 升到末代 1267.1，提升约 37%，说明进化确实在发生；
  2. 多样性诊断：平均线与最优线之间的"沟"就是种群内部的适应度差距。沟很宽 = 多样性好；两条线几乎贴在一起 = 种群趋同、多样性枯竭，是早熟收敛的预警信号（见 7.4 节）。
  • 注意口径：带约束问题时本文代码只统计可行个体的平均（报告口径），避免罚函数值混入真实指标。

3.3 收敛代数（Convergence Generation）

$g^* = \min\left\{ g \in \{0, 1, \dots, G-1\} : f_{\text{best}}(g) \ge f_{\text{best}}(G-1) - \varepsilon \right\}, \quad \varepsilon = 10^{-9}$

• 方向：越小越好（越快收敛到最终水平）；
• 解读：历史最优首次达到最终最优值 $f^*$ 的代数。$g^*$ 小说明前期搜索高效；$g^*$ 接近 $G-1$ 说明"压哨"才找到，算法可能尚未真正收敛，需要加大 $G$。背包实例 $g^* = 189$（$G = 300$）——也就是说后 111 代一直在平台期，没有任何改进（组合优化后期提升困难是常态）；Rastrigin 实例 $g^* = 28$（$G = 200$），收敛极快。

3.4 多次运行均值与标准差（必须报告）

$\mu = \frac{1}{M}\sum_{m=1}^{M} f_m^*, \qquad \sigma = \sqrt{\frac{1}{M-1}\sum_{m=1}^{M}\left(f_m^* - \mu\right)^2}$

其中 $f_m^*$ 是第 $m$ 次独立运行（不同随机种子）得到的历史最优适应度，$M$ 是运行次数（建议 $M \ge 10$）。

• 方向：$\mu$ 越大越好（期望性能），$\sigma$ 越小越好（稳定性）；
• 解读：GA 是随机算法，单次结果靠运气，必须用多次运行刻画"期望性能 ± 稳定性"，论文中报告为 $\mu \pm \sigma$。背包实例 $M = 10$ 次独立运行最优值分别为 $[1582, 1592, 1614, 1624, 1602, 1630, 1615, 1608, 1608, 1612]$，得 $\mu = 1608.7$、$\sigma = 14.2$（$\sigma/\mu \approx 0.9\%$），最好一次 1630（恰好命中精确最优）、最差一次 1582；Rastrigin 实例 10 次运行全部命中全局最优（$\mu = 0.0000$、$\sigma = 0.0000$）。只报单次最优而不报统计，属于误导性报告。

3.5 与精确解（或参照解）的差距

$\delta = \frac{\left| z^* - f^* \right|}{z^*} \times 100\%$

其中 $z^*$ 是精确最优值（小规模问题用 scipy.optimize.milp、枚举、动态规划求得；大规模问题求不出精确解时，用文献最优值或松弛界代替）。

• 方向：越小越好，$\delta = 0$ 表示命中精确最优；
• 解读：GA 不保证最优，所以必须量化"差多少"，这是算法质量的最终裁判。背包实例：milp 求得精确最优 $z^* = 1630.0$，单次运行 $\delta = |1630 - 1614|/1630 = 0.982\%$；用 10 次运行均值算 $\delta = |1630 - 1608.7|/1630 = 1.307\%$。Rastrigin 实例理论最优 $f^*_{\text{理论}} = 0$ 已知，GA 结果与差分进化结果均为 0.000000。竞赛论文里"遗传算法求得的解与精确解的相对误差为 0.98%，说明算法能在可接受误差内高效求解该 NP-hard 问题"就是最有说服力的一句结论。

3.6 参数敏感性

$\mu(p) = \frac{1}{M'}\sum_{m=1}^{M'} f_m^*(p)$

固定其余参数，让目标参数 $p$（如变异率 $p_m$）在网格上变化，每个取值独立运行 $M'$ 次，比较 $\mu(p)$ 与 $\sigma(p)$。

• 方向：比较各参数取值下的 $\mu$（越大越好）与 $\sigma$（越小越好）；
• 解读：参数敏感性实验是"参数选择有依据"的证据，也是评审眼里的加分项。本文背包实例对变异率做扫描（$N=100$、$p_c=0.8$、$G=300$ 不变，各 $p_m$ 独立运行 5 次）：

$p_m$	5 次运行最优值均值	标准差
0.01	1630.0	0.0
0.05	1614.2	7.9
0.10	1569.6	22.3
0.20	1500.8	18.9

结论一目了然：变异率越大，均值越低、波动越大——过大的 $p_m$ 把好解"震碎"了；$p_m = 0.01$ 时 5/5 次全部命中精确最优 1630.0。这印证了 1.6 节的经验值：二进制编码取 $p_m \approx 1/L = 1/40 = 0.025$ 量级即可。真实建模时应对 $N$、$p_c$、$p_m$ 各做一组这样的扫描，把结果表贴进论文。

3.7 指标汇总表

指标	中文名	公式	方向	一句话解读	背包实例数值
$f^*$	历史最优适应度	$f^* = f_{\text{best}}(G-1) = \max_g \max_{x \in P(g)} f(x)$	越大越好	交付结果，精英保留下单调不减	1614.0（总价值）
$\bar{f}(g)$	每代平均适应度	$\frac{1}{N}\sum_{x \in P(g)} f(x)$	越大越好	种群整体水平；与最优线的沟 = 多样性	924.7 → 1267.1
$g^*$	收敛代数	$\min\{g : f_{\text{best}}(g) \ge f^* - \varepsilon\}$	越小越好	首次达到最终最优的代数，之后是平台期	189 / 300
$\mu$	多次运行均值	$\frac{1}{M}\sum_m f_m^*$	越大越好	期望性能，随机算法必报	1608.7
$\sigma$	多次运行标准差	$\sqrt{\frac{1}{M-1}\sum_m (f_m^* - \mu)^2}$	越小越好	稳定性	14.2（0.9%）
$\delta$	与精确解差距	$	z^* - f^*	/ z^* \times 100%$	越小越好
$\mu(p_m)$	参数敏感性	各参数取值下多次运行均值	越大越好	参数选择依据	0.01 → 1630.0；0.20 → 1500.8

四、可视化图表

遗传算法是"过程型"算法，光报一个最优值远远不够，画图看过程才能判断算法是否健康（有没有早熟、多样性如何、随机性多大）。以下 4 张图覆盖"收敛曲线、多次运行随机性、种群分布、方案可视化"，全部代码见第六节，图片自动保存到 figures/ 目录（ga_convergence.png、ga_multi_run.png、ga_rastrigin_pop.png、ga_knapsack.png）。

4.1 四张图速查表

图名（输出文件）	用途	关键解读点
① 适应度收敛曲线（ga_convergence.png）	展示单次运行"每代最优 + 每代平均"双线，判断收敛过程是否健康	最优线（蓝）单调不减（精英保留保证，若不满足说明代码有 bug）；平均线（橙）在最优线下方且上下波动（多样性）；两线间的沟越宽种群越多样；曲线初期陡升、后期平台；$g^* = 189$ 处竖线标注后长期停滞；最优线终点与绿色虚线（milp 精确值 1630）之间始终留着约 1% 的缝隙
② 多次运行对比（ga_multi_run.png）	展示随机算法的运行间差异，报告统计指标的依据	5 条灰线路径各异（随机性真实存在）但终点相近（1580~1630）；其中一条灰线顶到了精确最优 1630；蓝色粗线（10 次运行均值）平滑上升，代表"期望性能"；均值线同样略低于绿色虚线，差 1.31%
③ Rastrigin 等高线 + 最终种群（ga_rastrigin_pop.png）	实数编码下观察种群收敛与多样性	底色"蛋盒"状多峰地貌（几十个局部极小）；最终种群（白点）全部聚拢在全局最优 (0,0) 附近——说明搜索已"拿下"整个山谷；GA 最优解（橙色菱形）与理论最优（绿色星号）完全重合；若种群仍散布在多个谷底，说明未收敛或陷入不同局部最优
④ 背包价值-重量散点（ga_knapsack.png）	把 GA 方案与精确方案可视化对照	每个点 = 一件物品（横轴重量、纵轴价值），绿色大点 = 选中、灰色小点 = 未选；被选中的点几乎都是"高价值低重量"的左上角区域；左右两幅（GA 方案 vs milp 精确方案）几乎一致——仅 1 件物品不同（GA 用 8 号 v=70/w=27 替换了 milp 的 6 号 v=86/w=30），价值差 16、重量差 3；右下角红色标注容量 W = 315

4.2 每张图的详细解读

图① 收敛曲线

• 好图特征：最优线阶梯状单调上升；平均线在最优线下方小幅震荡、整体抬升；两条线不重合（保持距离说明种群没有趋同）。
• 异常特征一（早熟）：平均线很快追上并"贴死"最优线——种群趋同，之后的进化纯属浪费；异常特征二（不收敛）：到第 $G$ 代两条线仍在快速上升——$G$ 取小了，应加大代数；异常特征三（最优线有下降）：精英保留没生效或代码有 bug。
• 本例：背包曲线在 189 代前阶梯式上升，之后进入平台（后期改进停滞是组合优化的常态）；最优线终点 1614 与 milp 虚线 1630 之间的可见缝隙，正是 3.5 节 $\delta = 0.982\%$ 的可视化。

图② 多次运行对比

• 好图特征：灰线在前期发散（随机探索）、后期收拢（都进了同一优质区域）；均值粗线平滑上升。
• 解读：灰线的垂直散布宽度就是 $\sigma$ 的直观来源——10 次运行最优值从 1582 到 1630，散布约 48（$\sigma = 14.2$）。若所有灰线几乎重合，说明问题"太好解"或随机性被抹平；若灰线终点七零八落，说明算法不稳定，需要调参或加精英。
• 论文用法：这张图（或它的简化版）贴进论文，配合一句"10 次独立运行最优值均值 1608.7、标准差 14.2"即可完整交代算法的随机性表现。

图③ Rastrigin 等高线 + 最终种群

• 好图特征：末代种群高度聚集在全局最优附近（多样性在"该消失的时候消失"）；最优解与理论最优重合。
• 异常特征：种群散布在多个谷底——算法被困在不同局部最优、未全局收敛；种群仍大面积铺开——代数不够或变异率过大。
• 本例：100 个个体全部收拢在 (0,0) 附近，且 GA 最优解与星号（理论最优）重合，与 3.1 节 $f^* = 0.0000$ 相互印证。这张图是实数编码 GA "全局收敛"最直观的证据。

图④ 背包方案对照

• 好图特征：选中点集中于左上角（高价值低重量）；两幅图高度一致。
• 解读：左右两幅分别对应 GA 方案（总价值 1614、总重量 312）与 milp 方案（总价值 1630、总重量 315），都是 23 件物品、仅差 1 件。这张图把抽象的 0-1 串翻译成"拿了什么、没拿什么"，是竞赛论文里"算法方案的可解释性展示"。

五、符号说明

符号	含义	示例/单位
$N$	种群规模（个体数）	$N = 100$
$P(g)$	第 $g$ 代种群	$g = 0, 1, \dots, G-1$
$x$	个体（染色体），一条候选解	0-1 串 / 实数向量
$L$	二进制编码染色体长度（基因位数）	背包实例 $L = 40$
$d$	实数编码的变量维数	Rastrigin 实例 $d = 2$
$f(x)$	适应度函数（内部统一"越大越好"）	背包：罚函数值
$f_{\text{best}}(g)$	第 $g$ 代的历史最优适应度	单调不减
$\bar{f}(g)$	第 $g$ 代平均适应度	背包末代 1267.1
$f^*$	历史最优适应度（最终交付值）	背包 1614.0
$x^*$	历史最优个体（最优解）	Rastrigin $x^* \approx (0, 0)$
$g$	代数（从 0 起计）	——
$G$	最大代数（停止条件）	背包 300；Rastrigin 200
$g^*$	收敛代数	背包 189；Rastrigin 28
$p_c$	交叉率	0.8
$p_m$	变异率（二进制：每基因位；实数：每分量）	背包 0.05；Rastrigin 0.15
$e$	精英保留个数	2
$k$	锦标赛规模	3
$\lambda$	罚函数系数（超重单位惩罚）	6.81（≈ 平均价值密度的 2 倍）
$M$	独立运行次数	10
$\mu$	多次运行最优值均值	背包 1608.7
$\sigma$	多次运行最优值标准差（样本标准差，$M-1$ 分母）	背包 14.2
$z^*$	精确最优值（对照基准）	milp 求得 1630.0
$\delta$	与精确解的相对差距	0.982%
$n$	物品数（问题规模）	40
$v_i, w_i$	第 $i$ 件物品的价值与重量	$v_i \in [1,100]$，$w_i \in [1,30]$
$W$	背包容量	315.0（= 总重量的一半）
$a_i, b_i$	实数编码第 $i$ 维的取值下界、上界	$[-5.12, 5.12]$

六、可运行程序（完整代码）

环境要求：Python 3.12，依赖 numpy、scipy、matplotlib（仅用这三个库，均在项目 .venv 中安装，不需要 deap/geatpy 等第三方进化算法库）。以下所有代码块按顺序拼接保存为 ga_demo.py，在本文档所在目录运行即可：控制台打印第三节的全部指标（历史最优适应度、每代平均适应度、收敛代数、多次运行均值/标准差、与精确解差距、参数敏感性、耗时），并在 figures/ 子目录生成 4 张图（ga_convergence.png、ga_multi_run.png、ga_rastrigin_pop.png、ga_knapsack.png）。无图形界面环境可设 MPLBACKEND=Agg 跳过 plt.show() 的窗口弹出，图片照常保存。

# -*- coding: utf-8 -*-
"""
============================================================
遗传算法（Genetic Algorithm, GA）完整示例：
手写 GA（二进制编码 + 实数编码） + scipy 库方法对照
------------------------------------------------------------
实例 1：0-1 背包问题（40 件物品，np.random.default_rng(42) 生成数据）
    （注：不用 20 件是因为该规模下 GA 每次运行都能命中精确最优，
      随机性体现不出来；40 件规模下 GA 给出约 1% 误差的近似解，
      且多次运行结果互有差异，能完整演示多次运行统计指标）
    手写 GA（二进制编码、轮盘赌选择、两点交叉、按位变异、精英保留）
    vs scipy.optimize.milp 精确解对照
实例 2：2D Rastrigin 函数最小值（实数编码、锦标赛选择、算术交叉、高斯变异）
    vs scipy.optimize.differential_evolution（差分进化，库内进化算法参照）
输出：控制台打印第三节全部指标（历史最优适应度、每代平均适应度、收敛代数、
     多次运行均值/标准差、与精确解差距、参数敏感性、耗时）；
     figures/ 目录生成 4 张图：ga_convergence / ga_multi_run /
     ga_rastrigin_pop / ga_knapsack
依赖：numpy、scipy、matplotlib（不依赖 deap/geatpy 等第三方库）
============================================================
"""

# ========== 0. 导入库与全局设置 ==========
import os
import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import milp, LinearConstraint, Bounds, differential_evolution

# ---- 固定全局随机种子（与 default_rng 生成数据、GA 实例显式种子配合，结果完全可复现）----
np.random.seed(42)

# ---- matplotlib 中文显示设置（防止图内中文乱码）----
plt.rcParams["font.sans-serif"] = ["PingFang SC", "Arial Unicode MS", "SimHei"]
plt.rcParams["axes.unicode_minus"] = False   # 让负号"-"正常显示

# ---- 图片输出目录（相对当前工作目录的 figures/ 子目录）----
FIG_DIR = "figures"
os.makedirs(FIG_DIR, exist_ok=True)

# ---- 画图配色（固定"角色-颜色"映射，4 张图保持一致）----
C_BEST = "#2a78d6"   # 蓝色 = 每代最优 / 主曲线
C_MEAN = "#eb6834"   # 橙色 = 每代平均
C_EXACT = "#1baf7a"  # 青绿 = 精确解（milp / differential_evolution）
C_SEL = "#1baf7a"    # 青绿 = 被选中的物品
C_UNSEL = "#c9c8c4"  # 浅灰 = 未选中的物品
C_GRAY = "#9a9894"   # 灰色 = 多次运行的单次曲线
C_BAD = "#d03b3b"    # 红色 = 容量标注（总量约束提示）
C_INK = "#0b0b0b"    # 主文字颜色
C_GRID = "#e1e0d9"   # 网格线颜色

# ========== 1. 手写遗传算法类：初始化、适应度与三大遗传算子 ==========

class GA:
    """手写遗传算法（Genetic Algorithm）。

    术语约定（与本文第三节一致）：
      - 染色体 / 个体：一条解向量（背包问题：0-1 串；Rastrigin：二维实数向量）；
      - 种群：一代中全部 N 条染色体；
      - 适应度：衡量个体优劣的分数，本类内部统一按"越大越好"处理
        （maximize=True 时直接取目标值；maximize=False 时取目标值的相反数）；
      - 精英保留：每代把适应度最高的 n_elite 个个体原样复制进下一代。

    参数说明：
      fitness   : 适应度函数，输入一条染色体，输出一个数（问题自身方向）；
      n_dim     : 染色体长度（二进制编码时=基因位数；实数编码时=变量维数）；
      encoding  : "binary"=二进制编码（0/1 串）；"real"=实数编码（连续向量）；
      bounds    : 实数编码时每个变量的取值范围，shape=(n_dim, 2)，每行 [下界, 上界]；
      pop_size  : 种群规模 N；
      pc        : 交叉率（一对父代发生交叉的概率）；
      pm        : 变异率（二进制：每个基因位翻转的概率；实数：每个分量发生
                  高斯扰动的概率）；
      max_gen   : 最大代数 G；
      n_elite   : 精英保留个数；
      select_method : "roulette"=轮盘赌选择；"tournament"=锦标赛选择；
      tour_size : 锦标赛规模 k（每次随机抽 k 个个体比适应度）；
      crossover_method : 二进制编码时生效："single"=单点 / "two_point"=两点 /
                   "uniform"=均匀交叉；实数编码固定用算术交叉（BLX-α）；
      mutate_sigma_frac : 实数编码高斯变异标准差 = 该系数 × 变量取值范围宽度；
      maximize  : True=最大化问题（背包）；False=最小化问题（Rastrigin）；
      report    : 可选"报告函数"：输入个体，返回论文里要报告的真实指标值
                  （如背包问题只报告可行个体的真实价值，返回 None 表示不可行）。
                  只用于记录指标与画图，不参与选择；
      seed      : 随机种子（多次独立运行时给不同种子）。
    """

    def __init__(self, fitness, n_dim, encoding="binary", bounds=None,
                 pop_size=100, pc=0.8, pm=0.05, max_gen=200, n_elite=2,
                 select_method="roulette", tour_size=3,
                 crossover_method="two_point", mutate_sigma_frac=0.1,
                 maximize=True, report=None, seed=None):
        self.fitness = fitness
        self.n_dim = n_dim
        self.encoding = encoding
        self.bounds = np.asarray(bounds, dtype=float) if bounds is not None else None
        self.pop_size = pop_size
        self.pc = pc
        self.pm = pm
        self.max_gen = max_gen
        self.n_elite = n_elite
        self.select_method = select_method
        self.tour_size = tour_size
        self.crossover_method = crossover_method
        self.mutate_sigma_frac = mutate_sigma_frac
        self.maximize = maximize
        self.report = report
        self.rng = np.random.default_rng(seed)   # 每个 GA 实例独立随机流，便于复现

    # ---------- 1.1 适应度换算：统一成"越大越好"的分数 ----------
    def _score(self, ind):
        """把问题目标值换算成内部分数（越大越好），用于选择与精英比较。"""
        f = self.fitness(ind)
        return f if self.maximize else -f

    # ---------- 1.2 初始化种群 ----------
    def _init_population(self):
        if self.encoding == "binary":
            # 每个基因位以 0.5 概率取 0/1：染色体就是 0-1 串
            return [self.rng.integers(0, 2, self.n_dim).astype(float)
                    for _ in range(self.pop_size)]
        else:
            # 实数编码：在 [下界, 上界] 内均匀随机撒点
            lo, hi = self.bounds[:, 0], self.bounds[:, 1]
            return [self.rng.uniform(lo, hi) for _ in range(self.pop_size)]

    # ---------- 1.3 选择（轮盘赌 / 锦标赛） ----------
    def _select(self, pop, scores):
        if self.select_method == "roulette":
            # 轮盘赌：选中概率与适应度成正比，P(i) = f_i / Σf_j。
            # 分数先平移保证非负（适应度可能为负，如 Rastrigin 的相反数）。
            w = scores - scores.min() + 1e-12
            p = w / w.sum()
            return pop[self.rng.choice(self.pop_size, p=p)]
        else:
            # 锦标赛：随机抽 k 个个体，返回其中分数最高的（k = 锦标赛规模）。
            idx = self.rng.integers(0, self.pop_size, self.tour_size)
            return pop[max(idx, key=lambda i: scores[i])]

    # ---------- 1.4 交叉 ----------
    def _crossover(self, p1, p2):
        if self.rng.random() > self.pc:
            # 未触发交叉：两个父代原样进入子代（再交给变异处理）
            return p1.copy(), p2.copy()
        if self.encoding == "binary":
            if self.crossover_method == "single":
                # 单点交叉：随机切点 c，交换两条染色体 c 之后的基因段
                c = int(self.rng.integers(1, self.n_dim))
                c1 = np.concatenate([p1[:c], p2[c:]])
                c2 = np.concatenate([p2[:c], p1[c:]])
            elif self.crossover_method == "two_point":
                # 两点交叉：随机两个切点 a<b，交换中间基因段
                a, b = np.sort(self.rng.choice(np.arange(1, self.n_dim),
                                               2, replace=False))
                c1 = np.concatenate([p1[:a], p2[a:b], p1[b:]])
                c2 = np.concatenate([p2[:a], p1[a:b], p2[b:]])
            else:
                # 均匀交叉：每个基因位独立地以 0.5 概率交换
                mask = self.rng.random(self.n_dim) < 0.5
                c1 = np.where(mask, p1, p2)
                c2 = np.where(mask, p2, p1)
            return c1, c2
        else:
            # 实数编码：算术交叉（BLX-α），α ~ U(-0.25, 1.25)，
            # 子代 = α·父1 + (1-α)·父2，允许轻微外推以扩大搜索范围
            alpha = self.rng.uniform(-0.25, 1.25)
            c1 = alpha * p1 + (1 - alpha) * p2
            c2 = (1 - alpha) * p1 + alpha * p2
            return self._clip(c1), self._clip(c2)

    # ---------- 1.5 变异 ----------
    def _mutate(self, ind):
        if self.encoding == "binary":
            # 按位变异：每个基因位以概率 pm 翻转（0<->1）
            flip = self.rng.random(self.n_dim) < self.pm
            return np.where(flip, 1 - ind, ind)
        else:
            # 高斯变异：每个分量以概率 pm 加上 N(0, σ²) 扰动，σ 取
            # 变量取值范围的 mutate_sigma_frac 倍，扰动后裁剪回界内
            lo, hi = self.bounds[:, 0], self.bounds[:, 1]
            sigma = self.mutate_sigma_frac * (hi - lo)
            mask = self.rng.random(self.n_dim) < self.pm
            noise = self.rng.normal(0.0, sigma) * mask
            return self._clip(ind + noise)

    def _clip(self, x):
        """把实数个体裁剪回变量取值范围（变异/交叉后可能越界）。"""
        return np.clip(x, self.bounds[:, 0], self.bounds[:, 1])

# ========== 1.6 遗传算法主循环（接上一代码块，GA 类的 run 方法） ==========

    def run(self):
        """执行完整演化，返回 (历史最优个体, 历史最优报告值, 各代指标, 末代种群)。

        返回的 hist 字典：
          "best"        : 每代历史最优分数（内部"越大越好"口径）；
          "report_best" : 每代历史最优"报告值"（如背包问题的可行真实价值）；
          "report_mean" : 每代"报告值"的种群均值（只统计可报告个体）。
        """
        pop = self._init_population()
        best_ind, best_score = None, -np.inf
        best_report = None
        hist = {"best": [], "report_best": [], "report_mean": []}
        for g in range(self.max_gen):
            # (1) 计算当代全部个体的适应度分数
            scores = np.array([self._score(ind) for ind in pop])
            # (2) 更新历史最优（跨代记忆）
            i_best = int(np.argmax(scores))
            if scores[i_best] > best_score:
                best_score = scores[i_best]
                if self.report is None:
                    best_ind = pop[i_best].copy()
                    best_report = best_score
            # (3) 记录本代指标（报告口径：真实指标值，只统计可报告个体）
            if self.report is not None:
                pairs = [(self.report(ind), ind) for ind in pop]
                valid = [(r, ind) for r, ind in pairs if r is not None]
                if valid:
                    cur_best_rep, cur_best_ind = max(valid, key=lambda t: t[0])
                    if best_report is None or cur_best_rep > best_report:
                        best_report = cur_best_rep
                        best_ind = cur_best_ind.copy()
                hist["report_best"].append(best_report)
                hist["report_mean"].append(
                    float(np.mean([r for r, _ in valid])) if valid else np.nan)
            else:
                hist["report_best"].append(best_score)
                hist["report_mean"].append(float(np.mean(scores)))
            hist["best"].append(best_score)
            # (4) 精英保留：分数最高的 n_elite 个个体原样进入下一代
            order = np.argsort(scores)                      # 分数升序
            elites = [pop[i].copy() for i in order[-self.n_elite:]]
            # (5) 选择-交叉-变异，补满下一代
            children = []
            while len(children) < self.pop_size - self.n_elite:
                p1 = self._select(pop, scores)
                p2 = self._select(pop, scores)
                c1, c2 = self._crossover(p1, p2)
                children.append(self._mutate(c1))
                if len(children) < self.pop_size - self.n_elite:
                    children.append(self._mutate(c2))
            pop = elites + children
        # 循环结束后 best_report 即"历史最优适应度"（报告口径）
        return best_ind, best_report, hist, pop

# ========== 2. 实例 1：0-1 背包问题（40 件物品，二进制编码） ==========

# ---- 2.1 生成数据：np.random.default_rng(42) 保证任何机器上数据一致 ----
rng_data = np.random.default_rng(42)
N_ITEMS = 40
VALUES = rng_data.integers(1, 101, N_ITEMS).astype(float)   # 价值 v_i ∈ [1,100]
WEIGHTS = rng_data.integers(1, 31, N_ITEMS).astype(float)   # 重量 w_i ∈ [1,30]
CAPACITY = WEIGHTS.sum() / 2.0          # 背包容量 = 总重量的一半（约取一半物品）
# 惩罚系数：平均价值密度 × 2。含义：超重 1 单位扣掉的价值，
# 大于多数物品的价值密度，从而引导搜索回到可行域。
PENALTY = 2.0 * VALUES.sum() / WEIGHTS.sum()

def knap_fitness(ind):
    """背包问题适应度 = 总价值 − λ × 超重惩罚（内部用于选择）。"""
    v = float(np.dot(ind, VALUES))
    w = float(np.dot(ind, WEIGHTS))
    excess = max(0.0, w - CAPACITY)
    return v - PENALTY * excess

def knap_report(ind):
    """报告函数：可行个体的真实总价值；不可行个体返回 None（不计入统计）。"""
    if np.dot(ind, WEIGHTS) <= CAPACITY + 1e-9:
        return float(np.dot(ind, VALUES))
    return None

def run_knapsack_once(seed, pop_size=100, pc=0.8, pm=0.05, max_gen=300,
                      verbose=False):
    """运行一次背包 GA，返回 (最优个体, 最优可行价值, hist, 末代种群, 耗时)。"""
    ga = GA(fitness=knap_fitness, n_dim=N_ITEMS, encoding="binary",
            pop_size=pop_size, pc=pc, pm=pm, max_gen=max_gen, n_elite=2,
            select_method="roulette", crossover_method="two_point",
            maximize=True, report=knap_report, seed=seed)
    t0 = time.perf_counter()
    best_ind, best_val, hist, _ = ga.run()
    elapse = time.perf_counter() - t0
    if verbose:
        print(f"  seed={seed:<3d} 最优价值={best_val:7.1f}  耗时={elapse*1000:6.1f} ms")
    return best_ind, best_val, hist, elapse

# ========== 2.2~2.5 背包：单次运行 / 多次运行统计 / milp 精确解 / 参数敏感性 ==========

# ---- 2.2 单次运行（seed=3），打印单次运行指标 ----
SEED_MAIN = 3
t0 = time.perf_counter()
best_ind_knap, best_val_knap, hist_knap, _ = run_knapsack_once(SEED_MAIN)
T_SINGLE = time.perf_counter() - t0
gen_best = np.array(hist_knap["report_best"])            # 每代历史最优（可行价值）
gen_mean = np.array(hist_knap["report_mean"])            # 每代可行个体平均价值
# 收敛代数 g*：历史最优第一次达到最终最优值的代数（从 0 起计数）
g_star = int(np.argmax(gen_best >= gen_best[-1] - 1e-9))

# ---- 2.3 多次运行统计（M=10 次独立运行，不同随机种子）----
M_RUNS = 10
t0 = time.perf_counter()
multi_best, multi_hist = [], []
for m in range(M_RUNS):
    _, bv, h, _ = run_knapsack_once(seed=1 + m)   # 种子 1~10，其中含单次运行 seed=3
    multi_best.append(bv)
    multi_hist.append(np.array(h["report_best"]))
multi_best = np.array(multi_best)
T_MULTI = time.perf_counter() - t0
mu_knap = multi_best.mean()          # 多次运行最优值均值 μ
sd_knap = multi_best.std(ddof=1)     # 多次运行最优值标准差 σ（样本标准差）

# ---- 2.4 精确解对照：scipy.optimize.milp（HiGHS 求解器）----
# 把 max Σv·x 转成 milp 的最小化形式：min Σ(−v)·x，0-1 变量，Σw·x ≤ W
res_milp = milp(
    c=-VALUES,
    constraints=LinearConstraint(WEIGHTS.reshape(1, -1), -np.inf, CAPACITY),
    integrality=np.ones(N_ITEMS),
    bounds=Bounds(np.zeros(N_ITEMS), np.ones(N_ITEMS)),
)
x_exact = np.round(res_milp.x).astype(int)
v_exact = float(x_exact @ VALUES)     # 精确最优价值
gap_knap = abs(v_exact - best_val_knap) / v_exact * 100.0   # 相对差距（%）

# ---- 2.5 参数敏感性：变异率 pm ∈ {0.01, 0.05, 0.1, 0.2}，各独立运行 5 次 ----
PM_GRID = [0.01, 0.05, 0.1, 0.2]
sens_rows = []
for pm in PM_GRID:
    vals = []
    for m in range(5):
        _, bv, _, _ = run_knapsack_once(seed=200 + m, pm=pm)
        vals.append(bv)
    sens_rows.append((pm, float(np.mean(vals)), float(np.std(vals, ddof=1))))

# ========== 3. 实例 2：2D Rastrigin 函数最小值（实数编码） ==========

def rastrigin(x):
    """Rastrigin 函数 f(x) = 10d + Σ[x_i² − 10cos(2πx_i)]，
    在 x* = (0,0) 处取全局最小值 f* = 0；搜索域 [-5.12, 5.12]² 内
    有几十个局部极小点（多峰），是检验全局寻优能力的经典测试函数。"""
    x = np.asarray(x, dtype=float)
    d = x.size
    return 10 * d + float(np.sum(x ** 2 - 10 * np.cos(2 * np.pi * x)))

RAST_BOUNDS = np.array([[-5.12, 5.12], [-5.12, 5.12]])   # 两个变量的取值范围

def run_rastrigin_once(seed, pop_size=100, pc=0.8, pm=0.15, max_gen=200):
    """运行一次 Rastrigin GA，返回 (最优个体, 最优目标值, hist, 末代种群, 耗时)。"""
    ga = GA(fitness=rastrigin, n_dim=2, encoding="real", bounds=RAST_BOUNDS,
            pop_size=pop_size, pc=pc, pm=pm, max_gen=max_gen, n_elite=2,
            select_method="tournament", tour_size=3,
            crossover_method="arithmetic", mutate_sigma_frac=0.1,
            maximize=False, report=None, seed=seed)
    t0 = time.perf_counter()
    best_ind, best_score, hist, final_pop = ga.run()
    elapse = time.perf_counter() - t0
    return best_ind, -best_score, hist, final_pop, elapse   # 还原为最小化口径

# ---- 3.1 单次运行（seed=3）----
best_ind_rast, best_f_rast, hist_rast, final_pop_rast, T_rast = \
    run_rastrigin_once(SEED_MAIN)
gen_best_r = -np.array(hist_rast["best"])          # 每代历史最优目标值（越小越好）
gen_mean_r = -np.array(hist_rast["report_mean"])   # 每代平均目标值（越小越好）
g_star_rast = int(np.argmax(gen_best_r <= gen_best_r[-1] + 1e-9))

# ---- 3.2 多次运行统计（M=10 次独立运行）----
multi_best_r = []
for m in range(M_RUNS):
    _, bf, _, _, _ = run_rastrigin_once(seed=300 + m)
    multi_best_r.append(bf)
multi_best_r = np.array(multi_best_r)
mu_rast = multi_best_r.mean()
sd_rast = multi_best_r.std(ddof=1)

# ---- 3.3 库实现对照：scipy.optimize.differential_evolution ----
# 注：差分进化（DE）是另一种进化算法（无交叉率概念、用差分向量变异），
# scipy 内置，作为"库内进化算法"参照，与手写 GA 结果对比。
res_de = differential_evolution(rastrigin, bounds=[(-5.12, 5.12)] * 2,
                                seed=42, polish=True)
f_de = res_de.fun                                # DE 找到的最优目标值
gap_rast = abs(best_f_rast - f_de)               # GA 与 DE 的绝对差距（f* = 0 已知）

# ========== 4. 控制台打印全部指标 ==========
def hr(title):
    print("\n" + "=" * 62)
    print(title)
    print("=" * 62)

print("遗传算法（GA）完整示例：手写实现 + scipy 库方法对照")
print("运行目录:", os.getcwd())

hr("实例 1：0-1 背包问题（40 件物品，二进制编码，轮盘赌+两点交叉）")
print(f"物品价值 v = {VALUES.astype(int).tolist()}")
print(f"物品重量 w = {WEIGHTS.astype(int).tolist()}")
print(f"背包容量 W = {CAPACITY:.1f}（= 总重量的一半），惩罚系数 λ = {PENALTY:.2f}")
print(f"参数：种群规模 N = 100，交叉率 pc = 0.8，变异率 pm = 0.05，代数 G = 300")

hr("实例 1 指标 1~3：单次运行（seed=3）")
print(f"[指标1] 历史最优适应度（GA 最优可行价值）f* = {best_val_knap:.1f}")
print(f"[指标2] 每代平均适应度（末代可行个体平均价值）= {gen_mean[-1]:.1f}")
print(f"        初始代平均 = {gen_mean[0]:.1f}（对比末代可看出进化幅度）")
print(f"[指标3] 收敛代数 g* = {g_star}（历史最优首次达到 {best_val_knap:.1f} 的代数）")
print(f"[附加]  单次运行耗时 T = {T_SINGLE*1000:.1f} ms")
sel_idx = np.where(best_ind_knap > 0.5)[0] + 1
print(f"[方案]  GA 选择物品编号（1 起）: {sel_idx.tolist()}")
print(f"        总价值 = {best_val_knap:.1f}，总重量 = {float(best_ind_knap @ WEIGHTS):.1f} ≤ W = {CAPACITY:.1f}")

hr("实例 1 指标 4：多次运行统计（M = 10 次独立运行，随机种子不同）")
print(f"10 次运行最优值: {multi_best.astype(int).tolist()}")
print(f"[指标4] 最优值均值 μ = {mu_knap:.1f}，标准差 σ = {sd_knap:.1f}，"
      f"最差 = {multi_best.min():.1f}，最好 = {multi_best.max():.1f}")
print(f"[附加]  10 次运行总耗时 = {T_MULTI*1000:.1f} ms")

hr("实例 1 指标 5：与精确解对照（scipy.optimize.milp, HiGHS）")
print(f"milp 精确最优价值 z* = {v_exact:.1f}（最优方案: 物品 {np.where(x_exact==1)[0]+1}）")
print(f"GA 单次运行最优值     = {best_val_knap:.1f}（10 次运行均值 μ = {mu_knap:.1f}）")
print(f"[指标5] 相对差距 = |z* − f*| / z* × 100% = {gap_knap:.3f}%")
print(f"        （10 次运行均值与精确解的差距 = {abs(v_exact-mu_knap)/v_exact*100:.3f}%）")

hr("实例 1 指标 6：参数敏感性（变异率 pm，其余参数不变，各独立运行 5 次）")
print("   pm      5 次运行最优值均值      标准差")
for pm, m_val, s_val in sens_rows:
    print(f"  {pm:<6.2f}   {m_val:>12.1f}      {s_val:>8.1f}")

hr("实例 2：2D Rastrigin 函数最小值（实数编码，锦标赛+算术交叉+高斯变异）")
print("目标：min f(x) = 10d + Σ[x_i² − 10cos(2πx_i)]，x ∈ [-5.12, 5.12]²，已知全局最优 f* = 0")
print("参数：种群规模 N = 100，交叉率 pc = 0.8，变异率 pm = 0.15，代数 G = 200")
print(f"[指标1] 历史最优适应度（最优目标值）f* = {best_f_rast:.4f}")
print(f"[指标2] 末代平均目标值 = {gen_mean_r[-1]:.4f}（初始代平均 = {gen_mean_r[0]:.4f}）")
print(f"[指标3] 收敛代数 g* = {g_star_rast}")
print(f"[附加]  最优解 x* = ({best_ind_rast[0]:.6f}, {best_ind_rast[1]:.6f})")
print(f"[附加]  单次运行耗时 T = {T_rast*1000:.1f} ms")
print(f"[指标4] 10 次独立运行：均值 μ = {mu_rast:.4f}，标准差 σ = {sd_rast:.4f}，"
      f"最差 = {multi_best_r.max():.4f}，最好 = {multi_best_r.min():.4f}")
print(f"[指标5] 与 differential_evolution 对照（进化算法参照）: f_DE = {f_de:.6f}，"
      f"GA 与 DE 的差距 = {gap_rast:.6f}（理论全局最优 f* = 0）")

# ========== 5. 画图：图 1 + 图 2（背包收敛类，保存到 figures/ 子目录） ==========

# ---- 图 1：适应度收敛曲线（单次运行，每代最优 + 每代平均，双线）----
fig, ax = plt.subplots(figsize=(7, 4.5), dpi=110)
gens = np.arange(len(gen_best))
ax.plot(gens, gen_best, color=C_BEST, lw=2, label="每代最优（历史最优可行价值）")
ax.plot(gens, gen_mean, color=C_MEAN, lw=1.6, label="每代平均（可行个体平均价值）")
ax.axhline(v_exact, color=C_EXACT, ls="--", lw=1.4,
           label=f"精确最优值 z* = {v_exact:.1f} (milp)")
ax.axvline(g_star, color=C_GRAY, ls=":", lw=1.2)
ax.annotate(f"收敛代数 g* = {g_star}", xy=(g_star, gen_best[g_star]),
            xytext=(g_star + 8, gen_best[0] * 1.02), fontsize=9, color=C_INK)
ax.set_xlabel("代数 g")
ax.set_ylabel("背包总价值（越大越好）")
ax.set_title("图 1  遗传算法收敛曲线（0-1 背包，单次运行 seed=3）")
ax.grid(alpha=0.35, color=C_GRID)
ax.legend(loc="lower right", fontsize=9)
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ga_convergence.png"), dpi=150)
print("\n已保存 figures/ga_convergence.png")

# ---- 图 2：多次运行对比曲线（5 条灰线 + 均值粗线，展示随机性）----
fig, ax = plt.subplots(figsize=(7, 4.5), dpi=110)
gens = np.arange(multi_hist[0].size)
mean_curve = np.mean(np.stack(multi_hist, axis=0), axis=0)
for m in range(5):                                   # 画前 5 次运行的曲线（灰色）
    ax.plot(gens, multi_hist[m], color=C_GRAY, lw=0.9, alpha=0.75,
            label="单次运行" if m == 0 else None)
ax.plot(gens, mean_curve, color=C_BEST, lw=2.2, label="10 次运行均值（粗线）")
ax.axhline(v_exact, color=C_EXACT, ls="--", lw=1.4,
           label=f"精确最优值 z* = {v_exact:.1f} (milp)")
ax.set_xlabel("代数 g")
ax.set_ylabel("每代历史最优可行价值")
ax.set_title(f"图 2  多次独立运行的收敛差异（10 次运行，μ = {mu_knap:.1f}，σ = {sd_knap:.1f}）")
ax.grid(alpha=0.35, color=C_GRID)
ax.legend(loc="lower right", fontsize=9)
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ga_multi_run.png"), dpi=150)
print("已保存 figures/ga_multi_run.png")

# ========== 5. 画图：图 3 + 图 4（Rastrigin 种群分布 / 背包方案对照） ==========

# ---- 图 3：Rastrigin 等高线 + 最终种群散点（实数编码）----
pop_arr = np.array(final_pop_rast)                   # 单次运行的末代种群
xgrid = np.linspace(-5.12, 5.12, 300)
X, Y = np.meshgrid(xgrid, xgrid)
Z = np.array([[rastrigin([X[i, j], Y[i, j]]) for j in range(X.shape[1])]
              for i in range(X.shape[0])])
fig, ax = plt.subplots(figsize=(6.4, 5.6), dpi=110)
cs = ax.contourf(X, Y, Z, levels=25, cmap="viridis")
fig.colorbar(cs, ax=ax, label="f(x) 函数值")
ax.scatter(pop_arr[:, 0], pop_arr[:, 1], s=10, c="#ffffff", edgecolors=C_INK,
           linewidths=0.3, alpha=0.85, label="最终种群（100 个个体）")
ax.scatter([0], [0], marker="*", s=260, c=C_EXACT, edgecolors="white",
           label="全局最优 (0,0)，f* = 0")
ax.scatter([best_ind_rast[0]], [best_ind_rast[1]], marker="D", s=60, c=C_MEAN,
           edgecolors="white", label=f"GA 最优解，f = {best_f_rast:.4f}")
ax.set_xlim(-5.12, 5.12)
ax.set_ylim(-5.12, 5.12)
ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")
ax.set_title("图 3  Rastrigin 等高线 + GA 最终种群分布（实数编码）")
ax.legend(loc="upper right", fontsize=8, framealpha=0.9)
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ga_rastrigin_pop.png"), dpi=150)
print("已保存 figures/ga_rastrigin_pop.png")

# ---- 图 4：背包问题价值-重量散点 + GA / milp 选中方案对比 ----
fig, axes = plt.subplots(1, 2, figsize=(10.5, 4.6), dpi=110, sharex=True, sharey=True)
for ax, x_sel, title in [
    (axes[0], best_ind_knap, "GA 方案"),
    (axes[1], x_exact, "milp 精确最优方案"),
]:
    sel_mask = x_sel > 0.5
    ax.scatter(WEIGHTS[~sel_mask], VALUES[~sel_mask], s=45, c=C_UNSEL,
               edgecolors="white", label=f"未选（{np.sum(~sel_mask)} 件）")
    ax.scatter(WEIGHTS[sel_mask], VALUES[sel_mask], s=75, c=C_SEL,
               edgecolors=C_INK, linewidths=0.6, label=f"选中（{np.sum(sel_mask)} 件）")
    # 容量标注：W 是"总重量"约束（横轴是单件重量，画竖线会拉伸坐标轴，改用文字标注）
    ax.text(0.97, 0.03, f"容量 W = {CAPACITY:.0f}（总量约束）",
            transform=ax.transAxes, ha="right", va="bottom",
            fontsize=8.5, color=C_BAD)
    v_sel = float(x_sel @ VALUES)
    w_sel = float(x_sel @ WEIGHTS)
    ax.set_title(f"{title}：总价值 {v_sel:.0f}，总重量 {w_sel:.0f}", fontsize=10)
    ax.set_xlabel("重量 w_i")
    ax.grid(alpha=0.35, color=C_GRID)
    ax.legend(fontsize=8, loc="lower right")
axes[0].set_ylabel("价值 v_i")
fig.suptitle(f"图 4  0-1 背包：GA 方案 vs milp 精确方案（相对差距 {gap_knap:.3f}%）",
             fontsize=11)
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ga_knapsack.png"), dpi=150)
print("已保存 figures/ga_knapsack.png")

hr("运行完成：4 张图已保存到 figures/ 目录")
plt.show()   # 显示全部图片（无图形界面环境可设 MPLBACKEND=Agg 跳过）

七、结果解读与注意事项

7.1 运行输出解读（实例 1：0-1 背包，40 件物品）

以第六节代码（40 件物品，$N = 100$、$p_c = 0.8$、$p_m = 0.05$、$G = 300$、精英数 $e = 2$，轮盘赌 + 两点交叉）为例，运行脚本后控制台关键输出如下（数据由固定种子生成，任何机器上运行结果一致）：

==============================================================
实例 1 指标 1~3：单次运行（seed=3）
==============================================================
[指标1] 历史最优适应度（GA 最优可行价值）f* = 1614.0
[指标2] 每代平均适应度（末代可行个体平均价值）= 1267.1
        初始代平均 = 924.7（对比末代可看出进化幅度）
[指标3] 收敛代数 g* = 189（历史最优首次达到 1614.0 的代数）
[附加]  单次运行耗时 T = 366.2 ms
[方案]  GA 选择物品编号（1 起）: [2, 3, 4, 5, 8, 12, 13, 14, 15, 16, 17, 19, 24, 25, 26, 28, 29, 32, 34, 35, 37, 38, 40]
        总价值 = 1614.0，总重量 = 312.0 ≤ W = 315.0

==============================================================
实例 1 指标 4：多次运行统计（M = 10 次独立运行，随机种子不同）
==============================================================
10 次运行最优值: [1582, 1592, 1614, 1624, 1602, 1630, 1615, 1608, 1608, 1612]
[指标4] 最优值均值 μ = 1608.7，标准差 σ = 14.2，最差 = 1582.0，最好 = 1630.0
[附加]  10 次运行总耗时 = 3647.3 ms

==============================================================
实例 1 指标 5：与精确解对照（scipy.optimize.milp, HiGHS）
==============================================================
milp 精确最优价值 z* = 1630.0（最优方案: 物品 [ 2  3  4  5  6 12 13 14 15 16 17 19 24 25 26 28 29 32 34 35 37 38 40]）
GA 单次运行最优值     = 1614.0（10 次运行均值 μ = 1608.7）
[指标5] 相对差距 = |z* − f*| / z* × 100% = 0.982%
        （10 次运行均值与精确解的差距 = 1.307%）

==============================================================
实例 1 指标 6：参数敏感性（变异率 pm，其余参数不变，各独立运行 5 次）
==============================================================
   pm      5 次运行最优值均值      标准差
  0.01           1630.0           0.0
  0.05           1614.2           7.9
  0.10           1569.6          22.3
  0.20           1500.8          18.9

逐项解读：

• f* = 1614.0 vs z* = 1630.0：GA 在 $2^{40}$ 个方案中找出价值 1614 的可行方案（总重量 312 ≤ 315），与精确最优仅差 0.98%。对比 GA 方案与 milp 方案：两者只差 1 件物品——GA 用 8 号物品（价值 70、重量 27）替换了 milp 的 6 号物品（价值 86、重量 30），价值少 16（$86-70$）、重量少 3（$315-312$）。这说明 GA 不仅给出了好结果，而且结果"有道理可讲"，非常适合写进论文的方案说明。
• 平均适应度 924.7 → 1267.1：可行个体平均价值提升约 37%，说明进化在整个种群层面有效，而不是只有一两个"幸运个体"。
• g* = 189：前 189 代持续进步，后 111 代平台期。对 40 件规模的背包，300 代的设定合理（预留了平台期做"确认"）；若 $g^* \approx G$ 则需加大 $G$。
• μ = 1608.7、σ = 14.2：10 次运行全部落在 $[1582, 1630]$，波动只有约 0.9%，算法稳定；其中一次恰好命中精确最优 1630，说明 GA 有时也能"蒙对"。论文应报告 $\mu \pm \sigma$ 而不是挑最好的一次。
• 耗时：单次约 0.37 秒、10 次约 3.6 秒，40 件规模下成本很低；但注意评估次数是 $N \times G = 3$ 万次，若单次评估昂贵（如一次仿真 1 分钟），总时间会变成 500 小时——评估成本决定 GA 是否可用（见 2.3 节）。
• 参数敏感性：$p_m = 0.01$ 时 5/5 次全部命中精确最优 1630.0（均值 1630.0、标准差 0.0）；$p_m$ 增大到 0.20 时均值掉到 1500.8。变异率宁小勿大——它只负责"偶尔救场"，太大反而把交叉攒下的好基因破坏掉。

7.2 运行输出解读（实例 2：2D Rastrigin 函数最小值）

==============================================================
实例 2：2D Rastrigin 函数最小值（实数编码，锦标赛+算术交叉+高斯变异）
==============================================================
[指标1] 历史最优适应度（最优目标值）f* = 0.0000
[指标2] 末代平均目标值 = 3.4149（初始代平均 = 34.2949）
[指标3] 收敛代数 g* = 28
[附加]  最优解 x* = (0.000001, -0.000000)
[附加]  单次运行耗时 T = 278.6 ms
[指标4] 10 次独立运行：均值 μ = 0.0000，标准差 σ = 0.0000，最差 = 0.0000，最好 = 0.0000
[指标5] 与 differential_evolution 对照（进化算法参照）: f_DE = 0.000000，
      GA 与 DE 的差距 = 0.000000（理论全局最优 f* = 0）

逐项解读：

• f* = 0.0000（实际约 $10^{-10}$ 量级）：搜索域内有几十个局部极小，实数编码 GA 依然精准定位到全局最优 $x^* = (0, 0)$——这演示了 GA 在多峰连续问题上的全局搜索能力。打印只保留 4 位小数所以显示 0.0000。
• 末代平均 3.4149 vs 初始 34.2949：整个种群（而不只是最优个体）都从"平均离目标 34"进化到"平均离目标 3.4"，种群整体爬进了全局最优的山谷，与图③中种群聚拢现象一致。
• g* = 28/200：28 代就锁定了全局最优，之后 172 代基本是"巩固"。连续问题的前期探索效率远高于组合问题（对照背包的 189/300）。
• 10 次全部命中（$\mu = \sigma = 0.0000$）：本实例参数设置稳健，随机性几乎不影响最终解。两个实例的对照恰好说明：GA 的随机性表现因问题而异，因此 3.4 节的多次运行统计在任何 GA 论文里都不能省。
• 与 scipy 差分进化对照：两种进化算法都精确找到全局最优，互相印证"进化算法适合多峰连续优化"的结论。

7.3 四张图的解读（本例）

• 图①：蓝色最优线单调阶梯上升（精英保留生效），橙色平均线在其下方震荡上行；$g^* = 189$ 竖线后进入平台；终点 1614 与绿色虚线 1630 的可见缝隙即 0.98% 的 gap——这张图把"近似解与精确解的差距"画了出来。
• 图②：5 条灰线前期路径各异、后期收拢到 1580~1630 的窄带内；蓝色均值粗线平滑；可见一次运行顶到了绿色虚线（1630）。这张图是"报告 $\mu \pm \sigma$"的直观理由。
• 图③：蛋盒状多峰地貌上，末代 100 个白点全部聚拢在原点山谷，橙色菱形（GA 最优）与绿色星号（理论最优）重合——多峰问题被完全"拿下"。
• 图④：左（GA）右（milp）两幅方案几乎相同，都是 23 件物品；选中的绿色大点集中在左上角"高价值低重量"区域，只有 6 号（86/30）与 8 号（70/27）这一对交换。红色标注 W = 315 提示总量约束。

7.4 常见坑与应对

1. 早熟收敛（premature convergence）：症状——平均线早早"贴死"最优线（图①的沟消失）、$g^*$ 之后长平台、解的质量差强人意。成因——选择压力过大（轮盘赌 + 超级个体）、种群太小、变异率太小。应对——增大 $N$、改用锦标赛并调小 $k$、适当调大 $p_m$、减少精英个数 $e$；极端情况可引入小生境/拥挤度算子或重启机制。
2. 适应度设计不当：最常见的三类错误——(a) 最小化问题直接当最大化用（应取 $-f(x)$）；(b) 轮盘赌遇到负适应度不平移（概率公式失效，本文代码自动平移）；(c) 罚函数系数 $\lambda$ 设置不当：太小则最优个体不可行（"价值 9999 但超重 5000"的假最优），太大则可行域内差异被抹平（大家都拿差不多的分，进化失去方向）。经验：$\lambda$ 取"约束违反 1 单位带来的收益上限"的 1~2 倍，本文取平均价值密度的 2 倍（$\lambda = 6.81$）。同时务必区分选择口径与报告口径：选择可以用罚函数值，报告必须用可行个体的真实目标值（本文 knap_report 的做法）。
3. 编码不当：(a) 二进制表示连续变量时串长不足 → 精度不够（量化误差）；(b) 实数编码变异/交叉后不裁剪 → 越界解；(c) 排列编码（TSP）却用普通两点交叉 → 产生重复基因的非法解（应改用 PMX/OX 等排列专用交叉）；(d) 编码与问题"对不上"（如用二进制硬编码调度顺序）。原则：先设计解的表示，再设计算子。
4. 不报告多次运行统计：只贴"某一次运行"的最优值甚至收敛曲线。GA 每次运行结果都不同，单次结果可能是运气（本实例 10 次结果差 48）。评审会质疑"你是不是挑了最好的一次"。必须：独立运行 $M \ge 10$ 次（不同种子），报告 $\mu \pm \sigma$、最好与最差。
5. 参数没有依据：拍脑袋定 $N=500$、$G=10000$，既浪费又显得不专业。应做 3.6 节式敏感性扫描，论文里一句话"固定其余参数、扫描 $p_m$，结果显示 $p_m = 0.01$ 时均值最高，故采用"即可。
6. 把收敛曲线当"全局最优证明"：曲线平台只说明"算法不再改进"，不说明"到了全局最优"——它完全可能停在某个局部最优。严谨做法：能求精确解的问题报 gap（3.5 节），不能求的问题用多个不同启发式交叉印证或报告松弛界。
7. 计算预算失控：总评估次数 = $N \times G$（本例 3 万次），适应度若来自昂贵仿真，先算清楚时间账再选参数；可以先用小规模调参、再放大规模运行，或并行化评估（GA 的天然优势）。
8. 小问题用 GA 且不与精确解对比：40 件背包、20 城市 TSP 这类问题 milp/枚举几秒出精确解。用 GA 没问题，但不报 gap 就是态度问题——"GA 求得 1614，milp 精确最优 1630，相对差距 0.98%"一句即可把严谨度拉满。

7.5 竞赛论文写作建议（话术模板）

建模段（为什么用 GA、编码与适应度怎么设计）：

该问题为 40 维 0-1 组合优化问题，可行解空间规模达 $2^{40} \approx 1.1 \times 10^{12}$，无法穷举，属于 NP-hard 问题。本文采用遗传算法求解：以 0-1 串编码物品取舍方案（第 $i$ 位为 1 表示装入第 $i$ 件物品），适应度函数取 $f(x) = \sum v_i x_i - \lambda \max(0, \sum w_i x_i - W)$，其中罚系数 $\lambda$ 取平均价值密度的 2 倍以引导搜索回到可行域；采用轮盘赌选择、两点交叉、按位变异与精英保留策略。

参数段（参数及选择依据）：

对变异率 $p_m$ 进行敏感性分析（种群规模 $N = 100$、交叉率 $p_c = 0.8$、迭代 $G = 300$ 固定，各参数组合独立运行 5 次），结果显示 $p_m = 0.01$ 时平均最优值最高（1630.0）且标准差为 0，$p_m$ 过大将显著破坏优质解（$p_m = 0.20$ 时均值降至 1500.8），故取 $p_m = 0.05$（兼顾收敛速度与稳定性）。

结果段（单次 + 多次 + 精确对照，三段齐全）：

算法单次运行求得方案总价值 1614.0（总重量 312 ≤ W = 315）；10 次独立运行最优值均值 1608.7、标准差 14.2，说明算法结果稳定。为验证解的质量，用整数规划精确求解器（scipy.optimize.milp）求得该问题精确最优值 $z^* = 1630.0$，遗传算法最优解与精确解的相对差距仅为 0.98%（10 次均值口径为 1.31%），说明遗传算法能在可接受的误差范围内高效求解该 NP-hard 问题。

连续优化 / 收敛性段（实例 2 的写法）：

用 Rastrigin 多峰函数检验算法的全局寻优能力（搜索域 $[-5.12, 5.12]^2$ 内含数十个局部极小）：实数编码遗传算法于第 28 代收敛，最优解 $x^* = (0.000001, -0.000000)$，目标值 $f^* \approx 0$，与理论全局最优 $(0, 0)$ 一致；10 次独立运行均命中全局最优（$\mu = 0.0000$，$\sigma = 0.0000$），表明算法具有良好的全局搜索能力与稳定性。

八、延伸阅读

1. 差分进化（Differential Evolution, DE）：连续优化的另一主力进化算法。与 GA 的区别：没有交叉率的"显式杂交"，变异靠差分向量 $v = x_{r1} + F(x_{r2} - x_{r3})$ 实现，参数更少（$F$、$CR$、$N$），连续多峰问题上通常比 GA 更快更稳。scipy 内置 differential_evolution（本文实例 2 已用它做对照），开箱即用，是竞赛里"GA 之外的备胎"首选。
2. NSGA-II（多目标遗传算法）：竞赛多目标题（成本-时间-能耗、利润-风险）的主流武器。核心机制：非支配排序（把种群按帕累托前沿分层）+ 拥挤度距离（保证解在帕累托前沿上分布均匀）+ 精英策略，一次运行得到一整条帕累托前沿。geatpy、pymoo 等库有现成实现。
3. 自适应遗传算法（Adaptive GA）：针对"参数难调"的改进——让 $p_c$、$p_m$ 随种群适应度分布（如低于平均适应度的个体给更大的 $p_c/p_m$）或代数自适应调整，免去大部分调参工作。Srinivas & Patnaik（1994）的经典方案与后续 IAGA 变体是论文里"改进遗传算法"最常见的写法。
4. 遗传编程（Genetic Programming, GP）：把"染色体"从解向量升级为程序/表达式树，进化出"能解释数据的公式"（符号回归），用于自动发现函数关系、自动构造特征。Python 的 gplearn 库提供了符号回归实现，适合数据挖掘类题目。
5. 混合算法与更多变体：GASA（遗传-模拟退火混合，用 SA 精修 GA 的精英）、量子遗传（QGA）、小生境 GA（维持多种群多样性）、协同进化（CoEA）等。竞赛中"XX 改进遗传算法"类题目的标准套路：分析基础 GA 在本问题上的短板 → 针对性改编码/算子/加局部搜索 → 用 3.4/3.5 节指标证明改进有效。
6. 系列与资源：本系列第 11 篇《粒子群算法》、第 13 篇《蚁群算法》是与 GA 并列的智能优化方法，可对照学习；推荐资源：Holland《Adaptation in Natural and Artificial Systems》（GA 开山之作）、Michalewicz《How to Solve It: Modern Heuristics》（启发式方法总览，竞赛风格）、玄光男《遗传算法与工程优化》（工程应用案例）、scipy 官方文档 differential_evolution 页面（查 API 细节）、geatpy/deap 官方文档（现成框架，验证手写实现时作对照）。