进化派 (Evolutionaries)

"If nature can do it, so can we." —— 进化派的方法论宣言

进化派 (Evolutionaries) 是 Domingos 在《主算法 (The Master Algorithm)》中划分的五大流派之一。他们的核心信念可以概括为：智能不是被设计出来的，而是被进化出来的。生物大脑是 35 亿年自然选择的产物，与其手工指定先验或假设解析形式，不如把"学习"本身定义为在假设空间中执行的遗传搜索 (genetic search)——以适应度 (fitness) 为压力，以变异 (variation) 为创新，以选择 (selection) 为筛选，让答案"自动浮现"。

进化派与符号派 (Symbolists)、连接派 (Connectionists)、贝叶斯派 (Bayesians)、类比派 (Analogizers) 并列为 Domingos 总结的"机器学习五大部落 (tribes)"。本目录系统整理进化派的算法谱系、理论基础与现代复兴路径，并与本笔记其他章节中关于"启发式搜索 (heuristic search)"、"强化学习 (reinforcement learning)"、"自动机器学习 (AutoML)"的内容形成交叉引用网络。

---

1. 派系画像

维度	进化派的回答
核心隐喻	自然选择 (natural selection)、生物进化
学习的本质	在假设空间中做并行随机搜索
知识的载体	染色体 (chromosome) / 基因型 (genotype)，可以是位串、实向量、树、图
主算法	遗传算法 (Genetic Algorithm, GA) 及其衍生族
数学武器	概率论、组合优化、随机过程
代表人物	John Holland、David Goldberg、John Koza、Hans-Paul Schwefel、Ingo Rechenberg、Kenneth Stanley
代表算法	GA、GP、ES、CMA-ES、NEAT、PSO、ACO、NAS
优势	黑箱优化、不可微目标、组合空间、多模态
劣势	样本效率低、收敛慢、超参敏感
现代代表场景	神经架构搜索 (NAS)、超参优化、机器人形态进化、符号回归

进化派区别于其他流派的最关键特征是：它不需要梯度信息。这使得它在不可微 (non-differentiable)、离散 (discrete)、欺骗性 (deceptive) 或带噪声的目标上具有结构性优势。

---

2. 主算法：遗传搜索循环

进化派的"主算法"骨架可以用一张极简的循环图表达——所有具体方法 (GA、ES、GP、NEAT 等) 都是这张骨架在编码 (encoding)、变异算子 (variation operator)、选择压力 (selection pressure) 三个轴上的特化。

flowchart TD
    A[初始化种群<br/>Population P_0] --> B[评估适应度<br/>Fitness f x_i]
    B --> C{终止条件?}
    C -- 否 --> D[选择父代<br/>Parent Selection]
    D --> E[变异 / 交叉<br/>Crossover & Mutation]
    E --> F[生成子代<br/>Offspring]
    F --> G[环境选择<br/>Survivor Selection]
    G --> H[精英保留<br/>Elitism]
    H --> B
    C -- 是 --> I[返回最优个体]

形式化地，给定假设空间 \(\mathcal{H}\) 与适应度函数 \(f: \mathcal{H} \to \mathbb{R}\)，进化算法维护一个种群 \(P_t = \{x_1, \dots, x_N\} \subset \mathcal{H}\)，并按下式迭代：

\[P_{t+1} = \mathcal{S}_{\text{env}}\big(P_t \cup \mathcal{V}(\mathcal{S}_{\text{par}}(P_t))\big)\]

其中 \(\mathcal{S}_{\text{par}}\) 是父代选择，\(\mathcal{V}\) 是变异/重组算子，\(\mathcal{S}_{\text{env}}\) 是环境选择。整个循环可以视为一个广义的 EM 过程：选择是 E 步 (推断哪些假设有希望)，变异是 M 步 (在希望区域附近生成新假设)。

---

3. 算法谱系图

下图给出进化派算法的家族关系。注意它并不是严格的时间线，而是思想继承图——某些分支 (如群体智能) 与主干 (GA / ES) 是平行发展、互相借鉴的。

flowchart LR
    GA[GA<br/>Holland 1975] --> GP[GP<br/>Koza 1992]
    GA --> NSGA[NSGA-II<br/>Deb 2002]
    GA --> MEM[Memetic Algorithms]
    ES[ES<br/>Rechenberg 1973] --> CMA[CMA-ES<br/>Hansen 2001]
    CMA --> NES[NES / xNES]
    NES --> OAIES[OpenAI ES<br/>Salimans 2017]
    GA --> NEAT[NEAT<br/>Stanley 2002]
    NEAT --> HYP[HyperNEAT<br/>Stanley 2009]
    HYP --> ESHYP[ES-HyperNEAT]
    PSO[PSO<br/>Kennedy 1995] --> SI[群体智能 SI]
    ACO[ACO<br/>Dorigo 1992] --> SI
    SI --> MOO[多模态 / 多目标]
    NEAT --> NE[神经进化 NE]
    OAIES --> NE
    NE --> NAS[神经架构搜索 NAS]
    GA --> AML[AutoML / HPO]
    NAS --> AML

主要分支说明：

• GA 系：Holland 起源，强调位串编码与 schema 定理；Goldberg 在 1989 年的教科书将其工程化推广。
• GP 系：Koza 把"程序"作为可进化对象，结构化变异作用在抽象语法树上。
• ES 系：Rechenberg/Schwefel 起源于流体力学优化，强调实数变量与自适应高斯扰动；CMA-ES 是该分支的现代王者。
• 群体智能：PSO、ACO、ABC、FA、CS 等，借鉴鸟群、蚁群、蜂群等生物集体行为。
• 神经进化：用进化方法搜索神经网络的权重和拓扑，NEAT/HyperNEAT 是里程碑。
• AutoML / NAS：进化思想在深度学习时代的复兴，与 RL、贝叶斯优化共同构成 NAS 三大方法论。

---

4. 与梯度优化的对比

进化算法常被误读为"梯度下降的退化版本"。事实上，它们有结构性的不同。

维度	梯度优化 (SGD/Adam)	进化算法 (EA)
是否需要梯度	必须可导	完全不需要
信号类型	一阶/二阶解析梯度	标量适应度 (fitness)
黑箱性	不接受黑箱	天然黑箱友好
并行度	受限于 mini-batch	极高 (整个种群可独立评估)
通信成本	梯度张量	仅传种子或少量标量
样本效率	高	低 (典型 \(10^4 \sim 10^6\) 次评估)
局部极小值	易陷入	种群多样性提供跳出能力
超参敏感性	学习率、动量等	种群规模、变异率、选择压力
适用场景	可导损失、大规模监督学习	不可导、离散、组合、强化学习黑箱
收敛保证	凸情形有界	仅渐近 (Markov 链平稳分布)

经验法则：当目标函数可微、维度高、有大量数据时，用 SGD；当目标黑箱、奖励稀疏、有大规模并行 CPU、关心鲁棒性时，进化算法仍是有竞争力的选择 (Salimans 等人 2017 在 Atari 上证实了这一点)。

---

5. 现代复兴：从冷门到主流

进化算法在 1990 年代曾因 SVM、Boosting、深度学习相继登场而进入相对沉寂的二十年。但 2015 年之后，它们在三个方向上强势回归：

第一波回归来自神经架构搜索 (NAS)。Real 等人在 2017—2019 年的 AmoebaNet 系列工作中，用大规模进化搜索得到了在 ImageNet 上超越人工设计的网络结构；后续的 Regularized Evolution (Real 2019) 用"年龄正则化"取代了传统的精英保留，被证明比当时基于强化学习的 NAS-RL (Zoph & Le 2017) 更稳定、更高效。第二波是 OpenAI ES (Salimans et al. 2017)：他们把进化策略当作"可扩展的强化学习替代方案"，在 1440 个 CPU 上跑 Atari 与 MuJoCo，达到了与 A3C 相当的得分，但训练时间更短、并行通信开销几乎为零。第三波是 AutoML 工业化：Optuna、NNI、AutoGluon、DEAP、pymoo 等框架把进化与贝叶斯优化、Hyperband 等方法封装为开箱即用的服务，使非专家也能用 EA 调超参。

这三波回归的共同推力来自硬件——廉价 CPU 集群让"评估几千个个体"从奢侈变成常规操作。进化派从此摆脱了"理论玩具"的标签，重新成为机器学习工程实践的一部分。

---

6. 子页导航

本目录下分三个主题深入：

• 遗传算法与遗传编程 —— GA 完整流程、编码方式、选择/交叉/变异算子、Schema 定理、GP 树进化、NSGA-II 多目标、经典案例
• 进化策略与神经进化 —— ES 起源、CMA-ES 完整算法、OpenAI ES、NEAT/HyperNEAT、神经进化 vs RL 决策树
• 群体智能与 AutoML —— PSO、ACO、ABC/FA/CS、AutoML 综述、HPO 方法对比、NAS 三大策略、工业框架

---

7. 与既有页面的分工

本目录与 ../../02_Symbolic_AI/1_search.md 的 §evolutionary 节有内容重叠，但视角与深度都不同：

维度	02_Symbolic_AI/1_search.md	本目录
上下文	经典搜索算法的一个分支	进化派整体哲学与算法生态
GA 介绍	浅介绍 (流程 + 一个例子)	完整流程、算子细节、Schema 定理推导
覆盖算法	仅 GA 主线	GA / GP / ES / CMA-ES / NEAT / PSO / ACO / NAS
对比维度	与 A* / 模拟退火比较	与梯度优化、贝叶斯优化、RL 比较
现代应用	简短提及	OpenAI ES、AmoebaNet、DARTS 详细叙事

阅读建议：如果你只想知道"GA 是什么"，读 1_search.md 即可；如果你要在工程上用进化方法、或想理解它在深度学习时代的位置，从本目录开始。

---

参考文献

• Domingos, P. (2015). The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World. Basic Books. —— 五大流派划分原书，第 5 章专门讨论进化派。
• Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. —— GA 与 schema 定理的奠基作。
• Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. —— GA 工程化教科书。
• Eiben, A. E., & Smith, J. E. (2015). Introduction to Evolutionary Computing (2nd ed.). Springer. —— 进化计算现代教材，覆盖 GA/ES/GP/SI 全谱。
• Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press.
• Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.
• Salimans, T., Ho, J., Chen, X., et al. (2017). Evolution Strategies as a Scalable Alternative to Reinforcement Learning. arXiv:1703.03864.
• Stanley, K. O., & Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2), 99–127.
• Real, E., Aggarwal, A., Huang, Y., & Le, Q. V. (2019). Regularized evolution for image classifier architecture search. AAAI.

