Search code examples
genetic-algorithmneatgenome

NEAT: Speciating

I was trying to implement neat myself, using the original paper but got stuck.

Let's say that in the last generation I had the following species:

Specie 1:     members: 100    avg_score: 100
Specie 2:     members: 150    avg_score: 120
Specie 3:     members: 300    avg_score: 50
Specie 4:     members: 10     avg_score: 110

My attempt right now for the next gen. is the following:

  1. from each species, remove each genome except one random genome.
  2. place each genome in the species / perhaps create a new one

  3. set the score of the specie to the average of the scores of each genome in the specie.

    4.1 reproduce by killing the worst 90% in each specie.

    4.2 choose a specie, based on their score.

    4.3 from that specie, choose 2 genomes and breed a new genome.

I am not sure if this is the correct attempt, especially when I "kill" 90% of the genomes. This percentage value is choosen randomly by me right now (it's just about the concept).

If a specie, after the killing, has 0 members. Did it then go extinct?

In my given example, Specie 4 is likely to go extinct if I kill 90%.

Is my attempt correct, or how does a specie usually go extinct?

Solution

  • Firstly, I would STRONGLY suggest NOT trying to implement NEAT from scratch. It is a much more complex thing to do than it may seem at first (feel free to take a look at the public repositories of the many available implementations).

    Now, to answer your questions more specifically:

    There are many flavours of NEAT. In your case, your doubts seem to deal with the concept of elitism which, yes, is usually a parameter you need to set yourself. Typically the algorithm works like this:

    1. Speciate genomes. That is, arrange them into a given number of species putting those closer to each other together (e.g., k-means speciation).
    2. Select elites. You reserve a given number or percentage of individuals from each specie, and pass them to the new generation. Depending on how you apply this, there will always survive at least one member from each species!
    3. Choose genomes for reproduction, based on fitness (and perhaps on species' fitness as well). This also allows for different specific implementation flavours.
    4. Reproduction. There is asexual reproduction (variations on the chosen genome) and sexual reproduction. Sexual reproduction works by taking genes from two parents (again, different implementations) and then mutating some. There is inter and intra species sexual reproduction (is the other parent from the same species or from a different one), but you are free to disable either.
    5. Re-evaluation of the offspring (set new fitness values).
    6. Speciation.

    Note that speciation is re-applied periodically (typically every generation), so that species don't really have a strong definition (nothing really prevents an elite genome, copied unaltered to the next generation, to be assigned to a new species).

    If you are working with a fixed population size and k-means speciation, there will always be k species, no matter what. In a sense, they are all new species every iteration.