Answers.Body: <p>So let's first draw the network in each case, for better visualizing the problem:</p>
  <pre><code>Initial:
  ┌─┐
  │A│
  └┬┘
  ┌▽┐
  │B│
  └┬┘
  ┌▽┐
  │C│
  └─┘
  </code></pre>
  <h3>1st Generation:</h3>
  <pre><code>1st Gen
  Mutation #1   Mutation #2
  ┌────┐        ┌────┐
  │A   │        │A   │
  └┬──┬┘        └┬───┘
  ┌▽┐ ┆         ┌▽───┐
  │D│ ┆DIS      │B   │
  └┬┘ ┆         └┬──┬┘
  ┌▽───┐        ┌▽┐ ┆
  │ B  │        │E│ ┆DIS
  └┬───┘        └┬┘ ┆
  ┌▽───┐        ┌▽───┐
  │ C  │        │ C  │
  └────┘        └────┘
  </code></pre>
  <h3>2nd Generation</h3>
  <pre><code>1st Hypothesis (Same Result)
  ┌────┐
  │A   │
  └┬──┬┘
   ┆ ┌▽┐
  DIS│D│
   ┆ └┬┘
  ┌───▽┐
  │B   │
  └┬──┬┘
   ┆ ┌▽┐
  DIS│E│
   ┆ └┬┘
  ┌───▽┐
  │C   │
  └────┘
  </code></pre>
  <p>In order to converge the 2 mutations like this, we would need to:</p>
  <ul>
  <li>Somehow make topology accessible globally.</li>
  <li>Make one mutation search for the population, looking for an occurrence of a similar split.</li>
  </ul>
  <p>Both items go against the principle of evolution, as only 2 mating individuals should trade genetic information.</p>
  <pre><code>2nd Hypothesis (Two Mutants)
  ┌────┐   ┌────┐
  │A   │   │A   │
  └┬──┬┘   └┬──┬┘
   ┆ ┌▽┐    ┆ ┌▽┐
  DIS│D│   DIS│G│
   ┆ └┬┘    ┆ └┬┘
  ┌───▽┐   ┌───▽┐
  │B   │   │B   │
  └┬──┬┘   └┬──┬┘
   ┆ ┌▽┐    ┆ ┌▽┐
  DIS│F│   DIS│E│
   ┆ └┬┘    ┆ └┬┘
  ┌───▽┐   ┌───▽┐
  │C   │   │C   │
  └────┘   └────┘
  
  </code></pre>
  <p>Yes. This 2nd approach is the most usual. Each mutation generates a completely new gene.</p>
  <pre><code>┌────┐
  │A   │
  └┬──┬┘
  ┌▽┐┌▽┐
  │8││D│
  └─┘└┬┘
  ┌───▽┐
  │B   │
  └┬──┬┘
  ┌▽┐┌▽┐
  │u││F│
  └─┘└┬┘
  ┌───▽┐
  │C   │
  └────┘
  
  </code></pre>
  <hr />
  <blockquote>
  <p>Looks like a too complicated genome for the 3-rd generation, doesn't it?</p>
  </blockquote>
  <p>And yes. A 3rd generation <strong>could</strong> theoretically come up like this complicated genome.[1]</p>
  <pre><code>┌───────┐
  │A      │
  └┬──┬──┬┘
  ┌▽┐┌▽┐ ┆
  │G││D│DIS
  └┬┘└┬┘ ┆ 
  ┌▽──▽───┐
  │B      │
  └┬──┬──┬┘
  ┌▽┐┌▽┐ ┆ 
  │F││E│DIS
  └┬┘└┬┘ ┆
  ┌▽──▽───┐   
  │C      │   
  └───────┘   
  </code></pre>
  <p>But keep in mind that more complex structures are naturally harder to train and therefore will not survive if the performance does not justify the complexity.</p>
  <p>[1] - Usually disjoint genes and excess genes (those that do not match) are chosen from the fittest parent. However, in (very specific) cases where 2 parents have the same fit, it could be chosen randomly.</p>
  <p>Main source: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.5457&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.5457&amp;rep=rep1&amp;type=pdf</a></p>
  <hr />
  <p>In the end, you propose an interesting method, to use hashes instead of integers for identifying genes. This is a bold suggestion, and I'm not an expert, so <em>this part is mostly opinionated</em>:</p>
  <p>I believe original genes numeration idea is:</p>
  <ul>
  <li>Inspired on the natural genes sequencing</li>
  <li>For assuring uniqueness genes identifications</li>
  <li>And tracking history changes, just like Git.</li>
  </ul>
  <p>But it could also work using a hash.</p>
  <p>On one side, that could be a great feature, for allowing distant relatives to breed with consistency.
  On the other side, distant relatives tend to have a very different structure and the gene might not be so relevant to them.</p>
  <p>I encourage you to test it. And if it works better than the vanilla, you should release a paper!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-24T05:15:35.140Z
