跳转到内容
← 返回算法
元启发式算法计算机科学 · 组合优化 · 演化计算约 27 分钟阅读

遗传算法

Genetic Algorithms

1975 年，密歇根大学教授约翰·霍兰德（John Holland）出版了《自然与人工系统中的适应》（Adaptation in Natural and Artificial Systems），正式确立了遗传算法（Genetic Algorithm, GA）的理论框架。他的核心思想：如果自然界能通过几十亿年的选择、交叉…

遗传算法演化计算元启发式自然选择优化

1975 年，密歇根大学教授约翰·霍兰德（John Holland）出版了《自然与人工系统中的适应》（Adaptation in Natural and Artificial Systems），正式确立了遗传算法（Genetic Algorithm, GA）的理论框架。他的核心思想：如果自然界能通过几十亿年的选择、交叉、变异演化出人类的大脑，那么同样的机制可以被用来在计算机上求解复杂优化问题。

破除误解：遗传算法不是随机搜索

遗传算法使用了大量随机性，但不是盲目的随机搜索。它有两个关键结构：

  1. 选择压力（Selection Pressure）：适应度高的个体更可能被选中繁殖，好的解被保留并传播。
  2. 遗传操作（Genetic Operators）：交叉将不同解的优良部分组合，变异保持多样性、防止早熟收敛。

这两者共同形成了有方向的随机搜索——既不是爬山（只选更好的），也不是游走（完全无方向）。

核心算法框架

初始化：生成 N 个随机"个体"（候选解）
重复（直到满足终止条件）：
  评估：计算每个个体的适应度 f(x)
  选择：按适应度选出"父代"（适者更有机会被选）
  交叉：配对父代，交换基因段生成"子代"
  变异：以小概率随机修改子代的某些基因位
  替换：用子代替换（部分）父代，形成新种群
输出：历史上适应度最高的个体
```

手算一代：4 条 5 位染色体

上面那段伪代码有六个步骤，但只要种群足够小，一整代可以用笔算完。Goldberg 1989 年的教科书用的最小例子是：在 x∈[0,31]x \in [0, 31] 上最大化 f(x)=x2f(x) = x^2，解用 5 位无符号二进制编码（31=1111131 = \texttt{11111}），种群大小 4。下面按这个设定走完一代。

第一步：评估与轮盘赌选择

随机初始种群与它们的适应度：

编号染色体解码 $x$适应度 f=x2f = x^2占比 f/∑ff/\sum f期望被选中次数 4×4 \times 占比实际选中次数
101101131690.1440.581
211000245760.4921.972
3010008640.0550.220
410011193610.3091.231
合计11701.0004.004

种群平均适应度 $1170/4 = 292.5$，最好个体 576。

轮盘赌（Roulette Wheel）就是照第 5 列的占比切一个圆盘，转 4 次。个体 2 独占 49.2% 的盘面，转 4 次期望命中约 2 次；个体 3 只占 5.5%，期望 0.22 次。这一轮的结果是个体 3 被淘汰、个体 2 复制了两份，交配池 = {01101, 11000, 11000, 10011}。

这一列数字最该注意的是"期望"与"实际"的差：个体 1 的期望是 0.58 次，但实际只能取整数 0 或 1。种群只有 4 个时，取整误差大到能改变演化走向——这就是小种群 GA 的遗传漂变（genetic drift），好个体可能纯粹因为运气被漏掉。种群规模的第一个作用不是"搜索更广"，而是让选择概率有意义。

第二步：单点交叉

交配池两两配对，各随机选一个切点，两个父代交换切点之后的尾段。第一对在第 4 位后切，第二对在第 2 位后切（下面用 / 标出切点）：

text
配对 A（切点在第 4 位后）      配对 B（切点在第 2 位后）
  0110/1                        11/000
  1100/0                        10/011
  ------                        ------
  0110|0  →  01100              11|011  →  11011
  1100|1  →  11001              10|000  →  10000
```
配对父代切点子代
A01101 与 11000第 4 位后01100 与 11001
B11000 与 10011第 2 位后11011 与 10000

第三步：算账

