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

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 3

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