Geek Answers Handbook

Rating selection in genetic algorithm code

I need a code for the genetic algorithm ranking selection method . I have a method of choosing roulette and a tournament, but now I need ranking, and I'm stuck.

My roulette code is here (I use atomic structure 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 is the atom:

 typedef struct atom { int geno[VARS]; double pheno[VARS]; double fitness; } atom;
+5
algorithm artificial-intelligence genetic-algorithm selection
source share
3 answers

The choice of rank is easy to implement when you already know how to choose a roulette wheel. Instead of using fitness as a chance to choose, you use rank. Thus, for a population of N solutions, the best solution is ranked N, the second best rank N-1, etc. The worst person has a rank of 1. Now use the roulette wheel and start choosing.

The probability of choosing the best person is N / ((N * (N + 1)) / 2) or about 2 / N, for the worst individual it is 2 / (N * (N + 1)) or about 2 / N ^ 2.

This is called a linear ranking choice because the ranks form a linear progression. You can also think of ranks forming a geometric progression, for example, 1/2 ^ n, where n ranges from 1 for a better individual to N for a worse one. This, of course, gives a much greater likelihood of a better person.

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

+7
source share

My rank selection code 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
+2
source share

I created a genetic algorithm template in C ++.

My library of genetic algorithms is separate from GeneticAlgorithm and GAPopulation. These are all template classes so you can see the source code in API documents.

+1
source share

More articles:


All Articles