Incorrect behaviour of Elitism

[MarieLanger]

Describe the bug
In the config documentation, it is written that Elitism is “the number of most-fit individuals in each species that will be preserved as-is from one generation to the next.” (https://neat-python.readthedocs.io/en/latest/config_file.html). However, when plotting the mean/max fitness of all species over time (see screenshot below), some species eventually lost their most-fit individual, as seen by the fluctuations of their maximum fitness value. The elitism got set to 5 in my case.

To Reproduce
Looking at the source code of the reproduction-class, I observed that the elitism only gets applied to the non-stagnant species (https://neat-python.readthedocs.io/en/latest/_modules/reproduction.html), which explains the fluctuations.

Proposal regarding behaviour of Elitism
I would therefore like to propose to consider adding an additional boolean parameter to the config-file, by which the user can select whether elitism should be applied to all species, or only to the non-stagnant ones. Depending on the use case, users might want to choose how the elitism gets applied.
For the current implementation of elitism, I observed cases where the total best individual from the whole population got lost due to their species stagnating (e.g. species 5 in the screenshot at generation ~65). Some species also started to worsen in their fitness after loosing their best performing genome (e.g. species 4 in screenshot). This might also be related to this currently open issue:
#271

If adding an additional parameter to the config-file is not possible, I would at least like to propose to either change the description of Elitism to “the number of most-fit individuals in each non-stagnant species that will be preserved as-is from one generation to the next.”, or to apply elitism to all species.

Thank you!

Desktop:

• OS: Windows 10 64-bit
• Version neat-python 0.92

Screenshot:

[CodeReclaimers]

Thank you for the detailed report!

[ntraft]

@MarieLanger Is this actually the reason for the fluctuations you're seeing? If a species is marked as stagnant, then it should not appear in the next generation at all, should it? It generates no spawn. So it seems like there must be some other reason the max fitness is going down.

Is your fitness function actually deterministic? If it were stochastic, this would mean an elite's fitness could change.

[MarieLanger]

@ntraft Stagnant species can still exist in the next generation. "Stagnant" only means that the fitness of a generation is not improving. With the max_stagnation-parameter in the config-file, it is possible to specify the maximum number of generations a species is allowed to be stagnant until it is removed from the population. The default here is 15 (which I used), which means that a species is allowed to not have an increasing fitness for up to 15 generations until it gets removed. How long a species has been stagnant is also printed in the terminal-output under "stag" after each generation.

My fitness function is deterministic. I used neat-python to evolve neural networks that play Super Mario Bros and the fitness here was only dependent on how far the agents got within the level.

[ntraft]

@MarieLanger is_stagnant is only true if the species is being removed in this generation. See this line. "Stagnant" means max_stagnation has been exceeded. Otherwise all species would always "stagnant" except when stag == 0. If you look at the reproduction code here, you can see that only the non-stagnant species (remaining_species) get to spawn, meaning these are the only ones who make it into the next generation. Any species who are not in this list will literally not exist in the new_population. So this is when their line in the plot would terminate.

It seems like there is something more going on. I would also ask whether any part of your actions are stochastic. Or if the simulator itself is stochastic (are you sure that the positions of the enemies are not randomly initialized, and the entire rollout of their behaviors are perfectly deterministic?).

If everything is surely deterministic, then it seems like there is a bug in elitism but it is more subtle than what you've proposed.

[MarieLanger]

@ntraft It seems the definition of "stagnant" is used inconsistently within neat-python then. In the terminal outputs (example see below), "stag" denotes the number of generations a species has not improved in their fitness. Stagnation is also described in the documentation along with the word "stagnation limit", which implied to me that stagnation is not a process that happens once, but instead something that can occur over several generations (see here)

But I see your point, what you said makes sense. From the terminal outputs it was just not clear to me that "stagnation time" means "The time a species has not improved in their fitness, with max_stagnation minus stagnation_time being the time until a species is actually stagnant" (see this line) and not "The time a species has been stagnant", as implied by the variable-name.

Regarding the game, the enemies and items have a fixed position where they always start within the level and they have a fixed logic of how they react e.g. when hitting a block in front of them. Further, the actions of the player (left, right, jump) are only determined by the output of the respective network and nothing else.

---

Population of 31 members in 5 species:
ID   age  size  fitness  adj fit  stag
==== === ==== ======= ======= ====
1   44     9   3650.4    0.394    10
4   42     5    966.0    0.104     5
6   16     5    305.8    0.033     6
7    6     7   2490.3    0.269     5
8    3     5   1654.2    0.179     0
Total extinctions: 0
(not from the same experiment as the plot above, since I did not log all outputs back then)

[ntraft]

Right so it seems we have a deeper issue here. I guess the next thing to look at is to track the actual elite individuals, and figure out what is happening to them. (Is their fitness changing, or are they actually being dropped from the population? Are the elites actually the ones with max fitness? Is the max fitness of each species being reported correctly?)

[bable631]

I am also experiencing this issue with my own population. The simulation that I am running is entirely deterministic; a genome that is run through the simulation will always take the exact same actions every time, but for some reason the maximum fitness keeps dropping. I have monitored it generation by generation, and the species that had the two highest fitness genomes (the ONLY two genomes in that species, in fact) died after two generations of existence. Considering that my elitism value is set to two, both of these genomes should have survived, but instead they simply disappeared. Stagnation was not the cause (I added a print statement to the stagnation just so I know when something stagnates. That species did not, nor was its stagnation value ever near my max stagnation). The species just.., didn't reproduce? The species size remained at two for two generations and then disappeared. It's quite frustrating because those genomes were significantly better than the third best genome.

[th555]

One thing you can do to be absolutely sure that evaluation is deterministic is to cache all fitnesses (with a hash of the genotype or phenotype as a key) after the first evaluation, and use the cached fitness from then on instead of evaluating again. In my case the fitness should be deterministic in theory, but in practice the physics simulator was not really deterministic. I don't think I have seen a decreasing max fitness since I started using a fitness cache with elitism and species_elitism.

[bable631]

The simulation that I am running is entirely mathematics based. I created it specifically to be deterministic, and it's not very complex. I am one hundred percent certain that it is fully deterministic. The problem lies with the reproduction code.

…

On Friday, October 20, 2023, th555 ***@***.***> wrote: One thing you can do to be absolutely sure that evaluation is deterministic is to cache all fitnesses (with a hash of the genotype or phenotype as a key) after the first evaluation, and use the cached fitness from then on instead of evaluating again. In my case the fitness should be deterministic in theory, but in practice the physics simulator was not really deterministic. I don't think I have seen a decreasing max fitness since I started using a fitness cache with elitism and species_elitism. — Reply to this email directly, view it on GitHub <#272 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADE5WPFWO7KYIYGWPJKUN7DYALFVFAVCNFSM6AAAAAA2UU5JBSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTONZTGI4DGMZYGQ> . You are receiving this because you commented.Message ID: ***@***.***>