Answers.Body: <p>NEAT does not employ a feed forward concept and also it does not take any special action to avoid loops.</p>
  <p>Network is evaluated in non-recursive model. The only non-deterministic loop, the evaluation has is the loop for activating all the outputs. Pseudo code is something like this,</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>NOTE1: You can use a defensive mechanism (like a counter) to avoid a infinite loop</p>
  <p>NOTE2: When summing the input, outputs of nodes which were at least evaluated/calculated once are considered, otherwise their outputs are assumed to be zero.</p>
  <p>This is the note from the author of NEAT about identifying loops,</p>
  <blockquote>
  <p>Note that checking networks for loops in general in not necessary and therefore I stopped writing this function</p>
  <p>bool Network::integrity()</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T11:22:09.493Z
Answers.Text: I don't think that we are on the same page. If node A has a connection to node B and node B has a connection to node A you can't get the input of node A because it depends on it self. You added a note to stop infinite loops but how would you calculate the initial iteration?
Answers.UserDisplayName: Emad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T03:41:17.057Z
Answers.Text: @Emad, I have added another note regarding how NEAT handles the dependent value issue. That is: When summing the input, outputs of nodes which were at least evaluated/calculated once are considered, otherwise their outputs are assumed to be zero.
Answers.UserDisplayName: Morpheus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T04:02:00.530Z
Answers.Text: For example, suppose both A and B has links from sensors (actual input layer), in the first iteration of outer loop, A's input summing disregards B's output since B is not evaluated yet. And B does the same since A's output is not evaluated yet. Then both A and B calculate their outputs in the second inner loop. Then in the second iteration of outer loop, both A and B consider each other's outputs from first iteration. So you see this continues without an issue. Let me know if you need more clarification
Answers.UserDisplayName: Morpheus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T04:55:28.040Z
Answers.Text: Ok great. Now I understand. Can you please cite any reference for this. This is same as the first approach that I mentioned in the OP. But I fail to verify this in literature.
Answers.UserDisplayName: Emad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T13:24:57.263Z
Answers.Text: Literature fails to express all these implementation details I guess. However next valid reference we can take is the original source code, which is http://nn.cs.utexas.edu/?neat-c
Answers.UserDisplayName: Morpheus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T07:50:25.003Z
Answers.LastActivityDate: 2019-12-18T03:38:05.850Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Morpheus
Answers.Body: <p>You can use a feed forward style network, so that every node outputs to a higher node except output nodes. This will eliminate connection loops.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-13T06:24:01.957Z
Answers.Text: "higher" in what sense? Innovation number? or something else?
Answers.UserDisplayName: Emad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-13T13:06:54.793Z
Answers.Text: Yes, identification number or innovation number.
Answers.UserDisplayName: Terry T.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-14T14:17:35.970Z
Answers.Text: Ok but innovation number is not actually a measure of being later in the feed network. i.e. a new connection can form before one of the existing ones yet take higher innovation number.
Answers.UserDisplayName: Emad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-14T20:43:24.640Z
Answers.Text: Whoops it is actually this: a new connection is formed only when the first node is is closer to the input then the second node, or the fewest number of connections to get to the input is greater in the second node. Another question simailar to this can be found here https://ai.stackexchange.com/questions/6231/how-to-evaluate-a-neat-neural-network
Answers.UserDisplayName: Terry T.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-15T19:05:57.263Z
Answers.Text: I see. Yet in the literature it's a bit different. I appreciate your solution.
Answers.UserDisplayName: Emad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-13T04:24:21.347Z
Answers.LastActivityDate: 2019-08-13T04:24:21.347Z
Answers.UserDisplayName: Terry T.
Answers.Body: <p>This is what I do:</p>
  <p>During evaluation, I add visited counters to nodes and keep the paths.</p>
  <p>If we go [1i-5h-7h-4o-5h], 5h is visited twice, so</p>
  <p>I detect the loop [5h-7h-4o-5h] and mark the [4o-5h] connection as a loop.</p>
  <p>Then I let it continue evaluating.</p>
  <p>[1i-5h-7h-4o-5h-7h-4o] and 4o can't go to 5h again because it was marked as a loop.</p>
  <p>This way you don't avoid or ignore loops, you add them to your evaluation as a kind of memory.</p>
  <p>This is consistent with the stanley 02 paper</p>
  <p>Introduction Paragraph 1</p>
  <pre><code>In addition, memory is easily repre-
  sented through recurrent connections in neural networks, making NE a natural choice
  for learning non-Markovian tasks (Gomez and Miikkulainen, 1999, 2002).
  </code></pre>
  <p>He references recurrent connections being used as &quot;memory&quot;.</p>
  <p>Page 122 Figure 8 subtext:</p>
  <pre><code>A NEAT solution to the DPNV problem. This clever solution works by taking
  the derivative of the difference in pole angles. Using the recurrent connection to itself,
  the single hidden node determines whether the poles are falling away or towards each
  other.
  </code></pre>
  <p>So this recurrent connection should not be avoided, in fact it is required for the given solution.</p>
  <p>This is why I evaluate them once.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-31T06:57:38.720Z
