# Implementing the “original” NEAT algorithm in JavaScript

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

• I kindly request you to post this question in cross validated community for effective feedback. – quintumnia Mar 30 '18 at 18:39
• Thank you @quintumnia, for your advice. I posted it there, for anyone interested you can find it here. – Nigk Mar 30 '18 at 19:28
• @quintumnia It was flagged as off-topic there, so it's on stackoverflow now. After re-reading the topics, I think that's where I should've posted it in the first place. All help is still appreciated. – Nigk Apr 1 '18 at 19:03
• No worries,have faith and very soon you will be getting relevant answer – quintumnia Apr 2 '18 at 18:26

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?

Structural innovation is anything added that changes the topology of the network. So a structural innovation is any added connection or added node. I don't want to get too much into the implementation, but something similar to a dictionary global variable will work. When adding a connection (or node) between two nodes, we check if a connection (or node) has ever been placed between these two nodes before. If it has then we have stored an innovation number for what this connection (or node) is identical and we set its innovation number to that. We identify each node by its innovation number.

1. Is there a reason for storing the type of a node (input, hidden, output)?

Yes, there are many structural innovations that we do not want to happen. An innovation between two input node or an innovation between two output nodes are two examples of structural innovations we don't want.

1. 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.)

Although I am unsure if it is explicitly stated, it is implied that nodes have an innovation number. You can see this in Figure 2 and 3 of the paper where each node is labeled with a number.

1. How could I limit the mutation functions to not add backpropagation connections?

By backpropagation connections I assume you mean recurrent connections (correct me if I am wrong). You can prevent recurrent connections in many ways, but one way is to maintain a partially ordered set. When adding a connection between two nodes you check to see the order of those two nodes in the partially ordered set. The one that comes first will be the node from which the connection starts, while the second will be the node at which the connection ends.

• Node has a number not an innovation number, especially in figure 2. Do you mean the number of the node being equivalent to the innovation number of the connection. – Angel.King.47 Jan 15 at 21:27