解析神经网络进化框架 —— Neuroevolution

本文旨在通过代码分析让读者了解基于神经网络进化的机器学习实现方法。

之前 G 家的 Alpha Go 打败人类围棋冠军的事件将人工智能推上了人民群众议论的焦点。人工智能的热潮随之扑面而来，无论是手机、摄像、点外卖，无不标榜自己具有人工智能加成。一时间人工智能成为了时代的宠儿。

前不久在逛 github 的时候，偶然发现了一个叫 Neuroevolution.js 的文件，项目作者用它实现了一个人工智能玩游戏的 Demo

【游戏截图】

我认真的读了代码，结合有限的知识，下面尝试将代码讲解下，看看 Neuroevolution 是如何实现机器学习方式之一 —— 神经网络的。

神经网络 Neural Networks

首先介绍一下神经网络。神经网络的研究很早就已出现，今天“神经网络”已经是一个相当大的、多学科交叉的学科领域。神经网络的定义也多种多样，这里我们采用如下定义：

神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。

神经网络中最基本的成分是“神经元”模型，即上述定义中的“简单单元”。神经元互相相连，当有一个神经元接受外部信息并被“激活”，那么它会向相连神经元发送“化学物质”，改变它们的电位。如果某神经元的电位超过一个“阈值”，那么它也会向相连神经元发送“化学物质”。经过一系列的连锁反应，根据最后的神经元输出，就能得到相应的反馈，比如“跳”、“咬”等动作。

神经网络进化

神经网络进化是指通过一代又一代“优胜劣汰”方式筛选出适应“生存规则”的个体，这些个体所具备的“基因”含有能够使其作出对外部环境正确反应的神经网络。

神经网络进化的方式特点在于其越来越“智能”的进化过程无需人工干预，理想情况下仅依靠自身的逻辑就可产生趋于最优的解。

以 Demo 游戏为例，游戏中每一代会若干个个体，小鸟。每一代的个体全部死亡后会依据得分最高的一部分，使它们的基因延续给下一代（过程略复杂，后文有详解），如此往复，最后得到了一个或者多个能够持续穿越管道的个体。

如果你有足够耐心，可以看到存活个体已经掌握游戏生存规则，达到了人类难以企及的分数。

企业微信截图_20190402225041 【难以企及】

Neuroevolution 代码结构

Neuroevolution 文件中我们可以很清晰的看到它的代码结构，除 Neuroevolution 对象本身的属性和方法外，其中还包括 Generations、Generation、Genome、Network、Layer、Neuron 类（JS 的类可以通过 prototype 模拟的，所以虽然没使用 class 关键字，但本文也称之为“类”）。

下面我们分析下 Neuroevolution 对象和这些类的作用。

Neuroevolution 对象

Neuroevolution 对象（其实是个方法，但是 JS 中方法也是对象，姑且称之为对象）提供了一些基础配置，如下：

配置项	描述
activation	激活函数，经典 S（Sigmoid）函数
randomClamped	随机值函数，返回一个 -1 到 1 的浮点数
network	神经网络层配置
population	人口，每一代产生的个体数量
elitism	上一代最优基因的延续比例
randomBehaviour	下一代随机基因的比例
mutationRate	神经元的突触异变率
mutationRange	神经元的突触异变量
historic	上一代的存活人口
lowHistoric	是否不存储上一代神经网络
scoreSort	分数升降序，即声明分数越高越好还是越低越好
nbChild	生育数，上一代 2 个体繁殖的后代数量

这里的配置参数 network 如何配置？Demo 中使用的值 [2, [2], 1] 如何理解？

Neuvol = new Neuroevolution({
  population:50,
  network:[2, [2], 1],
});

Demo 代码

感知机和多层神经

network 配置项第一和第三个参数表示输入层和输出层的神经元个数，第一层我们称之为输入层，第三层我们称之为输出层。输入层和输出层就构成了一个感知机。

感知机能够轻易的实现逻辑与或非运算。

比如输入层有两个值 x1, x2，输出层为 y

y = x1 && x2  // 与运算
y = x1 || x2  // 或运算
y = !x1 // 非运算

感知机如果只有输入和输出层，且仅输出层有激活函数处理，功能是十分有限的，即使简单的异或问题也难以解决。