Answers.LastActivityDate: 2022-08-31T06:57:38.720Z
Answers.UserDisplayName: nurettin
Body: <p>I'm working on my own implementation of NEAT algorithm based on the original 2002 paper called "<a href="http://nn.cs.utexas.edu/downloads/papers/stanley.gecco02_1.pdf" rel="nofollow noreferrer">Efficient Reinforcement Learning through Evolving Neural Network Topologies</a>" (by Kenneth O. Stanley and Risto Miikkulainen). The way the algorithm is designed it may generate loops in connection of hidden layer. Which obviously will cause difficulties in calculating the output.</p>
  
  <p>I have searched and came across two types of approaches. One set like this <a href="https://ai.stackexchange.com/q/6231/2444">example</a> claim that the value should be calculated like a time series usually seen in RNNs and the circular nodes should use "old" values as their "current" output. But, this seems wrong since the training data is not always ordered and the previous value has nothing to do with current one.</p>
  
  <p>A second group like this <a href="https://ai.stackexchange.com/q/6329/2444">example</a> claim that the structure should be pruned with some method to avoid loops and cycles. This approach apart from being really expensive to do, is also against the core idea of the algorithm. Deleting connections like this may cause later structural changes.</p>
  
  <p>I my self have so far tried setting the unknown forward values as 0 and this hides the connection (as whatever weight it has will have no effect on the result) but have failed also for two reasons. One is my networks get big quickly destroying the "smallest network required" idea and also not good results.</p>
  
  <p>What is the correct approach? </p>
  
Tags: <neat>
Title: How do you implement NEAT by taking into account the loops?
UserDisplayName: Emad
ThreadText: # How do you implement NEAT by taking into account the loops?
  
  (Asked by: username_0 on 2019-02-17)
  
  I'm working on my own implementation of NEAT algorithm based on the original 2002 paper called "[Efficient Reinforcement Learning through Evolving Neural Network Topologies](http://nn.cs.utexas.edu/downloads/papers/stanley.gecco02_1.pdf)" (by Kenneth O. Stanley and Risto Miikkulainen). The way the algorithm is designed it may generate loops in connection of hidden layer. Which obviously will cause difficulties in calculating the output.
  
  I have searched and came across two types of approaches. One set like this [example](https://ai.stackexchange.com/q/6231/2444) claim that the value should be calculated like a time series usually seen in RNNs and the circular nodes should use "old" values as their "current" output. But, this seems wrong since the training data is not always ordered and the previous value has nothing to do with current one.
  
  A second group like this [example](https://ai.stackexchange.com/q/6329/2444) claim that the structure should be pruned with some method to avoid loops and cycles. This approach apart from being really expensive to do, is also against the core idea of the algorithm. Deleting connections like this may cause later structural changes.
  
  I my self have so far tried setting the unknown forward values as 0 and this hides the connection (as whatever weight it has will have no effect on the result) but have failed also for two reasons. One is my networks get big quickly destroying the "smallest network required" idea and also not good results.
  
  What is the correct approach?
  
  **Tags:** neat
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-12-16. Score: 2
  
  NEAT does not employ a feed forward concept and also it does not take any special action to avoid loops.
  
  Network is evaluated in non-recursive model. The only non-deterministic loop, the evaluation has is the loop for activating all the outputs. Pseudo code is something like this,
  
  ```
  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
  
  ```
  
  NOTE1: You can use a defensive mechanism (like a counter) to avoid a infinite loop
  
  NOTE2: When summing the input, outputs of nodes which were at least evaluated/calculated once are considered, otherwise their outputs are assumed to be zero.
  
  This is the note from the author of NEAT about identifying loops,
  
  > Note that checking networks for loops in general in not necessary and therefore I stopped writing this function
  >
  > bool Network::integrity()
  
  > **Comments:**
  > **username_0**: I don't think that we are on the same page. If node A has a connection to node B and node B has a connection to node A you can't get the input of node A because it depends on it self. You added a note to stop infinite loops but how would you calculate the initial iteration?  
  > **username_1**: @username_0, I have added another note regarding how NEAT handles the dependent value issue. That is: When summing the input, outputs of nodes which were at least evaluated/calculated once are considered, otherwise their outputs are assumed to be zero.  
  > **username_1**: For example, suppose both A and B has links from sensors (actual input layer), in the first iteration of outer loop, A's input summing disregards B's output since B is not evaluated yet. And B does the same since A's output is not evaluated yet. Then both A and B calculate their outputs in the second inner loop. Then in the second iteration of outer loop, both A and B consider each other's outputs from first iteration. So you see this continues without an issue. Let me know if you need more clarification  
  > **username_0**: Ok great. Now I understand. Can you please cite any reference for this. This is same as the first approach that I mentioned in the OP. But I fail to verify this in literature.  
  > **username_1**: Literature fails to express all these implementation details I guess. However next valid reference we can take is the original source code, which is http://nn.cs.utexas.edu/?neat-c  
  
  ---
  
  ### Answer by username_2 on 2019-08-13. Score: 1
  
  You can use a feed forward style network, so that every node outputs to a higher node except output nodes. This will eliminate connection loops.
  
  > **Comments:**
  > **username_0**: "higher" in what sense? Innovation number? or something else?  
  > **username_2**: Yes, identification number or innovation number.  
  > **username_0**: Ok but innovation number is not actually a measure of being later in the feed network. i.e. a new connection can form before one of the existing ones yet take higher innovation number.  
  > **username_2**: Whoops it is actually this: a new connection is formed only when the first node is is closer to the input then the second node, or the fewest number of connections to get to the input is greater in the second node. Another question simailar to this can be found here https://ai.stackexchange.com/questions/6231/how-to-evaluate-a-neat-neural-network  
  > **username_0**: I see. Yet in the literature it's a bit different. I appreciate your solution.  
  
  ---
  
  ### Answer by username_3 on 2022-08-31. Score: 0
  
  This is what I do:
  
  During evaluation, I add visited counters to nodes and keep the paths.
  
  If we go [1i-5h-7h-4o-5h], 5h is visited twice, so
  
  I detect the loop [5h-7h-4o-5h] and mark the [4o-5h] connection as a loop.
  
  Then I let it continue evaluating.
  
  [1i-5h-7h-4o-5h-7h-4o] and 4o can't go to 5h again because it was marked as a loop.
  
  This way you don't avoid or ignore loops, you add them to your evaluation as a kind of memory.
  
  This is consistent with the stanley 02 paper
  
  Introduction Paragraph 1
  
  ```
  In addition, memory is easily repre-
  sented through recurrent connections in neural networks, making NE a natural choice
  for learning non-Markovian tasks (Gomez and Miikkulainen, 1999, 2002).
  
  ```
  
  He references recurrent connections being used as "memory".
  
  Page 122 Figure 8 subtext:
  
  ```
  A NEAT solution to the DPNV problem. This clever solution works by taking
  the derivative of the difference in pole angles. Using the recurrent connection to itself,
  the single hidden node determines whether the poles are falling away or towards each
  other.
  
  ```
  
  So this recurrent connection should not be avoided, in fact it is required for the given solution.
  
  This is why I evaluate them once.
  
  
  ---
  
  