Rank Selection in GA?
genetic-algorithm, matlab, selection
Solution
If the population has `N` individuals, the best individual gets rank `N` and the worst `1` then
TotalFitness = sum(Fitness);
should be changed with:
TotalFitness = (N + 1) * N / 2;
(probably `TotalFitness` isn't anymore the right name for the variable, but let it go)
`(N + 1) * N / 2` is just the sum of the ranks:
1 + 2 + ... + N = (N + 1) * N / 2
The probability of selection should be changed from:
ProbSelection(i) = Fitness(i) / TotalFitness;
to
ProbSelection(i) = i / TotalFitness;
Here using the rank instead of the fitness and assuming that the first individual of the population is the worst and the last is the best (sorted population).
Hence the complexity of the rank selection algorithm is dominated by the complexity of the sorting (`O(N * log(N)`).
You can see that the probability of selection for the worst individual is:
1 / ((N + 1) * N / 2) = 2 / ((N + 1) * N)
and the probability for the best individual is:
N / (((N + 1) * N / 2)) = 2 * (N + 1)
This is a linear rank selection: the ranks are in a linear progression. There are other schemes of rank selection (e.g. exponential).
Problem
I have implemented `Roulette wheel selection` in `GA`. ``` TotalFitness=sum(Fitness); ProbSelection=zeros(PopLength,1); CumProb=zeros(PopLength,1); for i=1:PopLength ProbSelection(i)=Fitness(i)/TotalFitness; 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 ``` Now i was trying to implement `rank selection` in `GA`. I learned that: Rank selection first ranks the population and then every chromosome receives fitness from this ranking. The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population). I saw these link1 and link2 and what i understood is that: First i will sort the Fitness value of the Population. Then if the Population number is 10 then i will give the probability of selection to the Population like 0.1,0.2,0.3,...,1.0 . - Then i will calculate cumulative Fitness like roulette wheel. - And the next steps is same as roulette wheel. My Implementation: ``` 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 ``` Am i understanding the algo wrong?? If it is then can anyone give me any idea how to modify my roulette wheel to rank selection??