所以一般情况下，神经网络除了输入和输出层外，还会有若干的隐藏层，即 network 值第二项。

network 值第二项值为数组，数组项的个数表示隐藏层个数，每一项的数值表示该隐藏层的神经元个数。比如配置:

network: [2, [2, 2, 2], 1]

表示有 3 层隐藏层，每一层含有 2 个神经元。

通常情况下，我们称含有 1 个隐藏层的神经网络为单层神经网络，多个隐藏层的神经网络为多层神经网络。

隐藏层的主要工作是对输入层传过来的数据进行加工，然后传递给下一层网络，最终传递给输出层，如图：

【单层网络神经图片】

理论上隐藏层越多，神经网络的学习成本就越高。深度学习的神经网络其隐藏层数量是十分庞大的，可能会涉及上亿个参数需要调试。而神经网络进化是基于自身逻辑进行微调，从而产生足够”智能“的神经网络。

重新回到 Neuroevolution 对象，它具有如下方法：

方法	描述
set	覆盖默认配置参数
generations	`Generations` 实例
restart	重新开始生成后代
nextGeneration	返回下一代所有神经网络
networkScore	用于神经网络计分

其中 networkScore 方法用于为神经网络计分，通过配置参数 scoreSort 和其得分可以确定该神经网络在当代所有神经网络中的排名顺序。

下面我们看看其他的类。

Neuron 类

var Neuron = function () {
  this.value = 0;
  this.weights = [];
}

/**
 * Initialize number of neuron weights to random clamped values.
 *
 * @param {nb} Number of neuron weights (number of inputs).
 * @return void
 */
Neuron.prototype.populate = function (nb) {
  this.weights = [];
  for (var i = 0; i < nb; i++) {
    this.weights.push(self.options.randomClamped());
  }
}

Neuron 类很简单，它的实例由 value 和 weights 属性和一个 populate 方法组成。

value 即神经元的值，该值通过系列计算后由激活函数输出
weights 为神经元的突触，其个数等于输入层神经元个数
populate 方法可以向神经元突触填充随机值

Layer 类

/**
 * Neural Network Layer class.
 *
 * @constructor
 * @param {index} Index of this Layer in the Network.
 */
var Layer = function (index) {
  this.id = index || 0;
  this.neurons = [];
}

/**
 * Populate the Layer with a set of randomly weighted Neurons.
 *
 * Each Neuron be initialied with nbInputs inputs with a random clamped
 * value.
 *
 * @param {nbNeurons} Number of neurons.
 * @param {nbInputs} Number of inputs.
 * @return void
 */
Layer.prototype.populate = function (nbNeurons, nbInputs) {
  this.neurons = [];
  for (var i = 0; i < nbNeurons; i++) {
    var n = new Neuron();
    n.populate(nbInputs);
    this.neurons.push(n);
  }
}

Layer 类负责管理神经网络中的层。每个 Layer 实例需要确定它在整个网络中的位置 index，和它含有的神经元 neurons 数组。它提供的 populate 方法可以为实例填充神经元。

Network 类

Network 类负责管理神经网络，它的实例具有一个 layers 数组存放 Layer 实例。我们再看看 Network 实例的方法。

`perceptronGeneration` 方法

该方法会通过调用 Layer 和 Neuron 实例的填充方法将神经网络填充完整。它的填充过程如图：

4444 【神经网络填充图】

一个完整神经网络包含相应的层，每一层包含相应的神经元，而神经元包含值和突触。

值得注意的是，第一层输入层是没有突触的，之后的所有层包括最后的输出层的神经元都会拥有和输入神经元个数相同的突触数量。

那么突触具体的作用是什么呢？

`compute` 方法

从 compute 方法中可以解读到，突触其实就是用以对神经元的值进行微调的一种参数，当神经元接收到前一层神经元传递的值，接着和突触发生“反应”，然后根据所有突触的值，通过激活函数，成为当前神经元新的 value 值。

/**
 * Compute the output of an input.
 *
 * @param {inputs} Set of inputs.
 * @return Network output.
 */
