Ranking Selection in Genetic Algorithm code

Question

I need code for the ranking selection method on a genetic algorithm. I have create roulette and tournament selections method but now I need ranking and I am stuck.

My roulette code is here (I am using atom struct for genetic atoms) :

const int roulette (const atom *f)
{
  int i;
  double sum, sumrnd;

  sum = 0;
  for (i = 0; i < N; i++)
    sum += f[i].fitness + OFFSET;

  sumrnd = rnd () * sum;

  sum = 0;
  for (i = 0; i < N; i++) {
    sum += f[i].fitness + OFFSET;
    if (sum > sumrnd)
      break;
  }

  return i;
}

Where atom :

typedef struct atom
{
  int geno[VARS];
  double pheno[VARS];
  double fitness;
} atom;

what language are you coding in? Hope this [discussion](http://stackoverflow.com/questions/10152002/building-ranking-with-genetic-algorithm) helps you. — bonCodigo, Dec 01 '12 at 13:31
C++, this is a plain C part, but I am developing it in Nokia QT Framework — , Dec 01 '12 at 13:36

Andreas · Answer 1 · 2015-02-16T12:22:35.137

Rank selection is easy to implement when you already know on roulette wheel selection. Instead of using the fitness as probability for getting selected you use the rank. So for a population of N solutions the best solution gets rank N, the second best rank N-1, etc. The worst individual has rank 1. Now use the roulette wheel and start selecting.

The probability for the best individual to be selected is N/( (N * (N+1))/2 ) or roughly 2 / N, for the worst individual it is 2 / (N*(N+1)) or roughly 2 / N^2.

This is called linear rank selection, because the ranks form a linear progression. You can also think of ranks forming a geometric progression, such as e.g 1 / 2^n where n is ranging from 1 for the best individual to N for the worst. This of course gives much higher probability to the best individual.

You can look at the implementation of some selection methods in HeuristicLab.

score 2 · Answer 2 · edited Apr 04 '16 at 09:12

My code of Rank Selection in MatLab:

NewFitness=sort(Fitness);
NewPop=round(rand(PopLength,IndLength));

for i=1:PopLength
    for j=1:PopLength
        if(NewFitness(i)==Fitness(j))
            NewPop(i,1:IndLength)=CurrentPop(j,1:IndLength);
            break;
        end
    end
end
CurrentPop=NewPop;

ProbSelection=zeros(PopLength,1);
CumProb=zeros(PopLength,1);

for i=1:PopLength
    ProbSelection(i)=i/PopLength;
    if i==1
        CumProb(i)=ProbSelection(i);
    else
        CumProb(i)=CumProb(i-1)+ProbSelection(i);
    end
end

SelectInd=rand(PopLength,1);

for i=1:PopLength
    flag=0;
    for j=1:PopLength
        if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i))
            SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength);
            flag=1;
            break;
        end
    end
    if(flag==0)
        SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength);
    end
end

score 1 · Answer 3 · answered Nov 03 '15 at 05:17

I've made a template genetic-algorithm class in C++.

My library of genetic algorithm is separated from GeneticAlgorithm and GAPopulation. Those are all template classes so that you can see its origin code in API Documents.

Here are source codes and API documents.
- http://samchon.github.io/framework/api/cpp/d5/d28/classsamchon_1_1library_1_1GeneticAlgorithm.html
- http://samchon.github.io/framework/api/cpp/d8/dcd/classsamchon_1_1library_1_1GAPopulation.html

Ranking Selection in Genetic Algorithm code

3 Answers3

Linked