0
$\begingroup$

I'm having a rough time understanding the Rank Selection method for Genetic Algorithms. Here is what I think it does:

  • Tour1's Fitness: 0.87
  • Tour2's Fitness: 1.22
  • Tour3's Fitness: 1.03
  • Tour4's Fitness: 0.58

We rank them using their fitness:

  • 4) Tour2 -- Highest rank (N)
  • 3) Tour3
  • 2) Tour1
  • 1) Tour4 -- Lowest rank (1)

We generate a random number between 1 and 10 (sum of ranks), for example X = 3. We then loop and sum the ranks until its greater than X and we select the tour, in this example it will be Tour2 since it's rank is 4 and 4 > 3.

What I don't understand is how is this better than just randomly selecting a tour and why is it better than Roulette Wheel Selection? ALso please correct me if I'm missunderstanding the method.

$\endgroup$
2
$\begingroup$

It's about controlling selection pressure. With roulette wheel selection, there are several scaling issues. If you have two individuals p1 and p2 with fitness values 1 and 2 versus having values 1001 and 1002, roulette wheel selection behaves drastically differently. Similarly, suppose the optimal fitness value of your function is at some f(x)=100, and you generate an initial population with fitness values all around 1, and one individual at 20. Roulette wheel selection will drastically favor the one best solution, simply because it's so much better than the others. But early in a run, that's probably a mistake. The population will quickly be taken over by copies of that solution. Just being way better than bad alternatives doesn't tell me enough information to be that aggressive in selecting it.

Ranked selection just looks at the rankings and so doesn't have this problem. Whether you're a little better or a lot better, we can precisely control how aggressively to exploit those better solutions.

Darrell Whitley is generally credited with the idea of Rank-biased selection in [1]. He published code for performing selection using this method. I've cleaned up that code a bit below. You'd have to integrated it with your own code to properly get the population size, etc., but it should be fairly self-explanatory aside from the actual formula -- that you can just take on faith or go read Whitley's GENITOR paper for details.

// return the index into the population of the selected parent. 
// population must be sorted by fitness first
Chromosome select_parent(Population pop)
{ 
    double bias = 1.5;
    int index = (int)(pop.size() * (bias - sqrt(bias*bias - 4.0*(bias-1) * rand01())) 
        / 2.0 / (bias-1));
    return pop[index]; 
}

The bias term governs how strongly we want to favor higher ranked individuals. You could tweak that to increase or decrease selection pressure, though in practice, I've never changed it from the default value of 1.5 given in the Whitley paper.

The only other detail is that I invented a notation for "rand01" to mean a function that returns a random floating point number in the interval [0.0, 1.0).

[1] https://www.researchgate.net/profile/Darrell_Whitley2/publication/2527551_The_GENITOR_Algorithm_and_Selection_Pressure_Why_Rank-Based_Allocation_of_Reproductive_Trials_is_Best/links/5632149808ae3de9381e72c5/The-GENITOR-Algorithm-and-Selection-Pressure-Why-Rank-Based-Allocation-of-Reproductive-Trials-is-Best.pdf

$\endgroup$
  • $\begingroup$ Thank you for the explanation. Just one last thing please, is myexample valid? I'm trying to implement it and I cant seem to find a pseudocode for it. $\endgroup$ – Haytam Mar 28 '18 at 7:37
  • $\begingroup$ I edited the answer to include implementation details. $\endgroup$ – deong Mar 29 '18 at 14:41
0
$\begingroup$

It is a way of randomly selecting a tour -- but not all tours are equally likely. This method is more likely to pick a high-rank tour than a low-rank tour. Thus, it's a way of randomly selecting a tour, but biased towards the better (high-rank) tours. If you picked uniformly at random among the tours, you'd be more likely to get a lower-rank (worse) tour.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.