Network.prototype.compute = function (inputs) {
  // Set the value of each Neuron in the input layer.
  for (var i in inputs) {
    if (this.layers[0] && this.layers[0].neurons[i]) {
      this.layers[0].neurons[i].value = inputs[i];
    }
  }

  var prevLayer = this.layers[0]; // Previous layer is input layer.
  for (var i = 1; i < this.layers.length; i++) {
    for (var j in this.layers[i].neurons) {
      // For each Neuron in each layer.
      var sum = 0;
      for (var k in prevLayer.neurons) {
        // Every Neuron in the previous layer is an input to each Neuron in
        // the next layer.
        sum += prevLayer.neurons[k].value *
          this.layers[i].neurons[j].weights[k];
      }

      // Compute the activation of the Neuron.
      this.layers[i].neurons[j].value = self.options.activation(sum);
    }
    prevLayer = this.layers[i];
  }

  // All outputs of the Network.
  var out = [];
  var lastLayer = this.layers[this.layers.length - 1];
  for (var i in lastLayer.neurons) {
    out.push(lastLayer.neurons[i].value);
  }
  return out;
}

前文提到了很多次的激活函数，这里解释下。框架使用的激活函数代码如下：

/**
 * Logistic activation function.
 *
 * @param {a} Input value.
 * @return Logistic function output.
 */
activation: function (a) {
  ap = (-a) / 1;
  return (1 / (1 + Math.exp(ap)))
}

通过激活函数，我们可以将一个值使用约束在 0 到 1 的范围内，且当参数 a 等于 0 时，激活函数取值为 0.5。

激活函数在坐标系中呈现为 S 形连续图像，如图：

【S函数图像】

连续的图像能够确保在微小的修改下，得到的值是相近的，有利于参数微调（如果参数调整的幅度过大，就会产生”震荡“，使最优解难以被归纳得过）。

`getSave` 方法和 `setSave` 方法

这对方法中，getSave 方法是将神经网络的神经元和突触保存为一种结构，包含所有层的神经元个数和所有神经元突触的值。这种结构将神经网络中的层以数组的形式表示，这为复制神经网络的逻辑提供了方便。

setSave 方法正好相反，可以将上述的数据结构写入一个神经网络中，即将层和突触数据填充入新的神经网络。

Genome 类和 `Generation` 类

Genome 类负责将神经网络和外部环境因素关联，起到纽带的作用。每一个基因包含一个神经网络。

Generation 类负责管理 Genome 实例，直觉上我们会认为所有存活的基因都在 Generation 示例下，但实际上 Generation 仅仅负责记录存活失败的基因并为它们排序。它具有如下方法：

方法	描述
addGenome	往最新一代中添加一个 `Genome` 实例
breed	通过两个 `Genome` 实例繁殖出新一代的 `Genome` 实例
generateNextGeneration	生成新一代个体

addGenome 方法被用于生成新一代基因，并且该方法会对基因的“生存能力”进行排序。Demo 中每阵亡一个小鸟，就会生成新的基因。

generateNextGeneration 方法是比较核心的方法。当游戏中的个体全部存活失败，就会执行 generateNextGeneration 方法。新一代个体的生成逻辑是：

选取 elitism 比例的当代基因，然后复制该部分基因的神经网络用于下一代；
选取 randomBehaviour 比例的基因，随机初始化后用于下一代；
当代基因以序号 1 和 2，2 和 3，3 和 4 的方式繁殖出新一代基因，直到达到人口上限。

/**
 * Generate the next generation.
 *
 * @return Next generation data array.
 */
Generation.prototype.generateNextGeneration = function () {
  var nexts = [];

  for (var i = 0; i < Math.round(self.options.elitism *
      self.options.population); i++) {
    if (nexts.length < self.options.population) {
      // Push a deep copy of ith Genome's Nethwork.
      nexts.push(JSON.parse(JSON.stringify(this.genomes[i].network)));
    }
  }

  for (var i = 0; i < Math.round(self.options.randomBehaviour *
      self.options.population); i++) {
    var n = JSON.parse(JSON.stringify(this.genomes[0].network));
    for (var k in n.weights) {
      n.weights[k] = self.options.randomClamped();
    }
    if (nexts.length < self.options.population) {
      nexts.push(n);
    }
  }

  var max = 0;
  while (true) {
    for (var i = 0; i < max; i++) {
      // Create the children and push them to the nexts array.
      var childs = this.breed(this.genomes[i], this.genomes[max],
        (self.options.nbChild > 0 ? self.options.nbChild : 1));
      for (var c in childs) {
        nexts.push(childs[c].network);
        if (nexts.length >= self.options.population) {
          // Return once number of children is equal to the
          // population by generatino value.
          return nexts;
        }
      }
    }
    max++;
    if (max >= this.genomes.length - 1) {
      max = 0;
    }
  }
}