Answers.Text: Thanks for the answer! Specifically 'tracking history changes, just like Git' was what inspired me to think about hashes :) What really changes with hash-based approach is what genes are the same. In my approach more genes are treated as the same (as you see in hypothesis 1). Definitely I have to test both approaches now, I will put results here for you (but do not expect I will do it quickly - it is just a hobby for me)
Answers.UserDisplayName: gerichhome
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-24T05:31:49.403Z
Answers.Text: Great! I have no previous academic experience on Machine Learning, but if you want to publish a paper and want some help, I think I could join you. Anyway, I'm excited to see the results! :)
Answers.UserDisplayName: Andre Goulart
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-23T23:30:40.730Z
Answers.LastActivityDate: 2021-08-23T23:30:40.730Z
Answers.UserDisplayName: Andre Goulart
Body: <p>I have an interesting example for the NEAT and want to clarify what behavior is correct from NEAT's perspective and <strong>why</strong> (why the opposite is wrong, what are the consequences of choosing the different one).</p>
  <p>So let we have an initial network of 3 nodes and 2 edges:</p>
  <h2>Initial Condition</h2>
  <pre><code>Nodes: [A, B, C]
  Edges: {
  1: A-&gt;B
  2: B-&gt;C
  }
  </code></pre>
  <hr />
  <h2>1st Gen</h2>
  <p>Then in the 1-st generation we get 2 mutants:</p>
  <h4>Mutant 1 (edge 1 got split)</h4>
  <pre><code>Nodes: [A, B, C, D]
  Edges: {
  1: A-&gt;B DIS
  2: B-&gt;C
  3: A-&gt;D
  4: D-&gt;B
  }
  </code></pre>
  <h4>Mutant 2 (edge 2 got split)</h4>
  <pre><code>Nodes: [A, B, C, E]
  Edges: {
  1: A-&gt;B
  2: B-&gt;C DIS
  5: B-&gt;E
  6: E-&gt;C
  }
  </code></pre>
  <hr />
  <h2>2nd Gen</h2>
  <p>In the second generation 2 if we mutate Mutant 1 (by splitting edge 2) and mutate Mutant 2 (by splitting edge 1) which result should we get?</p>
  <h4>Hypothesis 1: the same result:</h4>
  <pre><code>Nodes: [A, B, C, D, E]
  Edges: {
  1: A-&gt;B DIS
  2: B-&gt;C DIS
  3: A-&gt;D
  4: D-&gt;B
  5: B-&gt;E
  6: E-&gt;C
  }
  </code></pre>
  <h3>or...</h3>
  <h4>Hypothesis 2: Two new mutants:</h4>
  <pre><code>Nodes: [A, B, C, D, F]
  Edges: {
  1: A-&gt;B DIS
  2: B-&gt;C DIS
  3: A-&gt;D
  4: D-&gt;B
  7: B-&gt;F
  8: F-&gt;C
  }
  </code></pre>
  <p>and</p>
  <pre><code>Nodes: [A, B, C, E, G]
  Edges: {
  1: A-&gt;B DIS
  2: B-&gt;C DIS
  5: B-&gt;E
  6: E-&gt;C
  9: A-&gt;G
  10: G-&gt;B
  }
  </code></pre>
  <hr />
  <p>In case the second hypothesis is correct, how does it deal with crossover in the next run?
  Say these 2 mutants are breeded. We get :</p>
  <h4>Breeding in 2nd Hypothesis</h4>
  <pre><code>Nodes: [A, B, C, D, E, F, G]
  Edges: {
  1: A-&gt;B DIS
  2: B-&gt;C DIS
  3: A-&gt;D
  4: D-&gt;B
  5: B-&gt;E
  6: E-&gt;C
  7: B-&gt;F
  8: F-&gt;C
  9: A-&gt;G
  10: G-&gt;B
  }
  </code></pre>
  <p>Looks like a too complicated genome for the 3-rd generation, doesn't it?</p>
  <p><em>In case the first option is correct then actually innovation numbers are somewhat redundant in NEAT and can be done differently.
  We can have node list as a list of strings (node names).
  Then instead of assigning the innovation number to an edge we can use string value calculated like <code>HASH(fromNodeName + toNodeName)</code>.
  That way whenever the new link is created in any generation between 2 nodes it gets the same innovation <strike>number</strike> name for it.
  When the node is created (by splitting an edge) its name can be taken right from the edge getting split and the innovation names of 2 new edges can be calculated like <code>HASH(fromNodeName + splitEdgeName)</code> and <code>HASH(splitEdgeName + toNodeName)</code>.
  That way the algorithm has no global variables, no shared list of all innovations and can be simply parallelized</em></p>
  
