5
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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 cc1, 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 formula is a bit more complicated. From my understanding, correct me if I'm wrong, this is a formula 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Aguy
    Aug 14, 2019 at 19:30
  • 2
    $\begingroup$ 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. $\endgroup$
    – nickw
    Aug 15, 2019 at 14:24
  • 2
    $\begingroup$ 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) $\endgroup$
    – nickw
    Aug 15, 2019 at 14:40
  • $\begingroup$ 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? $\endgroup$
    – Sheraff
    Jan 7, 2020 at 14:32
0
$\begingroup$

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:

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 formula 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 formula 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .