MOO-03.遗传算法

发表于 | 分类于
遗传算法（GA）原理与实现：编码、选择、交叉、变异、精英保留；与梯度法对比；pymoo/DEAP 示例；与 NSGA-II 等多目标扩展的衔接。

遗传算法（Genetic Algorithm，GA）是一类受生物进化启发的随机搜索方法：维护一组候选解（种群），通过选择—交叉—变异迭代改进，在不可微、多峰、组合的黑盒优化中广泛使用。多目标系列里的 NSGA-II、SPEA2 本质上是 GA 的 Pareto 扩展——理解单目标 GA，是读懂 MOO-02 的前提。

段末注释：GA 属于 进化计算（Evolutionary Computation，EC）大家族；与 进化策略（ES）、差分进化（DE）等同族，共享「种群 + 随机算子」范式。

系列： MOO-01 帕累托最优 → MOO-02 算法实现 → 本文
前置：Math-04 单目标优化

一、核心思想：种群搜索而非单点下降

梯度法从一点 $\mathbf{x}_t$ 沿 $-\nabla f$ 移动；GA 同时维护 $N$ 个个体 ${\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(N)}}$，每代：

  1. 评估适应度（fitness）$F(\mathbf{x}^{(i)})$——最小化问题常取 $F = -f$ 或 $1/(1+f)$；
  2. 选择优秀个体作父代（偏利用，exploitation）；
  3. 交叉组合父代基因产生子代（探索新组合）；
  4. 变异随机扰动（维持多样性）；
  5. 环境选择（含精英保留）组成下一代。

图 1　遗传算法主循环

对比维度 梯度下降 / Adam 遗传算法
梯度 需要 $\nabla f$ 不需要
目标 连续可微为主 black-box、离散、多峰均可
并行 单点串行 种群天然并行评估
收敛 局部极小 无全局最优保证，但可跳出局部极
样本效率 高（尤其凸问题） 低，常需 $10^3$–$10^5$ 次评估

段末注释：black-box 指只能调用 $f(\mathbf{x})$ 返回值、无法求导或内部不可见的优化场景。

二、编码：决策变量如何变成「染色体」

图 2　三种常见编码

编码（encoding）把 $\mathbf{x} \in \mathcal{X}$ 映射为 GA 操作的染色体（chromosome）。

编码 染色体形式 典型问题 交叉/变异
二进制 ${0,1}^L$ 特征选择、背包 单点/均匀交叉；位翻转
实数 $\mathbf{x} \in [x_l, x_u]^d$ 超参、连续设计 SBX 交叉；多项式变异 PM
排列 $(\pi_1,\ldots,\pi_n)$ 置换 TSP、排程 OX/PMX；交换/倒位变异
整数 $\mathbb{Z}^d \cap [l,u]$ 层数、离散档位 均匀交叉 + 整数变异

原则：编码必须与问题结构一致——对 TSP 用实数向量会产生大量无效路径；对神经网络超参用二进制效率低。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 实数编码示例：3 维超参 [lr, batch, dropout]
import numpy as np

def random_individual(rng):
  return {
      "lr":       10 ** rng.uniform(-5, -2),   # log-uniform
      "batch":    int(rng.choice([8, 16, 32, 64])),
      "dropout":  rng.uniform(0.0, 0.5),
  }

def decode(ind):
  """染色体 → 决策向量 / 训练配置。"""
  return ind  # 实数编码时常为恒等映射

三、遗传算子

图 3　选择、交叉、变异

3.1 选择（Selection）

从种群中挑父代，常用：

方法 机制 特点
锦标赛（Tournament） 随机抽 $k$ 个，取最优 实现简单；pymoo 默认
轮盘赌（Roulette） 按适应度比例抽样 易过早收敛（super individual）
排序选择（Rank） 按排名而非绝对适应度 缓解尺度敏感

锦标赛大小 $k$：$k=2$ 选择压力小、多样性好；$k$ 增大则更快收敛、易早熟。

3.2 交叉（Crossover）

算子 适用编码 说明
单点/两点 二进制 交换片段
SBX 实数 模拟二进制交叉，子代在父代附近；prob=0.9, eta=15 常见
OX / PMX 排列 保持排列合法性
均匀交叉 通用 每位独立来自父代 A 或 B

