Implementing the “original” NEAT algorithm in JavaScript

Implementing the “original” NEAT algorithm in JavaScript
0.0 0

#1

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

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

  2. In the original paper, only connections have an innovation number, but in other sources, nodes do as well. Is this necessary for crossover?

  3. How could I limit the mutation functions to not add backpropagation 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!)