# How do you implement NEAT by taking into account the loops?

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" (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 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 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?

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()

• 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?
Dec 16, 2019 at 11:22
• @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. Dec 18, 2019 at 3:41
• 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 Dec 18, 2019 at 4:02
• 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.
Dec 18, 2019 at 4:55
• Literature fails to express all these implementation details I guess. However next valid reference we can take is the original source code, which is nn.cs.utexas.edu/?neat-c Dec 18, 2019 at 13:24

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.

• "higher" in what sense? Innovation number? or something else?
Aug 13, 2019 at 6:24
• Yes, identification number or innovation number. Aug 13, 2019 at 13:06
• 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.
Aug 14, 2019 at 14:17
• 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 ai.stackexchange.com/questions/6231/… Aug 14, 2019 at 20:43
• I see. Yet in the literature it's a bit different. I appreciate your solution.
Aug 15, 2019 at 19:05

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.