Answers.Body: <blockquote>
    <ol>
    <li>What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?</li>
    </ol>
  </blockquote>
  
  <p>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.</p>
  
  <blockquote>
    <ol start="2">
    <li>Is there a reason for storing the type of a node (input, hidden, output)?</li>
    </ol>
  </blockquote>
  
  <p>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.</p>
  
  <blockquote>
    <ol start="3">
    <li>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.)</li>
    </ol>
  </blockquote>
  
  <p>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.</p>
  
  <blockquote>
    <ol start="4">
    <li>How could I limit the mutation functions to not add backpropagation connections?</li>
    </ol>
  </blockquote>
  
  <p>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.</p>
  
  <p>As a note, we can prevent recurrent connections but often times allowing them provides opportunities to find a better solution (as @PaulG comments)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-09T12:57:12.930Z
Answers.Text: 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.
Answers.UserDisplayName: PaulG
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-03T05:51:42.650Z
Answers.Text: @PaulG - I was just trying to answer the question, but I can see why it might be confusing. Edited, thanks
Answers.UserDisplayName: Andrew Butler
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-15T21:27:12.220Z
Answers.Text: 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.
Answers.UserDisplayName: Angel.King.47
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-03-31T17:51:46.430Z
Answers.LastActivityDate: 2019-10-03T05:50:40.680Z
Answers.LastEditDate: 2019-10-03T05:50:40.680Z
Answers.UserDisplayName: Andrew Butler
Body: <p>I've recently read the paper <a href="http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf" rel="nofollow noreferrer">Evolving Neural Networks through Augmenting Topologies</a> which introduces NEAT. I am now trying to prototype it myself in JavaScript. However, I stumbled across a few questions I can't answer.</p>
  
  <ol>
  <li><p>What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?</p>
  
  <blockquote>
    <p>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</p>
  </blockquote></li>
  <li><p>Is there a reason for storing the type of a node (input, hidden, output)?</p></li>
  <li><p>In the original paper, only connections have an innovation number, but in <a href="http://www.automatonsadrift.com/neat/" rel="nofollow noreferrer">other sources</a>, nodes do as well. Is this necessary for the crossover? (This has already been asked <a href="https://ai.stackexchange.com/q/5496/2444">here</a>.)</p></li>
  <li><p>How could I limit the mutation functions to not add recurrent connections?</p></li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-07T19:42:09.333Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <neural-networks><genetic-algorithms><evolutionary-algorithms><neat><neuroevolution>
Title: Several questions regarding the NEAT algorithm
UserDisplayName: Nigk
ThreadText: # Several questions regarding the NEAT algorithm
  
  (Asked by: username_0 on 2018-03-30)
  
  I've recently read the paper [Evolving Neural Networks through Augmenting Topologies](http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf) 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](http://www.automatonsadrift.com/neat/), nodes do as well. Is this necessary for the crossover? (This has already been asked [here](https://ai.stackexchange.com/q/5496/2444).)
  4. How could I limit the mutation functions to not add recurrent connections?
  
  **Tags:** neural-networks, genetic-algorithms, evolutionary-algorithms, neat, neuroevolution
  > **Comments:**
  > **username_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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-03-31. Score: 3 | Accepted 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?
  
  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.
  
  > 2. 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.
  
  > 3. 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.
  
  > 4. 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)
  
  > **Comments:**
  > **username_4**: 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.  
  > **username_3**: 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.  
  > **username_2**: @PaulG - I was just trying to answer the question, but I can see why it might be confusing. Edited, thanks  
  
  ---
  
  