---

遗传算法与遗传编程

本页深入展开遗传算法 (Genetic Algorithm, GA) 与遗传编程 (Genetic Programming, GP) 的算法细节、理论基础与工程实践。这两者构成进化派的"主干"——GA 提供了通用的位串/实数染色体进化框架，GP 把进化对象从向量推广到程序结构本身。

阅读本页前，建议先看 本页 §1（派系入口） 了解进化派整体定位；本页比 ../../02_Symbolic_AI/1_search.md 中的 §evolutionary 节更深、更技术化。

---

1. 遗传算法 GA 的完整流程

GA 由 John Holland 在 1975 年的 Adaptation in Natural and Artificial Systems 中正式提出。其核心思想：把候选解 (candidate solution) 编码为"染色体 (chromosome)"，用模拟自然选择的过程在解空间中并行搜索。

1.1 形式化定义

给定： - 假设空间 \(\mathcal{H}\) (解空间) - 编码函数 \(\phi: \mathcal{H} \to \mathcal{G}\)，将解映射到基因型空间 \(\mathcal{G}\) - 适应度函数 \(f: \mathcal{H} \to \mathbb{R}\) (越大越好)

GA 维护种群 \(P_t = \{g_1, \dots, g_N\} \subset \mathcal{G}\)，规模 \(N\) 通常在 \(50 \sim 500\) 之间。每一代 (generation) 执行：

flowchart TD
    A[初始化种群 P_0<br/>random or heuristic] --> B[解码并评估<br/>f x_i = f phi inverse g_i]
    B --> C{终止?<br/>maxGen / fitness target / no improve}
    C -- 否 --> D[父代选择<br/>roulette / tournament / rank]
    D --> E[交叉<br/>1pt / 2pt / uniform / SBX]
    E --> F[变异<br/>bitflip / Gaussian / polynomial]
    F --> G[评估子代]
    G --> H[环境选择<br/>generational / steady-state]
    H --> I[精英保留<br/>top-k 直接进入下一代]
    I --> B
    C -- 是 --> J[返回 best-so-far]

1.2 与一般搜索的关系

GA 可以视为带种群的随机束搜索 (stochastic beam search)，但有三个本质区别： 1. 多解并行：维护 \(N\) 个候选解，而非单一前沿。 2. 重组 (recombination)：交叉算子混合两个父代的信息——这是其他启发式搜索 (模拟退火、爬山) 没有的。 3. 隐式并行性 (implicit parallelism)：根据 schema 定理，每代实际上同时评估了 \(\mathcal{O}(N^3)\) 个 schema (见 §7)。

---

2. 编码方式

编码 (encoding / representation) 是 GA 设计中最关键的决策。错误的编码会让所有算子都失效。

编码方式	染色体形态	典型场景	对应交叉/变异
二进制 (binary)	\(\{0, 1\}^l\)	子集选择、布尔规则、组合优化	bit-flip mutation, 1-point/uniform crossover
实数 (real-valued)	\(\mathbb{R}^d\)	连续函数优化、神经网络权重	Gaussian mutation, BLX-α / SBX
排列 (permutation)	\(S_n\) 上的排列	TSP、调度、装配序列	order crossover (OX), PMX, swap mutation
树 (tree)	抽象语法树	GP 程序进化、符号回归	subtree crossover, point mutation
图 (graph)	节点+边	神经网络拓扑 (NEAT)、电路	NEAT-style add-node / add-link
灰码 (Gray code)	\(\{0,1\}^l\)	数值优化但避免 Hamming cliff	同二进制

Hamming cliff (汉明断崖)：标准二进制编码下相邻整数 (如 7 = 0111 与 8 = 1000) 的 Hamming 距离可能很大，单 bit-flip 跳不过去。Gray code 保证相邻整数 Hamming 距离恒为 1，是数值优化的常见技巧。

编码选择原则： - 完备性：每个合法解至少有一种编码。 - 非冗余性：编码与解尽量一一对应 (避免大量等价基因型)。 - 局部性 (locality)：基因型上的小变化对应表型 (phenotype) 上的小变化——否则变异变成"洗牌"。

---

3. 选择算子

选择算子决定了选择压力 (selection pressure)——高适应度个体相对低适应度个体的繁殖优势。压力过低 (近随机搜索) 收敛慢；压力过高 (只复制最优个体) 早熟收敛 (premature convergence)。

3.1 轮盘赌 Roulette Wheel

每个个体被选中的概率正比于其适应度： $\(p_i = \frac{f_i}{\sum_{j=1}^N f_j}\)$ 问题：当 \(f\) 取负值或量纲悬殊时崩溃；适应度尺度漂移 (scale drift) 时压力难控。

3.2 锦标赛 Tournament Selection

随机抽取 \(k\) 个个体，取适应度最高的作为父代。锦标赛规模 \(k\) 直接控制选择压力： - \(k=1\)：纯随机 - \(k=2\)：温和压力，最常用 - \(k=N\)：每次都选最优 (退化为 truncation selection)

锦标赛的期望选择压力 (takeover time)：在无变异、无交叉的极限下，\(k\)-tournament 让全种群收敛到最优个体所需代数约为 \(\mathcal{O}(\log N / \log k)\)。

3.3 排序选择 Rank-based

按适应度排序后赋概率，与具体 \(f\) 值无关。线性排序： $\(p_i = \frac{1}{N}\Big[\eta^- + (\eta^+ - \eta^-)\frac{i-1}{N-1}\Big]\)$ 其中 \(i\) 是排名 (1 最差，\(N\) 最好)，\(\eta^+ \in [1, 2]\) 控制压力，\(\eta^+ + \eta^- = 2\)。

3.4 Boltzmann 选择

模拟模拟退火，温度 \(T\) 随代数下降： $\(p_i \propto \exp(f_i / T)\)$ \(T\) 大时近均匀，\(T \to 0\) 时退化为贪心。可与模拟退火混合得到 GASA 类算法。

选择算子	压力可控性	计算开销	适应度尺度敏感
Roulette	难调	\(\mathcal{O}(N)\)	高度敏感
Tournament	易调 (\(k\))	\(\mathcal{O}(k)\)	不敏感
Rank	易调 (\(\eta^+\))	\(\mathcal{O}(N \log N)\) 排序	完全不敏感
Boltzmann	可调度 (\(T\))	\(\mathcal{O}(N)\)	敏感 (但 \(T\) 可缓解)

实践推荐：默认用 tournament (\(k=2\) 或 \(k=3\))——压力可控、对适应度尺度鲁棒、实现简单。

---

4. 交叉算子

交叉 (crossover, recombination) 是 GA 区别于其他随机搜索的核心创新：通过混合两个父代基因，期望"好的组件 (building block)"组合产生更好的子代。

4.1 单点交叉 1-point

随机选切点 \(c \in \{1, \dots, l-1\}\)，子代 1 = \(p_1[1:c] + p_2[c+1:l]\)，子代 2 反之。 问题：染色体头尾的基因更难分离 (positional bias)，离得远的基因不易共同遗传。

4.2 两点交叉 2-point

选两个切点，交换中段。缓解了单点的位置偏倚，是工程默认选择之一。

4.3 均匀交叉 Uniform

每个位置以概率 \(p\) (常 \(p=0.5\)) 独立从 \(p_1\) 或 \(p_2\) 继承。 - 优点：完全消除位置偏倚。 - 缺点：高度破坏长度大的 building block——只适合基因独立性强的问题。

4.4 模拟二进制交叉 SBX

实数 GA 的事实标准 (Deb & Agrawal 1995)。给定两父代实值 \(x_1, x_2\)，子代为： $\(c_{1,2} = 0.5 \big[(1 \mp \beta_q)(x_1) + (1 \pm \beta_q)(x_2)\big]\)$ 其中 \(\beta_q\) 由分布参数 \(\eta_c\) (典型 \(\eta_c \in [2, 5]\)) 控制： $\(\beta_q = \begin{cases}(2u)^{1/(\eta_c+1)} & u \le 0.5 \\ (1/(2(1-u)))^{1/(\eta_c+1)} & u > 0.5\end{cases}, \quad u \sim \mathcal{U}[0,1]\)$ SBX 的关键性质：子代分布以父代为中心、\(\eta_c\) 越大子代越靠近父代——模拟了二进制单点交叉在实数域的"局部性"。

---

5. 变异算子

变异 (mutation) 提供探索 (exploration)——把种群推到当前未覆盖的区域，防止早熟。

5.1 Bit-flip (二进制)

每位以概率 \(p_m\) (典型 \(1/l\)，使期望每染色体翻 1 位) 独立翻转。

5.2 高斯变异 Gaussian (实数)

\(x_i \leftarrow x_i + \mathcal{N}(0, \sigma_i^2)\)。\(\sigma_i\) 可全局共享、按维度独立、或自适应 (这就过渡到 ES，见 进化策略与神经进化)。

5.3 多项式变异 Polynomial Mutation

