Stagnation
asimaranov opened this issue · 12 comments
Hi! Has there something, like a stagnation in python neat library(http://neat-python.readthedocs.io/en/latest/config_file.html#defaultstagnation-section) , to remove stagnat species?
SharpNEAT 2.x does not have this, but I think SharpNEAT 1.x did (I think the source code is still on sourceforge). Overall I think that might be the wrong solution to the problem of progress stagnation, so e.g. how many generations of no progress should we wait for? Or should we do this based on clock time (because some experiments run much faster than others), and if we remove the species perhaps another species very similar to it will just re-emerge.
In an ideal situation there would be high diversity and new species would take up fitness space and gradually push the stagnant species to be very small and perhaps out of existence altogether. Or maybe a genome in the stagnant species will crossover with one from another species and form a new fitter genome and species - in which case the stagnant species remains stagnant but it was useful to keep it in the population.
My hunch is that finding ways of maintaining diversity is the main issue with NEAT right now, hence the interest in things like novelty search and multi-objectives.
Whether stagnation is absolutely needed or not depends on whether the NEAT implementation makes it possible for a species to go extinct otherwise. NEAT-Python has a minimum species size of 2, and won't put species below this except due to stagnation. I'm currently contemplating some stagnation options that would do something like checking for whether the offspring are going into new species (and possibly for their fitness); if not, then the structural mutation rate may need increasing (something particularly problematic in fractured domains according to a relatively-recent paper by Stanley and others).
Perhaps one approach to stagnation generally is to trigger some large disruptive event in the population as a whole, e.g. a significant change to the objective function. One analogy might be Sarth being hit by an asteroid, changing environmental conditions, wiping out the dinosaurs, etc.
I'm leaning towards use of multiple objectives, so e.g. if you have two objectives and thus fitness scores then each genome can be considered to have a position in a 2D fitness space. Genomes in crowded regions of the space have their fitness lowered in a sort of fuzzy version of fitness sharing in NEAT. That kind of approach is an alternative to speciation based on comparing genomes, but needs research to explore the idea further.
Interesting idea re stagnation; will have to think about that...
NPGA (Niched Pareto GA) is one algorithm in use that does something like that w/regard to multiple objectives.
Thanks for the answer! My problem in that. I'm trying to create 4-legged walker. At start some species trying to get up, but crawling species show much better fitness, and finally all the species begin to crawl. And at some point 'crawlers' are stop showing better results, and population enter the local maximum. I thought that stagnation would help to avoid this.
Another question, Sharpneat 2.x is not a improvement of a Sharpneat 1.x? Is it independent library?
Try using the product of the median body height and the distance for the fitness function. (If it's the entire population, and they start plateauing after all of them do crawling, then stagnation wouldn't help.)
I use a product of specie x and y(height) coordinate as fitness
I'm surprised they don't at least fall over then crawl. That could actually be the seed of something - controlling falling.
@asimaranov - at what point is the height for fitness determined? I'm guessing the x is distance traveled at the end relative to the starting point; how is y defined?
Every unit of I add to local fitness of every creature a production of current x position, and y. After some time I send local fitness, and start new iteration
Unit of time*
In order to encourage them to start trying controlled falling (which is actually what a run is!), you might try not multiplying until the end - accumulate x positions and y positions, add up the former, and multiply by something like the median of the latter. (Or, if you need intermediate fitnesses for some reason, by the median of height so far.) As it is, they have to get all the way to walking - both moving forward and balancing without crawling - all at once.