新个体解码 $x$适应度
0110012144
1100125625
1101127729
1000016256
合计1754
上一代这一代变化
适应度总和11701754+50%
平均适应度292.5438.5+50%
最优个体576（$x=24$）729（$x=27$）+27%

一代之内，平均适应度涨了五成，最好解从 24 走到 27（真正的最优是 312=96131^2 = 961）。

变异这一步在本例里没有实际发生——按常用的 pm≈0.001p_m \approx 0.001，20 个基因位每代期望翻转 20×0.001=0.0220 \times 0.001 = 0.02 位，也就是平均五十代才翻一位。变异不是搜索的引擎，是保险丝：它的作用是保证某个位置不会因为全种群都取了同一个值而永久锁死。真正推动搜索的是交叉。

看第二对配对最能理解交叉在干什么：11000（x=24x{=}24，高位很好）与 10011（x=19x{=}19，低位有 1）拼出了 11011（x=27x{=}27），比两个父代都好。这正是霍兰德设想的机制——不同个体各自持有一段有价值的片段，交叉把它们装到一起。下一节的模式定理就是在给这句话找数学表述。

模式定理：为什么遗传算法有效

霍兰德的模式定理（Schema Theorem）给出了理论解释。

一个模式（Schema）是基因串的一个模板，如 1*0*1（* 可以是 0 或 1）。定义模式 $H$ 的适应度 fˉ(H)\bar{f}(H) 为该模式所有实例的平均适应度。模式定理断言：短的、低阶的、高适应度的模式在下一代中的期望样本数为：

m(H,t+1)≥m(H,t)⋅fˉ(H)fˉ⋅(1−pc⋅δ(H)l−1−o(H)⋅pm)m(H, t+1) \geq m(H, t) \cdot \frac{\bar{f}(H)}{\bar{f}} \cdot \left(1 - p_c \cdot \frac{\delta(H)}{l-1} - o(H) \cdot p_m\right)

其中 δ(H)\delta(H) 是模式的定义长度（第一个与最后一个固定位之间的距离），$o(H)$ 是模式的阶（固定位的数量），pc,pmp_c, p_m 是交叉和变异概率。

直觉：优良的"基因片段"（短、高适应度的模式）会指数级增长，这就是遗传算法能搜索庞大空间的理论基础。

把定理代进上一节的数字

用上一节的种群验算两个模式，可以看清这个不等式到底能预测什么、不能预测什么。$l = 5$，取 pc=1.0p_c = 1.0、pm=0.001p_m = 0.001。

模式一：$H_1 = \texttt{1}$（"最高位是 1"，即 x≥16x \geq 16）。阶 $o = 1$，定义长度 δ=0\delta = 0（只有一个固定位，首尾重合）。

  • 第 0 代实例：11000（576）与 10011（361），所以 m(H1,0)=2m(H_1, 0) = 2
  • fˉ(H1)=(576+361)/2=468.5\bar f(H_1) = (576 + 361)/2 = 468.5，种群平均 fˉ=292.5\bar f = 292.5，比值 $= 1.602$
  • 破坏项：1−1.0×04−1×0.001=0.9991 - 1.0 \times \frac{0}{4} - 1 \times 0.001 = 0.999
  • 预测：m(H1,1)≥2×1.602×0.999=3.20m(H_1, 1) \geq 2 \times 1.602 \times 0.999 = 3.20

第 1 代实际有几个 1****？子代是 01100、11001、11011、10000——后三个都以 1 开头，实际 3 个。预测下界 3.20 与实际 3 基本吻合（不等式给的是期望的下界，单次抽样落在附近很正常）。

模式二：$H_2 = \texttt{11}$（首尾都是 1）。阶 $o = 2$，定义长度 δ=4\delta = 4——跨越了整条染色体*。

  • 第 0 代实例：只有 10011（361），m(H2,0)=1m(H_2, 0) = 1，fˉ(H2)/fˉ=361/292.5=1.234\bar f(H_2)/\bar f = 361/292.5 = 1.234
  • 破坏项：1−1.0×44−2×0.001=−0.0021 - 1.0 \times \frac{4}{4} - 2 \times 0.001 = -0.002
  • 预测：m(H2,1)≥1×1.234×(−0.002)<0m(H_2, 1) \geq 1 \times 1.234 \times (-0.002) < 0

