Answers.Body: <p>Following is the pseudo code of the NEAT's network evaluation (converted from original source code), </p>
  
  <pre><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
  </code></pre>
  
  <p>Note that there is no recursion for feed forwarding concepts according to the original author. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T07:56:05.977Z
Answers.LastActivityDate: 2019-12-16T07:56:05.977Z
Answers.UserDisplayName: Morpheus
Answers.Body: <p>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;</p>
  
  <ol>
  <li>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!)</li>
  <li>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. </li>
  </ol>
  
  <p>I believe these should work, however i have not tested them.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-12T17:00:35.483Z
Answers.LastActivityDate: 2019-03-12T17:00:35.483Z
Answers.UserDisplayName: the Decoy
Answers.Body: <p>In my implementation, I used a recursion system to calculate the output nodes. It works as follows:</p>
  
  <ol>
  <li>Assume a feed-forward network</li>
  </ol>
  
  <blockquote>
    <p>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!)</p>
  </blockquote>
  
  <ol start="2">
  <li>Define function <code>x</code>, a recursive function that takes in a node number</li>
  <li>Define function <code>y</code>, a second function that takes in a node and returns all the connections with that node as an output</li>
  </ol>
  
  <p><strong>In the recursive function:</strong></p>
  
  <ol>
  <li><p>Call function <code>y</code></p></li>
  <li><p>Call function <code>x</code> on function y outputs</p></li>
  <li><p>If the parameter for <code>x</code> is any input node, return the node value.</p></li>
  </ol>
  
  <p>This was the most elegant way of implementing I could think of, and its a lot simpler than explicitly tracking all of the connections.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-08T01:49:02.833Z
Answers.LastActivityDate: 2019-08-08T01:54:16.720Z
Answers.LastEditDate: 2019-08-08T01:54:16.720Z
Answers.UserDisplayName: Terry T.
Answers.Body: <p>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. </p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-08T18:40:01.940Z
Answers.LastActivityDate: 2019-08-08T21:17:36.910Z
Answers.LastEditDate: 2019-08-08T21:17:36.910Z
Answers.UserDisplayName: nickw
Answers.Body: <p>Okay, so instead of telling you to just not have recurrent connections, i'm actually going to tell you how to identify them.</p>
  <p>First thing you need to know is that recurrent connections are calculated <strong>after</strong> all other connections <em>and</em> neurons. So which connection is recurrent and which is not depends on the <strong>order of calculation</strong> 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.</p>
  <p>Lets say we have this neural network:
  <a href="https://i.sstatic.net/TKiZF.png" rel="nofollow noreferrer">Neural Network</a></p>
  <p>We devide this network into 3 layers (even though conceptually it has 4 layers):</p>
  <pre><code>Input Layer  [1, 2]
  Hidden Layer [5, 6, 7]
  Output Layer [3, 4]
  </code></pre>
  <p>First rule: <strong>All outputs from the output layer are recurrent connections</strong>.</p>
  <p>Second rule: <strong>All outputs from the input layer may be calculated first</strong>.</p>
  <p>We create two arrays. One containing the order of calculation of all neurons <em>and</em> connections and one containing all the (potentially) recurrent connections.
  Right now these arrays look somewhat like this:</p>
  <pre><code>Order of 
  calculation: [1-&gt;5, 2-&gt;7 ]
  
  Recurrent:   [ ]
  </code></pre>
  <p>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:</p>
  <pre><code>3, 6, 5, 7
  </code></pre>
  <p>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:</p>
  <pre><code>[3, 6, 5, 7]
  </code></pre>
  <p>Now we ask: Can we calculate 7? No, because 6 is missing. But we already visited 6...</p>
  <pre><code>[3, 6, 5, 7,] &lt;- 6
  </code></pre>
  <p>Third rule is: <strong>When you visit a neuron that has already been visited before, set the connection that you followed to this neuron as a recurrent connection</strong>.
  Now your arrays look like this:</p>
  <pre><code>Order of 
  calculation: [1-&gt;5, 2-&gt;7 ]
  
  Recurrent:   [6-&gt;7 ]
  </code></pre>
  <p>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:</p>
  <pre><code>[1-&gt;5, 2-&gt;7, 7, 7-&gt;4, 7-&gt;5, 5, 5-&gt;6, 6, 6-&gt;3, 3, 4, 6-&gt;7]
  </code></pre>
  <p>Let's assume we have [x-&gt;y, y]</p>
  <p>Where x-&gt;y is the calculation of x*weight(x-&gt;y)</p>
  <p>And</p>
  <p>Where y is the calculation of Sum(of inputs to y). So in this case Sum(x-&gt;y) or just x-&gt;y.</p>
  <p>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...</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-13T12:32:34.960Z
Answers.Text: It's preferable that answers are self-contained, so, rather than linking to another post (in another website), I suggest that you provide the necessary info to answer the question here, in this answer.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-12T20:41:19.403Z
Answers.LastActivityDate: 2020-12-13T13:50:58.540Z
Answers.LastEditDate: 2020-12-13T13:50:58.540Z
Answers.UserDisplayName: Ukendt
Answers.Body: <p>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.</p>
  
  <pre><code>0 -&gt; 5
  1 -&gt; 5
  5 -&gt; 2
  2 -&gt; 3
  3 -&gt; 4
  3 -&gt; 5
  RESTART
  0 -&gt; 5
  1 -&gt; 5
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-05-01T20:15:42.793Z
Answers.Text: Thanks for the reply, okay, I'm not sure if that answers my question, node3 cannot be calculated and node5 cannot be calculated, because they both depend on each other, how can you evaluate either node? Am I missing something?
Answers.UserDisplayName: Chris
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-05-01T21:11:33.980Z
Answers.Text: I don't see how it can't be calculated. The first unresolved value you get is when calculating 5 (3 -> 5).
  
  Considering 0 has a value of .5, 1 has a value of .8, and 3 is unresolved, you may consider the following
  
  v5 = .5 * w0 + .8 * w1 + (3?) * w3
  Where the 3? is an unresolved value. I think the hack here is to initialize it to zero so your equation becomes 
  v5 = .5 * w0 + .8 * w1 + 0 * w3
  Reduces to
  v5 = .5 * w0 + .8 * w1
  
  This can calculate a value for 5 that can be used to calculate 2. You can then calculate 3 from 2. Then the next time 5 is calculated the value wouldn't be zero
