Ranking Selection in Genetic Algorithm code
Solution 1
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.
Solution 2
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
Solution 3
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.
Admin
Updated on June 04, 2022Comments
-
Admin almost 2 years
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;