下界是个负数，也就是一句废话——不等式没说错，但什么信息都没给。而实际上第 1 代有两个 1***1（11001 与 11011）：10011 尾部那个 1 在第二对交叉中传给了 11011，01101 尾部那个 1 传给了 11001。

这一对对照就是模式定理的全部性格：

  1. 它只管短模式。 定义长度一长，单点交叉几乎必然把它切断，1−pcδ/(l−1)1 - p_c\delta/(l-1) 直接趋零甚至转负，定理退化为无信息。所谓"积木块假说（Building Block Hypothesis）"——GA 靠拼装短的高适应度片段工作——正是这个偏好的名字。
  2. 它是单代的下界，不是长期预测。 上面 H2H_2 的实例数从 1 涨到 2，定理完全没预测到，因为它只算"最坏情况下能保住多少"，不算交叉新造出的实例。
  3. 编码方式决定了哪些模式是"短"的。 同一个问题换一种位排列，δ\delta 就变了，GA 的行为随之变。这解释了为什么 GA 的效果对编码极其敏感——而编码是使用者的选择，不是算法的一部分。

编码：把解变成"基因"

遗传算法的第一步是选择编码方式，将问题的解表示为可以被遗传操作处理的形式：

  • 二进制编码（霍兰德原始方案）：解编码为 0/1 串。
  • 实值编码：解直接用实数向量表示，适合连续优化问题。
  • 排列编码：解是元素的排列，如 TSP 中的城市顺序。
  • 树编码：用于遗传编程（Genetic Programming, GP），个体是程序/表达式树。

排列编码值得单独一提，因为它暴露了 GA 的一个结构性麻烦：标准的单点交叉在排列上是非法的。把两条城市顺序在中间剪断互换，结果几乎必然出现重复城市和遗漏城市——不是"差的解"，是根本不成立的解。于是 TSP 上的 GA 必须换一整套专用算子（顺序交叉 OX、部分匹配交叉 PMX、边重组交叉 ERX 等）。这说明遗传算法不是一个即插即用的黑箱：换问题往往要重新设计算子，而算子的好坏直接决定成败。

关键遗传操作

选择（Selection）：

  • 轮盘赌选择（Roulette Wheel）：个体被选中的概率正比于其适应度
  • 锦标赛选择（Tournament）：随机取 $k$ 个个体，选适应度最高者
  • 精英保留（Elitism）：直接将最优个体复制到下一代

上文的手算用的是轮盘赌，而实践中锦标赛选择用得更多，原因是轮盘赌有一个具体的毛病：它对适应度的绝对数值敏感。若某个个体的适应度是 10610^6、其余都是 10210^2，它会独占几乎整个盘面，一代之内种群就全变成它的复制品（早熟收敛）；反过来，若所有适应度都是 $1000$ 上下的微小差异，选择压力又几乎为零，退化成随机游走。锦标赛选择只比较排序、不看数值差多少，因此对适应度的尺度免疫——把"数值"换成"名次"，这是元启发式里最常见的一次稳健性修补。

交叉（Crossover）：

  • 单点交叉：在随机位置切断，交换两个父代的后半段
  • 多点交叉：多个切点
  • 均匀交叉：每个基因位独立地以 50% 概率来自父代 A 或 B

变异（Mutation）：以小概率（通常 0.001∼0.010.001 \sim 0.01）随机翻转基因位，防止种群陷入单一解。

演化计算家族

遗传算法只是演化计算（Evolutionary Computation）家族的一员：

算法提出者/时期特点
遗传算法（GA）Holland, 1975二进制编码，交叉为主
演化策略（ES）Rechenberg, 1973实值编码，变异为主，自适应步长
遗传编程（GP）Koza, 1992个体是程序树，自动编程
差分进化（DE）Storn & Price, 1997实值向量，向量差分变异
CMA-ESHansen, 2001协方差矩阵自适应，连续优化最强之一