交叉概率 $p_c$：通常 $0.8$–$0.95$；过低则搜索退化为纯变异。

3.3 变异（Mutation）

算子 适用 说明
位翻转 二进制 $p_m \approx 1/L$
PM（Polynomial Mutation） 实数 有界扰动；eta=20
高斯扰动 实数 $\mathbf{x} \leftarrow \mathbf{x} + \mathcal{N}(0,\sigma^2)$
交换/倒位 排列 局部重排

变异概率 $p_m$：不宜过大（随机游走）或过小（停滞）。

3.4 精英保留（Elitism）

最优个体直接进入下一代，防止最优解因交叉/变异丢失。NSGA-II 的环境选择是精英策略的 Pareto 扩展。

四、标准 GA 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
输入: 目标 f(x) 最小化, 种群规模 N, 最大代数 G, 交叉率 pc, 变异率 pm
P ← 随机初始化 N 个合法个体
评估 F(x) for all x in P
for g = 1 .. G:
    Q ← ∅
    while |Q| < N:
        p1, p2 ← TournamentSelect(P, k=2)
        c1, c2 ← Crossover(p1, p2) with probability pc
        c1 ← Mutate(c1, pm);  c2 ← Mutate(c2, pm)
        Q ← Q ∪ {c1, c2}
    P ← EnvironmentalSelect(P ∪ Q, N)   # 含精英保留
输出: P 中适应度最优个体

终止条件：固定代数 $G$、适应度平台（连续 $K$ 代无改进）、或评估预算 $N_{\mathrm{eval}}$ 用尽。

五、Python 实现

5.1 pymoo（推荐，与 MOO 统一）

单目标实数优化可用 GA 或 DE（差分进化，常更稳）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# pip install pymoo
import numpy as np
from pymoo.core.problem import Problem
from pymoo.algorithms.soo.nonconvex.ga import GA
from pymoo.operators.crossover.sbx import SBX
from pymoo.operators.mutation.pm import PM
from pymoo.operators.sampling.rnd import FloatRandomSampling
from pymoo.optimize import minimize

class Sphere(Problem):
    def __init__(self):
        super().__init__(n_var=10, n_obj=1, xl=-5, xu=5)

    def _evaluate(self, x, out, *args, **kwargs):
        out["F"] = np.sum(x ** 2, axis=1).reshape(-1, 1)

problem = Sphere()
algorithm = GA(
    pop_size=50,
    sampling=FloatRandomSampling(),
    crossover=SBX(prob=0.9, eta=15),
    mutation=PM(eta=20),
    eliminate_duplicates=True,
)
res = minimize(problem, algorithm, ("n_gen", 100), seed=42, verbose=False)
print("best f:", res.F[0, 0], "x:", res.X[0])

多目标时把 GA 换成 NSGA2 即得帕累托前沿（见 MOO-02 §三）。

5.2 最小手工 GA（教学用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import numpy as np

def sphere(x):
    return np.sum(x ** 2)

def tournament(pop, fit, k=2):
    idx = np.random.choice(len(pop), k, replace=False)
    return pop[idx[np.argmin(fit[idx])]]

def sbx(p1, p2, eta=15, xl=-5, xu=5):
    c = np.empty_like(p1)
    for j in range(len(p1)):
        if np.random.rand() < 0.5:
            u = np.random.rand()
            beta = (2*u)**(1/(eta+1)) if u <= 0.5 else (1/(2*(1-u)))**(1/(eta+1))
            c[j] = 0.5 * ((1+beta)*p1[j] + (1-beta)*p2[j])
        else:
            c[j] = p1[j] if np.random.rand() < 0.5 else p2[j]
    return np.clip(c, xl, xu)

rng = np.random.default_rng(0)
N, G, d = 40, 80, 5
pop = rng.uniform(-5, 5, (N, d))
fit = np.array([sphere(x) for x in pop])

for _ in range(G):
    offspring = []
    for _ in range(N):
        p1 = tournament(pop, fit)
        p2 = tournament(pop, fit)
        c = sbx(p1, p2) if rng.random() < 0.9 else p1.copy()
        if rng.random() < 1/d:
            c[rng.integers(d)] += rng.normal(0, 0.5)
            c = np.clip(c, -5, 5)
        offspring.append(c)
    combined = np.vstack([pop, offspring])
    combined_fit = np.array([sphere(x) for x in combined])
    order = np.argsort(combined_fit)[:N]
    pop, fit = combined[order], combined_fit[order]

