Roulette-wheel selection in Genetic algorithm. Population needs to be sorted first?

Question

Hi all. In a genetic algorithm, when selecting members for crossover using roulette-wheel selection method, does the population first need to be sorted by fitness rank?

The possibilities seem to be:

1. sort population first by ascending fitness
2. sort population by descending fitness
3. don't sort population & let the roulette ball fall where it may..

I'm thinking that sorting either way may have no effect - a pebble landing at random on a wheel containing different sized (by fitness) slices will have exactly the same outcome chance whether the larger slices are grouped together or not. But I'm not 100% convinced.

What do you think?

The need to do a sort every generation affects the speed of the algorithm too, so I'd prefer not to (I would do a sort if using elitism, but I'm not in this case). Thanks if you know, as I cannot find a definitive answer via google etc..

Answer 1

No, you don't actually need to sort them. You are exactly correct that it will have no effect if the higher-ranked members are grouped together or not (at least with a good random number generator :) ).

Your intuition is dead on here - statistically, it will have no effect to sort, and as you mention, you don't have to waste a bunch of time and effort sorting things!

Answer 2

You do not need to sort the population if you use such a selection.

And you are also correct about the complexity, a sort is n*log(n), making the genetic algorithm significantly slower (but still, the complexity remains polynomial, a critical feature of a genetic algorithms).

Here is how I would do it (and get extra points at school for this):

1. implement a more generic solution using hooks - before mutation, after selection etc etc.

2. measure the number of iterations and the speed of the algorithm / each iteration

3. do your sorting in a hook. measure. now let the hook be empty and measure and so on.

You will get some nice data and experimentally verify what your intuition tells you.

Answer 3

Even if you apply elitism, there is no need to sort the population.

Finding the best N individuals only requires a single iteration through the population.