Stochastic Uniform Sampling

I'm not a big fan of roulette wheel selection. I've seen it remove the diversity of a population much to quickly for a solution to be found, and it bothers me that my choice of fitness function can have unintended consequences on selection pressure. However, stochastic uniform sampling appears to be a reasonable alternative while still be a fitness proportional selection mechanism. I'm planning on including it in my Haskell GA library (which is coming along reasonably well) along with tournament selection (and any others I come across).

The idea of stochastic uniform sampling (SUS) is almost the same as roulette wheel selection. The only difference is that while with roulette wheel selection the "roulette wheel" is spun N times (with N the number of individuals in the population) with a single "head" that can land anywhere in the wheel, with SUS the wheel has N "heads" and it is spun once (conceptually). The space between each head is the average fitness of the population. This helps to prevent the resulting population from consisting of only a few very fit individuals, as the average fitness would then be very small, allowing many heads to hit other individuals. Since it is fitness proportional, it is still possible to highly favor a small set of individuals, but it should do much better then roulette wheel at this.

Another way to think of SUS is to imagine the individuals on a line. The line represents the total fitness of the population, and each individual has a segment proportional to its share of the total fitness of the population. Now imagine a comb with equally space teeth (where the space between them is, again, the average population fitness). With the comb's leftmost tooth all the way to the left of the line, move it a random amount to the right, where the distance moved is between 0 and the average population size. Now, select the individual that each tooth of the comb falls within as part of the new population.

My GA library aims to allow the user to select different operators and combine them in any way they desire. This means I need to supply some commonly used mechanisms, and stochastic uniform sampling fits in with this very nicely.