How to evaluate a NEAT neural network?

Question

I'm trying to write my own implementation of NEAT and I'm stuck on the network evaluate function, which calculates the output of the network.

NEAT as you may know contains a group of neural networks with continuously evolving topologies by the addition of new nodes and new connections. But with the addition of new connections between previously unconnected nodes, I see a problem that will occur when I go to evaluate, let me explain with an example:

INPUTS = 2 yellow nodes
HIDDEN = 3 blue nodes
OUTPUT = 1 red node

In the image a new connection has been added connecting node3 to node5, how can I calculate the output for node5 if I have not yet calculated the output for node3, which depends on the output from node5?

(not considering activation functions)

node5 output =  (1 * 0.5) + (1 * 0.2) + (node3 output * 0.8)
node3 output =  ((node5 output * 0.7) * 0.4)

Answer 1

Consider the execution order, 5 will have an invalid value because it hasn't been set form 3 yet. However the second time around it should have a value set. The invalid value should falloff after sufficient training.

0 -> 5
1 -> 5
5 -> 2
2 -> 3
3 -> 4
3 -> 5
RESTART
0 -> 5
1 -> 5

Answer 2

Following is the pseudo code of the NEAT's network evaluation (converted from original source code),

Until all the outputs are active
    for all non-sensor nodes
        activate node
        sum the input
    for all non-sensor and active nodes
        calculate the output

Note that there is no recursion for feed forwarding concepts according to the original author.

Answer 3

I can think of two possible ways of enforcing NEAT to create a feed forward network. One elegant one and one a little more cumbersome one;

1. Only allow the "add connection" mutation to connect a node with another node that have a higher maximum distance from an input node. This should result in feed forward network, without much extra work. (Emergent properties are great!)
2. Run as you did and create a fully connected network with NEAT and then prune it during a forward pass. After creating the network, run through it and remove connections that try to connect to a node already used in the forward pass (example 3->5). Alternatively just remove unused input connections to nodes during the forward pass. Given how NEAT mutates, it should not be possible that you remove a vital connection and cut the the network in two. This property of NEAT make sure your signal will always be able to reach the output, even if you remove those "backwards pointing" connections.

I believe these should work, however i have not tested them.

The original NEAT paper assumed a feed forward ANN, even though its implementation as described would result in a fully connected network. I think it was just an assumption of the paradigm they worked in. The confusion is fully understandable.

Answer 4

In my implementation, I used a recursion system to calculate the output nodes. It works as follows:

1. Assume a feed-forward network

Only allow the "add connection" mutation to connect a node with another node >that have a higher maximum distance from an input node. This should result in >feed forward network, without much extra work. (Emergent properties are great!)

2. Define function x, a recursive function that takes in a node number
3. Define function y, a second function that takes in a node and returns all the connections with that node as an output

In the recursive function:

1. Call function y

2. Call function x on function y outputs

3. If the parameter for x is any input node, return the node value.

This was the most elegant way of implementing I could think of, and its a lot simpler than explicitly tracking all of the connections.

Answer 5

Hello chris i am also implementing this algorithm from scratch and the way i go about activating my mlp net is as follows: I instantiate a list of nodes(actives), this is set to all input nodes initially, i then pass that to a function that initializes an empty list(next actives) and proceeds to loop through each set of conns for each node in the actives list, it adds each "to" node from those connections to the "next actives) list unless its an output node or has already been activated, once all the "actives" list is looped through, i call the function again this time passing "next actives" as the actives list unless "next actives" is still empty after then i know the net has been fully activated.

in this scenario the connection from node three to node five would be evaluated but it would not be added to the next actives list because it had already been activated, preventing an infinite loop.

Answer 6

Okay, so instead of telling you to just not have recurrent connections, i'm actually going to tell you how to identify them.

First thing you need to know is that recurrent connections are calculated after all other connections and neurons. So which connection is recurrent and which is not depends on the order of calculation of your NN. Also, the first time when you put data into the system, we'll just assume that every connection is zero, otherwise some or all neurons can't be calculated.

Lets say we have this neural network: Neural Network

We devide this network into 3 layers (even though conceptually it has 4 layers):

Input Layer  [1, 2]
Hidden Layer [5, 6, 7]
Output Layer [3, 4]

First rule: All outputs from the output layer are recurrent connections.

Second rule: All outputs from the input layer may be calculated first.

We create two arrays. One containing the order of calculation of all neurons and connections and one containing all the (potentially) recurrent connections. Right now these arrays look somewhat like this:

Order of 
calculation: [1->5, 2->7 ]

Recurrent:   [ ]

Now we begin by looking at the output layer. Can we calculate Neuron 3? No? Because 6 is missing. Can we calculate 6? No? Because 5 is missing. And so on. It looks somewhat like this:

3, 6, 5, 7

The problem is that we are now stuck in a loop. So we introduce a temporary array storing all the neuron id's that we already visited:

[3, 6, 5, 7]

Now we ask: Can we calculate 7? No, because 6 is missing. But we already visited 6...

[3, 6, 5, 7,] <- 6

Third rule is: When you visit a neuron that has already been visited before, set the connection that you followed to this neuron as a recurrent connection. Now your arrays look like this:

Order of 
calculation: [1->5, 2->7 ]

Recurrent:   [6->7 ]

Now you finish the process and in the end join the order of calculation array with your recurrent array so, that the recurrent array follows after the other array. It looks somethat like this:

[1->5, 2->7, 7, 7->4, 7->5, 5, 5->6, 6, 6->3, 3, 4, 6->7]

Let's assume we have [x->y, y]

Where x->y is the calculation of x*weight(x->y)

And

Where y is the calculation of Sum(of inputs to y). So in this case Sum(x->y) or just x->y.

There are still some problems to solve here. For example: What if the only input of a neuron is a recurrent connection? But i guess you'll be able to solve this problem on your own...