A few questions on prototyping NEAT in JavaScript

Question

I've recently read the original paper about NeuroEvolution of Augmenting Topologies by Kenneth O. Stanley and am now trying to prototype it myself in JavaScript. I stumbled across a few questions I can't answer.

---

My questions:

1. What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?

   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. Is there a reason for storing the type of a node (input, hidden, output)?

3. In the original paper, only connections have an innovation number, but in other sources, nodes do as well. Is this necessary for crossover? (This has already been asked here.)

4. How could I limit the mutation functions to not add recurrent connections?

I think that's it for now. All help is appreciated.

---

The relevant parts of my code:

Genome

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++;
    }
}

Node

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

Connection

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;
    }
}

All answers an sources are welcome. (You are an awesome person!)

Answer 1

First, I would very strongly advice against implementing NEAT yourself. If you take a look at the (many) available implementations, it is quite a large project!

1. A structural innovation is any new node or connection that is added to a genome and that has not been seen before. Imagine you have input nodes 1, 2, 3 and output nodes 4, 5. If only connection 2-4 is available, introducing connection 3-4 would be an structural innovation. To check for novelty you need to store all seen structures (i.e., a list of all connections and nodes) with a unique ID for each (this is the core idea behind NEAT, actually!). In our example, connection 2-4 may take ID=1, and connection 3-4 would take ID=2. You can see the connection is new in that no other connection in the list connects 2 and 4. Nodes are normally introduced by creating "a stop" in a connection and simply take the next available ID. For example, connection 2-4 would be deleted and you would have connections 2-5 and 5-4, where node ID=5 is created in the process (as well as two new connections). Note the IDs for nodes and connections may be independent (that is: if you use IDs for connections at all).
2. I'm struggling to think of a hard requirement for this. In principle you could simply store nodes in fixed order (input first, output next, then hidden) and then guess their type given their index, which is how you normally do it anyway for performance reasons (imagine trying to remove a node, you would only want to select a hidden node, so you would restrict search to those indices). Some tasks may be more efficient having that info, though, for example checking for recurrent connections (see 4).
3. IDs are useful in crossover, as they allow to quickly know which elements are common between two genomes. Whether to have IDs for nodes as well as connections is an open implementation decision. No IDs for connections makes simpler code (connections are identified by the IDs of the nodes they connect). But you lose the ability to tell apart two connections that connect the same nodes. There is an argument that says that a connection between two given nodes does not necessarily mean the same at different times in evolution (see how your quote mentions "in the same generation"). This is probably not a relevant factor, though! As I said, the convenience for IDs for both nodes and connections is still debated in the NEAT community.
4. In many cases you do not want to allow recurrent connections. The standard way to do this is to check for recurrence every time you try to add a connection. This is a costly step, yes!

If you have more doubts, I recommend you take a look at this implementation by Colin Green for reference. If he is not the person who knows more about NEAT implementation, he comes close.