Rank Selection in GA?

Question

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:

1. First i will sort the Fitness value of the Population.

2. 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 .

3. Then i will calculate cumulative Fitness like roulette wheel.
4. 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??

Answer 1

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