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

$\endgroup$
1
$\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.

$\endgroup$
  • $\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 at 19:30
  • 1
    $\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 at 14:24
  • 1
    $\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 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.