1
$\begingroup$

I (mis?)understood the NEAT algorithm has the following steps:

  1. Create a genome pool with N random genomes
  2. Calculate each genome fitness
  3. Assign each genome to a species
  4. Calculate the adjusted fitness and the number of offspring of each species
  5. Breed each species through mutation/crossover from the stronger genomes
  6. go to step 2.

Step 3 is tricky: speciation is made placing each genome G in the first species in which it is compatible with the representative genome of that species, or in a new species if G is not compatible with any existing species. Compatible is meant as having compabilitity distance below a certain threshold. Regarding representative genome NEAT paper says:

Each existing species is represented by a random genome inside the species from the previous generation

Somewhere I've found that keeping the number of species stable is good, and this is achieved automatically with dynamic thresholding. However, dynamic thresholding makes hard to evaluate species behaviour across generations.

Let me give one example: Assume that in Generation 20, Species 1 has Genome A as representative and Species 2 has Genome B as representative. Assume elitism is implemented.

As the representative genome is taken from previous generation, assume that in Generation 21, Genome A and B are still representatives for Species 1 and 2, however assume compatibility threshold has changed (i.e. bigger) in order to reach the target species number. With this change, A and B have now a compatibility distance lower than threshold and should be placed in the same Species, however they are representatives of different species.

How to solve this issue?

More in general, with dynamic thresholding, how to make sure species management across generations is consistent? E.g. NEAT paper also says:

If the maximum fitness of a species did not improve in 15 generations, the networks in the stagnant species were not allowed to reproduce.

How to make sure that across all 15 generations, we are still considering that same single species and this has not drastically changed (so that they are actually different 'objects'?). E.g. in the example above, if A and B are both placed in Species 1 in Generation 21, Species 2 no longer represents what it represented in Generation 20.

$\endgroup$
  • 1
    $\begingroup$ In SharpNEAT v2 I dropped the speciation scheme described in the original NEAT paper and replaced it with k-means applied to the genomes (see: sharpneat.sourceforge.net/research/speciation-kmeans.html), however, I believe the speciation approach as a whole remains an untested hypothesis. $\endgroup$ – redcalx Oct 21 '18 at 19:23
0
$\begingroup$

In some implementations, the specie representatives change each generation. This allows for a dynamic definition of what a specie is. If you speciate from scratch(meaning each specie is assigned a new representative) every generation, you won't have the problem where a representative leaves its specie.

$\endgroup$
0
$\begingroup$

I think in the specific case you described if the representatives are now compatible you would move the lower fitness representative into the higher fitness representatives species, then with the remainder of the lower representatives species (all other genomes that didnt have compat distances close enough to move into the other species) you would just randomly pick a new representative and carry on with the process.

$\endgroup$

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.