How does this algorithm corresponds to the roulette wheel selection?

Question

I am trying to implement a roulette wheel selection. I have understood this algorithm:

1. Calculate the sum S of all chromosome fitnesses in population
2. Generate a random number, r, from interval (0,S)
3. Loop through the population and sum fitnesses from 0 till S, this is the partial sum, call it P.
4. When the P > S: stop and return the corresponding chromosome.

What I don't understand is how this corresponds to doing this instead: Roulette wheel selection algorithm (the answer with 44 votes). This makes sense to me, but not the one above.

Answer 1

The following is done using the sum

def choose_parent_using_RWS(genes, S, points):
    P = randint(0, int(S))
    for x in genes:
        P += evaluate(x, points)
        if P > S:
            return x
    return genes[-1]

the following is done by normalizing between 0 and 1

def choose_parent_using_RWS(genes, S, points):
    P = randint(0, int(S))/S
    for x in genes:
        P += evaluate(x, points)/S
        if P > S/S:
            return x
    return genes[-1]

Answer 2

In the answer with 44 votes, the range has been normalised between 0 to 1 which is easier to understand but requires extra steps for calculations.

You can implement the approach you mentioned. In that while calculating the sum, each individual chromosome adds its own value, so when a random number is generated between 0 and S we assume that if r is between 2 numbers whose range is equal to the above mentioned value, it is chosen with the probability proportional to its fitness value. The bigger the value the more is the probability of r to come in its range.

For example, lets say that a chromosome having a fitness of 23 (assumption) is the 5th chromosome when you iterate and the total sum S is 130. The sum of the first 4 chromosomes is, lets say, 54. So if random r is between 55 and 77 (both inclusive), this chromosome is chosen.

After normalisation, 55/130 ~= 0.423 and 77/130 ~= 0.5923 is the range a random number r2 (between 0 and 1) should fall for this chromosome to be selected.