next up previous

4.2.2 Population Selection     continued...

Roulette wheel selection suffers from the disadvantage of being a high-variance process with the result that there are often large differences between the actual and expected numbers of copies made --- there is no guarantee that the best solution will be copied. De Jong [15] tested an elitist scheme, which gave just such a guarantee by enlarging the population to include a copy of the best solution if it hadn't been retained. He found that on problems with just one maximum (or minimum) the algorithm performance was much improved, but on multimodal problems it was degraded.

Numerous schemes which introduce various levels of determinism into the selection process have been investigated. Overall, it seems that a procedure entitled stochastic remainder selection without replacement offers the best performance. In this, the expected number of copies of each solution is calculated as

Each solution is then copied times, being the integer part of . The fractional remainder

is treated as the probability of further duplication. For example, a solution for which would certainly be copied once and would be copied again with probability 0.8. Each solution is successively subjected to an appropriately weighted simulated coin toss until the new population is complete.