<p>This is not the average JS question! Thanks for the links, it's a really interesting paper. I can't claim to be an expert, I have only done toy GA problems, but I did read this paper and related ones. Here is what I understand:</p>

<ol>
<li><p>I think all you need to worry about is whether a parent, by mutation, produces the same novel gene more than once in a generation. That is, two children, whose gene with the newest innovation number are identical. You can cull those right away. I think they say that it is possible for the same gene to appear in two species at the same time, and they basically say that's fine, that's rare enough not to worry about.</p></li>
<li><p>I can find at least one reason: "In NEAT, a bias is a node that can connect to any node other than inputs."</p></li>
<li>I believe your question is "must nodes have an innovation number to do crossover?" The answer is no. In the original paper (e.g. Figure 4) they show crossover implemented in a way where only connections have innovation numbers.</li>
<li>If you want to change the mutation function to be architecture aware, rather than avoiding recurrent structure, you might want to explicitly add structures you do want. Suppose you want to avoid recurrent connections because you are evolving an image classifier, and you know that convolutions are more suited to the task. In this case, you want your mutation function to be able to add/remove <em>layers</em> (and the needed connections). This was <a href="https://arxiv.org/pdf/1703.01041.pdf" rel="nofollow noreferrer">explored in detail last year</a> by Google Brain:</li>
</ol>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Based on your comment about your motivation for question 4, I think you are mistaken. In the XOR example in the original paper, figure 5, they show a starting phenotype that involves no hidden layer. This starting phenotype is not a solution to the XOR problem, but it provides a good starting point: "NEAT is very consistent in finding a solution. It did not fail once in 100 simulations." That is without any penalization for recurrence.</p>
A few questions on prototyping NEAT in JavaScript
<p>I've recently read the original <a href="http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf" rel="nofollow noreferrer">paper</a> 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.</p>

<hr>

<h2>My questions:</h2>

<ol>
<li><p>What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?</p>

<blockquote>
  <p>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</p>
</blockquote></li>
<li><p>Is there a reason for storing the type of a node (input, hidden, output)?</p></li>
<li><p>In the original paper, only connections have an innovation number, but in <a href="http://www.automatonsadrift.com/neat/" rel="nofollow noreferrer">other sources</a>, nodes do as well. Is this necessary for crossover? (This has already been asked <a href="https://ai.stackexchange.com/questions/5496/neat-innovation-for-connection-genes-only">here.</a>)</p></li>
<li><p>How could I limit the mutation functions to not add recurrent connections?</p></li>
</ol>

<p>I think that's it for now. All help is appreciated.</p>

<hr>

<h2>The relevant parts of my code:</h2>

<h3>Genome</h3>

<pre><code>class Genome {
    constructor(inputs, outputs) {
        this.inputs = inputs;
        this.outputs = outputs;
        this.nodes = [];
        this.connections = [];
        for (let i = 0; i &lt; inputs + outputs; i++) {
            this.nodes.push(new Node());
        }
        for (let i = 0; i &lt; inputs; i++) {
            for (let o = 0; o &lt; 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++;
    }
}
</code></pre>

<h3>Node</h3>

<pre><code>class Node {
    constructor() {
        this.value = 0;
        this.previousValue = 0;
    }
}
</code></pre>

<h3>Connection</h3>

<pre><code>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 &lt; connections.length; c++) {
            if (connections[c].input === i &amp;&amp; connections[c].output === o) {
                return connections[c];
            }
        }
        return false;
    }
}
</code></pre>

<p>All answers an sources are welcome. (You are an awesome person!)</p>