3. The Fundamentals of Neuroevolution

Neuroevolution 指的是使用EA去优化（学习）一个人工神经网络。可以是只学习权重，也可以是学习连接方式（拓扑结构），也可以是学习学习策略。

3.1 Neuroevolution Taxonomy

3.1.1 Fixed-Topology Neuroevolution

也就是固定拓扑连接结构，然后进化其权重。

3.1.2 Topology and Weight Evolving Artificial Neural Networks

3.1.3 Direct Encoding

3.1.4 Indirect Encoding

3.2 Case Study: Evolving a Simple Walking Agent

这里作者使用了上一章讲过的EA方法去训练了一个双足行走机器人，并且效果超过了普通的强化学习。

3.3 Neuroevolution of Augmenting Topologies

3.3.1 Motivation and Challenges

Motivation是非常明确的，神经网络的网络架构搜索范围十分庞大，人工去一个个尝试是十分tedious的，于是我们可以使用EA让其自动搜索策略。

但是，人们发现了几个问题：

Competing Conventions: 通过置换，交换标签之类的操作，可以实现基因型完全不一样的两个网络，实际对应的是功能相同的同一个网络。出现这种情况，会导致crossover之类的操作使性能骤降。
Loss of Structural Innovations: 第二个问题是添加新的结构（比如新的节点或者连接）在开始时经常会伤害性能，所以这些变异会在它们证明自己有用之前就被抹去。比如你添加了一个新的节点，但是在权重被微调之前，往往是会立刻损伤性能的。

有一些尝试是添加最开始没有任何影响的结构，但是如果没有系统的方法去保护，这些新颖的结构，最终只会收敛到一个保守的拓扑结构。所以我们需要建立对冒险性的拓扑结构的保护。
Complexity versus, search efficiency: 许多尝试在一开始就在一个很大的空间、很大的网络去进行搜索，这会增加搜索的负担，同时有很多胡乱的连接，网络需要很长的时间去调整。作者认为理想情况是，网络应该在必要的时候才复杂化，应该从一个小的架构开始慢慢的变复杂。

总的来说，为了利用拓扑进化，我们需要。

一种对competing encoding具有鲁棒性的crossover方法。
一种保护并且滋养新的架构的mutations方法。
一种不需要专门的惩罚（方法），就可以从较小的解慢慢生长到复杂的解的方法。

3.3.2 Genetic Encoding and Historical Markings

NEAT 使用Node Genes和Connection Genes来表示神经网络。

mutations有以下两种：

add connection: 在两个原来不相连的节点之间添加新的连接。
add node: 在两个原来相连的节点之间添加新的节点。原来的连接disable，新加的连入新节点的边的权重为1，连出新节点的权重为原来的权重，这样不立刻影响网络，可以平滑过渡。

NEAT 有一个 innovation number 的概念，给每一个mutation都做了记号，当不同个体的一个结构变化在功能上是一样的时候，它们的 innovation number是一样的。比如上面那两张图。

crossover 这个操作首先根据两条genome，把基因分成matching genes、disjoint genes、excess genes。matching genes直接遗传，disjoint genes和excess genes根据fitness的不同采取不同的遗传策略。

NEAT 为了保护新的物种，提出了 Speciation 。基本的思想是把把物种进行隔离。定义compatibility distance $\delta$ 来衡量两个 genome 的相似程度。

$$\delta = \frac{c_1 E}{N} + \frac{c_2 D}{N} + c_3 \cdot \overline{W}$$

其中，$c_1, c_2, c_3$ 是决定每一项重要性的系数（超参数），$E$ 是excess genes的数量，$D$ 是disjoint genes的数量，$\overline{W}$ 是matching genes的权重差异的平均值。$N$ 是两个genome中较大的那个的基因数量。

$E$: the number of excess genes.
$D$: the number of disjoint genes.
$\overline{W}$: the average weight difference of matching genes.
$N$: the normalization factor (usually the genome length of the larger parent, to normalize for network size).

这个值如果大于一个阈值$\delta_t$，那么两个genome就被认为使不同的物种，如果小于，就认为是同一个物种。

NEAT 还提出了一个 fitness sharing 。大概的想法是不让一个物种占据全部。方法是把适应度除以种群的数量。

$$f_i' = \frac{f_i}{\sum_{j=1}^n \operatorname{sh}(\delta(i,j))}. \tag{2} $$

其中，$\operatorname{sh}(\delta(i,j))$ 是sharing function，如果$\delta(i,j)$ 大于一个阈值$\delta_t$，那么$\operatorname{sh}(\delta(i,j))$ 为0，否则为1。

3.3.4 Example: Double Pole Balancing

NEAT 所进行的实验。

3.4 Scaling up Neuroevolution

略