Evolving Neural Networks through Augmenting Topologies (NEAT)

作者: Kenneth O. Stanley and Risto Miikkulainen (The University of Texas at Austin)
发表时间: 2002 (Based on TR 2001)

1. 引言 (Introduction)

神经进化 (Neuroevolution, NE) 是利用遗传算法来训练神经网络的方法。传统的神经进化方法通常固定神经网络的拓扑结构（即神经元和连接的数量及布局），仅进化连接的权重。

然而，神经网络的拓扑结构（Topology）对其功能也至关重要。一个核心问题是：同时进化拓扑结构和权重是否能比仅进化权重带来优势？

早期关于进化拓扑结构的研究（TWEANNs）结论不一，甚至有观点认为固定拓扑结构（如 ESP 算法）效率更高。本文提出了 NEAT (NeuroEvolution of Augmenting Topologies) 方法，旨在通过正确的方式进化拓扑结构，从而显著提升学习效率。

NEAT 的设计旨在解决进化拓扑结构时的三个主要技术挑战：
1. 交叉 (Crossover)：如何在不同的拓扑结构之间进行有意义的交叉？（解决竞争约定问题）
2. 保护创新 (Protecting Innovation)：如何防止新产生的结构（往往初始适应度较低）在优化前被淘汰？
3. 最小化结构 (Minimizing Structure)：如何确保网络在整个进化过程中保持尽可能简单，从而最小化搜索空间？

2. 背景与挑战 (Background & Challenges)

2.1 竞争约定问题 (The Competing Conventions Problem)

这是神经进化中的一个主要难题。对于同一个神经网络功能，存在无数种不同的表达方式（例如隐藏层神经元的排列顺序不同）。如果两个父代网络功能相同但编码（基因排列）不同，直接交叉往往会产生功能受损的后代。

图1：竞争约定问题示意图。两个网络计算相同的函数，但隐藏节点的顺序不同。直接交叉会导致关键信息的丢失（如 [C, B, C] 丢失了 A 的信息）。

当网络拓扑结构不同时，这个问题变得更加严重。不知道哪个基因对应哪个结构，交叉就变成了乱序组合。

2.2 保护创新

在 TWEANN 中，通过变异增加新的结构（如新节点或新连接）通常会暂时降低网络的适应度（Fitness）。如果直接与整个种群竞争，这些拥有新结构但尚未优化的个体很快就会死掉。这就像自然界中的新物种需要一个生态位（Niche）来生存一样。

3. NEAT 方法 (The NEAT Method)

NEAT 通过以下三个核心技术解决了上述问题：

3.1 遗传编码 (Genetic Encoding)

NEAT 使用直接编码。每个基因组包含两部分列表：
1. 节点基因 (Node Genes)：列出输入、隐藏和输出节点。
2. 连接基因 (Connection Genes)：列出连接的起点、终点、权重、是否启用 (Enable bit) 以及最重要的 创新号 (Innovation Number)。

图2：基因型到表现型的映射。基因组（上）通过连接基因直接描述了神经网络（下）。注意第三个基因被禁用（Disabled），因此连接 2->5 在网络中不显示。

3.2 历史标记 (Historical Markings) - 解决交叉问题

NEAT 的核心创新在于使用 创新号 (Innovation Number) 来跟踪基因的历史起源。
* 每当通过变异产生一个新的连接基因时，系统会分配一个全局唯一的创新号。
* 继承自同一祖先的基因将拥有相同的创新号。

通过创新号，系统确切地知道不同基因组中的哪些基因是匹配的（同源的），哪些是不匹配的。

图3：NEAT 的两种结构变异。
1. 添加连接 (Add Connection)：在两个节点间增加新连接，赋予新的创新号。
2. 添加节点 (Add Node)：在现有连接中间插入新节点。原连接被禁用，产生两个新连接和新节点。

在交叉（Crossover）时，NEAT 利用创新号对齐基因：
* 匹配基因 (Matching Genes)：创新号相同的基因。随机继承。
* 不相交 (Disjoint) / 过剩 (Excess) 基因：只存在于一方的基因。通常从适应度更高的父代继承。