在基因繁殖过程中，新基因的每个神经元会获得两个父基因提供的神经元的突触，并且基于 mutationRate 配置参数，可能会使突触产生变化。

/**
 * Breed to genomes to produce offspring(s).
 *
 * @param {g1} Genome 1.
 * @param {g2} Genome 2.
 * @param {nbChilds} Number of offspring (children).
 */
Generation.prototype.breed = function (g1, g2, nbChilds) {
  var datas = [];
  for (var nb = 0; nb < nbChilds; nb++) {
    // Deep clone of genome 1.
    var data = JSON.parse(JSON.stringify(g1));
    for (var i in g2.network.weights) {
      // Genetic crossover
      // 0.5 is the crossover factor.
      // FIXME Really should be a predefined constant.
      if (Math.random() <= 0.5) {
        data.network.weights[i] = g2.network.weights[i];
      }
    }

    // Perform mutation on some weights.
    for (var i in data.network.weights) {
      if (Math.random() <= self.options.mutationRate) {
        data.network.weights[i] += Math.random() *
          self.options.mutationRange *
          2 -
          self.options.mutationRange;
      }
    }
    datas.push(data);
  }

  return datas;
}

以 mutationRange 为 0.5 为例，突触的变化范围在 (-0.5, 0.5)。

Generations 类

Generations 负责记录当代个体和生成下一代所有个体，它具有如下几个方法：

方法	描述
firstGeneration	生成初代
nextGeneration	生成下一代
addGenome	往最新一代中添加基因（个体）

另外 Generations 还有一个同名的属性 generations，是一个数组，用于存放当代个体的最终状态。

每一代生成后，同时会向 generations 数组中插入一个空的 Generation 实例。在当代的个体存活失败时，通过 addGenome 方法生成新的基因，该基因保存了传入的神经网络数据，然后根据 score 值排序候放入 Generation 实例的 genomes 数组中。

由于使用了多处同名函数，这里的逻辑是有点绕的，可以仔细阅读代码辅助理解。

最后我们再看下游戏是如何和框架集成的。

集成

从 game.js 文件看，首先是初始化 Neuroevolution 框架。

Neuvol = new Neuroevolution({
  population:50,
  network:[2, [2], 1],
});

游戏中每一代生成 50 个个体，输入层 2 个神经元，1 层隐藏层，含有 2 个神经元，输出层 1 个神经元。

游戏开始时，会调用 nextGeneration 方法生成个体，然后根据个体数量产生对应游戏中的 bird 实例（游戏中一个鸟配一个神经网络）。

游戏过程中，会不断调用 bird 对应 network 实例的 compute 方法，根据输出值判断是否需要执行 flap 方法。也就是鸟会根据其神经网络的输出值判断是否进行跳跃。

然后在判断存活失败时，会对鸟的神经网络打分（当前的游戏分数），用以在当代个体中排序。

最后当当代个体全部失败后，游戏会重新调用 start 方法，使用游戏重新开始。但是这时的神经网络已经完成了一代的进化。

if(this.birds[i].isDead(this.height, this.pipes)){
  this.birds[i].alive = false;
  this.alives--;
  //console.log(this.alives);
  Neuvol.networkScore(this.gen[i], this.score);
  if(this.isItEnd()){
    this.start();
  }
}

总结

神经网络进化只是机器学习中的一种实现方式，还有很多实现方式，包括强化学习、规则学习、计算学习等，而仅就神经网络形式而言，也有 RBF （Radial Basis Function，径向基函数）网络、ART （Adaptive Resonance Theory，自适应谐振理论）网络、深度学习等常见的神经网络。

如果大家有兴趣，推荐阅读周志华教授编著的《机器学习》一书。

mengtuifrontend / Blog