cgenetic-algorithmroulette-wheel-selection

Implementation of Roulette wheel Selection


I'm coding a genetic algorithm from scratch in C, I'm stuck in the roulette wheel implementation, here how I code it:

void selection(Chromosome * chromosome){

double totalFitness=0;
double totalProbability=0;
double probability=0;
double rndNumber;
double min,max;
int i;

min=0.0;
max=1.0;

for(i=0;i<POPULATION_SIZE;i++){
 totalFitness += chromosome[i].fitness;
  }

  for(i=0;i<POPULATION_SIZE;i++){
   chromosome[i].probability = (chromosome[i].fitness)/totalFitness;
   printf("Chromosome %d with probability %f\n",i, chromosome[i].probability);
  }
 srand((unsigned)time(NULL));
 for(i=0;i<POPULATION_SIZE;i++){
  rndNumber = ((double)rand()/(double)RAND_MAX);
  if(chromosome[i].probability >= rndNumber){
  printf("Chromosome %d selected \n",i);




}}}

The output return one or no chromosome selected, which isn't the expected result. I'm wondring if this is the wright way to dot it??

Thanks in advance.


Solution

  • When you pick a chromosome, you should determine the random number only once and then accumulate the offset, so that you consider all ranges:

                           | random number 
                           |
                           X
        +--------------+-----+----+--+--++---+-----+
        |              |     |    |  |  ||   |     |
        +--------------+-----+----+--+--++---+-----+
       0.0            p0   p0+p1                  1.0 == sum(p[i])
    

    In code:

    double rndNumber = rand() / (double) RAND_MAX;
    double offset = 0.0;
    int pick = 0;
    
    for (i = 0; i < POPULATION_SIZE; i++) {
        offset += chromosome[i].probability;
        if (rndNumber < offset) {
            pick = i;
            break;
        }
    }
    
    printf("Chromosome %d selected.\n", pick);