javascript - 关于在 JavaScript 中制作 NEAT 原型(prototype)的几个问题

Question

我最近读了原著 paper关于神经进化 由 Kenneth O. Stanley 撰写的 Augmenting Topologies，现在我正在尝试自己用 JavaScript 对其进行原型(prototype)设计。我偶然发现了几个我无法回答的问题。

---

我的问题:

1. “结构性创新”的定义是什么？如何存储这些信息以便检查之前是否已经发生过创新？

   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

2. 是否有存储节点类型(输入、隐藏、输出)的原因？

3. 在原始论文中，只有连接具有创新编号，但在other sources中，节点也是如此。这对交叉有必要吗？ (这已经被问过here.)

4. 如何限制变异函数不添加循环连接？

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

---

我的代码的相关部分:

基因组

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

首先，我强烈建议不要自己实现 NEAT。如果您看一下(许多)可用的实现，这是一个相当大的项目!

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

如果你还有更多疑惑，推荐你看看this implementation科林格林供引用。如果他不是更了解 NEAT 实现的人，那么他就差不多了。