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 you've described there is roulette wheel selection, not rank selection. To do rank selection, rather than weighting each candidate by its fitness score, you weight it by its "rank" (that is, best, second best, third best, etc.).

For instance, you might give the first one a weighting of 1/2, the second a weighting of 1/3, the third a weighting of 1/4, etc. Or the worst gets weighting 1, the second worst gets weighting 2, etc.

The important point is that absolute or relative fitness scores are not considered, only the rankings. So the best is more likely to be chosen than the second best, but the two have the same probabilities of being chosen whether the best had ten times the score of the second best, or only had a slightly greater score.