How should Stochastic Universal Sampling be combined with Elitism in Genetic Programming?

Question

Having implemented Ranked Selection ("RS") and Stochastic Universal Sampling ("SUS") [Baker, 1987] I'd now like to introduce Elitism (reintroduction of the fittest last-generation members into next-generation) to observe its purported benefits.

There are references to SUS and Elitism being combined, such as by Melanie Mitchell in An Introduction to Genetic Algorithms. However I've come across a (very vague) online reference suggesting combination of the two methods is to be avoided. I wonder whether, in the latter case, an incorrect implementation is the cause of the two methods' incompatibility.

I would therefore be grateful if someone more experienced with GP can provide a description of how SUS and Elitism should be combined. From my knowledge of the two mechanisms, the logical implementation would be to select K fittest individuals from a population size N, then perform SUS over the entire ranked population (including the K elite) but only make N-K selections (instead of the N selections which would take place without elitism).

Is someone able to confirm this proposed implementation is mathematically sound, and the recommended approach?

Answer 1

There is certainly no problem with combining elitism and Stochastic Universal Sampling. I would recommend you read a paper Why use Elitism and Sharing in a Multi-Objective Genetic Algorithm? which specifically addresses the benefits of using elitism in a SUS case.

Furthermore, because it seems you may be interested I know of another paper that focuses more so on the theoretical background of selection functions that you may find of interest (they refer to SUS as roulette wheel selection) The Effects of Selection on Noisy Fitness Optimization

Good luck!