这张表里 CMA-ES 单独值得记一笔：它同属演化计算家族，却几乎不用交叉，而是维护一个多元正态采样分布、逐代从采样结果里估计协方差矩阵（等价于学出"哪些方向该走大步、哪些该走小步"）。下文"争议"一节会回到它——它正是把 GA 从连续优化主场挤出去的那个方法。

现场：NASA 的 ST5 演化天线

遗传算法在真实工程里最有说服力的一个案例，是 NASA 的 Space Technology 5（ST5）任务天线。

Gregory Hornby、Jason Lohn 与 Derek Linden 用两套演化算法自动设计这颗卫星的 X 波段天线：一套是实值参数向量（GA 风格，天线臂不允许分叉），另一套是树状生成式表示（遗传编程风格，允许分叉）。两套各自产出的最优天线都被真实制造并测试，结果都优于承包商手工设计的那一版。其中一个设计通过测试与审核，装上了三颗 ST5 卫星，于 2006 年 3 月 22 日发射升空。它是第一个被实际部署使用的计算机演化天线，也是第一个上天的计算机演化硬件。

演化出来的天线形状不像人会画的东西——不对称、弯折怪异，没有工程直觉能解释每一段为什么弯在那里。但这不是本案例最重要的部分。最重要的是后面发生的事：任务的轨道参数后来发生变更，天线的性能要求随之改变。团队做的事是调整适应度函数、重跑搜索，在不到一个月内演化出了一批满足新要求的新天线。

这才是该记住的判断：演化算法在这里的价值不是"设计得比人好"，而是把"设计"变成了一个可以重跑的计算过程。手工设计一旦需求变更，要重走一遍设计-仿真-评审的周期；而一个已经调好的适应度函数加一台机器，可以在需求变更后重新出发。这个性质在需求不稳定、评价标准可量化（这里是天线增益的仿真结果）的场景下极有价值——反过来说，适应度函数难以量化的场景，GA 就没有立足点。

应用

  • 电路与天线设计：上一节的 ST5 天线是最著名的案例；演化算法在模拟电路拓扑设计上也有长期应用。
  • 机器学习超参数优化与架构搜索（AutoML / NAS）：演化方法搜索神经网络架构与超参数空间。
  • 游戏与控制策略：演化控制器参数；OpenAI 用演化策略在 MuJoCo 与 Atari 上训练策略，其实现可扩展到一千个以上的并行工作节点，把 3D 人形行走任务压到 10 分钟内解决。
  • 生物信息学：蛋白质结构预测、分子对接优化。

失败现场：为 GA 量身定制的函数，反而输给了爬山

1992 年，Melanie Mitchell、Stephanie Forrest 与 John Holland 做了一件很有科学精神的事：他们设计了一族叫做"皇家大道"（Royal Road）的测试函数，目的就是构造出遗传算法应该最擅长的地形——函数由一组明确的短"积木块"组成，拼齐的积木越多得分越高，正是积木块假说描述的理想情况。预期是 GA 在这上面会大幅领先局部搜索方法。

结果反了。 一个极其朴素的随机变异爬山法（Random Mutation Hill Climbing, RMHC）——只保留单个当前解，随机翻一位，变好就接受、变差就丢——在这族函数上显著击败了 GA，差距达到数量级。

诊断出的主要原因叫"搭便车"（hitchhiking）：某个高阶积木块一旦在某个个体上首次出现，这个个体适应度很高，会被迅速复制满整个种群；而在复制的同时，这个个体在其他位置上那些无关甚至有害的取值也被一起带了过去。这些"搭便车"的 0 就此占住了那些位置，后来的积木块很难再在那里被发现——种群多样性在一次成功之后反而崩塌了。

这个结果的分量在于它的来源：做实验的人正是遗传算法的创立者本人和他的合作者，他们本来是要证明 GA 的优势。 后续二十多年里，"GA 什么时候真的会赢过爬山法"成了演化计算领域一个独立的研究问题（Mitchell 等人随后就以此为题写了专文），而不是一个可以假定的前提。

代价与争议

