Genetic Algorithm - what is steady state selection?
I'm doing a final year project on genetic algorithms - specifically of the Dawkins Weasel type. I've done roulette selection and tournament selection, still to do steady state selection, but I'm not sure exactly what it is and references I find online are all pretty vague.
Does anyone know how it should be implemented? Any pointers would be great.
Many thanks.
Answer
Typically, the run of a genetic algorithm is divided into generations - each generation your selection and reproduction process replaces all (or at least most) of the population. In a steady state genetic algorithm you only replace a few individuals at a time.
Use a standard selection technique to pick parents to produce these few offspring. Then randomly select the same number of individuals, kill them off, and replace them with the offspring (you could select unfit individuals for death, but that may wipe out population diversity in a non-trivial problem).
You should only evaluate fitness once per individual - after you evaluate the fitness, save it and then reuse that number in the future. Protip: when a new individual is created, flag it as being unevaluated, and then evaluate it the first time it's needed (this way, if an individual is created and then randomly selected for death before being used, you don't consume time evaluating its fitness).
A basic implementation should be fairly simple, but you can check out Essentials of Metaheuristics (pages 45-46, ebook available free).