图4：利用创新号匹配不同拓扑结构的基因组。无需复杂的拓扑分析，只需线性对齐创新号即可实现有意义的交叉。

3.3 物种形成 (Speciation) - 保护创新

为了保护创新，NEAT 将种群划分为不同的物种 (Species)。
* 兼容性距离 (Compatibility Distance $\delta$)：基于两个基因组中过剩基因 (E)、不相交基因 (D) 的数量以及匹配基因权重的平均差异 ($\bar{W}$) 计算。
$$ \delta = \frac{c_1 E}{N} + \frac{c_2 D}{N} + c_3 \cdot \bar{W} $$
* 显式适应度共享 (Explicit Fitness Sharing)：个体必须与同物种的其他成员共享适应度。这限制了任何单一物种过度统治种群，并保护了新产生的小物种（创新），让它们有时间优化自己的结构。

3.4 从最小结构增量增长 (Incremental Growth from Minimal Structure)

与其他通常从随机拓扑开始的方法不同，NEAT 从没有任何隐藏节点的最小网络开始（所有输入直接连接到输出）。
* 随着进化进行，通过变异逐步增加结构。
* 这确保了 NEAT 始终在解决问题所需的最小维度的搜索空间中进行搜索，从而极大提高了效率。

4. 实验验证 (Performance Evaluations)

4.1 XOR 问题 (验证性实验)

XOR 问题需要隐藏层才能解决。
* 结果：NEAT 能够可靠地进化出解决 XOR 问题的结构。
* 效率：平均在 32 代内找到解决方案，且生成的网络结构非常紧凑（通常只有 1-2 个隐藏节点）。

图5：(a) 初始种群没有隐藏节点。(b) 进化出的最优 XOR 网络结构。

4.2 双倒立摆平衡 (Double Pole Balancing)

这是一个具有挑战性的强化学习基准任务，要求同时平衡两根长短不一的杆子。

实验 1：带速度信息 (With Velocity)

• 对比算法：Evolutionary Programming, Conventional NE, SANE, ESP。
• 结果：NEAT 所需的评估次数最少，证明了其在标准任务上的高效性。

实验 2：无速度信息 (Without Velocity) - 困难任务

• 这是一个非马尔可夫 (Non-Markovian) 任务，网络必须进化出循环连接 (Recurrent connections) 来拥有记忆功能。
• 对比算法：Cellular Encoding (CE), ESP。
• 结果：
  • NEAT 比 CE 快 25倍。
  • NEAT 比 ESP 快 5倍。

结论：在困难任务中，进化拓扑结构的优势最为明显。NEAT 能够避免陷入局部最优（Deception）。

5. 分析与消融研究 (Analysis & Ablations)

为了证明 NEAT 的每个部分都是必要的，作者进行了消融实验（移除某个组件后测试性能）。

图6：NEAT 各组件之间的依赖关系。历史标记是基础，支持交叉和物种形成；物种形成支持增量增长（保护创新）；增量增长确保搜索空间最小化。

可视化物种形成

图7：双倒立摆任务中的物种演化图。横轴代表种群大小，纵轴代表代数。可以看到新物种（右侧）不断产生，旧物种（左侧）逐渐灭绝。高亮部分表示该物种内出现了高适应度的个体，最终导向解决方案。

6. 讨论与结论 (Discussion & Conclusion)

NEAT 的优势

1. 效率：通过始终在最小维度的空间搜索，NEAT 比固定拓扑方法和其他 TWEANN 更快。
2. 复杂化 (Complexification)：NEAT 不仅是在优化，而且是在复杂化解决方案。它从简单开始，随着任务需求增加复杂度。这与生物进化的过程高度相似。
3. 避免局部最优：通过同时维护不同拓扑结构的物种，NEAT 不容易陷入单一拓扑的局部最优解。

结论

NEAT 证明了进化拓扑结构如果方法得当（使用历史标记解决交叉、使用物种形成保护创新、从最小结构开始），可以显著优于固定拓扑的神经进化方法。它为持续协同进化 (Continuous Coevolution) 和复杂系统的自动生成提供了新的可能性。

图8：NEAT 为无速度双倒立摆问题找到的一个优雅且紧凑的解决方案。它利用自身的一个循环连接计算导数，从而推断出速度信息。