遗传算法

一、直观理解：让「好方案」像生物一样交叉变异地繁衍

遗传算法（Genetic Algorithm, GA）把每个可行方案编码成一条「染色体」，用目标函数当适应度。算法维持一群方案（种群），反复进行：

1. 选择：适应度高的个体更易进入下一代；
2. 交叉：两个父代交换片段，产生子代；
3. 变异：以小概率改动基因，保持多样性。

经过若干代，种群往往向更好区域集中。它不依赖梯度，能处理不可微、离散、黑箱目标，但不保证全局最优，结果带随机性。

定位（必读）：遗传算法属于智能优化，仅在精确方法与凸方法不可行时作兜底。能写成 LP/MILP/凸 NLP/网络算法/DP 的问题，应优先精确求解。使用 GA 必须报告随机种子、多次运行统计，并与贪心/松弛圆整等基线比较。

二、适用场景与优缺点

类型	说明
适用场景	目标黑箱或高度非凸；离散结构难紧线性化；精确求解器超时且无好分解；需快速得可行近优作工程参考。
核心优点	不需导数；框架通用；易并行；可处理混合编码（二进制、排列、实数）。
局限与缺点	无最优性证明；参数敏感；约束处理麻烦；可复现性依赖种子；易被误用于本可用 intlinprog 的问题。

动用 GA 前的强制检查清单：

1. 是否已尝试 LP/MILP/NLP/图算法/DP？
2. 是否有简单基线（随机可行解、贪心、局部搜索）？
3. 适应度是否包含约束惩罚或修复算子？
4. 能否固定 rng 并做 $N\ge 10$ 次独立实验？

三、核心原理

1. 编码

问题类型	常见编码
0-1 选择	二进制串
连续参数	实数向量
路径/排序	排列染色体 + 专门交叉（OX、PMX）

解码：染色体 → 决策变量 → 目标与约束。

2. 适应度

通常由目标变换而来。最小化 $f$ 可取 $Fitness=1/(1+f)$ 或排序名次。约束违反用罚函数：

$$F(x)=f(x)+\rho\sum_j \max(0,h_j(x))^2$$

或用修复算子把后代拉回可行域（往往更稳）。

3. 算子

• 选择：轮盘赌、锦标赛；
• 交叉：单点、两点、均匀、模拟二进制（SBX）；
• 变异：位翻、高斯扰动、交换两点（排列）。

4. 终止

代数上限、最优值停滞代数、评价次数预算。终止后得到的是历史最好个体，不是证明最优。

四、关键决策

1. 先基线后 GA

至少实现：随机采样、贪心、若存在则 MILP 限时解。GA 必须报相对基线的改进百分比。

2. 参数

种群规模 $20\sim 200$、交叉率 $0.6\sim 0.9$、变异率 $1/n$ 量级为常见起点。应用网格或少量试探，避免只展示「调到最好」的一次运气。

3. 约束

优先修复；罚因子 $\rho$ 过小会不可行，过大会先只关心可行。

4. 可复现

rng(2026, "twister");

每次独立运行换种子，汇总最好/均值/标准差。

5. 何时停用 GA

一旦找到紧的数学规划模型且可在时限内 gap 可接受，应以精确解为准。

五、MATLAB 示例

例：用 ga 解一个非凸连续问题（演示流程，非鼓励滥用）

$$\min\ x_1^2+x_2^2+0.5(1-\cos(3\pi x_1))(1-\cos(3\pi x_2)) \quad x\in[-2,2]^2$$

fun = @(x) x(1)^2 + x(2)^2 + ...
    0.5*(1-cos(3*pi*x(1)))*(1-cos(3*pi*x(2)));
nvars = 2;
lb = [-2, -2]; ub = [2, 2];

