Roulette Selection in Genetic Algorithms

Answer 1

It's been a few years since i've done this myself, however the following pseudo code was found easily enough on google.

for all members of population
    sum += fitness of this individual
end for

for all members of population
    probability = sum of probabilities + (fitness / sum)
    sum of probabilities += probability
end for

loop until new population is full
     do this twice
         number = Random between 0 and 1
       for all members of population
           if number > probability but less than next probability 
                then you have been selected
       end for
     end
     create offspring
end loop

The site where this came from can be found here if you need further details.

Answer 2

Here is some code in C :

// Find the sum of fitnesses. The function fitness(i) should return the fitness value for member i

float sumFitness = 0.0f;

for (int i=0; i < nmembers; i++)

    sumFitness += fitness(i);

// Get a floating point number in the interval 0.0 ... sumFitness

float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;

// Translate this number to the corresponding member

int memberID=0;

float partialSum=0.0f;

while (randomNumber > partialSum)

{ partialSum += fitness(memberID);

memberID++; }

// We have just found the member of the population using the roulette algorithm

// It is stored in the "memberID" variable

// Repeat this procedure as many times to find random members of the population

Answer 3

From the above answer, I got the following, which was clearer to me than the answer itself.

To give an example:

Random(sum) :: Random(12) Iterating through the population, we check the following: random < sum

Let us chose 7 as the random number.

Index | Fitness | Sum | 7 < Sum
0 | 2 | 2 | false
1 | 3 | 5 | false
2 | 1 | 6 | false
3 | 4 | 10 | true :: break
4 | 2 | 12

Through this example, the most fit (Index 3) has the highest percentage of being chosen (33%); as the random number only has to land within 6->10, and it will be chosen.

    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
    }       
    double rand = (((double)rand() / (double)RAND_MAX) * sum);
    sum = 0;
    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
        if (rand < sum) {
            //breed i
            break;
        }
    }