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 .
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??
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).