酷应用

学界 | NEAT学习：教机器自我编程

百家作者：机器之心 2017-10-05 05:21:42

选自medium

机器之心编译

参与：Nurhachu Null、路雪

本文介绍了一种机器学习方法：通过增强拓扑的进化神经网络（Evolving Neural Networks through Augmenting Topologies，NEAT）。该方法受到进化过程的启发，能够将复杂问题分解，进而解决问题。

在这篇文章中我要阐述一种机器学习方法，叫作「通过增强拓扑的进化神经网络」（Evolving Neural Networks through Augmenting Topologies，NEAT）。

引言

我爱学习。翻开关于我不了解的话题的书或论文，并且尝试着去理解，真是太令人兴奋了。有些人喜欢在闲暇的时候玩一下字谜游戏、数独或者猜谜游戏来活跃思维，而我喜欢阅读论文并且试着实现文中提出的算法。虽然热爱学习，但是我不可能将喜欢的东西全部学完，所以我特别着迷于如何让计算机为我学习，并向我呈现可能最大化我的学习效率的一些有趣的信息。这些有助于将复杂的信息结构化的算法是「专家系统」的一部分。所以这些算法的目标就是「创造」一个我在做决策的时候能够随时向其咨询的「专家」。让我们站在一个比较高的视角看看这个能够帮助创造这些「专家」的模型 NEAT。本文将介绍这一概念。

NEAT 是什么？

NEAT 指「Networks through Augmented Topologies」（通过增强拓扑的进化神经网络），描述了自学习机器的算法概念，这些算法概念受启发于进化过程中的遗传修饰（genetic modification）。

生命本身就是很有魅力的。每当我观察自然界的时候，我都会看到一个存在于所有的生命体中的共同特征，它叫作信息。信息似乎就是繁殖的核心遗传特征。自然界在过去的 37 亿年里能够优化信息，创造很多共存的不同物种。达尔文的「适者生存、不适者淘汰」的理念启迪了我们对物种进化的理解。进化计算机科学家的目标就是构建能够模仿自然进化来解决复杂问题的系统。

描述 NEAT 工作原理的最简单、最容易的方式就是举例。如果你必须设计一个以最佳方式为你玩游戏的专家系统，那么相关的因素会是什么呢？

首先，为「玩家」定义所有允许他们执行的潜在操作是非常重要的。以超级玛丽为例，它能够跳跃、躲闪、向左走、向右走、转动、快跑等等。如果我们将一台机器与这些动作联系起来，并且允许它来执行这些动作，那么它将有能力做这些事。

第二，要给计算机制定一个目标。NEAT 使用一个叫做「适应度评分（Fitness Score）」的变量。适应度评分是一个能够对成功做出奖励的数学函数。在类似《超级玛丽》的游戏中，适应度评分就是玩家朝着终点线不断前进。适应度评分包含很多类似的变量，例如收集的硬币数、击败的敌人数，或者完成游戏所需的时间。

第三，定义进化的规则非常重要。NEAT 允许节点突变、节点之间产生新的连接，以及在新的后代中继承最合适的神经网络。此外，NEAT 确保不同的「物种」可以共存，直至它们为了生成新的、更适合的后代而进行彼此之间的竞争。为了保证适者生存，已经被尝试过的神经网络不会进行重复，而现存的神经网络会进行自我优化，NEAT 为每一个作为历史记录者的基因都添加了一个新的数字。

上图展示了通过添加一个连接和添加一个节点所形成的突变。上面的例子中从 2 到 4 的连接被取消了，另外还建立了一个新的从 3 到 5 的连接。下面的例子中是节点的突变，你可以看到从 2 到 4 的连接被取消了，并且引入了一个新的节点 6，然后生成了从 3 到 6、从 6 到 4 的新连接。

上图展示了进化是如何发生的。parent 1 和 parent 2 在节点和连接上有着相似的结构，但是它们也有区别。机器现在使用二元逻辑来增加或去除节点/连接。基本的决策机制基于同真为真，真假为假，同假为假（true and true is true, true and false is false, false and false is false）-真与真是真，真与假是假，假与假是假-。这种方式能够确保后代的继承信息对适应度评分是有效的，新生后代中会采用新的进化节点和/或连接，已经被取消的父节点仍保持被取消的状态。「匹配的基因是随机遗传的，不相交基因（中间阶段不匹配）和过剩基因（最后阶段不匹配）是从更加适合的 parent 继承的。在这种情况下，假设它们有着相等的适应度评分，那么不相交基因（disjoint gene）和过剩基因（excess gene）也是随机继承的。被取消的基因或许在未来的后代中重新被激活：有一个预置条件就是，如果继承的基因在一个 parent 中被取消，那么这个基因就会被取消。」[Stanley, Miikkulainen, Page 109, NEAT]

现在所有的东西已经差不多清楚了，NEAT 可以通过迭代和进化新的神经网络的方式在游戏中运行，以达到最佳的适应度评分。我特别推荐阅读一下这篇论文（论文摘要见下文），文章写得很棒，只要稍微 google 以下，新手也能够理解。但是如果你要来一个从头开始的课程，那你也可以看一下这个精彩视频：

NEAT 将复杂的问题分割成较小的、能够被优化的问题，来解决复杂问题，这真的很棒。NEAT 智能体可以开发来解决多种不同的子任务，然后联合起来解决更加复杂的问题。使用 NEAT 的一个例子就是新药品的创造：首先列出所有可能被用到的原子；然后，定义一个能够使仿真结果理解奖励系统的适应度函数；最后定义一套进化规则。另一个 NEAT 可以被用来选择生产新药物的制造技术。一旦这两个系统被结合在一起，一个促进成本效率优化的适应度函数就能创造出生产新药物的最佳方法。这在理论上听起来很棒，但是很明显，这在研发中是一个很复杂的问题，需要花费很多功夫。

论文：Evolving Neural Networks through Augmenting Topologies

地址：http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

摘要：神经进化领域的一个重要问题是如何利用带有权重的进化神经网络拓扑。我们展示了一种方法，即通过增强拓扑的进化神经网络（NeuroEvolu- tion of Augmenting Topologies，NEAT），该方法在有挑战性的基准强化学习任务中的表现优于最好的固定拓扑（fixed-topology）方法。我们认为效率提升原因在于（1）部署一种不同拓扑交叉的方法，（2）使用物种形成（speciation）保护结构化创新，（3）从最小结构渐进增长。我们通过一系列烧蚀研究论证这一观点，这些研究表明每个模块对整个系统以及其他模块都是必需的。结果就是显著加快的学习。NEAT 还对 GA 有很大的贡献，因为它展示了进化既可以优化解决方案，也可以使之复杂化，这使得逐代进化出更加复杂的解决方案成为可能，并且强化了与生物进化的类比。