遗传算法 GA · 深度手册

分类：优化类 ｜ 难度：★★☆ 进阶 ｜ 编号：ga

一、这是什么（一句话用途）

高维 / 非线性 / 离散全局优化

二、核心思想

遗传算法（GA）模拟达尔文进化：维护一个解的"种群"，让适应度高的个体有更多机会把"基因"（解的编码）传给下一代，再通过交叉（ recombination）组合父母优点、变异（mutation）引入新探索，种群逐代演化逼近最优。它对问题的数学结构几乎没有要求（无需梯度、可处理离散/混合变量），擅长高维、多峰、非线性全局搜索；代价是计算量大、结果带随机性、收敛速度不保证。

三、数学原理与推导

编码：解表示为染色体（二进制串或实数向量）。种群规模 $N$。

适应度 $f(x)$（常对目标做平移/缩放使其非负）。选择概率常用轮盘赌 $p_i=f_i/\sum f_j$，或锦标赛。交叉以概率 $p_c$ 交换两父代片段产生子代（实数编码用模拟二进制交叉/算术交叉）。变异以概率 $p_m$ 扰动基因（翻转位或加高斯噪声）。

理论基础（模式定理）：包含 $k$ 个确定位的模式 $H$，其种群中数量随代数以与平均适应度高于种群均值的倍数大致指数增长：

$$m(H,t+1)\ge m(H,t)\frac{\bar{f}_H}{\bar{f}}\Big(1-p_c\frac{\delta(H)}{L-1}-p_m o(H)\Big)$$

即优于平均、短定义距、低阶的模式被放大，驱动搜索朝向高适应度区域。

四、建模 / 求解步骤

1. 编码(二进制 / 实数)
2. 初始化种群
3. 计算适应度
4. 选择 + 交叉 + 变异
5. 迭代至收敛

五、关键公式速查

适应度 f(x)；下一代由选择 / 交叉 / 变异产生

六、典型示例

参数寻优、路径规划、特征选择。

完整算例（数字演示，照着算一遍）

场景：max f(x)=−x²+10x (x∈[0,10])，种群 20，交叉 0.8，变异 0.1。

演化：第 1 代最优 x≈6, f≈24；第 50 代收敛 x≈5, f=25。

结论：GA 找到 x*=5, f*=25（解析同），适合离散/非凸。

七、Python 实现示例

import os, numpy as np
import pandas as pd
HERE = os.path.dirname(os.path.abspath(__file__))
df = pd.read_csv(os.path.join(HERE,"..","datasets","ga.csv"))
X = df[["x","y"]].to_numpy(dtype=float)   # 候选解的目标值 f=y(越小越好)
N=20; pop=X[np.random.default_rng(2).choice(len(X),N)]
for _ in range(50):
    fit = -pop[:,1]
    sel = pop[np.argsort(fit)[-10:]]
    kids=[]
    for _ in range(10):
        a,b=sel[np.random.choice(len(sel),2)]
        c=a+(b-a)*np.random.rand(); kids.append(c)
    pop=np.vstack([sel,np.array(kids)])
    pop=pop[np.argsort(-pop[:,1])][:N]
print("最优解 x=%.3f f=%.3f"%(pop[0,0],pop[0,1]))

配套文件：py_ga.py（需 numpy / pandas；与下方数据集配套练习）

八、MATLAB 实现示例

%% 遗传算法示例（MATLAB/Octave）
df = readtable('..\datasets\ga.csv');
X = table2array(df(:,1:2));
rng(2); pop=X(randi(height(X),20,1),:);
for i=1:50
  fit=-pop(:,2); sel=pop(sort(fit,'descend'),:); sel=sel(1:10,:);
  kids=[];
  for j=1:10, a=sel(randi(10),:); b=sel(randi(10),:); kids=[kids; a+(b-a).*rand(1,2)]; end
  pop=[sel; kids]; pop=pop(sort(-pop(:,2)),:); pop=pop(1:20,:);
end
fprintf('最优 x=%.3f f=%.3f\n', pop(1,1), pop(1,2));

配套文件：m_ga.m（基础 MATLAB / Octave 即可运行）

九、练手数据集（可下载）

30 个候选解的 (x, f(x)) 采样，目标最小化 f。用于遗传算法寻优。

• 字段：x, y
• 行数：30 行
• 下载：ga.csv

十、常见误区与避坑清单

• 编码与适应度设计关键
• 早熟收敛(多样性丢失)
• 参数(交叉率 / 变异率)要调

十一、结果怎么解读

看适应度曲线是否收敛。

十二、常与谁搭配

连续优化可换 PSO。

十三、论文写作技巧（怎么把它写进论文）

把 遗传算法 GA 写进论文，核心不是堆公式，而是讲清「为什么用它、结果怎么呈现、如何对比」三件事。

1. 动机怎么写（为什么用它而不是别的）

先把问题「数学化」：决策变量、目标函数、约束条件——这一步写清楚比算法本身更重要。再说明为何用 遗传算法 GA 求解：连续可导用梯度 / 解析法，组合 / 非凸 / 黑箱用启发式（GA / PSO / SA）。

2. 结果怎么写（图表与指标）

放「收敛曲线（迭代 vs 目标值）」+「最优解参数表」+「约束是否满足」三件套。若是多目标，放 Pareto 前沿散点图。

3. 可直接套用的写作话术

• 中文模板：针对<问题>，本文采用 遗传算法 GA 进行高维 / 非线性 / 离散全局优化。该方法能够自动刻画<优势>，在处理<场景>时相较<对比方法>更具<特点>。
• 英文模板：To address , we adopt 遗传算法 GA to 高维 / 非线性 / 离散全局优化. Benefiting from its ability to , it outperforms on .

4. 同类易踩的写作坑

务必说明约束是否全部满足、是否陷入局部最优（可多次随机初始化对比）；别把无约束结果当约束最优报。

5. 典型论文段落范例（可直接参考 / 改写）

下面是一段可直接套用的论文表述，已按本算法定制，填空处（…）替换成你的真实数值即可。

将配送中心选址建模为带容量约束的总成本最小化问题，本文采用 遗传算法 GA 求解，得到 5 个选址及其服务分配方案，目标值较贪婪启发式降低 12.4%，且全部约束满足。

We formulate the distribution center location as a total-cost minimization problem with capacity constraints and solve it via 遗传算法 GA, yielding 5 sites and their service assignments. The objective is 12.4% lower than a greedy heuristic while satisfying all constraints.

十四、相关手册（延伸阅读）

• 粒子群算法 PSO · 优化类

十五、本手册导航

• 上一篇：模拟退火 SA · 优化类
• 下一篇：粒子群算法 PSO · 优化类
• 返回：算法深度手册库 ｜ 资料站首页

---

本手册由「算法深度手册生成器」自动产出，配套提供 Python / MATLAB 双版本示例与可下载练手数据集。