Answers.Body: <p>Even if this thread is old i want to add something to your answer, regarding to the second formula. The fitness sharing mechanism works like this:</p>
  <pre><code>foreach(s in species):
     foreach(i in s.individuals):
        i.fitness /= s.Count;
  </code></pre>
  <p>So in each species, the adjusted fitness of an individual is divided by the &quot;clients&quot; in that species. Why? This is how the formula works:</p>
  <ul>
  <li>f'[i] is the adjusted/shared fitness of agent i</li>
  <li>f[i] is the current fitness of agent i</li>
  <li>sh(i,j) returns 1 if both i &amp; j are compatible (considering the first formula your provided does not exceed the threshold) or 0 otherwise.</li>
  <li>Sum(sh(i,j)) just counts how many individuals are in the same species with i, plus itself (because i can be equal to j while parsing through Sigma). So if you have a Species class with a List of clients, Sum(...) is just list.Count.</li>
  </ul>
  <p>Everything is explained clearly in Stanley's paper at page 110.</p>
  <p>In this situation, the average fitness of a species is just the sum of all clients' adjusted fitness.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-02T18:59:38.400Z
Answers.LastActivityDate: 2023-03-02T19:01:42.037Z
Answers.LastEditDate: 2023-03-02T19:01:42.037Z
Answers.UserDisplayName: Formula PS4
Answers.Body: <p>The first equation deals with distance. <strong>Delta</strong>, or distance, is the measure of how <strong>compatible</strong> two genomes are with each other. <code>c1</code>, <code>c2</code> and <code>c3</code> are parameters you set to dictate the importance of <code>E</code>,  <code>D</code> and <code>W</code>. Note that if you change c<code>c1</code>, <code>c2</code> or <code>c3</code>, you will most likely also have to change dt, which is the distance threshold, or the maximum distance apart 2 genomes can be before they are separated into different species. <code>E</code> represents the total number of <strong>excess</strong> genes. <code>D</code> represents the total number of <strong>disjoint</strong> genes in both genomes, <code>W</code> represents the total <strong>weight difference</strong> between genes that match, and finally, <code>N</code> represents the number of connections / genes the genome with the larger number of connections has. For example, take the following 2 genomes:</p>
  
  <pre><code>[[1,.25][2,.55],[4,.78],[6,.2]]
  and
  [[1,.15][3,.92],[5,.37]]
  </code></pre>
  
  <p>Where the 0 index represents innovation number and the 1 index represents weight value. <code>E</code>  would be 1, since there is 1 excess gene, gene <code>6</code>. <code>D</code> would be 4, since connections <code>2</code> and <code>4</code> are not in genome 2, and connections <code>3</code> and <code>5</code> are not in genome 1. <code>W</code> would be .10, since only connection <code>1</code> is shared between the two genomes.</p>
  
  <p>The second formula is a bit more complicated. From my understanding, correct me if I'm wrong, this is a formula for adjusting fitness. <code>f′i</code> is the adjusted fitness, which will replace the original fitness, <code>fi</code>. For every genome <code>j</code> in the <strong>entire population</strong>, yes, entire population and not just every genome in its specie, it will calculate the distance between <code>j</code> and <code>i</code>, <code>i</code> being the genome of fitness <code>fi</code>. Then it will sum up all the distance    values, and divide the original fitness <code>fi</code> by the total distance sum, and set <code>f'i</code> to that. Next,</p>
  
  <blockquote>
    <p>Every species is
    assigned a potentially different number of offspring in proportion to the sum of adjusted fitnesses <code>f`i</code> of its member organisms.</p>
  </blockquote>
  
  <p>This assigning of number of species offspring is used so that one specie can't take over the entire population, which is the whole point of speciation in the first place, so in conclusion, these two formulas are vital to the function and efficiency of the NEAT algorithm.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-14T19:30:11.753Z
Answers.Text: This all makes so much sense now, thankyou. It's been a while since I've had a look at the paper or even done anything with NEAT so I'm going to have to have a refresher to get up to speed with the rest of it . Again, thanks very much.
Answers.UserDisplayName: Aguy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-15T14:24:16.957Z
Answers.Text: This is a great explaination, although it should be noted that the divisor in the second function (the summation) reduces to the number of genomes in the same species as i, so you can speciate first and find the genomes shared fitness by simply dividing it by the number of genomes in this species, this prevents any one species from growing to large and taking over a population as reproduction is based of the shared fitness of the genomes. TLDR the larger a species gets the higher the divisor in the shared fitness function will be and thus will get a lower shared fitness.
Answers.UserDisplayName: nickw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-15T14:40:16.353Z
Answers.Text: Adding to this your correct on the S(i,j) part but the sh() function which applies the distance threshold from the speciation implies that this summation is reduced to the number of genomes in the species (apologies for not expounding on this above)
Answers.UserDisplayName: nickw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-07T14:32:50.343Z
Answers.Text: This is an awesome answer, very clear. There's still something that could be improved though: when defining `W` with only 1 gene in common, it's hard to understand whether it's just a sum or an average difference. The process of speciation is also not very clear, beyond just the distance formula, how does it work in a population at time t, and how do you progress from t to t+1?
Answers.UserDisplayName: Sheraff
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-13T18:24:48.027Z
Answers.LastActivityDate: 2019-08-13T18:24:48.027Z
Answers.UserDisplayName: Terry T.
Body: <p>I've been reading up on how NEAT (Neuro Evolution of Augmenting Topologies) works and I've got the main idea of it, but one thing that's been bothering me is how you split the different networks into species. I've gone through the algorithm but it doesn't make a lot of sense to me and the paper I read doesn't explain it very well either so if someone could give an explanation of what each component is and what it's doing then that would be great thanks.</p>
  
  <p>The two equations are:</p>
  
  <p><span class="math-container">$\delta = \frac{c_{1}E}{N} + \frac{c_{2}D}{N} + c_{3} .\overline{W}$</span></p>
  
  <p><span class="math-container">$f_{i}^{'} = \frac{f_i}{\sum_{j=1}^{n}sh(\delta(i,j))}$</span></p>
  
  <p>By the way, I can understand the greek symbols so you don't need to explain those to me</p>
  
  <p><a href="http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf" rel="nofollow noreferrer">The original paper</a></p>
  
Tags: <neural-networks><machine-learning><neat>
Title: How does the NEAT speciation algorithm work?
UserDisplayName: Aguy
ThreadText: # How does the NEAT speciation algorithm work?
  
  (Asked by: username_0 on 2018-12-16)
  
  I've been reading up on how NEAT (Neuro Evolution of Augmenting Topologies) works and I've got the main idea of it, but one thing that's been bothering me is how you split the different networks into species. I've gone through the algorithm but it doesn't make a lot of sense to me and the paper I read doesn't explain it very well either so if someone could give an explanation of what each component is and what it's doing then that would be great thanks.
  
  The two equations are:
  
  $\delta = \frac{c\_{1}E}{N} + \frac{c\_{2}D}{N} + c\_{3} .\overline{W}$
  
  $f\_{i}^{'} = \frac{f\_i}{\sum\_{j=1}^{n}sh(\delta(i,j))}$
  
  By the way, I can understand the greek symbols so you don't need to explain those to me
  
  [The original paper](http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf)
  
  **Tags:** neural-networks, machine-learning, neat
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-08-13. Score: 6 | Accepted answer
  
  The first equation deals with distance. **Delta**, or distance, is the measure of how **compatible** two genomes are with each other. `c1`, `c2` and `c3` are parameters you set to dictate the importance of `E`, `D` and `W`. Note that if you change c`c1`, `c2` or `c3`, you will most likely also have to change dt, which is the distance threshold, or the maximum distance apart 2 genomes can be before they are separated into different species. `E` represents the total number of **excess** genes. `D` represents the total number of **disjoint** genes in both genomes, `W` represents the total **weight difference** between genes that match, and finally, `N` represents the number of connections / genes the genome with the larger number of connections has. For example, take the following 2 genomes:
  
  ```
  [[1,.25][2,.55],[4,.78],[6,.2]]
  and
  [[1,.15][3,.92],[5,.37]]
  
  ```
  
  Where the 0 index represents innovation number and the 1 index represents weight value. `E` would be 1, since there is 1 excess gene, gene `6`. `D` would be 4, since connections `2` and `4` are not in genome 2, and connections `3` and `5` are not in genome 1. `W` would be .10, since only connection `1` is shared between the two genomes.
  
  The second username_1 is a bit more complicated. From my understanding, correct me if I'm wrong, this is a username_1 for adjusting fitness. `f′i` is the adjusted fitness, which will replace the original fitness, `fi`. For every genome `j` in the **entire population**, yes, entire population and not just every genome in its specie, it will calculate the distance between `j` and `i`, `i` being the genome of fitness `fi`. Then it will sum up all the distance values, and divide the original fitness `fi` by the total distance sum, and set `f'i` to that. Next,
  
  > Every species is
  > assigned a potentially different number of offspring in proportion to the sum of adjusted fitnesses `f`i` of its member organisms.
  
  This assigning of number of species offspring is used so that one specie can't take over the entire population, which is the whole point of speciation in the first place, so in conclusion, these two formulas are vital to the function and efficiency of the NEAT algorithm.
  
  > **Comments:**
  > **username_0**: This all makes so much sense now, thankyou. It's been a while since I've had a look at the paper or even done anything with NEAT so I'm going to have to have a refresher to get up to speed with the rest of it . Again, thanks very much.  
  > **username_3**: This is a great explaination, although it should be noted that the divisor in the second function (the summation) reduces to the number of genomes in the same species as i, so you can speciate first and find the genomes shared fitness by simply dividing it by the number of genomes in this species, this prevents any one species from growing to large and taking over a population as reproduction is based of the shared fitness of the genomes. TLDR the larger a species gets the higher the divisor in the shared fitness function will be and thus will get a lower shared fitness.  
  > **username_3**: Adding to this your correct on the S(i,j) part but the sh() function which applies the distance threshold from the speciation implies that this summation is reduced to the number of genomes in the species (apologies for not expounding on this above)  
  > **username_4**: This is an awesome answer, very clear. There's still something that could be improved though: when defining `W` with only 1 gene in common, it's hard to understand whether it's just a sum or an average difference. The process of speciation is also not very clear, beyond just the distance username_1, how does it work in a population at time t, and how do you progress from t to t+1?  
  
  ---
  
  ### Answer by username_1 on 2023-03-02. Score: 0
  
  Even if this thread is old i want to add something to your answer, regarding to the second username_1. The fitness sharing mechanism works like this:
  
  ```
  foreach(s in species):
     foreach(i in s.individuals):
        i.fitness /= s.Count;
  
  ```
  
  So in each species, the adjusted fitness of an individual is divided by the "clients" in that species. Why? This is how the username_1 works:
  
  * f'[i] is the adjusted/shared fitness of agent i
  * f[i] is the current fitness of agent i
  * sh(i,j) returns 1 if both i & j are compatible (considering the first username_1 your provided does not exceed the threshold) or 0 otherwise.
  * Sum(sh(i,j)) just counts how many individuals are in the same species with i, plus itself (because i can be equal to j while parsing through Sigma). So if you have a Species class with a List of clients, Sum(...) is just list.Count.
  
  Everything is explained clearly in Stanley's paper at page 110.
  
  In this situation, the average fitness of a species is just the sum of all clients' adjusted fitness.
  
  
  ---
  
  