Tags: <neat><neuroevolution>
Title: Different ways to produce the same network in NEAT
UserDisplayName: gerichhome
ThreadText: # Different ways to produce the same network in NEAT
  
  (Asked by: username_0 on 2021-08-16)
  
  I have an interesting example for the NEAT and want to clarify what behavior is correct from NEAT's perspective and why (why the opposite is wrong, what are the consequences of choosing the different one).
  So let we have an initial network of 3 nodes and 2 edges:
  Initial Condition
  Nodes: [A, B, C]
  Edges: {
  1: A->B
  2: B->C
  }
  
  
  1st Gen
  Then in the 1-st generation we get 2 mutants:
  Mutant 1 (edge 1 got split)
  Nodes: [A, B, C, D]
  Edges: {
  1: A->B DIS
  2: B->C
  3: A->D
  4: D->B
  }
  
  Mutant 2 (edge 2 got split)
  Nodes: [A, B, C, E]
  Edges: {
  1: A->B
  2: B->C DIS
  5: B->E
  6: E->C
  }
  
  
  2nd Gen
  In the second generation 2 if we mutate Mutant 1 (by splitting edge 2) and mutate Mutant 2 (by splitting edge 1) which result should we get?
  Hypothesis 1: the same result:
  Nodes: [A, B, C, D, E]
  Edges: {
  1: A->B DIS
  2: B->C DIS
  3: A->D
  4: D->B
  5: B->E
  6: E->C
  }
  
  or...
  Hypothesis 2: Two new mutants:
  Nodes: [A, B, C, D, F]
  Edges: {
  1: A->B DIS
  2: B->C DIS
  3: A->D
  4: D->B
  7: B->F
  8: F->C
  }
  
  and
  Nodes: [A, B, C, E, G]
  Edges: {
  1: A->B DIS
  2: B->C DIS
  5: B->E
  6: E->C
  9: A->G
  10: G->B
  }
  
  
  In case the second hypothesis is correct, how does it deal with crossover in the next run?
  Say these 2 mutants are breeded. We get :
  Breeding in 2nd Hypothesis
  Nodes: [A, B, C, D, E, F, G]
  Edges: {
  1: A->B DIS
  2: B->C DIS
  3: A->D
  4: D->B
  5: B->E
  6: E->C
  7: B->F
  8: F->C
  9: A->G
  10: G->B
  }
  
  Looks like a too complicated genome for the 3-rd generation, doesn't it?
  In case the first option is correct then actually innovation numbers are somewhat redundant in NEAT and can be done differently.
  We can have node list as a list of strings (node names).
  Then instead of assigning the innovation number to an edge we can use string value calculated like HASH(fromNodeName + toNodeName).
  That way whenever the new link is created in any generation between 2 nodes it gets the same innovation number name for it.
  When the node is created (by splitting an edge) its name can be taken right from the edge getting split and the innovation names of 2 new edges can be calculated like HASH(fromNodeName + splitEdgeName) and HASH(splitEdgeName + toNodeName).
  That way the algorithm has no global variables, no shared list of all innovations and can be simply parallelized
  
  **Tags:** neat, neuroevolution
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-08-23. Score: 1 | Accepted answer
  
  So let's first draw the network in each case, for better visualizing the problem:
  Initial:
  ┌─┐
  │A│
  └┬┘
  ┌▽┐
  │B│
  └┬┘
  ┌▽┐
  │C│
  └─┘
  
  1st Generation:
  1st Gen
  Mutation #1   Mutation #2
  ┌────┐        ┌────┐
  │A   │        │A   │
  └┬──┬┘        └┬───┘
  ┌▽┐ ┆         ┌▽───┐
  │D│ ┆DIS      │B   │
  └┬┘ ┆         └┬──┬┘
  ┌▽───┐        ┌▽┐ ┆
  │ B  │        │E│ ┆DIS
  └┬───┘        └┬┘ ┆
  ┌▽───┐        ┌▽───┐
  │ C  │        │ C  │
  └────┘        └────┘
  
  2nd Generation
  1st Hypothesis (Same Result)
  ┌────┐
  │A   │
  └┬──┬┘
   ┆ ┌▽┐
  DIS│D│
   ┆ └┬┘
  ┌───▽┐
  │B   │
  └┬──┬┘
   ┆ ┌▽┐
  DIS│E│
   ┆ └┬┘
  ┌───▽┐
  │C   │
  └────┘
  
  In order to converge the 2 mutations like this, we would need to:
  
  Somehow make topology accessible globally.
  Make one mutation search for the population, looking for an occurrence of a similar split.
  
  Both items go against the principle of evolution, as only 2 mating individuals should trade genetic information.
  2nd Hypothesis (Two Mutants)
  ┌────┐   ┌────┐
  │A   │   │A   │
  └┬──┬┘   └┬──┬┘
   ┆ ┌▽┐    ┆ ┌▽┐
  DIS│D│   DIS│G│
   ┆ └┬┘    ┆ └┬┘
  ┌───▽┐   ┌───▽┐
  │B   │   │B   │
  └┬──┬┘   └┬──┬┘
   ┆ ┌▽┐    ┆ ┌▽┐
  DIS│F│   DIS│E│
   ┆ └┬┘    ┆ └┬┘
  ┌───▽┐   ┌───▽┐
  │C   │   │C   │
  └────┘   └────┘
  
  
  Yes. This 2nd approach is the most usual. Each mutation generates a completely new gene.
  ┌────┐
  │A   │
  └┬──┬┘
  ┌▽┐┌▽┐
  │8││D│
  └─┘└┬┘
  ┌───▽┐
  │B   │
  └┬──┬┘
  ┌▽┐┌▽┐
  │u││F│
  └─┘└┬┘
  ┌───▽┐
  │C   │
  └────┘
  
  
  
  
  Looks like a too complicated genome for the 3-rd generation, doesn't it?
  
  And yes. A 3rd generation could theoretically come up like this complicated genome.[1]
  ┌───────┐
  │A      │
  └┬──┬──┬┘
  ┌▽┐┌▽┐ ┆
  │G││D│DIS
  └┬┘└┬┘ ┆ 
  ┌▽──▽───┐
  │B      │
  └┬──┬──┬┘
  ┌▽┐┌▽┐ ┆ 
  │F││E│DIS
  └┬┘└┬┘ ┆
  ┌▽──▽───┐   
  │C      │   
  └───────┘   
  
  But keep in mind that more complex structures are naturally harder to train and therefore will not survive if the performance does not justify the complexity.
  [1] - Usually disjoint genes and excess genes (those that do not match) are chosen from the fittest parent. However, in (very specific) cases where 2 parents have the same fit, it could be chosen randomly.
  Main source: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.5457&rep=rep1&type=pdf
  
  In the end, you propose an interesting method, to use hashes instead of integers for identifying genes. This is a bold suggestion, and I'm not an expert, so this part is mostly opinionated:
  I believe original genes numeration idea is:
  
  Inspired on the natural genes sequencing
  For assuring uniqueness genes identifications
  And tracking history changes, just like Git.
  
  But it could also work using a hash.
  On one side, that could be a great feature, for allowing distant relatives to breed with consistency.
  On the other side, distant relatives tend to have a very different structure and the gene might not be so relevant to them.
  I encourage you to test it. And if it works better than the vanilla, you should release a paper!
  
  > **Comments:**
  > **username_0**: Thanks for the answer! Specifically 'tracking history changes, just like Git' was what inspired me to think about hashes :) What really changes with hash-based approach is what genes are the same. In my approach more genes are treated as the same (as you see in hypothesis 1). Definitely I have to test both approaches now, I will put results here for you (but do not expect I will do it quickly - it is just a hobby for me)  
  > **username_1**: Great! I have no previous academic experience on Machine Learning, but if you want to publish a paper and want some help, I think I could join you. Anyway, I'm excited to see the results! :)  
  
  ---
  
  