JavaScript 中有关 NEAT 原型设计的几个问题

Question

我最近阅读了 paper 关于 NeuroEvolution 的原著由 Kenneth O. Stanley 撰写的 Augmenting Topologies，现在我正在尝试自己在 JavaScript 中对其进行原型制作。我偶然发现了几个我无法回答的问题。

我的问题：

"structural innovation" 的定义是什么，我如何存储这些以便检查之前是否已经发生过创新？

However, by keeping a list of the innovations that occurred in the current generation, it is possible to ensure that when the same structure arises more than once through independent mutations in the same generation, each identical mutation is assigned the same innovation number
存储节点类型（输入、隐藏、输出）是否有原因？
原论文中只有connection有创新号，但在other sources, nodes do as well. Is this necessary for crossover? (This has already been asked here.)
如何限制突变函数不添加循环连接？

我想就到此为止了。感谢所有帮助。

我代码的相关部分：

基因组

class Genome {
    constructor(inputs, outputs) {
        this.inputs = inputs;
        this.outputs = outputs;
        this.nodes = [];
        this.connections = [];
        for (let i = 0; i < inputs + outputs; i++) {
            this.nodes.push(new Node());
        }
        for (let i = 0; i < inputs; i++) {
            for (let o = 0; o < outputs; o++) {
                let c = new Connection(this.nodes[i], this.nodes[inputs + o], outputs * i + o);
                this.connections.push(c);
            }
        }
        innovation = inputs * outputs;
    }
    weightMutatePerturb() {
        let w = this.connections[Math.floor(random(this.connections.length))].weight;
        w += random(-0.5, 0.5);
    }
    weightMutateCreate() {
        this.connections[Math.floor(random(this.connections.length))].weight = random(-2, 2);
    }
    connectionMutate() {
        let i = this.nodes[Math.floor(random(this.nodes.length))];
        let o = this.nodes[Math.floor(random(this.inputs, this.nodes.length))];
        let c = Connection.exists(this.connections, i, o);
        if (c) {
            c.enabled = true;
        } else {
            this.connections.push(new Connection(i, o, innovation));
            innovation++;
        }
    }
    nodeMutate() {
        let oldCon = this.connections[Math.floor(Math.random(this.connections.length))];
        oldCon.enabled = false;
        let newNode = new Node();
        this.nodes.push(newNode);
        this.connections.push(new Connection(oldCon.input, newNode, innovation, 1));
        innovation++;
        this.connections.push(new Connection(newNode, oldCon.output, innovation, oldCon.weight));
        innovation++;
    }
}

节点

class Node {
    constructor() {
        this.value = 0;
        this.previousValue = 0;
    }
}

连接

class Connection {
    constructor(input, output, innov, weight) {
        this.input = input;
        this.output = output;
        this.innov = innov;
        this.weight = weight ? weight : random(-2, 2);
        this.enabled = true;
    }
    static exists(connections, i, o) {
        for (let c = 0; c < connections.length; c++) {
            if (connections[c].input === i && connections[c].output === o) {
                return connections[c];
            }
        }
        return false;
    }
}

欢迎所有答案和来源。（你是一个很棒的人！）

Answer 1

这不是一般的 JS 问题！感谢您提供的链接，这是一篇非常有趣的论文。我不能自称是专家，我只做过玩具 GA 问题，但我确实阅读了这篇论文和相关论文。这是我的理解：

我想你需要担心的是 parent 是否通过突变在一代人中多次产生相同的新基因。即两个children，其创新号最新的基因完全相同。你可以马上剔除那些。我觉得他们说同一个基因有可能同时出现在两个物种身上，他们基本上说没关系，这种情况很少见，不用担心。
我至少能找到一个原因："In NEAT, a bias is a node that can connect to any node other than inputs."
我相信你的问题是"must nodes have an innovation number to do crossover?"答案是否定的。在原始论文（例如图 4）中，他们展示了以只有连接具有创新数的方式实现的交叉。
如果您想将变异函数更改为架构感知，而不是避免循环结构，您可能想要显式添加您确实需要的结构。假设您想避免循环连接，因为您正在改进图像分类器，并且您知道卷积更适合这项任务。在这种情况下，您希望您的突变函数能够 add/remove 层（以及所需的连接）。这是 explored in detail last year 作者 Google Brain:

Some of the mutations acting on this DNA are reminiscent of NEAT. However, instead of single nodes, one mutation can insert whole layers—i.e. tens to hundreds of nodes at a time. We also allow for these layers to be removed, so that the evolutionary process can simplify an architecture in addition to complexifying it.

根据您对问题 4 的动机的评论，我认为您错了。在原始论文的 XOR 示例中，图 5，它们显示了一个不涉及隐藏层的起始表型。这个起始表型不是 XOR 问题的解决方案，但它提供了一个很好的起点："NEAT is very consistent in finding a solution. It did not fail once in 100 simulations." 没有任何复发惩罚。

Answer 2

首先，我强烈建议不要自己实施 NEAT。如果你看一下（许多）可用的实现，这是一个相当大的项目！

结构创新是添加到基因组中且以前从未见过的任何新节点或连接。假设您有输入节点 1、2、3 和输出节点 4、5。如果只有连接 2-4 可用，引入连接 3-4 将是一种结构创新。为了检查新颖性，您需要存储所有看到的结构（即所有连接和节点的列表），每个结构都有一个唯一的 ID（这实际上是 NEAT 背后的核心思想！）。在我们的示例中，连接 2-4 可能采用 ID=1，而连接 3-4 可能采用 ID=2。您可以看到连接是新的，因为列表中没有其他连接连接 2 和 4。通常通过在连接中创建 "a stop" 来引入节点，并简单地获取下一个可用 ID。例如，连接 2-4 将被删除，您将拥有连接 2-5 和 5-4，其中节点 ID=5 是在此过程中创建的（以及两个新连接）。请注意，节点和连接的 ID 可能是独立的（即：如果您完全使用连接 ID）。
我正在努力想出一个 hard 的要求。原则上，您可以简单地以固定顺序存储节点（首先输入，然后输出，然后隐藏），然后根据索引猜测它们的类型，出于性能原因，这通常是您通常这样做的方式（想象一下尝试删除一个节点，您会只想 select 一个隐藏节点，因此您可以将搜索限制在这些索引中）。不过，某些任务可能会更有效地使用该信息，例如检查经常性连接（请参阅 4）。
ID 在交叉中很有用，因为它们可以快速了解两个基因组之间哪些元素是共同的。是否为节点和连接提供 ID 是一个开放的实施决定。连接没有 ID 使代码更简单（连接由它们连接的节点的 ID 标识）。但是你失去了区分连接相同节点的两个连接的能力。有一个论点说，两个给定节点之间的连接在进化的不同时间不一定意味着相同（请参阅您的引用如何提到 "in the same generation"）。不过，这可能不是相关因素！正如我所说，节点和连接的 ID 的便利性在 NEAT 社区中仍然存在争议。
在许多情况下，您不想允许重复连接。执行此操作的标准方法是在每次尝试添加连接时检查是否重复。这是一个代价高昂的步骤，是的！

如果你还有更多疑惑，推荐你看看Colin Green的this implementation，以供参考。如果他不是更了解 NEAT 实现的人，他就差不多了。

JavaScript 中有关 NEAT 原型设计的几个问题

A few questions on prototyping NEAT in JavaScript

javascript

neural-network

genetic-algorithm

recurrent-neural-network

evolutionary-algorithm

我的问题：

我代码的相关部分：

基因组

节点

连接