Search code examples
machine-learningartificial-intelligencegenetic-algorithm

How does the NEAT speciation algorithm work?

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 a explanation of what each component is and what it's doing then that would be great thanks.

The 2 equations are:

$\delta = \frac{c_{1}E}{N} + \frac{c_{2}E}{N} + c_{3} .W$

$f_{i}^{'} = \frac{f_i}{\sum_{j=1}^{n}sh(\delta(i,j))}$

The original paper

Solution

  • Speciation in NEAT is similar to fitness sharing used by other evolutionary algorithms. The idea is to penalize similar solutions, creating a pressure toward a more diverse population.

    The delta term is a measure of distance between two solutions. The measure of distance used here is specialized for the variable-length genomes used by NEAT. Small delta values indicate more similar solutions.

    The sharing function implemented in NEAT results in a value of 0 or 1 if the distance between two solutions is greater or less than a given threshold, respectively. Each solution is compared to each other solution in the candidate population, and the fitness is modified by the sum of resulting sharing function values. If a solution is similar to several other solutions in the population it's modified fitness will be significantly reduced.