5

I've recently read the paper Evolving Neural Networks through Augmenting Topologies which introduces NEAT. I am now trying to prototype it myself in JavaScript. However, I stumbled across a few questions I can't answer.

  1. What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?

    However, by keeping a list of the innovations that occurred in the current generation, it is possible to ensure that when the same structure arises more than once through independent mutations in the same generation, each identical mutation is assigned the same innovation number

  2. Is there a reason for storing the type of a node (input, hidden, output)?

  3. In the original paper, only connections have an innovation number, but in other sources, nodes do as well. Is this necessary for the crossover? (This has already been asked here.)

  4. How could I limit the mutation functions to not add recurrent connections?

nbro
  • 39,006
  • 12
  • 98
  • 176
Nigk
  • 63
  • 1
  • 6
  • 1
    These questions were also asked on Stack Overflow: [https://stackoverflow.com/q/49589689/3924118](https://stackoverflow.com/q/49589689/3924118). Please, next time, **ask only one question per post**, even if the questions are related. – nbro Jul 07 '19 at 19:42

1 Answers1

3
  1. What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?

Structural innovation is anything added that changes the topology of the network. So a structural innovation is any added connection or added node. I don't want to get too much into the implementation, but something similar to a dictionary global variable will work. When adding a connection (or node) between two nodes, we check if a connection (or node) has ever been placed between these two nodes before. If it has then we have stored an innovation number for what this connection (or node) is identical and we set its innovation number to that. We identify each node by its number.

  1. Is there a reason for storing the type of a node (input, hidden, output)?

Yes, there are many structural innovations that we do not want to happen. An innovation between two input node or an innovation between two output nodes are two examples of structural innovations we don't want.

  1. In the original paper, only connections have an innovation number, but in other sources, nodes do as well. Is this necessary for crossover? (This has already been asked here.)

Although I am unsure if it is explicitly stated, it is implied that nodes have an identifying number. You can see this in Figure 2 and 3 of the paper where each node is labeled with a number.

  1. How could I limit the mutation functions to not add backpropagation connections?

By backpropagation connections I assume you mean recurrent connections (correct me if I am wrong). You can prevent recurrent connections in many ways, but one way is to maintain a partially ordered set. When adding a connection between two nodes you check to see the order of those two nodes in the partially ordered set. The one that comes first will be the node from which the connection starts, while the second will be the node at which the connection ends.

As a note, we can prevent recurrent connections but often times allowing them provides opportunities to find a better solution (as @PaulG comments)

Andrew Butler
  • 587
  • 3
  • 10
  • Node has a number not an innovation number, especially in figure 2. Do you mean the number of the node being equivalent to the innovation number of the connection. – Angel.King.47 Jan 15 '19 at 21:27
  • Andrew Butler - In the paper, http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf the author states (on page 106) that recurrent connections can happen. And on pages 121-122 they demonstrate how a recurrent connection created a clever solution to the DPNV problem. – PaulG Aug 09 '19 at 12:57
  • @Angel.King.47 - edited, thanks – Andrew Butler Oct 03 '19 at 05:42
  • @PaulG - I was just trying to answer the question, but I can see why it might be confusing. Edited, thanks – Andrew Butler Oct 03 '19 at 05:51