参数调优困难：种群大小、交叉率、变异率、选择策略——每个参数都显著影响结果，且对不同问题需要不同设置。

评估代价：每代需要评估整个种群的适应度。若适应度函数计算代价高（如模拟仿真），遗传算法可能极慢。ST5 天线那个案例之所以能成立，一部分原因就是天线增益可以靠电磁仿真自动打分。

早熟收敛（Premature Convergence）：种群多样性快速丧失，所有个体趋于相同，陷入局部最优。对策：增大变异率、引入迁移岛屿模型（Island Model）。上文"搭便车"现象是它的一种具体机制。

缺乏理论保障：和大多数元启发式算法一样，遗传算法没有收敛到全局最优的实际保证。

关于"没有免费的午餐"，通常被念错的那一句

"没有免费的午餐"定理（No Free Lunch, Wolpert & Macready, 1997）常被当作"所以任何算法都一样，选哪个无所谓"来引用。这是把它读反了。

定理说的是：在所有可能的目标函数上取平均，任意两个不重复采样的搜索算法期望性能完全相同。而"所有可能的目标函数"这个集合里，绝大多数是纯噪声——输入与输出之间没有任何可利用的结构。真实问题不是从这个集合里均匀抽出来的：它们有局部性、有平滑性、有可分解的结构。

所以定理的真正含义恰好相反：既然不存在普适的最优算法，那么一个算法的全部价值就在于它的归纳偏置与目标问题类的结构是否匹配。 问题不该是"GA 好不好"，而是"GA 假设了什么结构，我的问题有没有这种结构"。GA 假设的是"解可以被分解成若干可组合的片段，且这些片段在编码上彼此靠近"。皇家大道实验说明：即使这个假设成立，也不足以保证 GA 赢；而排列编码的 TSP 说明：假设不成立时连算子都得重写。

争议：GA 是不是已经被挤出主流

过去二十年，GA 在几个曾经的主场上被更专门的方法替代了，这是一个应当直说的事实：

  • 连续参数优化：这一块基本让给了 CMA-ES（协方差矩阵自适应演化策略）。它同属演化计算家族，但不靠交叉——它维护一个多元正态分布，从采样结果里估计出搜索方向与各方向的合适步长（即协方差矩阵），逐代更新。在非可分（变量间强耦合）的连续问题上，它是公认的强基线。
  • 超参数调优：主流转向了贝叶斯优化与基于多臂老虎机的资源分配。Hyperband（Li 等，JMLR 2018）的做法甚至更朴素——它不做"聪明的选点"，而是给随机采样的配置分配少量预算、把表现差的早停掉、把预算集中给活下来的，报告的加速超过一个数量级。相比 GA 一代一代把整个种群评估完，这类方法在"评估很贵"的场景下效率高得多。

但"被淘汰"是过头的说法，因为在几个具体场景里演化方法仍然占优：

  • 神经架构搜索：Real 等人在 AAAI 2019 上用正则化演化（在锦标赛选择里加入"年龄"属性，偏好较年轻的基因型）搜出的 AmoebaNet-A，是当时第一个超过人工设计的演化所得图像分类器；在与一个知名强化学习搜索方法的同硬件对照实验中，演化在搜索早期就更快达到同等结果。
  • 强化学习的黑箱替代：OpenAI 的演化策略（Salimans 等，2017）之所以有竞争力，不是因为样本效率更高，而是因为它几乎完美并行——每个工作节点只需回传一个标量，可扩展到一千个以上节点。这是"算法效率"输给"工程可扩展性"的一个反例。

综合起来的诚实表述是：遗传算法失去的是"通用默认优化器"这个位置，保住的是"目标函数是黑箱、不可微、评估可并行、且解具有可组合结构"这一块地盘。这与它在 1975 年被提出时的定位（对达尔文机制的一次通用计算模拟）已经不同——它没有被证伪，而是被限定了适用范围。这在算法史上是常态。