Deb 提出的实数 GA 标准变异。给定边界 \([x^L, x^U]\) 与分布参数 \(\eta_m\) (典型 \(20\))： $\(x_i' = x_i + (x^U - x^L)\delta, \quad \delta = \begin{cases}(2u)^{1/(\eta_m+1)} - 1 & u < 0.5 \\ 1 - (2(1-u))^{1/(\eta_m+1)} & u \ge 0.5\end{cases}\)$ \(\eta_m\) 越大变异越保守。

5.4 自适应变异

记录每个体的变异率 \(p_m^{(i)}\) 作为额外基因，让其自身参与进化——成功的 \(p_m\) 会被选择保留。这是连接 GA 与 ES 的桥梁。

---

6. 精英保留与多样性保护

6.1 精英保留 Elitism

每代直接复制 top-\(k\) 个体到下一代，保证 best-so-far 单调不降。\(k\) 通常是种群规模的 \(1\% \sim 10\%\)。\(k\) 过大会失去多样性，过小则无法保护好解。

6.2 多样性危机

无任何保护时，GA 倾向于早熟收敛——种群迅速塌缩到第一个发现的局部最优周围。两种主流解法：

Fitness sharing (Goldberg & Richardson 1987)：让相近个体互相"分享"适应度，模拟生态位竞争。 $\(f'_i = \frac{f_i}{\sum_{j=1}^N \mathrm{sh}(d_{ij})}, \quad \mathrm{sh}(d) = \max\Big(0,\ 1 - (d/\sigma_{\text{share}})^\alpha\Big)\)$

Crowding (De Jong 1975)：子代只与其最相似的父代竞争生存，从而保护不同生态位。

Island model (孤岛模型)：把种群分成 \(K\) 个孤立子种群，偶尔迁移 (migration)。天然适合分布式实现。

---

7. Schema 定理 (Holland 1975)

Schema 定理是 GA 唯一的经典理论保证。它把 GA 的"隐式并行性"形式化。

7.1 Schema 的定义

Schema (模式) 是定义在字母表 \(\{0, 1, *\}^l\) 上的字符串，\(*\) 表示通配。例如 \(H = 1\!*\!*\!0\!*\) 表示所有"第 1 位为 1、第 4 位为 0"的位串集合 (在 \(l=5\) 时含 \(2^3 = 8\) 个字符串)。

两个关键属性： - 阶 (order) \(o(H)\)：\(H\) 中固定位 (非 \(*\)) 的数量。例 \(o(1\!*\!*\!0\!*) = 2\)。 - 定义长度 (defining length) \(\delta(H)\)：第一个固定位与最后一个固定位的距离。例 \(\delta(1\!*\!*\!0\!*) = 4 - 1 = 3\)。

7.2 定理陈述

记 \(m(H, t)\) 为第 \(t\) 代种群中匹配 schema \(H\) 的个体数，\(f(H)\) 为这些个体的平均适应度，\(\bar f\) 为种群平均适应度，\(p_c, p_m\) 分别为交叉与变异概率，\(l\) 为染色体长度。在轮盘赌选择 + 单点交叉 + bit-flip 变异下：

\[m(H, t+1) \geq m(H, t) \cdot \frac{f(H)}{\bar f} \cdot \left[1 - p_c \frac{\delta(H)}{l-1} - o(H)\, p_m\right]\]

7.3 逐项解释

• \(\frac{f(H)}{\bar f}\)：选择压力项。如果 schema \(H\) 优于平均水平 (\(f(H) > \bar f\))，它会被选择性放大。
• \(1 - p_c \frac{\delta(H)}{l-1}\)：交叉破坏项。schema 跨度 \(\delta(H)\) 越大，越容易被单点切开破坏。
• \(1 - o(H) p_m\)：变异破坏项。schema 阶 \(o(H)\) 越大，越多固定位面临变异破坏。

7.4 推论：Building Block Hypothesis

短的 (small \(\delta\))、低阶的 (small \(o\))、高于平均适应度的 schema——称为积木块 (building blocks)——会以指数速率增长。GA 通过重组积木块构造越来越大的好解。这就是 Holland 与 Goldberg 主张的"GA 之所以能工作"的解释。

7.5 Linkage Problem

building block 假说有一个隐含前提：相关基因在染色体上要排得近。否则交叉概率 \(p_c \delta(H)/(l-1)\) 会反复破坏它们。这就是 linkage problem (连锁问题)。

解决思路： - 手工编码：领域知识把相关基因排近。 - mGA / fmGA (messy GA)：让 GA 自己学连锁结构。 - EDA (Estimation of Distribution Algorithms)：跳过显式交叉，直接学种群的概率模型 (BOA、UMDA 等)，从分布中采样新一代。

Schema 定理给出的是必要而非充分条件。它解释"GA 在何种条件下能工作"，但不能保证 GA 一定收敛到全局最优。这与 SGD 的凸优化收敛证明性质不同。

---

8. 遗传编程 GP

遗传编程 (Genetic Programming, GP) 由 John Koza 在 1992 年提出。它把进化对象从位串/实向量推广到计算机程序——具体地，是表示程序的抽象语法树 (AST)。

8.1 函数集与终端集

GP 程序由两类节点组成：

节点类型	角色	示例
函数集 (Function Set)	内部节点	\(\{+, -, \times, /, \sin, \cos, \mathrm{if}, \mathrm{and}\}\)
终端集 (Terminal Set)	叶节点	\(\{x_1, x_2, \dots, c_1, c_2, \dots\}\)

Closure 性质：函数集中任意函数对终端集与其他函数的输出都必须有定义——例如 \(/\) 必须处理除零 (常用 protected division: \(x/y = 1\) if \(y=0\))。

Sufficiency 性质：函数集与终端集的组合空间必须包含目标程序。

8.2 树状交叉与变异

flowchart LR
    subgraph P1["父代 1: x*x+sin x"]
        A1["+"] --> B1["*"]
        A1 --> C1["sin"]
        B1 --> D1["x"]
        B1 --> E1["x"]
        C1 --> F1["x"]
    end
    subgraph P2["父代 2: x+1 / 2"]
        A2["/"] --> B2["+"]
        A2 --> C2["2"]
        B2 --> D2["x"]
        B2 --> E2["1"]
    end
    subgraph C["子代 (在 sin 子树与 x+1 子树处交换)"]
        AC["+"] --> BC["*"]
        AC --> CC["+"]
        BC --> DC["x"]
        BC --> EC["x"]
        CC --> FC["x"]
        CC --> GC["1"]
    end

子树交叉 (subtree crossover)：随机选每个父代的一个子树交换。这是 GP 的标准重组算子。

点变异 (point mutation)：用同元数 (arity) 的另一函数替换某节点；或用同类型的另一终端替换叶节点。

子树变异 (subtree mutation)：删掉一个子树，原地长一棵随机新子树。

8.3 Bloat 与控制

Bloat (膨胀) 是 GP 最棘手的现象：树规模随代数无节制增长，但适应度并不相应提升。原因之一是"中性变异"——不影响输出的代码 (introns) 在交叉中提供保护，因此被选择性保留。

控制手段：

• Depth limit：硬限制树深度。简单暴力，但有效。
• Parsimony pressure (节俭压力)：在适应度中加入复杂度惩罚 \(f' = f - \alpha \cdot \text{size}(\text{tree})\)。
• Tarpeian method：以一定概率把超过阈值的个体直接判死。
• Operator equalization：维护各 size bin 的固定配额。

8.4 经典应用

• 符号回归 (symbolic regression)：在数据 \(\{(x_i, y_i)\}\) 上进化函数 \(f\) 使 \(\sum (f(x_i) - y_i)^2\) 最小。Eureqa / PySR 是这一方向的现代代表。
• 分类规则进化：演化决策列表或 if-then 规则。
• 电路设计：Koza 团队用 GP 重新发明了多项已申请专利的模拟电路 (low-pass filter、放大器拓扑)，被称为 "human-competitive results"。
• 博弈策略：进化棋类启发式 / 扑克策略。

---

9. 多目标进化算法：NSGA-II

现实问题常有相互冲突的目标 (准确率 vs 模型大小、产能 vs 成本)。多目标优化 (Multi-Objective Optimization, MOO) 的目标不是单一最优解，而是 Pareto 前沿 (Pareto front)。

Pareto 支配 (dominance)：解 \(a\) 支配 \(b\) 当且仅当 \(a\) 在所有目标上不差于 \(b\) 且至少有一个严格优于。Pareto 前沿是所有不被任何解支配的解的集合。

NSGA-II (Deb et al. 2002) 是 MOO 领域被引最多的算法之一，核心机制：

1. Fast non-dominated sorting：把种群按支配关系分层 (\(F_1\) 是当前 Pareto 前沿，\(F_2\) 是去掉 \(F_1\) 后的前沿，依此类推)。复杂度 \(\mathcal{O}(MN^2)\)。
2. Crowding distance：每层内部按"邻域稀疏度"排序，鼓励解在前沿上均匀分布。
3. Selection：先比层数 (低层优)，同层比 crowding distance (大者优)。
4. 环境选择：父+子合并后取 top-\(N\)。

NSGA-II 在 NAS、超参优化、机器学习模型权衡中被广泛使用 (例 NSGA-Net 直接搜模型族的 Pareto 前沿)。

---

10. 实例

10.1 0/1 背包问题

物品集 \(\{(w_i, v_i)\}_{i=1}^n\)，容量 \(W\)。 - 编码：二进制位串 \(x \in \{0,1\}^n\)，\(x_i=1\) 表示装入第 \(i\) 个。 - 适应度：\(f(x) = \sum v_i x_i\) 若 \(\sum w_i x_i \le W\)，否则给重罚 \(f = -\infty\) 或 \(f = -\sum w_i x_i\)。 - 算子：1-point crossover + bit-flip。 - 典型表现：100 物品、200 种群、500 代可逼近最优 95%+。

10.2 TSP

\(n\) 城市访问问题。 - 编码：排列 \(\pi \in S_n\)。 - 适应度：\(f(\pi) = -\sum d(\pi_i, \pi_{i+1})\)。 - 算子：order crossover (OX) 或 PMX；2-opt 局部搜索做 hybrid (memetic algorithm)。

10.3 符号回归

数据 \(\{(x_i, y_i)\}\)，目标找 \(f\)。 - GP 树编码，函数集 \(\{+, -, \times, /, \sin, \exp, \log\}\) (protected)。 - 适应度：\(-\mathrm{MSE}(f, \text{data})\)，可加 parsimony 惩罚。 - 现代实践：PySR (Cranmer 2023) 与 Eureqa 把 GP 与符号简化结合，成功在物理学方程发现 (Feynman 数据集) 上重现已知公式。

---

11. Python 实现示例 (DEAP 风格)

下面给出一个最小可运行的 GA 主循环，用于在 \(f(x) = \sum_{i=1}^{20} x_i^2\) (即 OneMax 的取反) 上演示二进制 GA。

import random
from typing import List, Tuple

POP_SIZE = 100
CHROM_LEN = 20
P_CROSS = 0.9
P_MUT = 1.0 / CHROM_LEN
GENERATIONS = 50
TOURN_K = 3

Chrom = List[int]

def fitness(c: Chrom) -> int:
    return sum(c)  # OneMax: 越多 1 越好

def tournament(pop: List[Chrom]) -> Chrom:
    contestants = random.sample(pop, TOURN_K)
    return max(contestants, key=fitness)

def one_point_crossover(p1: Chrom, p2: Chrom) -> Tuple[Chrom, Chrom]:
    if random.random() >= P_CROSS:
        return p1[:], p2[:]
    cut = random.randint(1, CHROM_LEN - 1)
    return p1[:cut] + p2[cut:], p2[:cut] + p1[cut:]

def bitflip_mutation(c: Chrom) -> Chrom:
    return [1 - g if random.random() < P_MUT else g for g in c]

def init_population() -> List[Chrom]:
    return [[random.randint(0, 1) for _ in range(CHROM_LEN)]
            for _ in range(POP_SIZE)]

def run_ga():
    pop = init_population()
    best = max(pop, key=fitness)
    for gen in range(GENERATIONS):
        new_pop = [best]  # 1-elitism
        while len(new_pop) < POP_SIZE:
            p1, p2 = tournament(pop), tournament(pop)
            c1, c2 = one_point_crossover(p1, p2)
            new_pop.append(bitflip_mutation(c1))
            if len(new_pop) < POP_SIZE:
                new_pop.append(bitflip_mutation(c2))
        pop = new_pop
        cur_best = max(pop, key=fitness)
        if fitness(cur_best) > fitness(best):
            best = cur_best
        print(f"Gen {gen:3d}  best={fitness(best)}  avg={sum(map(fitness,pop))/POP_SIZE:.2f}")
    return best

if __name__ == "__main__":
    run_ga()

工程上更推荐直接用 DEAP (creator + tools + algorithms.eaSimple)、pymoo (多目标优先)、或 PyGAD (轻量、对接 sklearn / Keras)。

---

12. 调参与陷阱

超参	典型范围	调参直觉
种群规模 \(N\)	\(50 \sim 500\)	维度高、多模态 → 大；评估贵 → 小
交叉概率 \(p_c\)	\(0.6 \sim 0.95\)	通常较高，让重组主导
变异概率 \(p_m\)	\(1/l \sim 5/l\)	太低无探索，太高变随机搜索
锦标赛规模 \(k\)	\(2 \sim 5\)	大 → 强压力 → 易早熟
精英比例	\(1\% \sim 10\%\)	太大失多样性
最大代数	\(10^2 \sim 10^4\)	加 early stopping

常见陷阱： 1. 适应度尺度悬殊 → 用 rank/tournament 替换 roulette。 2. 早熟收敛 → 加 fitness sharing / 增大变异率 / 用孤岛模型。 3. 评估太慢 → 用代理模型 (surrogate) 或缓存重复个体。 4. GP bloat → 加 depth limit + parsimony pressure。 5. 离散约束 → 用修复算子 (repair operator) 而不是惩罚函数 (penalty)。

---

13. 交叉引用

• 父页：本页 §1（派系入口） —— 进化派整体定位与算法谱系
• 同目录：进化策略与神经进化 —— ES/CMA-ES/NEAT 是 GA 的连续/拓扑推广
• 同目录：群体智能与 AutoML —— PSO/ACO/NAS 与 GA 的对比
• 既有页：../../02_Symbolic_AI/1_search.md §evolutionary —— GA 作为启发式搜索的视角
• 相关页：贝叶斯派的 BOHB / TPE 是 HPO 中 GA 的有力竞争者，见 贝叶斯派

---

参考文献

• Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. —— GA 与 schema 定理原始文献。
• Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. —— GA 工程化教科书。
• Goldberg, D. E., & Richardson, J. (1987). Genetic algorithms with sharing for multimodal function optimization. ICGA.
• De Jong, K. A. (1975). An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan.
• Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press.
• Koza, J. R. (1994). Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press.
• Deb, K., & Agrawal, R. B. (1995). Simulated binary crossover for continuous search space. Complex Systems, 9, 115–148.
• Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
• Eiben, A. E., & Smith, J. E. (2015). Introduction to Evolutionary Computing (2nd ed.). Springer.
• Cranmer, M. (2023). Interpretable machine learning for science with PySR and SymbolicRegression.jl. arXiv:2305.01582.
• Fortin, F.-A., et al. (2012). DEAP: Evolutionary algorithms made easy. JMLR, 13, 2171–2175.

---

进化策略与神经进化

本页深入讨论进化派在连续优化与神经网络进化两个方向的代表性算法：进化策略 (Evolution Strategies, ES)、协方差矩阵自适应 ES (CMA-ES)、OpenAI ES、NEAT、HyperNEAT。这些方法的共同特征是把"变异"作为主要进化算子 (相对于 GA 的"交叉为主")，并在变异分布上做大量自适应工作。

阅读本页前推荐先看 本页 §1（派系入口） 与 遗传算法与遗传编程，理解 GA 的基本术语。

---

1. 进化策略的起源

进化策略 (ES) 由 Ingo Rechenberg 与 Hans-Paul Schwefel 在 1960 年代后期于柏林技术大学独立于 Holland 的 GA 发展起来。最早的应用场景是风洞翼型优化——目标连续、不可解析微分、评估昂贵。

ES 与 GA 的核心差异：

维度	GA (Holland)	ES (Rechenberg/Schwefel)
起源	自适应系统理论	工程优化 (流体力学)
染色体	二进制位串为主	实数向量为主
主算子	交叉	变异
选择	适应度比例选择	截断选择 (\(\mu\) 选 \(\lambda\))
自适应	变异率手调	变异步长 \(\sigma\) 自适应
理论	Schema 定理	1/5 成功率规则、IGO/自然梯度

---

2. 经典 ES 变体

2.1 (1+1)-ES：最小工作模型

种群只有一个个体 \(\theta_t \in \mathbb{R}^d\)，每代生成一个变异后代： $\(\theta'_t = \theta_t + \sigma_t \cdot \mathbf{z}, \quad \mathbf{z} \sim \mathcal{N}(0, I_d)\)$ 若 \(f(\theta'_t) \ge f(\theta_t)\)，则 \(\theta_{t+1} = \theta'_t\)，否则保留 \(\theta_t\)。

2.2 (\(\mu\), \(\lambda\))-ES vs (\(\mu\) + \(\lambda\))-ES

• (\(\mu\), \(\lambda\))：\(\mu\) 父代生成 \(\lambda > \mu\) 子代，只在子代中选 \(\mu\) 个进入下一代——父代不参与，强制更新。
• (\(\mu\) + \(\lambda\))：父子合并取 top-\(\mu\)，单调不降。

实践中 (\(\mu\), \(\lambda\)) 更常用——它在自适应步长场景下避免"陈旧 \(\sigma\) 拖累 \(\theta\)"的问题。典型比例 \(\lambda / \mu \approx 4 \sim 7\)。

2.3 1/5 成功率规则 (Rechenberg 1973)

\(\sigma\) 太小则收敛慢；\(\sigma\) 太大则成功率低。Rechenberg 的经验法则：目标成功率 \(\approx 1/5\)。 - 若最近若干代成功率 \(> 1/5\) → \(\sigma \leftarrow \sigma / c\) (放大步长，\(c \in (0.8, 1)\)) - 若 \(< 1/5\) → \(\sigma \leftarrow \sigma \cdot c\) - 若 \(\approx 1/5\) → 保持

这是历史上第一个自适应步长的进化算法机制。它在球面函数上有理论支撑 (源自渐近收敛速率分析)，是后续 CMA-ES、xNES 等算法的思想根基。

---

3. CMA-ES：进化策略的现代王者

Covariance Matrix Adaptation Evolution Strategy (CMA-ES) 由 Nikolaus Hansen 与 Andreas Ostermeier 在 1996—2001 年发展，被广泛认为是当今最强的黑箱连续优化算法之一。在 BBOB (Black-Box Optimization Benchmark) 等基准上长期处于第一梯队。

3.1 算法骨架

CMA-ES 在每一代用一个多元高斯分布采样 \(\lambda\) 个候选解： $\(\mathbf{x}_i^{(g+1)} \sim \mathbf{m}^{(g)} + \sigma^{(g)} \mathcal{N}(\mathbf{0}, \mathbf{C}^{(g)}), \quad i=1,\dots,\lambda\)$

其中： - \(\mathbf{m}^{(g)} \in \mathbb{R}^d\)：分布均值 (当前最佳估计) - \(\sigma^{(g)} \in \mathbb{R}_+\)：全局步长 (overall step size) - \(\mathbf{C}^{(g)} \in \mathbb{R}^{d \times d}\)：协方差矩阵 (形状/尺度先验)

每代评估后，从 \(\lambda\) 个子代中选 top-\(\mu\) 更新 \(\mathbf{m}, \sigma, \mathbf{C}\)。CMA-ES 的精髓全在于这三个量怎么自适应更新。

3.2 均值更新

$\(\mathbf{m}^{(g+1)} = \sum_{i=1}^\mu w_i\, \mathbf{x}_{i:\lambda}^{(g+1)}, \quad \sum w_i = 1,\ w_1 \ge \dots \ge w_\mu \ge 0\)$ \(\mathbf{x}_{i:\lambda}\) 是按适应度排序后第 \(i\) 个子代。权重 \(w_i\) 通常按对数衰减。\(\mu_{\mathrm{eff}} = 1/\sum w_i^2\) 称作有效选择质量。

3.3 协方差矩阵更新：rank-1 与 rank-\(\mu\)

rank-\(\mu\) 更新：从本代 top-\(\mu\) 子代估计协方差， $\(\mathbf{C}_\mu^{(g+1)} = \sum_{i=1}^\mu w_i (\mathbf{x}_{i:\lambda} - \mathbf{m}^{(g)})(\mathbf{x}_{i:\lambda} - \mathbf{m}^{(g)})^\top / \sigma^{(g)2}\)$ 但单代样本太少，估计噪声大。

rank-1 更新：用进化路径 (evolution path) \(\mathbf{p}_c\) 累积多代位移信息： $\(\mathbf{p}_c^{(g+1)} = (1-c_c)\mathbf{p}_c^{(g)} + \sqrt{c_c(2-c_c)\mu_{\mathrm{eff}}} \cdot \frac{\mathbf{m}^{(g+1)} - \mathbf{m}^{(g)}}{\sigma^{(g)}}\)$ $\(\mathbf{C}^{(g+1)} = (1-c_1-c_\mu)\mathbf{C}^{(g)} + c_1\mathbf{p}_c\mathbf{p}_c^\top + c_\mu \mathbf{C}_\mu^{(g+1)}\)$

直觉：若连续多代均值都朝同一方向移动，路径 \(\mathbf{p}_c\) 长度大，CMA-ES 把这个方向"刻入"协方差，未来采样更倾向这个方向——形成长程相关性的捕获。

3.4 全局步长控制 (CSA)

类似地维护共轭进化路径 (conjugate evolution path) \(\mathbf{p}_\sigma\)： $\(\mathbf{p}_\sigma^{(g+1)} = (1-c_\sigma)\mathbf{p}_\sigma^{(g)} + \sqrt{c_\sigma(2-c_\sigma)\mu_{\mathrm{eff}}}\cdot \mathbf{C}^{(g)\,-1/2} \frac{\mathbf{m}^{(g+1)}-\mathbf{m}^{(g)}}{\sigma^{(g)}}\)$ $\(\sigma^{(g+1)} = \sigma^{(g)} \exp\!\left(\frac{c_\sigma}{d_\sigma}\left(\frac{\|\mathbf{p}_\sigma\|}{E\|\mathcal{N}(0,I)\|}-1\right)\right)\)$

直觉：若连续多步几乎共线 (路径长)，说明 \(\sigma\) 偏小 → 增大；若互相抵消 (路径短)，说明 \(\sigma\) 太大 → 减小。这是 1/5 规则的连续/各向异性推广。

3.5 与自然梯度的关系：IGO 框架

Wierstra 等人 (2014) 在 NES 论文中证明：CMA-ES 在某种参数化下可以解释为搜索分布参数空间上的自然梯度上升——其中 Fisher 信息度量自动产生了 rank-1/rank-\(\mu\) 更新的形式。Ollivier 等人 (2017) 的 Information-Geometric Optimization (IGO) 框架进一步把整族进化算法 (CMA-ES, xNES, PBIL, EDA) 统一为同一个参数空间上的信息几何流。

工程要点：CMA-ES 的"魔法"几乎全部由 Fisher 几何决定。它的"超参"很少需要调——库的默认值在 80% 场景下直接可用。

3.6 适用规模

• 维度 \(d \le 100\)：标准 CMA-ES 完全胜任。
• \(d \in [100, 1000]\)：用 sep-CMA-ES (对角协方差) 或 LM-CMA-ES (低秩近似)。
• \(d > 1000\)：协方差矩阵 \(\mathcal{O}(d^2)\) 内存崩盘——切换到 NES 变体或 OpenAI ES 类仅高斯各向同性扰动的简化方案。

---

4. ES 的现代视角：作为黑箱优化器

把 ES 看成"模拟退火 + 自适应方差 + 多采样"是合理的工程图景。它的几个工程优势：

1. 零阶 (zeroth-order)：只需 \(f(\theta)\)，不需要 \(\nabla f\)。
2. 可并行：\(\lambda\) 个子代独立评估。
3. 不变性 (invariance)：CMA-ES 对适应度的单调变换不变 (只用 ranking)，对线性变换不变 (协方差自适应)——这两点让它在病态尺度问题上比 SGD 更鲁棒。
4. 不依赖反向传播：评估器可以是模拟器、真实机器人、人类打分。

---

5. OpenAI ES：把 ES 推到大规模 RL

Salimans, Ho, Chen, Sidor (OpenAI, 2017) 的论文《Evolution Strategies as a Scalable Alternative to Reinforcement Learning》是 ES 在深度学习时代复兴的标志事件。

5.1 算法

参数 \(\theta \in \mathbb{R}^d\) (整个神经网络的展平向量)。每一步：

1. 采样 \(n\) 个高斯扰动 \(\epsilon_1, \dots, \epsilon_n \sim \mathcal{N}(0, I)\)。
2. 评估 \(F_i = F(\theta + \sigma \epsilon_i)\) (在环境上 rollout 一回合的回报)。
3. 估计梯度并更新： $\(\nabla_\theta \mathbb{E}_{\epsilon}[F(\theta + \sigma\epsilon)] \approx \frac{1}{n\sigma}\sum_{i=1}^n F_i\, \epsilon_i\)$ $\(\theta \leftarrow \theta + \alpha \cdot \frac{1}{n\sigma}\sum_{i=1}^n F_i\, \epsilon_i\)$

这其实就是 NES (Natural Evolution Strategies) 的固定方差版本——一个在 \(\theta\) 上做的 score-function gradient (REINFORCE 类) 估计。

5.2 工程关键创新：种子通信

数千 CPU 工人 (worker) 之间的通信成本是大规模 ES 的瓶颈。OpenAI 的 trick：所有 worker 持有同一个 RNG seed 表，通信只需广播 \((i, F_i)\) 二元组——每个 worker 自己用 seed \(i\) 重生成 \(\epsilon_i\)。这把通信量从 \(\mathcal{O}(d)\) 砍到 \(\mathcal{O}(1)\)。

5.3 ES vs PPO 对比

维度	OpenAI ES	PPO / A3C
信号	整回合标量回报	逐步骤 advantage
梯度	有限差分估计	反向传播解析梯度
样本效率	低 (\(10^7 \sim 10^9\) frames)	高 (\(10^6 \sim 10^8\))
时间效率 (墙钟)	快 (CPU 易并行)	受 GPU/数据效率限制
通信	每步 \(\mathcal{O}(1)\)	每步梯度 \(\mathcal{O}(d)\)
探索	参数空间扰动	动作空间随机性
对稀疏奖励	鲁棒 (回合级回报)	较脆弱
对超长 horizon	鲁棒	credit assignment 难
实现复杂度	极简 (~50 行)	中等 (replay/clipping/GAE)

OpenAI 在 1440 CPU 上跑 Atari 达到了与 A3C 接近的得分，墙钟时间反而更短。结论：在大规模并行可用、奖励稀疏、长 horizon 场景下，ES 是 RL 的强力替代。

---

6. NEAT：拓扑与权重协同进化

NeuroEvolution of Augmenting Topologies (NEAT) 由 Kenneth Stanley 与 Risto Miikkulainen 在 2002 年提出。它解决了进化神经网络拓扑长期难以工程化的三个核心问题：竞争对齐 (competing conventions)、初始爆炸、好结构早夭。

6.1 三大创新

(1) Innovation Number (历史标记)：每条新增连接被分配一个全局递增的 ID。两条连接是否"同源 (homologous)"由 ID 决定，而非由网络结构对齐——彻底解决了拓扑交叉的对齐难题。

(2) Speciation (物种保护)：把种群按结构距离划分物种 (species)。距离公式： $\(\delta = \frac{c_1 E}{N} + \frac{c_2 D}{N} + c_3 \bar{W}\)$ 其中 \(E\) = excess genes (一方拥有、另一方完全没有的基因)，\(D\) = disjoint genes (中间不匹配)，\(\bar W\) = 共享基因的权重平均差。\(\delta < \delta_t\) 视为同种。

Explicit fitness sharing：物种内适应度被均分 (\(f_i' = f_i / |S|\))，让小物种 (新拓扑) 不被大物种淹没——是"渐进式复杂化"的核心保护机制。

(3) 渐进式复杂化 (complexification)：从最小拓扑 (输入直连输出) 开始，只通过 add-node / add-link 变异单调增加结构复杂度。这避免了"先复杂化再剪枝"的浪费。

6.2 NEAT 的 speciation 流程

flowchart TD
    A[新一代子代生成] --> B[对每个个体]
    B --> C{与现有物种<br/>代表的 delta 距离}
    C -- delta < delta_t --> D[加入该物种]
    C -- 所有物种都不匹配 --> E[创建新物种<br/>该个体作代表]
    D --> F[物种内适应度共享<br/>f_i divide |S|]
    E --> F
    F --> G[按物种调整<br/>分配繁殖配额]
    G --> H[淘汰长期停滞物种]
    H --> I[下一代选择 / 变异]

6.3 NEAT 的应用

• OpenAI Gym 控制任务：CartPole、Pendulum 上 NEAT 在数百代内逼近最优。
• MarI/O：YouTuber SethBling 用 NEAT 玩超级马里奥兄弟，在公众科普上影响力极大。
• 机器人控制：连续控制下与传统 RL 竞争。

---

7. HyperNEAT：间接编码与几何先验

直接编码 (NEAT) 在百万参数神经网络上不可扩展——每个连接都要单独表示。HyperNEAT (Stanley, D'Ambrosio, Gauci 2009) 用间接编码 (indirect encoding) 解决这个问题。

7.1 CPPN：模式产生网络

Compositional Pattern Producing Network (CPPN) 是一个普通神经网络，但其"任务"不是分类——而是产生其他神经网络的连接权重。具体地，对目标网络中每对神经元 \((u, v)\)，它们的位置 \((x_u, y_u, x_v, y_v)\) 输入 CPPN，CPPN 输出连接权重 \(w_{uv}\)： $\(w_{uv} = \mathrm{CPPN}(x_u, y_u, x_v, y_v)\)$

CPPN 用 NEAT 进化 (它本身也是一个神经网络)，激活函数集除了 sigmoid 还有 sin / Gaussian / abs——这些函数族有助于产生对称、重复、梯度等几何模式。

7.2 几何先验

HyperNEAT 的核心洞察：真实问题中神经网络的连接模式往往有几何结构 (视网膜→V1 的 retinotopic mapping、运动皮层的躯体地图等)。把神经元放在几何坐标空间里、让 CPPN 学坐标到权重的映射，相当于强加了"相邻神经元应有相关权重"这种位置归纳偏置 (positional inductive bias)。

7.3 后续发展

• ES-HyperNEAT (Risi & Stanley 2010)：让 CPPN 自己决定放多少神经元、放在哪——不再固定 substrate。
• Adaptive HyperNEAT：把学习率也作为 CPPN 的输出之一。
• 这一族思想与现代深度学习的 HyperNetwork (Ha et al. 2016) 直接相通——一个神经网络生成另一个神经网络的权重。

---

8. 神经进化 vs 强化学习：何时选哪个

flowchart TD
    A[决策起点] --> B{奖励是否稠密<br/>每步可观测?}
    B -- 否 / 稀疏 --> NE1[偏向 NE / ES]
    B -- 是 --> C{动作空间是否离散<br/>且小?}
    C -- 是 --> RL1[偏向 RL DQN/PPO]
    C -- 否 / 连续高维 --> D{策略是否需要<br/>长时记忆?}
    D -- 是 --> NE2[NE / NEAT 拓扑搜索]
    D -- 否 --> E{算力 GPU vs CPU?}
    E -- 主要 GPU --> RL2[偏向 RL]
    E -- 大量 CPU --> NE3[偏向 ES]
    A --> F{要进化网络结构吗?}
    F -- 是 --> NE4[NEAT / NAS]
    F -- 否 --> G{超参对结果敏感吗?}
    G -- 是 --> NE5[ES 更鲁棒]
    G -- 否 --> RL3[RL 样本效率优]

总结启发式：

倾向 NE/ES	倾向 RL
奖励稀疏 / 仅有最终结果	奖励稠密
高维连续控制、长 horizon	离散小动作空间、短 horizon
需要进化拓扑	拓扑固定
CPU 集群充裕、GPU 紧	GPU 充裕
黑箱仿真器 (无梯度)	可微仿真
容忍低样本效率	关心样本效率

---

9. 实战考量

9.1 种群规模与并行

• CMA-ES：默认 \(\lambda = 4 + \lfloor 3\ln d \rfloor\)，对 \(d=100\) 约 \(\lambda=18\)。可放大到几百加快收敛 (在并行充足时)。
• OpenAI ES：典型 \(n = 1000 \sim 10000\)。论文用了 1440 CPU 工人，每代每工人评估若干扰动。
• NEAT：\(N = 150 \sim 300\)。物种数通常控制在 5—15 之间 (\(\delta_t\) 自适应)。

9.2 与 SGD 的混合

• Genetic SGD：每代用 SGD 微调子代再评估——典型 memetic 思路。
• PBT (Population-Based Training)：DeepMind 提出的 GA + SGD 杂交，用于超参/学习率在线调整 (Jaderberg et al. 2017)。
• ES + 反向传播：Conti et al. 2018 在 ES 损失上做反向传播，形成 ES-Gradient hybrid。

9.3 实现陷阱

• 高斯扰动的方差需正则化——不归一化在高维下扰动量级随 \(\sqrt{d}\) 暴涨。
• ES 对适应度排序的尺度不变性只在用 rank-based fitness shaping 时成立 (减均值除标准差，或转秩)。
• NEAT 的 \(\delta_t\) 不能固定——种群进化中结构距离尺度漂移，需自适应。

---

10. 实例：Gymnasium 环境上的 ES vs PPO 伪代码

下面给出在同一 Gym 环境上跑 OpenAI ES 与 PPO 的极简对比骨架——结构高度相似，区别只在更新规则。

# ============ OpenAI ES ============
def openai_es(env, policy_net, n_workers=64, sigma=0.1, alpha=0.01, gens=500):
    theta = flatten(policy_net.parameters())
    for g in range(gens):
        seeds = [rng.randint(2**31) for _ in range(n_workers)]
        rewards = []
        for s in seeds:                          # 可并行 ray.remote
            eps = sample_normal_with_seed(s, theta.shape)
            theta_perturbed = theta + sigma * eps
            r = rollout(env, unflatten(theta_perturbed))
            rewards.append(r)
        rewards = rank_normalize(rewards)        # fitness shaping
        grad_est = sum(r * regen_eps(s, theta.shape)
                       for r, s in zip(rewards, seeds)) / (n_workers * sigma)
        theta = theta + alpha * grad_est

# ============ PPO (skeleton) ============
def ppo(env, policy_net, value_net, T=2048, K=10, eps=0.2, gens=500):
    for g in range(gens):
        traj = collect_trajectories(env, policy_net, T)
        adv = gae(traj, value_net)
        for _ in range(K):
            ratio = exp(policy_net.logp(traj) - traj.old_logp)
            surr = min(ratio * adv, clip(ratio, 1-eps, 1+eps) * adv)
            loss = -surr.mean() + 0.5 * (value_net(traj.s) - traj.ret).pow(2).mean()
            sgd_step(loss)

实际工程中 ES 部分通常用 ray / torch.distributed 跑工人池，PPO 用 Stable-Baselines3 / RLlib。

---

11. 交叉引用

• 父页：本页 §1（派系入口） —— 进化派整体定位
• 同目录：遗传算法与遗传编程 —— GA 的位串/树编码版本
• 同目录：群体智能与 AutoML —— PSO/ACO/NAS 的对比
• 强化学习：../../../2_ReinforcementLearning/ —— PPO/A3C/SAC 的细节，本页只做对比
• 深度学习：../../../1_DeepLearning/ —— HyperNetwork、神经架构搜索的相关页

---

参考文献

• Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog. —— ES 的原始博士论文。
• Schwefel, H.-P. (1981). Numerical Optimization of Computer Models. Wiley.
• Hansen, N., & Ostermeier, A. (2001). Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2), 159–195.
• Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772. —— CMA-ES 权威工程教程。
• Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J., & Schmidhuber, J. (2014). Natural Evolution Strategies. JMLR, 15, 949–980.
• Ollivier, Y., Arnold, L., Auger, A., & Hansen, N. (2017). Information-geometric optimization algorithms: A unifying picture via invariance principles. JMLR, 18, 1–65.
• Salimans, T., Ho, J., Chen, X., Sidor, S., & Sutskever, I. (2017). Evolution Strategies as a Scalable Alternative to Reinforcement Learning. arXiv:1703.03864.
• Stanley, K. O., & Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2), 99–127.
• Stanley, K. O., D'Ambrosio, D. B., & Gauci, J. (2009). A hypercube-based encoding for evolving large-scale neural networks. Artificial Life, 15(2), 185–212.
• Risi, S., & Stanley, K. O. (2010). Evolving plastic neural networks with novel adaptation rules. GECCO.
• Conti, E., Madhavan, V., Petroski Such, F., Lehman, J., Stanley, K. O., & Clune, J. (2018). Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents. NeurIPS.
• Jaderberg, M., et al. (2017). Population Based Training of Neural Networks. arXiv:1711.09846.
• Ha, D., Dai, A., & Le, Q. V. (2016). HyperNetworks. arXiv:1609.09106.

---

群体智能与 AutoML

本页聚焦进化派的两条平行线：群体智能 (Swarm Intelligence, SI) 与自动机器学习 (AutoML)。前者是模拟蚁群、鸟群、蜂群等生物集体行为的去中心化优化方法；后者是把进化与其他黑箱优化技术应用于机器学习管线本身——超参、模型族、神经网络架构都成为被搜索的对象。

阅读本页前推荐先看 本页 §1（派系入口）。本页与 遗传算法与遗传编程、进化策略与神经进化 共同构成进化派系列。

---

1. 群体智能：去中心化、局部交互、涌现

群体智能 (Swarm Intelligence, SI) 由 Beni 与 Wang 在 1989 年提出，作为机器人集群协同的研究范式。它的三大支柱：

1. 去中心化 (decentralization)：没有全局调度者；每个个体只看自己附近的状态。
2. 局部交互 (local interaction)：个体之间通过简单规则、有限信息通信。
3. 涌现 (emergence)：全局智能行为从大量简单个体的互动中"自发"产生。

SI 与 GA 的核心差异：

维度	GA	SI (PSO/ACO)
个体之间关系	选择竞争 (适者生存)	协作交流 (信息素 / 全局最优共享)
主算子	交叉 + 变异	更新规则 (move toward best)
是否有"代"	有显式代际	通常连续更新
主隐喻	自然选择	集群行为

---

2. 粒子群优化 PSO

Particle Swarm Optimization (PSO) 由 James Kennedy 与 Russell Eberhart 在 1995 年提出，灵感来自鸟群协同觅食。

2.1 算法

每个粒子 \(i\) 维护： - 位置 \(\mathbf{x}_i \in \mathbb{R}^d\) - 速度 \(\mathbf{v}_i \in \mathbb{R}^d\) - 个体历史最优 \(\mathbf{p}_i\) (personal best) - 全局最优 \(\mathbf{g}\) (global best, 或邻域最优 \(\mathbf{l}_i\))

每步更新： $\(\mathbf{v}_i^{t+1} = \omega \mathbf{v}_i^t + c_1 r_1 (\mathbf{p}_i - \mathbf{x}_i^t) + c_2 r_2 (\mathbf{g} - \mathbf{x}_i^t)\)$ $\(\mathbf{x}_i^{t+1} = \mathbf{x}_i^t + \mathbf{v}_i^{t+1}\)$

其中 \(r_1, r_2 \sim \mathcal{U}[0,1]^d\) 逐分量采样；\(\omega\) 为惯性权重；\(c_1, c_2\) 分别为认知 (cognitive) 与社会 (social) 学习因子，典型 \(c_1 = c_2 = 1.49\)，\(\omega \in [0.4, 0.9]\)。

2.2 参数直觉

• \(\omega\) 大 → 强惯性、强探索；\(\omega\) 小 → 强收敛。常见线性下降调度：从 0.9 退到 0.4。
• \(c_1\) 大 → 粒子相信自己历史 → 多模态保护。
• \(c_2\) 大 → 粒子相信全局 → 快速收敛但易早熟。
• Clerc constriction factor (\(\chi\)): 更稳定的设置 \(\mathbf{v} \leftarrow \chi[\mathbf{v} + c_1 r_1 (\mathbf{p}_i - \mathbf{x}) + c_2 r_2 (\mathbf{g} - \mathbf{x})]\)，\(\chi = 2/|2 - \varphi - \sqrt{\varphi^2 - 4\varphi}|\)，\(\varphi = c_1+c_2 > 4\)。

2.3 拓扑结构

• gbest (star)：所有粒子共享全局最优 → 收敛快、易早熟。
• lbest (ring)：每个粒子只看左右邻居 → 收敛慢但抗早熟。
• Von Neumann lattice：每个粒子看上下左右 4 邻居。
• 随机拓扑：动态变化邻居关系。

2.4 重要变体

• CLPSO (Comprehensive Learning PSO, Liang 2006)：每个维度独立选学习目标，提升多模态搜索。
• APSO (Adaptive PSO)：根据进化状态自适应 \(\omega, c_1, c_2\)。
• Bare-bones PSO：去掉速度，直接 \(\mathbf{x}_i^{t+1} \sim \mathcal{N}((\mathbf{p}_i + \mathbf{g})/2, |\mathbf{p}_i - \mathbf{g}|)\)。

---

3. 蚁群算法 ACO

Ant Colony Optimization (ACO) 由 Marco Dorigo 在 1992 年博士论文中提出。它的灵感来自蚂蚁通过信息素 (pheromone) 间接通信、最终汇聚到最短路径的现象。

3.1 ACO 的关键机制

1. 解的构造：每只蚂蚁逐步构造一个完整解 (例如 TSP 的一条路径)，决策时按概率： $\(p_{ij}^k = \frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{l \in N_i^k}[\tau_{il}]^\alpha [\eta_{il}]^\beta}\)$ 其中 \(\tau_{ij}\) 是边 \((i,j)\) 上的信息素浓度，\(\eta_{ij}\) 是启发式 (例 \(1/d_{ij}\))，\(\alpha, \beta\) 分别控制信息素与启发式的影响。

2. 信息素更新：所有蚂蚁完成一轮后： $\(\tau_{ij} \leftarrow (1-\rho)\tau_{ij} + \sum_{k=1}^m \Delta\tau_{ij}^k\)$ \(\rho \in (0, 1]\) 是蒸发率，\(\Delta\tau_{ij}^k = Q/L^k\) (若蚂蚁 \(k\) 走过 \((i,j)\)，否则 0)，\(L^k\) 是该蚂蚁解的总代价。

3. 正反馈：好解的边获得更多信息素 → 后续蚂蚁更倾向走这些边 → 强化好解。蒸发机制防止过度强化早期发现的次优解。

3.2 ACO 变体

• AS (Ant System)：原始版本 (Dorigo 1992)，所有蚂蚁更新。
• MMAS (MAX-MIN Ant System, Stützle 2000)：信息素被限制在 \([\tau_{\min}, \tau_{\max}]\)，仅 best-so-far 蚂蚁更新——大幅缓解早熟。
• ACS (Ant Colony System, Dorigo & Gambardella 1997)：引入局部信息素更新 + 伪随机比例选择规则。
• Rank-based AS：仅 top-\(\sigma\) 蚂蚁更新，按排名加权。

3.3 应用场景

ACO 最适合离散组合优化： - TSP、车辆路径 (VRP)、调度、网络路由 (AntNet)、装配序列、特征选择。 - 在连续优化上不如 PSO/CMA-ES——离散信息素结构在连续空间里不自然。

---

4. 其他群体算法 (简表)

4.1 人工蜂群 ABC (Karaboga 2005)

模拟蜂群觅食。三类蜂： - 雇佣蜂 (employed)：维护一个食物源 (候选解)，做局部搜索。 - 观察蜂 (onlooker)：根据雇佣蜂跳舞 (适应度) 选食物源去搜索。 - 侦察蜂 (scout)：当食物源耗尽 (limit 代不改进) 时随机重启。

更新规则：\(x'_{ij} = x_{ij} + \phi(x_{ij} - x_{kj})\)，\(\phi \in [-1, 1]\)，\(k\) 是其他随机食物源。

ABC 的优势是参数少 (主要是 limit 与种群规模)、抗早熟好；劣势是多维、多模态以外的问题上对 PSO/CMA-ES 没有显著优势。

4.2 萤火虫算法 FA (Yang 2008)

每只萤火虫被亮度高的吸引： $\(\mathbf{x}_i \leftarrow \mathbf{x}_i + \beta_0 e^{-\gamma r_{ij}^2}(\mathbf{x}_j - \mathbf{x}_i) + \alpha \boldsymbol{\epsilon}_i\)$ 其中 \(r_{ij} = \|\mathbf{x}_i - \mathbf{x}_j\|\)，\(\beta_0\) 是基础吸引力，\(\gamma\) 是衰减系数，\(\alpha\) 是随机扰动幅度。

特点是距离衰减 —— 较亮的萤火虫只对近邻有强吸引，自然形成多个生态位 → 适合多模态优化。

4.3 布谷鸟搜索 CS (Yang & Deb 2009)

灵感：布谷鸟把蛋下到其他鸟的巢里，被发现就被丢出。算法步骤： 1. 用 Lévy flight 生成新解：\(\mathbf{x}_i^{t+1} = \mathbf{x}_i^t + \alpha \otimes L(s, \lambda)\)，\(L\) 是 Lévy 分布 (重尾，长程跳跃)。 2. 随机替换某些"巢"中的解。 3. 概率 \(p_a\) 抛弃最差的若干"被发现"的蛋，重生成。

Lévy flight 的重尾特性使 CS 比 PSO 更具全局探索能力。

4.4 群体算法对比

算法	主要灵感	信息共享方式	强项	弱项
PSO	鸟群	共享 personal/global best	连续优化、实现简单	高维易早熟
ACO	蚁群信息素	信息素矩阵	离散组合、TSP	连续优化别扭
ABC	蜂群分工	适应度比例舞蹈	多模态、参数少	高维收敛慢
FA	萤火虫亮度衰减	距离衰减吸引	多模态	参数 (\(\gamma\)) 敏感
CS	布谷鸟+Lévy	替换最差巢	全局探索强	局部精调差，常需混合

---

5. 群体智能 vs GA 总览

维度	GA	SI (PSO/ACO)
编码	位串/实数/树	实数 / 路径 / 离散结构
主操作	选择 + 交叉 + 变异	更新规则 (向 best 移动)
信息流	父代→子代 (代际)	个体之间持续共享
收敛速度	较慢	较快 (但易早熟)
多样性保护	sharing/crowding/island	拓扑/惯性
适用	通用	取决于具体算法

---

6. AutoML：自动化的机器学习管线

AutoML (Automated Machine Learning) 的目标是让非专家也能构建高质量机器学习系统——把数据预处理、特征工程、模型选择、超参优化、模型集成、部署整个管线自动化。

6.1 AutoML 的子问题

flowchart LR
    A[原始数据] --> B[数据清洗 / 缺失值处理]
    B --> C[特征工程 / 特征选择]
    C --> D[模型族选择]
    D --> E[超参数优化 HPO]
    E --> F[神经架构搜索 NAS]
    E --> G[模型集成 / 蒸馏]
    F --> H[部署 / 监控]
    G --> H
    subgraph 元学习
        M1[元数据]
        M2[warm-start]
    end
    M1 -.- B
    M1 -.- D
    M2 -.- E

主要子问题： - HPO (Hyperparameter Optimization)：学习率、正则化、网络宽度等。 - NAS (Neural Architecture Search)：网络结构本身。 - 元学习 (Meta-learning)：用历史任务经验加速新任务。 - 数据增强搜索：AutoAugment、RandAugment。 - 特征工程：FeatureTools、AutoCross。

6.2 AutoML 的三大流派

• 进化型：把 ML 管线编码为染色体进化 (TPOT、AutoML-Zero)。
• 贝叶斯型：高斯过程或 TPE 拟合超参→性能映射 (Hyperopt、Optuna)。
• 强化学习型：把 ML 管线构造作为 MDP (Zoph & Le NAS-RL、Google Vizier)。

---

7. 超参数优化方法对比

方法	原理	维度	是否需要平滑性	典型工具
网格搜索 (Grid)	离散网格遍历	低 (\(\le 4\))	否	sklearn
随机搜索 (Random)	均匀采样	中 (\(\le 20\))	否	sklearn
进化方法	GA / CMA-ES / TPE	中—高	否	DEAP, nevergrad
贝叶斯优化 (BO)	GP/TPE/SMAC	中 (\(\le 50\))	软 (核函数假设)	scikit-optimize, Optuna, BoTorch
Hyperband	多臂赌博机 + 早停	任意	否	hyperband, HpBandSter
BOHB	BO + Hyperband 杂交	中—高	软	HpBandSter
PBT	进化 + 在线训练	任意	否	Ray Tune

经验法则： - 维度 \(\le 5\)、评估便宜：随机搜索就够。 - 维度 5–30、评估贵：贝叶斯优化 / TPE。 - 训练曲线信息可用：Hyperband / BOHB (更省资源)。 - 超参与训练同步调整：PBT。 - 不可微目标 / 离散选择多：CMA-ES、GA。

Bergstra & Bengio 2012 在 Random Search for Hyper-Parameter Optimization 中证明：在很多场景下随机搜索优于网格搜索——因为大多数超参不重要 ("low effective dimensionality")，网格在不重要维度上浪费评估。这是 HPO 入门必读。

---

8. NAS 神经架构搜索

NAS 是 AutoML 中最受关注的子问题，目标是自动发现优于人工设计的神经网络架构。

8.1 三个维度

任何 NAS 方法都要回答三个问题：

维度	选项
搜索空间 (search space)	macro (整网) / cell-based / hierarchical / morphism-based
搜索策略 (search strategy)	RL / 进化 / 贝叶斯 / 可微分 / 随机
性能估计 (performance estimation)	完全训练 / early stopping / 权重共享 / 性能预测器

8.2 搜索空间

• macro：整个网络层层指定 (Zoph & Le 2017 原版)。空间大、搜索难。
• cell-based：搜小 cell、堆叠成网络 (NASNet、AmoebaNet、DARTS)。主流选择——大幅缩小空间，可迁移到不同分辨率/任务。
• hierarchical：cell 内部还是有层次的 motif。
• morphism-based：从已知模型出发，通过等价变换 (NetMorph) 扩展。

8.3 搜索策略

8.3.1 进化型：AmoebaNet (Real et al. 2019)

把架构编码为 DAG 染色体。Regularized Evolution 关键创新：用 "age-based" 选择替代精英保留——总是淘汰最老的个体，避免被早期偶然好解长期支配。在相同算力下击败 NAS-RL，发现 ImageNet top-1 = 83.9% 的 AmoebaNet-A。

8.3.2 RL 型：NAS-RL (Zoph & Le 2017)

Controller 是一个 RNN，逐步采样架构描述符；架构在 CIFAR 上训练得验证准确率作为 reward；用 REINFORCE / PPO 更新 controller。 - 原始版本：800 GPU × 28 天。 - 后续 NASNet、ENAS 大幅降本。

8.3.3 可微分：DARTS (Liu et al. 2019)

把"在 candidate ops 中选一个"变成 softmax 加权和： $\(\bar o^{(i,j)}(x) = \sum_{o \in \mathcal{O}} \frac{\exp(\alpha_o^{(i,j)})}{\sum_{o'} \exp(\alpha_{o'}^{(i,j)})}\, o(x)\)$ 其中 \(\alpha\) 是架构参数，与权重 \(w\) 一起用 SGD 训练 (双层优化)。最后取 \(\arg\max \alpha\) 离散化。

DARTS 把 NAS 成本从 GPU-days 降到几个 GPU-hours，被广泛复用。但有 known issues：搜索-评估 gap、跳跃连接坍缩等，催生了 PC-DARTS、Fair-DARTS、SDARTS 等改进。

8.4 NAS 三大策略对比图

flowchart TD
    SP[搜索空间] --> S1[搜索策略]
    S1 --> RL[强化学习<br/>RNN controller<br/>NAS-RL Zoph 2017]
    S1 --> EV[进化<br/>染色体 + 突变 / 交叉<br/>AmoebaNet Real 2019]
    S1 --> DG[可微<br/>softmax over ops<br/>DARTS Liu 2019]
    RL --> P1[完整训练<br/>每个采样架构]
    EV --> P1
    DG --> P2[权重共享<br/>One-shot]
    P1 --> EVAL[准确率 reward]
    P2 --> EVAL
    EVAL --> S1

维度	NAS-RL	AmoebaNet	DARTS
策略	强化学习	进化 (Regularized Evolution)	可微 (双层优化)
算力	800 GPU·days	\(\sim\) 3000 GPU·days	0.4 GPU·days
是否 one-shot	否	否 (后续 ENAS 是)	是
复现稳定性	差 (PPO 调参)	好	中 (易跳跃连接坍缩)
搜出网络	NASNet	AmoebaNet	DARTS-cells

8.5 性能预测器与权重共享

完整训练每个候选成本极高，三大降本技术：

1. Performance Predictor：用历史数据 (架构, 准确率) 训一个回归器，新架构直接预测 → PNAS、Neural Predictor。
2. Weight Sharing / One-Shot：一个 supernet 包含所有候选；训练 supernet 后所有子网继承权重 → ENAS、SPOS、ProxylessNAS。
3. Early Stopping / Learning Curve Extrapolation：提前终止低潜力训练 → Hyperband / Successive Halving。

8.6 ProxylessNAS 与硬件感知

ProxylessNAS (Cai et al. 2019) 直接在目标硬件 (手机/GPU/FPGA) 上搜索，把延迟纳入损失： $\(\mathcal{L} = \mathcal{L}_{\mathrm{CE}} + \lambda_1 \|w\|^2 + \lambda_2 \mathbb{E}[\mathrm{Latency}]\)$ 延迟通过子模块查表得到、对架构参数可微。这一思路推动了 MobileNet-V3、EfficientNet 等手机端 SOTA 网络的诞生。

---

9. 工业 AutoML 框架对比

框架	主要算法	强项	适用场景
DEAP	GA/GP/ES (Python)	灵活、教科书式 API	研究、教学、自定义 EA
pymoo	NSGA-II/III、MOEA/D	多目标优化	工程优化、Pareto 前沿
nevergrad (Facebook)	CMA-ES、TBPSA、bayes	黑箱基准多	通用黑箱优化
Optuna	TPE、CMA-ES、NSGA-II	sklearn/PyTorch 无缝、剪枝	HPO 工业首选
Hyperopt	TPE	早期经典	HPO，逐渐被 Optuna 替代
Ray Tune	PBT、ASHA、BOHB、Optuna	分布式 + 调度	大规模分布式 HPO
NNI (微软)	TPE、SMAC、PPO、Evolution、DARTS	NAS + HPO 一体	NAS 实验
AutoGluon (AWS)	模型集成 + 元学习	表格/图像/文本一键	端到端工程部署
AutoKeras	NAS + Bayesian	Keras 用户友好	快速上手
AutoSklearn	SMAC + meta-learning	sklearn 兼容	表格小数据
TPOT	GP 进化 sklearn 管线	管线整体进化	表格 ML 管线优化
AutoML-Zero	演化基本指令	从零进化算法本身	研究 / 极致自动化

---

10. AutoML 的局限

AutoML 不是银弹。三个根本性局限：

10.1 搜索成本

• AmoebaNet：\(\sim\) 3000 GPU·days
• 早期 NAS-RL：800 GPU·days
• DARTS / one-shot 大幅降低，但仍非"免费午餐"

碳排放问题被 Strubell et al. (2019) 量化：训练单个大型 NAS 模型的碳排放接近一辆汽车整个生命周期。

10.2 泛化与转移

• 在 CIFAR-10 上搜出的架构未必在 ImageNet 上最优 (虽然实践中 transfer 通常有效)。
• 在 ImageNet-1k 上搜的架构未必在医学影像、卫星图像上最优。
• 代理任务 (proxy task) 偏差：用小数据集 / 少 epoch 做 proxy，搜出的偏好和大规模实际任务可能错位。

10.3 可解释性

• 进化/RL 搜出的架构常带"奇怪"的连接 (skip 链、不规则 op 组合)，人类难以理解为何有效。
• HPO 给出"\(\eta = 3.7 \times 10^{-4}\)" 的最优值，没有提供原理性洞察。
• 与符号派 / 贝叶斯派对"可解释性"的追求形成张力。

10.4 公平性与 reproducibility

Lindauer & Hutter (2020) 系统综述指出：很多 NAS 论文比较的是不同搜索算法 + 不同搜索空间，无法分离贡献。NAS-Bench-101/201/301 等基准的出现让 NAS 研究终于可以公平比较算法本身。

---

11. 工程实践 checklist

部署 AutoML 系统时应过的清单：

• [ ] 搜索空间是否合理？过大 → 浪费；过小 → 找不到。
• [ ] proxy task 与目标任务的相关性？做 transfer 实验。
• [ ] 算力预算上限？把 wall-clock 与 GPU-days 都做约束。
• [ ] 早停策略？Hyperband / ASHA 通常省 5—10×。
• [ ] 是否 one-shot？supernet 训练成本 + 子网继承精度。
• [ ] 多目标 (准确率 + 延迟 + 内存)？用 NSGA-II / Pareto。
• [ ] 元学习 warm-start？可加速冷启动。
• [ ] 监控搜索过程：top-\(k\) 多样性、收敛曲线、超参重要度。
• [ ] 最终验证：full training + 独立测试集 + 多 seed。
• [ ] 可重复性：固定 seed、记录所有超参、容器化。

---

12. 交叉引用

• 父页：本页 §1（派系入口） —— 进化派整体定位与算法谱系
• 同目录：遗传算法与遗传编程 —— GA/GP 是 AutoML 进化分支的引擎
• 同目录：进化策略与神经进化 —— ES/CMA-ES 在 HPO 与 NAS 中重要
• 深度学习：../../../1_DeepLearning/ —— NAS 搜出来的 AmoebaNet/DARTS 网络的细节
• 贝叶斯派：贝叶斯派 —— TPE/SMAC/BO 是 HPO 的贝叶斯阵营

---

参考文献

• Beni, G., & Wang, J. (1989). Swarm intelligence in cellular robotic systems. NATO Advanced Workshop on Robots and Biological Systems.
• Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN, 4, 1942–1948. —— PSO 原始文献。
• Clerc, M., & Kennedy, J. (2002). The particle swarm: explosion, stability, and convergence in a multidimensional complex space. IEEE TEC, 6(1), 58–73.
• Liang, J. J., Qin, A. K., Suganthan, P. N., & Baskar, S. (2006). Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE TEC, 10(3), 281–295.
• Dorigo, M. (1992). Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano. —— ACO 原始博士论文。
• Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to TSP. IEEE TEC, 1(1), 53–66.
• Stützle, T., & Hoos, H. H. (2000). MAX-MIN ant system. Future Generation Computer Systems, 16(8), 889–914.
• Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical Report, Erciyes University.
• Yang, X.-S. (2008). Nature-Inspired Metaheuristic Algorithms. Luniver Press. —— 萤火虫算法。
• Yang, X.-S., & Deb, S. (2009). Cuckoo search via Lévy flights. World Congress on Nature & Biologically Inspired Computing.
• Bergstra, J., & Bengio, Y. (2012). Random search for hyper-parameter optimization. JMLR, 13, 281–305.
• Snoek, J., Larochelle, H., & Adams, R. P. (2012). Practical Bayesian optimization of machine learning algorithms. NeurIPS.
• Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., & Talwalkar, A. (2017). Hyperband: A novel bandit-based approach to hyperparameter optimization. JMLR, 18, 1–52.
• Falkner, S., Klein, A., & Hutter, F. (2018). BOHB: Robust and efficient hyperparameter optimization at scale. ICML.
• Zoph, B., & Le, Q. V. (2017). Neural architecture search with reinforcement learning. ICLR. —— NAS-RL 原始文献。
• Real, E., Aggarwal, A., Huang, Y., & Le, Q. V. (2019). Regularized evolution for image classifier architecture search. AAAI. —— AmoebaNet。
• Liu, H., Simonyan, K., & Yang, Y. (2019). DARTS: Differentiable architecture search. ICLR.
• Pham, H., Guan, M. Y., Zoph, B., Le, Q. V., & Dean, J. (2018). Efficient neural architecture search via parameter sharing. ICML. —— ENAS。
• Cai, H., Zhu, L., & Han, S. (2019). ProxylessNAS: Direct neural architecture search on target task and hardware. ICLR.
• Strubell, E., Ganesh, A., & McCallum, A. (2019). Energy and policy considerations for deep learning in NLP. ACL.
• Lindauer, M., & Hutter, F. (2020). Best practices for scientific research on neural architecture search. JMLR, 21, 1–18.
• Akiba, T., Sano, S., Yanase, T., Ohta, T., & Koyama, M. (2019). Optuna: A next-generation hyperparameter optimization framework. KDD.
• Olson, R. S., & Moore, J. H. (2016). TPOT: A tree-based pipeline optimization tool for automating machine learning. Automated Machine Learning Workshop.

---

评论