How should roulette wheel selection be organized for non-sorted population in genetic algorithm?

Question

My question is linked with this one: Roulette-wheel selection in Genetic algorithm. Population needs to be sorted first? If we don't sort the population what is the way of organizing roulette wheel selection for it? Surely, we have to search in linear way now. Have you got any code snippets in C++ or Java for this case?

Answer 1

The population does not need to be sorted at all - the key to roulette selection is that the probability of a given individual being selected for reproduction is proportional to its fitness.

Say you have an unsorted population, with fitnesses as follows:

[12, 45, 76, 32, 54, 21]

To perform roulette selection, you need only pick a random number in the range 0 to 240 (the sum of the population's fitness). Then, starting at the first element in the list, subtract each individual's fitness until the random number is less than or equal to zero. So, in the above case, if we randomly pick 112, we do the following:

Step 1: 112 - 12 = 100. This is > 0, so continue.
Step 2: 100 - 45 = 55.  This is > 0, so continue.
Step 3: 55 - 76 = -21.  This is <= 0, so stop.

Therefore, we select individual #3 for reproduction. Note how this doesn't require the population to be sorted at all.

So, in pseudocode, it boils down to:

let s = sum of population fitness
let r = random number in range [0, s].
let i = 0.
while r > 0 do:
    r = r - fitness of individual #i
    increment i
select individual #i - 1 for reproduction.

Note that the - 1 in the final line is to counteract the increment i that's done within the last iteration of the loop (because even though we've found the individual we want, it increments regardless).