Answers.UserDisplayName: Zakk Diaz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-05-01T21:17:57.683Z
Answers.Text: That makes sense, ty.
Answers.UserDisplayName: Chris
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-02T07:31:13.163Z
Answers.Text: @Chris: NEAT does not *usually* allow backwards connections and loops AFAIK, connections are normally feed-forward. So you are creating more work for yourself here. In principle it can be made to work, and for all I know there are some notes on implementing recurrent NNs in NEAT somewhere. But you may want to consider starting with feed-forward only.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-04T14:05:17.850Z
Answers.Text: @NeilSlater, So you're saying hidden nodes should not connect with other hidden nodes? Just inputs to hidden, inputs to output and hidden to output?
Answers.UserDisplayName: Chris
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-04T14:37:11.450Z
Answers.Text: @Chris - no, I am saying that nodes should not link in a way that causes loops.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-10T07:18:02.097Z
Answers.Text: @Chris: Actually, from re-reading the documentation, recurrent connections can be quite common and are not necessarily defended against in original NEAT implementations. It seems that the algorithm relies on weeding them out if they are not useful.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-05-01T19:28:32.923Z
Answers.LastActivityDate: 2018-05-01T19:28:32.923Z
Answers.UserDisplayName: Zakk Diaz
Body: <p>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.</p>
  
  <p>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:
  <a href="https://i.sstatic.net/cJTjN.png" rel="noreferrer"><img src="https://i.sstatic.net/cJTjN.png" alt="Network"></a></p>
  
  <pre><code>INPUTS = 2 yellow nodes
  HIDDEN = 3 blue nodes
  OUTPUT = 1 red node
  </code></pre>
  
  <p>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?</p>
  
  <p>(not considering activation functions)</p>
  
  <pre><code>node5 output =  (1 * 0.5) + (1 * 0.2) + (node3 output * 0.8)
  node3 output =  ((node5 output * 0.7) * 0.4)
  </code></pre>
  
Tags: <neural-networks><genetic-algorithms><evolutionary-algorithms><neat>
Title: How to evaluate a NEAT neural network?
UserDisplayName: Chris
ThreadText: # How to evaluate a NEAT neural network?
  
  (Asked by: username_0 on 2018-05-01)
  
  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)
  
  **Tags:** neural-networks, genetic-algorithms, evolutionary-algorithms, neat
  
  ---
  
  ## 6 answers
  
  ### Answer by username_7 on 2018-05-01. Score: 5 | Accepted answer
  
  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
  
  > **Comments:**
  > **username_0**: Thanks for the reply, okay, I'm not sure if that answers my question, node3 cannot be calculated and node5 cannot be calculated, because they both depend on each other, how can you evaluate either node? Am I missing something?  
  > **username_7**: I don't see how it can't be calculated. The first unresolved value you get is when calculating 5 (3 -> 5).  Considering 0 has a value of .5, 1 has a value of .8, and 3 is unresolved, you may consider the following  v5 = .5 * w0 + .8 * w1 + (3?) * w3 Where the 3? is an unresolved value. I think the hack here is to initialize it to zero so your equation becomes  v5 = .5 * w0 + .8 * w1 + 0 * w3 Reduces to v5 = .5 * w0 + .8 * w1  This can calculate a value for 5 that can be used to calculate 2. You can then calculate 3 from 2. Then the next time 5 is calculated the value wouldn't be zero  
  > **username_0**: That makes sense, ty.  
  > **username_8**: @Chris: NEAT does not *usually* allow backwards connections and loops AFAIK, connections are normally feed-forward. So you are creating more work for yourself here. In principle it can be made to work, and for all I know there are some notes on implementing recurrent NNs in NEAT somewhere. But you may want to consider starting with feed-forward only.  
  > **username_0**: @NeilSlater, So you're saying hidden nodes should not connect with other hidden nodes? Just inputs to hidden, inputs to output and hidden to output?  
  > **username_8**: @Chris - no, I am saying that nodes should not link in a way that causes loops.  
  > **username_8**: @Chris: Actually, from re-reading the documentation, recurrent connections can be quite common and are not necessarily defended against in original NEAT implementations. It seems that the algorithm relies on weeding them out if they are not useful.  
  
  ---
  
  ### Answer by username_1 on 2019-12-16. Score: 5
  
  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 by username_2 on 2019-03-12. Score: 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 by username_3 on 2019-08-08. Score: 2
  
  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 by username_4 on 2019-08-08. Score: 2
  
  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 by username_5 on 2020-12-12. Score: 0
  
  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...
  
  > **Comments:**
  > **username_6**: It's preferable that answers are self-contained, so, rather than linking to another post (in another website), I suggest that you provide the necessary info to answer the question here, in this answer.  
  
  ---
  
  