🧬 10-遗传算法¶
目标:当问题「没有梯度 / 离散 / 黑箱」时,用进化式启发搜索找近似最优。本讲掌握:编码、选择、交叉、变异、 精英保留四个算子 + 两个手写实验(多峰函数优化 / TSP)。面试考点:四个算子各干什么、为什么能全局搜索、 早熟收敛、二进制编码的 Hamming 悬崖。
§0 算法骨架与适用场景¶
生物隐喻:种群(候选解集合)→ 适应度(目标值)→ 选择(优胜劣汰)→ 交叉(基因重组)→ 变异(随机扰动)→ 新一代。
伪代码
初始化种群(随机)
repeat G 代:
计算每个个体的适应度
精英保留最优的 elite 个
按适应度选择父代(锦标赛/轮盘赌)
交叉生成子代(pc); 变异(pm); 子代入新种群
若早熟(多样性消失)→ 加大变异
与梯度法对比:
| 维度 | 梯度下降 | 遗传算法 |
|---|---|---|
| 需要的信息 | 梯度(可导) | 仅目标函数值(黑箱) |
| 解空间 | 连续 | 连续/离散均可(靠编码) |
| 搜索方式 | 局部迭代 | 种群并行 + 重组全局搜索 |
| 收敛性质 | 快但可能困在局部最优 | 慢但不易卡死 |
| 典型场景 | 训练神经网络 | TSP / 调度 / 特征选择 / 超参搜索 |
核心概念¶
(a) 🗂️ 遗传算法知识地图¶
这篇讲"物竞天择式"的搜索:遗传算法用编码、选择、交叉、变异四算子迭代出更好的解,能用二进制基因做函数优化、排列编码解 TSP,并深挖模式定理、早熟收敛与 Hamming 悬崖两大坑。
flowchart TB
Node1["🧠 算法骨架"]
Node1 --> Node2["🧠 编码"]
Node2 --> Node3["🧠 选择策略"]
Node3 --> Node4["🧠 交叉"]
Node4 --> Node5["🧠 变异"]
Node5 --> Node6["🧠 模式定理"]
Node6 --> Node7["🧠 早熟收敛"]
Node7 --> Node8["🧠 Hamming 悬崖"]
Node8 --> Node9["🧠 参数与变体"]
- 节点1(算法骨架):初始化种群 → 算适应度 → 选择 → 交叉 → 变异 → 换代,循环直到收敛;每一步都对应生物学:适者生存、交配重组、基因突变。
- 节点2(编码):二进制基因(16 位量化 [0,1])适合函数优化,排列编码(城市顺序)适合 TSP;编码方式决定交叉变异怎么设计,是 GA 的第一步棋。
- 节点3(选择策略):锦标赛(随机抽 k 个取最优)压力可控、保留多样性;轮盘赌按适应度比例抽签、压力更平滑;代码里锦标赛是默认。
- 节点4(交叉):单点交叉交换两条基因尾部模拟重组;TSP 用顺序交叉 OX 保证子代是合法排列(不重复、不缺城市)。
- 节点5(变异):位翻转变异随机扰动、排列反转对应 2-opt 一步;变异率 pm 太小会早熟,太大破坏好基因——它是全局搜索能力的"保险丝"。
- 节点6(模式定理):模式定理说明"短、低阶、高适应度的基因模式"在种群中的数量按指数增长,这就是 GA 能全局搜索的理论依据。
- 节点7(早熟收敛):种群太快同质化、所有个体挤在一个局部峰,就"早熟"了;对策是控制选择压力、调大变异率、保持多样性。
- 节点8(Hamming 悬崖):二进制相邻数值(如 0111→1000)可能差很多位,交叉变异很难一步跨越,导致搜索卡壳;用 Gray 编码可缓解。
- 节点9(参数与变体):种群规模、交叉率、变异率都有经验表;变体如 NSGA-II 做多目标优化、并行 GA 提速;应用落点从超参搜索到网络结构搜索都能谈。
§0.1 配图:遗传算法的流程图与生物学对应¶
配一张标准流程图,把四个算子串起来:

图注:遗传算法流程图——初始化 → 适应度评估 → 选择 → 交叉 → 变异 → 新一代循环 (来源:Wikimedia Commons,CC BY-SA 4.0)。
生物学对应表(面试讲起来更有画面感):
| 生物概念 | GA 中的实现 |
|---|---|
| 基因/染色体 | 编码后的解(二进制串 / 排列 / 实数向量) |
| 种群 | 一组候选解的集合 |
| 适应度 | 目标函数值(越高越好,TSP 用负环长) |
| 选择 | 锦标赛 / 轮盘赌,优秀个体有更高概率繁殖 |
| 交叉 | 两个父本交换片段生成子代(基因重组) |
| 变异 | 随机翻转/扰动,维持多样性 |
| 精英保留 | 最优个体直接进入下一代(不参与遗传,防退化) |
🧩 核心设计自由度就两个:编码(决定解空间怎么映射)与算子(决定怎么搜索)。 后面 §1 的 TSP 就是换编码 + 换算子重写一遍主循环。
✍️ §1.1 手算遗传算法一代:解码 → 适应度 → 轮盘赌 → 交叉 → 变异¶
四个算子背得再熟,一代数字跑一遍才真正理解"优胜劣汰"如何落在二进制串上。 简化:$N_B=4$ 位二进制基因,$x\in[0,1]$ 量化为 $\tfrac{\text{val}}{15}$,目标 $f(x)=x\sin(10\pi x)+1$(多峰)。
第 1 步:解码 + 适应度(4 个个体)
| 基因 | val | $x=\text{val}/15$ | $f(x)$ |
|---|---|---|---|
| 0000 | 0 | 0.000 | 1.0000 |
| 0111 | 7 | 0.467 | 1.4041 |
| 1000 | 8 | 0.533 | 0.5381 |
| 1111 | 15 | 1.000 | 1.0000 |
0111 适应度最高(1.4041)——它的 $x\approx0.467$ 正好靠近全局峰附近;1000 适应度最低。
第 2 步:轮盘赌选择概率(适应度比例)
$$p(0000)=\frac{1.000}{3.942}=0.254,\quad p(0111)=\frac{1.404}{3.942}=0.356,\quad p(1000)=0.137,\quad p(1111)=0.254$$
累计概率 $[0.254,\ 0.610,\ 0.746,\ 1.000]$:随机数落在哪个区间就选中谁——适应度越高被抽中概率越大。
第 3 步:单点交叉(父本 0111 × 1000,交叉点在第 2 位后)
$$\underbrace{01}_{0111}|\underbrace{00}_{1000} \Rightarrow \text{子1: }0100,\qquad \underbrace{10}_{1000}|\underbrace{11}_{0111} \Rightarrow \text{子2: }1011$$
$$x(0100)=\tfrac{4}{15}=0.267,\ f=1.231;\qquad x(1011)=\tfrac{11}{15}=0.733,\ f=0.365$$
交叉把两个父本的片段拼出新解——"基因重组"的数学形式。
第 4 步:变异(以 0111 翻第 4 位为例,变异率 $p_m$ 很小)
$$0111 \xrightarrow{\text{第4位翻转}} 0110$$
手算收获:
- 解码是二进制→实数的桥梁:
val = 2×val + bit(左移+或)正是笔记本里decode的实现 - 轮盘赌 = 适应度比例抽样:0111 有 35.6% 概率被选为父本(适者生存)
- 交叉创造新基因型但不创造新等位基因;变异才引入全新位型——所以变异率虽小但不可少
- 二进制相邻值 0111(7)→1000(8) 要翻 4 位(Hamming 悬崖):交叉变异很难一步跨越,这就是 §2 要讲的坑
下面 numpy 复算。
# ---- §1.1 验证:numpy 复算遗传算法一代 ----
import numpy as np
NB = 4
def decode(gene):
val = 0
for bit in gene:
val = (val << 1) | int(bit)
return val / (2 ** NB - 1)
def target(x):
return x * np.sin(10 * np.pi * x) + 1.0
pop = ['0000', '0111', '1000', '1111']
fs = [target(decode(g)) for g in pop]
print('个体 x f(x)')
for g, f in zip(pop, fs):
print(f' {g} {decode(g):.3f} {f:.4f}')
assert abs(fs[1] - 1.4041) < 1e-3 and abs(fs[2] - 0.5381) < 1e-3
# 轮盘赌
p = np.array(fs) / np.sum(fs)
print('\n轮盘赌概率 =', np.round(p, 4))
print('累计 =', np.round(np.cumsum(p), 4))
# 单点交叉 @第2位后
p1, p2, cut = '0111', '1000', 2
c1, c2 = p1[:cut] + p2[cut:], p2[:cut] + p1[cut:]
print(f'\n交叉: {p1} × {p2} @位{cut} -> {c1}, {c2}')
print(f'子代: x={decode(c1):.3f} f={target(decode(c1)):.4f} | x={decode(c2):.3f} f={target(decode(c2)):.4f}')
assert abs(target(decode(c1)) - 1.2309) < 1e-3
# 变异:0111 翻第 4 位
gene = '0111'; idx = 3
mut = ''.join(str(1 - int(b)) if i == idx else b for i, b in enumerate(gene))
print(f'变异: {gene} 翻第{idx+1}位 -> {mut}')
# Hamming 悬崖
hd = sum(a != b for a, b in zip('0111', '1000'))
print(f'Hamming 悬崖: 0111(7) -> 1000(8) 相差 {hd} 位')
print('\n✓ 与手算一致')
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'DejaVu Sans']
plt.rcParams['axes.unicode_minus'] = False
rng = np.random.default_rng(2024)
# ---------- 测试函数:f(x)=x·sin(10πx)+1, x∈[0,1],多峰,全局最大 1.85 (x≈0.85) ----------
def target(x):
return x * np.sin(10 * np.pi * x) + 1.0
# ================= 遗传算法四算子(手写核心) =================
# 编码:二进制基因(NB=16 位)。x ∈ [0,1] 被量化成 2^16 个档位。
# 为什么用二进制:交叉/变异对位操作自然、搜索粒度可控;代价是 Hamming 悬崖(见 §2)。
NB = 16
def decode(gene):
# 二进制基因 → [0,1] 的实数:按位累加得整数 val,再除以 2^NB-1 归一化
# 例:NB=4 时 1010 -> 10/15 ≈ 0.667
val = 0
for bit in gene:
val = (val << 1) | int(bit) # 左移一位再或上当前位 = 二进制转整数
return val / (2 ** NB - 1)
def fitness(gene):
return target(decode(gene)) # 适应度 = 目标函数值(越高越好)
def init_pop(size):
# 随机种群:每行一个个体,NB 个 0/1 位
return rng.integers(0, 2, size=(size, NB))
def select_tournament(pop, fits, k=3):
# 锦标赛选择:随机抽 k 个个体,取适应度最高的那个作为父本
# 作用:保持选择压力又不至于让最强个体垄断(保留多样性)
idx = rng.choice(len(pop), k, replace=False)
return pop[np.argmax(fits[idx])].copy()
def crossover(p1, p2, pc=0.85):
# 单点交叉:以概率 pc 在随机断点 pt 交换两条基因的尾部,模拟基因重组
if rng.random() > pc: # 不交叉时直接复制父本
return p1.copy(), p2.copy()
pt = int(rng.integers(1, NB)) # 断点取 1..NB-1(至少交换一位)
c1 = np.concatenate([p1[:pt], p2[pt:]])
c2 = np.concatenate([p2[:pt], p1[pt:]])
return c1, c2
def mutate(gene, pm=0.01):
# 位翻转变异:每位以概率 pm 取反(0→1 或 1→0)
# 作用:引入随机扰动,防止种群过早同化(早熟收敛),保住全局搜索能力
g = gene.copy()
mask = rng.random(NB) < pm # 布尔掩码:哪些位要翻转
g[mask] = 1 - g[mask]
return g
def ga(pop_size=60, gens=120, pm=0.01, pc=0.85, elite=2, seed=1):
# 主循环:初始化 → 每代评估/记录/选亲/交叉/变异/精英保留
global rng
rng = np.random.default_rng(seed) # 固定随机种子:实验可复现
pop = init_pop(pop_size)
best_hist, mean_hist = [], [] # 记录每代最优与平均适应度(画收敛曲线用)
for _ in range(gens):
fits = np.array([fitness(g) for g in pop])
best_hist.append(fits.max()); mean_hist.append(fits.mean())
order = np.argsort(fits)[::-1] # 按适应度从高到低排序(精英在前)
newpop = [pop[i].copy() for i in order[:elite]] # 精英保留:最优 elite 个直接进下一代
while len(newpop) < pop_size:
p1 = select_tournament(pop, fits) # 锦标赛选父本1
p2 = select_tournament(pop, fits) # 锦标赛选父本2
c1, c2 = crossover(p1, p2, pc) # 交叉产生两个子代
c1 = mutate(c1, pm); c2 = mutate(c2, pm) # 变异
newpop.extend([c1, c2])
pop = np.array(newpop[:pop_size]) # 补齐到种群规模
fits = np.array([fitness(g) for g in pop])
return np.array(best_hist), np.array(mean_hist), pop[np.argmax(fits)] # 末代最优个体
bh, mh, bg = ga(seed=1)
bx = decode(bg) # 解码末代最优基因 → 最优解的 x 坐标
print('GA 找到: x = %.4f, f = %.4f(全局最优 ≈ 1.8505 @ x≈0.85)' % (bx, target(bx)))
print('收敛:首代最优 %.3f → 末代最优 %.3f' % (bh[0], bh[-1]))
assert abs(target(bx) - 1.8505) < 1e-3 # 必须逼近全局最优(多峰函数不卡在局部峰)
# ========== 图 1:GA 在多峰函数上找到全局最优 ==========
gx = np.linspace(0, 1, 400)
fig, ax = plt.subplots(figsize=(7.2, 4.6))
ax.plot(gx, target(gx), lw=1.6, color='#4C72B0', label='f(x) = x·sin(10πx)+1')
ax.axvline(bx, color='#C44E52', ls='--', lw=1.2)
ax.plot(bx, target(bx), '*', ms=15, color='#C44E52', label='GA 找到 (x=%.3f, f=%.3f)' % (bx, target(bx)))
ax.set_xlabel('x'); ax.set_ylabel('f(x)')
ax.set_title('GA 在多峰函数上找到全局最优(未卡在左侧局部峰)', fontsize=12)
ax.legend(fontsize=9); ax.grid(alpha=0.3); plt.tight_layout(); plt.show()
# ========== 图 2:收敛曲线 ==========
fig, ax = plt.subplots(figsize=(7.2, 4.2))
ax.plot(bh, lw=1.8, color='#C44E52', label='每代最优')
ax.plot(mh, lw=1.4, color='#4C72B0', alpha=0.8, label='每代平均')
ax.set_xlabel('代数'); ax.set_ylabel('适应度')
ax.set_title('GA 收敛曲线:最优提升 + 均值追赶(种群整体变好)', fontsize=12)
ax.legend(fontsize=9); ax.grid(alpha=0.3); plt.tight_layout(); plt.show()
# ================= 图 3:变异率 pm 的影响(早熟 vs 破坏) =================
# pm 太小:种群很快同质化,找不到新区域(早熟收敛);
# pm 太大:好基因频繁被破坏,收敛慢甚至发散。
fig, ax = plt.subplots(figsize=(7.2, 4.2))
for pm, col in [(0.001, '#8E8E93'), (0.01, '#4C72B0'), (0.15, '#C44E52')]:
bh2, _, _ = ga(pm=pm, seed=1)
ax.plot(bh2, lw=1.5, color=col, label='pm = %.3f' % pm)
ax.set_xlabel('代数'); ax.set_ylabel('每代最优适应度')
ax.set_title('变异率对比:pm 太小→早熟,太大→破坏优秀基因', fontsize=12)
ax.legend(fontsize=9); ax.grid(alpha=0.3); plt.tight_layout(); plt.show()
§0.2 选择策略详解:锦标赛 vs 轮盘赌¶
选择决定「搜索压力」(exploitation 强度),是 GA 的杠杆:
轮盘赌(Roulette):个体被选概率 ∝ 适应度占比 $p_i = f_i / \sum_j f_j$。
- 优点:实现直观;缺点:适应度尺度敏感(一个超级个体垄断抽签概率 → 早熟), 适应度为负时还要平移处理。
锦标赛(Tournament):随机抽 $k$ 个个体,取其中适应度最高者。
- 优点:只比大小不比数值(对负适应度/尺度变化鲁棒)、选择压力由 $k$ 控制 ($k$ 大 → 压力大 → 收敛快但多样性差);
- 本讲代码选它:
select_tournament(pop, fits, k=3)。
排序选择(Rank):按适应度排名给固定概率——比轮盘赌稳,比锦标赛贵一点。
📌 面试选择题:轮盘赌对适应度尺度敏感;锦标赛只看相对排序;$k$ 是压力的旋钮。 手撕代码优先锦标赛(3 行实现,效果稳)。
§1 排列编码与 TSP:遗传算法也能跑组合优化¶
多峰函数用的是二进制编码;TSP(旅行商)要用排列编码:一条染色体 = 一个城市访问顺序。 此时交叉不能乱切(会得到重复城市),要用部分匹配交叉(PMX)或顺序交叉(OX):
OX 交叉步骤(见代码):
- 从父本 P1 随机选一段
[a,b],原样继承到子代 - 从父本 P2 的
b+1起循环扫描,按顺序填入子代空缺位(跳过重复城市) - 保证每个城市在子代恰好出现一次(仍是合法环)
变异用反转片段(2-opt 一步):随机选一段反转顺序 → 相当于局部扰动。
编码决定了交叉/变异的含义——这是遗传算法的设计要点,面试高频。
# ================= 排列编码 GA 求解 TSP =================
Nc = 12
rng12 = np.random.default_rng(2) # 本实例: GA 27.12 < 最近邻 29.85(改善约 9%,见下方对照)
cities = rng12.random((Nc, 2)) * 10
dist = np.sqrt(((cities[:, None, :] - cities[None, :, :]) ** 2).sum(-1)) # 距离矩阵 d[i,j]
def tour_len(order):
# 环长 = 沿顺序相邻城市距离之和 + 回起点的边(封闭环)
return sum(dist[order[i], order[(i + 1) % Nc]] for i in range(Nc))
def ox_cross(p1, p2):
# 顺序交叉 OX:保证子代是合法排列(不重复、不缺城市)
a, b = sorted(rng12.integers(0, Nc, size=2).tolist()) # 随机选段 [a,b]
child = [-1] * Nc # 子代初始化成占位符
child[a:b + 1] = p1[a:b + 1] # 步骤1:P1 的 [a,b] 段原样继承
# 步骤2:从 P2 的 b+1 位置开始循环扫描,把未出现过的城市按序填入子代空缺
fill = [x for x in list(p2[b + 1:]) + list(p2[:b + 1]) if x not in child]
k = 0
for i in range(Nc):
if child[i] == -1: # 遇到空缺就补一个
child[i] = fill[k]; k += 1
return child
def invert_mut(order):
# 反转变异:随机选一段 [a,b] 反转顺序(对应 TSP 里 2-opt 一步)
i, j = sorted(rng12.integers(0, Nc, size=2).tolist())
return order[:i] + order[i:j + 1][::-1] + order[j + 1:]
def ga_tsp(pop_size=120, gens=250, pc=0.9, pm=0.25, elite=3, seed=1):
# 主循环与函数优化版同构:适应度 = 环长越小越好 → 用 -环长 作为适应度
r = np.random.default_rng(seed)
pop = [r.permutation(Nc).tolist() for _ in range(pop_size)] # 随机排列作为初始种群
best_hist = []
best_tour = None; best_len = np.inf
for _ in range(gens):
fits = np.array([-tour_len(o) for o in pop]) # 适应度取负环长(越大越好)
best_hist.append(-fits.max())
order = np.argsort(fits)[::-1]
newpop = [pop[i][:] for i in order[:elite]] # 精英保留
while len(newpop) < pop_size:
# 锦标赛选父本:随机抽 3 个个体,取适应度最高者的下标
i1 = int(np.argmax(fits[r.choice(len(pop), 3, replace=False)]))
i2 = int(np.argmax(fits[r.choice(len(pop), 3, replace=False)]))
if r.random() < pc:
c1 = ox_cross(pop[i1], pop[i2]); c2 = ox_cross(pop[i2], pop[i1])
else:
c1 = pop[i1][:]; c2 = pop[i2][:]
if r.random() < pm:
c1 = invert_mut(c1); c2 = invert_mut(c2)
newpop += [c1, c2]
pop = newpop[:pop_size]
l = tour_len(pop[order[0]])
if l < best_len: # 记录全局最优
best_len = l; best_tour = pop[order[0]][:]
return np.array(best_hist), best_tour, best_len
bh_t, bt, bl = ga_tsp(seed=1)
print('TSP GA 最优环长: %.2f' % bl)
# ---------- 对照:最近邻启发式(从每座城市出发,每次走最近的未访问城市) ----------
def nearest_neighbor():
best = np.inf
for s in range(Nc): # 每个起点都试
un = set(range(Nc)); un.discard(s)
cur = [s]
while un:
nxt = min(un, key=lambda j: dist[cur[-1], j]) # 挑最近的未访问城市
cur.append(nxt); un.discard(nxt)
best = min(best, tour_len(cur))
return best
nn_len = nearest_neighbor()
print('最近邻启发式: %.2f;GA 相对改善 %.1f%%' % (nn_len, (nn_len - bl) / nn_len * 100))
assert bl < nn_len, 'GA 应优于最近邻基线'
# ========== 图:GA 找到的 TSP 路径 + 收敛曲线 ==========
fig, ax = plt.subplots(1, 2, figsize=(11.5, 4.6))
ax[0].plot(cities[:, 0], cities[:, 1], 'o', color='#4C72B0')
order_l = bt + [bt[0]] # 闭合环
ax[0].plot(cities[order_l, 0], cities[order_l, 1], '-', color='#C44E52', lw=1.5)
ax[0].set_title('GA 找到的 TSP 最优路径(环长 %.2f)' % bl, fontsize=12)
ax[0].grid(alpha=0.3)
ax[1].plot(bh_t, lw=1.6, color='#C44E52')
ax[1].set_title('TSP 遗传算法收敛:环长逐代下降', fontsize=12)
ax[1].set_xlabel('代数'); ax[1].set_ylabel('最优环长')
ax[1].grid(alpha=0.3)
plt.tight_layout(); plt.show()
§1.2 为什么 GA 能全局搜索:模式定理(Schema Theorem)¶
GA 不是「盲目的随机搜索」,它有理论支撑。模式(schema) = 染色体上带
通配符 * 的模板,如 1**0*;适应度高的模式在群体中的代表数按指数增长
(Holland 1975):
$$\mathbb{E}[m(H,t+1)] \ge m(H,t)\cdot\frac{f(H)}{\bar f}\cdot\left(1 - p_c\frac{\delta(H)}{L-1} - p_m\,o(H)\right)$$
其中 $\delta(H)$ 是模式跨度、$o(H)$ 是定义位个数。直观解读:
- 短定义距(小 δ)、低阶(小 o)、高适应度的模式(building block,积木块) 会被选择压指数放大;
- 交叉/变异会破坏模式,但概率与模式复杂度成正比——简单模式更抗破坏。
工程含义:
- GA 的有效搜索单位是「模式」而非个体——这就是为什么种群要有多样性(模式库);
- 编码要设计成短积木块易保持(例如让相关变量位相邻)——二进制码对某些问题合适, 对另一些问题(如连续优化)用实数编码 + SBX 更好;
- 锦标赛等选择压力大时,高适应度模式放大更快,但也更快耗尽多样性(早熟)。
📌 面试答「GA 为什么有效」:选择放大好积木块,交叉重组积木块,变异注入新积木块—— 三者配合使优良模式指数增长。能写出上式第一行已超出绝大多数候选者。
§2 早熟收敛与 Hamming 悬崖(两大经典坑)¶
早熟收敛(premature convergence):某个高适应度个体快速复制扩散,种群失去多样性 → 搜索停滞在局部最优。 缓解:锦标赛/轮盘赌(压力可调)、精英保留(不丢最优)、自适应变异、岛屿模型/迁徙、多样化惩罚。
Hamming 悬崖:二进制相邻整数可能对应完全不同的基因(如 0111...1 与 1000...0)。
梯度式的交叉变异难以在小范围移动 → 可用 Gray 码 消除悬崖。
§2.1 参数怎么调 + 实战经验表¶
GA 的参数(种群规模、交叉率、变异率、代数、精英数)没有万能值,但经验区间很集中:
| 参数 | 推荐区间 | 调大 → | 调小 → |
|---|---|---|---|
| 种群规模 pop | 50~500 | 多样性好但每代慢 | 早熟风险 |
| 交叉率 pc | 0.7~0.95 | 探索强、收敛慢 | 更像随机搜索 |
| 变异率 pm | 0.001~0.1(二进制) | 破坏好基因 | 早熟、卡死 |
| 精英数 elite | 1~5 | 收敛快但多样性降 | 最优可能丢失 |
| 代数 gens | 100~1000 | 更接近最优 | 欠收敛 |
工程套路(先粗后细):
- 先用小种群 + 短代数跑通,确认编码/算子正确(能逼近已知最优);
- 看收敛曲线:若最优曲线早早就平了 → 早熟(加大 pm / 减选择压力 / 加大种群);
- 若曲线缓慢爬升、末代仍在涨 → 代数不够(加代数 / 加大交叉);
- 固定随机种子上线前多做几次(GA 是随机算法,单次结果会抖)。
💡 面试若问「GA 和深度学习有什么关系」:超参搜索(神经网络结构/学习率的进化搜索)、 NEAT 演化神经网络、以及「进化策略(ES)」作为黑箱优化器都有实际应用——但正式训练主体仍是梯度法。
§2.2 变体速览:NSGA-II / 多目标 / 并行¶
知道这些变体名字,面试可以快速展示知识面:
- NSGA-II:多目标 GA(Pareto 前沿),非支配排序 + 拥挤度距离,业界标准;
- 实数编码 GA:连续优化直接用浮点向量 + 模拟二进制交叉(SBX)与多项式变异;
- 协同进化:把问题拆成子种群各自进化再协作(如车辆路径的订单-车辆双种群);
- 并行 GA:岛屿模型(各岛独立进化 + 定期迁徙)——分布式框架常见;
- 遗传编程(GP):个体是程序/表达式树,交叉交换子树——用于符号回归、自动特征工程。
📌 一句话定位:GA 是「编码 + 算子」的框架,换编码换算子就能适配新问题; 面试只要讲清「为什么种群并行能全局搜索」就立于不败之地。
§2.3 GA 的实际应用落点(结合 ML 场景谈)¶
除了教科书 TSP/背包,GA 在 ML 工程里真正高频出现的地方:
- 超参数搜索:神经网络的学习率/层数/头数组成一个「离散+连续」混合空间, GA 比网格搜索快、比随机搜索更能「继承好组合」(NAS 的演化版本就是这么做的);
- 特征选择:每个特征一个基因位(选/不选),适应度 = 模型交叉验证得分 + 特征数惩罚——工业上常用来做高维筛选;
- 神经网络结构搜索(NAS):编码网络结构(层类型/连接),用 GA/进化算法搜索架构;
- 调度/排程:工厂排程、GPU 任务调度(离散排列问题);
- 对抗样本/程序合成:遗传编程(GP)自动生成表达式或小段程序。
与深度学习的真实关系:LLM 训练本体不用 GA(梯度法足够好),但超参/结构/数据配比 这类「离散决策」问题,GA 与贝叶斯优化并列是常用武器——知道这个分界,面试就不怕被追问。
§3 面试追问与自测¶
- 四个算子各干什么、为什么能全局搜索?(选择=局部开发、交叉/变异=全局探索)
- 早熟收敛是什么、怎么缓解?(多样性管理)
- 二进制编码的 Hamming 悬崖?Gray 码怎么解决?
- TSP 用什么编码、交叉为什么不能简单单点?(排列编码 + OX/PMX)
- GA vs 模拟退火?(种群并行 vs 单点马尔可夫链,见 11 篇)
自测清单
- 手写二进制解码 / 锦标赛选择 / 单点交叉 / 位翻转变异
- 用 GA 跑通多峰函数并逼近全局最优(本讲断言)
- 默写 OX 交叉步骤,手撕 TSP GA
- 讲清早熟与悬崖,并各给一种解法
💡 下节预告:单点搜索也能全局收敛——11 模拟退火与禁忌搜索。