print("best:", fit[0])

5.3 带约束的处理

策略 做法
惩罚函数 $\tilde{f} = f + \lambda \cdot \mathrm{violation}$
修复 将非法 $\mathbf{x}$ 投影回可行域
约束支配 多目标时用 pymoo 的 n_ieq_constr 
1
2
3
4
5
6
7
class ConstrainedSphere(Problem):
    def __init__(self):
        super().__init__(n_var=2, n_obj=1, n_ieq_constr=1, xl=-5, xu=5)

    def _evaluate(self, x, out, *args, **kwargs):
        out["F"] = (x[:, 0]**2 + x[:, 1]**2).reshape(-1, 1)
        out["G"] = (x[:, 0] + x[:, 1] - 1).reshape(-1, 1)  # g <= 0 可行

六、超参数与实践建议

参数 建议 说明
pop_size $30$–$200$ 维数 $d$ 大时适当增大
n_gen 直到预算或平台 与 pop_size 乘积 ≈ 总评估次数
$p_c$ $0.9$ SBX 交叉
PM eta $15$–$30$ 小 → 大步变异
重复运行 $\ge 5$ seeds GA 随机性强，报告最优/均值
评估缓存 对确定性 $f$ 去重 组合空间重复个体常见

工程 Checklist：

  1. 决策变量归一化到相近尺度（或 log 编码如学习率）；
  2. 固定 seed 复现，多 seed 报分布；
  3. 先在小种群/少代数验证 pipeline，再放大预算；
  4. 若单目标且连续，可对比 CMA-ES、Optuna TPE 作基线。

七、偏好场景与优劣势

维度 说明
适合 目标不可微；多峰/非凸；混合离散-连续；组合优化；评估可并行；需要一批候选解而非单点
典型应用 超参搜索、特征选择、排程/路径、蛋白质序列空间（配合适应度模型）、神经架构搜索（NAS）
优势 实现直观；不依赖梯度；易加约束与自定义编码；种群提供多样性
局限 样本效率低；高维 $d \gtrsim 100$ 时收敛慢；无最优性保证；超参（$N,p_c,p_m$）需调
何时不用 目标可微、维数高、评估贵（$\lesssim 500$ 次）→ 用贝叶斯优化 MOO-02 §七 或 CMA-ES

八、从 GA 到多目标：一行扩展

单目标 GA 多目标扩展 变化点
适应度标量排序 非支配排序 Rank 分层
拥挤/多样 拥挤距离 / 参考点 NSGA-II / NSGA-III
环境选择 精英 + Pareto + 多样性 MOO-02 
1
2
3
# 单目标 GA → 双目标 NSGA-II：仅改算法类与 Problem.n_obj
from pymoo.algorithms.moo.nsga2 import NSGA2
algorithm = NSGA2(pop_size=100)  # 交叉/变异算子与 GA 相同（SBX+PM）

差分进化 DE 可看作另一种进化算子（变异用向量差），pymoo 中 DE 在单目标黑盒上常与 GA 互作基线。

九、与本仓库主题的衔接

主题 关系
MOO-01/02 NSGA-II = GA + Pareto 环境选择
Math-04 优化 GA 是无梯度路线，与 SGD 互补
贝叶斯优化 昂贵评估时 BO 样本效率更高
酶/抗体设计 序列组合空间 + 实验适应度 → GA / 主动学习循环
RL-03-17 进化策略 ES 与 GA 同属 EC，连续控制常用 ES

十、小结

概念 一句话
种群 并行维护多个候选解
选择 优者更易繁殖（锦标赛最常用）
交叉 组合父代基因（实数用 SBX）
变异 随机扰动防早熟
精英保留 最优解不丢失
→ NSGA-II 把标量适应度换成 Pareto 排序

遗传算法不是「比梯度法更好」，而是在无法求导、组合爆炸、需要一批折衷候选时的实用默认。掌握 GA 后，阅读 NSGA-II、MOEA/D 的伪代码会一目了然。

段末注释：早熟收敛（premature convergence）指种群过早聚集到局部最优，丧失多样性；增大变异、增大锦标赛随机性、或增大种群可缓解。

-------------本文结束感谢您的阅读-------------