% ---- 基线：多起点 fmincon（若可微）----
baseline = inf; xBestLocal = [];
for k = 1:20
    rng(1000 + k);
    x0 = lb + rand(1, 2).*(ub - lb);
    optsL = optimoptions("fmincon", "Display", "off");
    [xk, fk] = fmincon(fun, x0, [], [], [], [], lb, ub, [], optsL);
    if fk < baseline
        baseline = fk; xBestLocal = xk;
    end
end
fprintf("局部搜索基线最好 f = %.6f at [%.4f, %.4f]\n", ...
    baseline, xBestLocal(1), xBestLocal(2));

% ---- GA：多次独立运行 ----
nRuns = 15;
fRuns = zeros(nRuns, 1);
xRuns = zeros(nRuns, nvars);
seeds = 2026 + (0:nRuns-1);

gaOpts = optimoptions("ga", ...
    "Display", "off", ...
    "PopulationSize", 40, ...
    "MaxGenerations", 80, ...
    "FunctionTolerance", 1e-8);

for r = 1:nRuns
    rng(seeds(r), "twister");
    [xr, fr] = ga(fun, nvars, [], [], [], [], lb, ub, [], gaOpts);
    fRuns(r) = fr; xRuns(r, :) = xr;
end

fprintf("GA %d 次: best=%.6f, mean=%.6f, std=%.6f\n", ...
    nRuns, min(fRuns), mean(fRuns), std(fRuns));
fprintf("随机种子列表: "); disp(seeds);
fprintf("相对基线改进: %.2f%%\n", ...
    100*(baseline - min(fRuns)) / max(abs(baseline), eps));

0-1 背包：更应优先 DP/intlinprog，GA 仅作对照

v = [10 8 15 6 12]; w = [5 4 8 3 6]; W = 15; n = numel(v);
% 精确
f = -v'; intcon = 1:n;
[xIP, fIP] = intlinprog(f, intcon, w, W, [], [], zeros(n,1), ones(n,1));
fprintf("IP 最优价值 = %g\n", -fIP);

% GA 二进制（兜底示范）
fit = @(x) -v * x(:) + 1000 * max(0, w*x(:) - W); % 罚不可行
opts = optimoptions("ga", "PopulationType", "bitstring", ...
    "Display", "off", "PopulationSize", 60, "MaxGenerations", 100);
vals = zeros(10,1);
for r = 1:10
    rng(300+r);
    [xga, fga] = ga(fit, n, [], [], [], [], [], [], [], opts);
    % 修复：若超重则按 v/w 丢掉
    x = xga(:) > 0.5;
    while w*x > W
        idx = find(x); [~, j] = min(v(idx)./w(idx)); x(idx(j)) = 0;
    end
    vals(r) = v * x;
end
fprintf("GA 可行价值 best/mean = %g / %.2f （对比 IP %g）\n", ...
    max(vals), mean(vals), -fIP);

六、如何解释结果

强制报告模板：

1. 为何使用 GA（精确法失败原因）；
2. 编码、算子、参数、评价次数预算；
3. 随机种子列表与运行次数；
4. 最好/最差/均值/标准差；
5. 基线方法与数值对比；
6. 约束如何处理及最终方案可行性；
7. 明确表述：「近优候选，非证明全局最优」。

七、常见误区

1. 小规模 LP/IP 却用 GA 并宣称最优

严重不严谨。应 linprog/intlinprog。

2. 只跑一次种子幸运结果

必须多次运行。

3. 不写约束惩罚导致「最优」不可行

可行性是底线。

4. 参数调到过拟合某次随机

报告默认参数与敏感性，或交叉验证式预算。

5. 与基线比较时基线故意很弱

应包含领域贪心或限时精确解。

6. 把种群均值当最优解

应输出历史精英个体。

八、小结

遗传算法的核心思想可以概括为：

用种群、选择、交叉与变异在搜索空间中启发式地演化更好方案，适合精确方法难以施展的黑箱或强非凸问题。

它在本课程体系中是兜底工具而非首选。正确用法是：先尽精确与结构方法，再以可复现实验（种子、多次运行、基线对比）报告近优结果，绝不把 GA 包装成「全局最优算法」。