The most efficient and easy way to write the NEAT algorithm
Hello Everyone,
This is my first medium article and I had to write this as I have searched through the internet, but found no easy-to-understand articles.
I thought about the NEAT Algorithm for a long time, read the paper many times over, but did not understand how to implement it. I even managed to do it once or twice, but it was not elegant, and only worked crudely.
This was when i tried to follow video tutorials on youtube(i don’t do that very often), but I was greeted with awesome explainations, not code.
So here i bring you the easiest and probably the most efficient way to code the NEAT algo.
(I’ll be doing this in python, but it can be implemented in any language)
The first thing to do is to make a node.py, connection.py, genome.py, connectionh.py (connection history) and a main.py
The node.py goes as follows:
This will have a number and a layer.
The connection.py goes as follows:
Connection expects the 2 nodes it connects. It has a weight, an innovation number, and a bool to make it turn on/off.
Now for the connectionh.py :
This file contains the history of all connections of all genomes. This should only be one in the program. It recieves the inputs and the outputs for the neural network, which is the base neuralnet. It also has a list of all the connections with innovation numbers, and a global innovation number, which is the highest connection attained yet.
And now, the most important part, the genome.py:
This is not the full file, but it is a start.
The genome class accepts a connection history object and a boolean asking whether or not to create a starting network. (This becomes important when mating or when cloning genomes)
The input and output layers are the bounds of the network. You can change it to fit your needs. The creation_rate is just a percent of how many random connections should be generated at the start (when actually using it, change it to a lower value, 0.6 is just for debugging purposes).
The createNetwork function creates a sample network with just the input and output nodes and some random connections. The total_nodes comes in handy as we do not have to specify the node number when adding more nodes(mutation).
The add_connection function is a little complicated :
This is the function which adds a random connection between any two random nodes.
n1 and n2 are random nodes at the start, representing the starting and the ending of the connection. The while loops check if the n1 is on the outputlayer (it can’t, as there is nothing beyond), if n2 is on the inputlayer, or if n2’s layer is smaller/equal to n1’s layer (we cannot have connections going backwards or on the same layer).
The we create 2 connections, x and c. c is to check whether this connection exists in the connection history, while x is the connection to be added.
if c is not null, we can say that the connection already exists, and therefore assign it (x) the existing innovation number, and add it to the genomes connections. We also check if the connection already exists in the connections to avoid any errors.
if c is null, we know the connection does not exist in the connection history, so we set x’s innovation to the global innovation number and then increment it. Then a copy can be appended to the connection history, and the connection can be appended to the genomes connections.
THAT’S IT!
The only thing remaining is the mutations.
There are, according to my research, 5 types of mutations in NEAT:
- Adding Connections
Just call the add_connection function
2. Adding Nodes
Add the add_node function to the genome class:
The next are to be added in the connection class.
3. Randomizing weights
4. Shifting the weights between a random value between -0.2 and 0.2
5. Enabling/Disabling Connections
Thanks for reading!!