跨域连接

  • 达尔文：算法借走了变异与选择，却没带走三样东西：适应度由环境与同类共同决定并随时间改变（频率依赖），种群有空间结构与隔离，代与代之间没有整齐的边界。用一个固定的全局适应度函数替换这三者之后，它更像人工育种而非自然演化——育种者知道自己要什么，自然不知道。把算法结果当成演化论的证据是越界的。
  • 演化发育生物学：真实生物的基因型不直接等于表型，中间隔着发育，而发育带着强约束——同一处改动在不同阶段后果完全不同。遗传算法的编码解码是设计者写的直连映射，等于取消了这一层。这解释了它为什么对编码方式极端敏感：那份映射本该是被演化出来的，如今成了使用者的自由参数。
  • 自旋玻璃：适应度地形的崎岖程度可以被精确定义，自旋玻璃正是"大量相互竞争的耦合造出无数近乎简并的极小值"这类地形的可解模型。由此得到一条可用判断：地形若几乎处处平滑，梯度类方法完胜；若极小值密集且彼此隔着高势垒，任何单点搜索都会被困住，维持多样性才开始有意义。
  • 最优化：没有免费午餐说的是在所有可能目标函数上取平均时算法无差别，而那个集合里绝大多数是纯噪声。真实问题不是从那里均匀抽出来的，所以定理的正确读法是：算法的全部价值在于归纳偏置与问题结构是否匹配。这里假设的是"解可分解成若干可组合的片段且片段在编码上彼此靠近"——先检验这条，再谈调参。
  • 模拟退火：两者都用随机性，用法却不同。退火用温度控制接受劣解的概率，随机性是逃离局部极小的手段；这里的随机性主要落在交叉与选择上，指望的是片段重组。皇家大道实验的教训正在这里：维持种群本身不构成优势，多样性一旦崩塌，种群就退化成一个走得更慢的单点搜索。

参考文献

  • Holland, J. H. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.（第2版：MIT Press, 1992）
  • Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.（f(x)=x2f(x)=x^2 五位编码最小例子的出处）
  • Koza, J. R. Genetic Programming. MIT Press, 1992.
  • Wolpert, D. H. & Macready, W. G. "No Free Lunch Theorems for Optimization." IEEE Transactions on Evolutionary Computation 1(1), 67–82 (1997).
  • Mitchell, M., Forrest, S. & Holland, J. H. "The Royal Road for Genetic Algorithms: Fitness Landscapes and GA Performance." Proc. First European Conference on Artificial Life, MIT Press, 1992.（RMHC 击败 GA 与"搭便车"现象）
  • Hornby, G. S., Lohn, J. D. & Linden, D. S. "Computer-Automated Evolution of an X-Band Antenna for NASA's Space Technology 5 Mission." Evolutionary Computation 19(1), 1–23 (2011).
  • Hansen, N. & Ostermeier, A. "Completely Derandomized Self-Adaptation in Evolution Strategies." Evolutionary Computation 9(2), 159–195 (2001).（CMA-ES）
  • Real, E., Aggarwal, A., Huang, Y. & Le, Q. V. "Regularized Evolution for Image Classifier Architecture Search." AAAI 2019, 4780–4789. arXiv:1802.01548.
  • Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A. & Talwalkar, A. "Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization." Journal of Machine Learning Research 18, 1–52 (2018).
  • Salimans, T., Ho, J., Chen, X., Sidor, S. & Sutskever, I. "Evolution Strategies as a Scalable Alternative to Reinforcement Learning." arXiv:1703.03864, 2017.

延伸阅读

  • Mitchell, M. An Introduction to Genetic Algorithms. MIT Press, 1996.（皇家大道实验作者本人的教科书，对模式定理的局限讲得最坦诚）
  • Hansen, N. "The CMA Evolution Strategy: A Tutorial." arXiv:1604.00772, 2016.（CMA-ES 的标准入门）
  • Eiben, A. E. & Smith, J. E. Introduction to Evolutionary Computing. 2nd ed. Springer, 2015.（把 GA/ES/GP/DE 放进统一框架的教材）

正文中引用本条 · 6 · 其中 6 条来自其他领域

生命科学查尔斯·达尔文理查德·道金斯酶与生物催化：让不可能的反应在体温下发生自然选择：从达尔文到现代综合
化学酶催化
医学与公共卫生免疫系统