How to perform rank based selection in a genetic algorithm?

Question

I am implementing a small genetic algorithm framework - primarily for private use, unless I manage to make something reasonable at which time I will post it as open source. Right now I am focusing on selection techniques. So far I have implemented roulette wheel selection, stochastic universal sampling and tournament selection. Next on my list is rank based selection. I had a little more difficulty finding information about that than the other techniques that I've already implemented, but here is my understanding so far.

1. When you have your population from which you want to get reasonable parents for the next round, you first go through it and divide the fitness of each individual by the total fitness in the population.

2. Then you use some other selection technique (such as roulette wheel) to actually determine whom to select for breeding.

Is this correct? If so, am I right in thinking that the rank adjustment is a sort of preprocessing step which then has to be followed by an actual selection procedure that picks out the candidates? Please correct me if I have misunderstood any of this. I am grateful for any additional pointers.

Answer 1

What have you described is simply Roulette wheel selection.In Roulette wheel selection:

• Parents are selected according to their fitness
• The better the chromosomes are, the more chances to be selected they have.

Imagine a roulette wheel where all chromosomes in the population are placed, each chromosome has its place big accordingly to its fitness function, like on the following picture.
This selection will have problems when the finesses differs very much. Outstanding individuals will introduce a bias in the beginning of the search that may cause a premature convergence and a loss of diversity.
For Example:

if an initial population contains one or two very fit but not the best individuals and the rest of the population are not good, then these fit individuals will quickly dominate the whole population and prevent the population from exploring other potentially better individuals. Such a strong domination causes a very high loss of genetic diversity which is definitely not advantageous for the optimization process.

But in Rank Selection:

1. Rank selection first ranks the population and then every chromosome receives fitness from this ranking.

2. The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population).

3. After this all the chromosomes have a chance to be selected.

4. Rank-based selection schemes can avoid premature convergence.
5. But can be computationally expensive because it sorts the populations based on fitness value.
6. But this method can lead to slower convergence, because the best chromosomes do not differ so much from other ones.

So the process will be:

1. First sort the Fitness value of the Population.

2. Then if the Population number is 10 then give the probability of selection to the Population like 0.1,0.2,0.3,...,1.0 .

3. Then calculate cumulative Fitness and make roulette wheel.
4. And the next steps is same as roulette wheel.

My Implementation 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

Note: you can also see my question regarding rank selection here in this link and my article here.