Choosing only the top x% for selection in a genetic algorithm

Question

I am currently working on a StringEvolver and I'm not quite sure about a specific term which may be used in GAs.

In genetic algorithms, elitism refers to that subset of the population that get promoted to the next generation directly; correct?

But is there a specific term for using only, for example, the top 75% of the current population for the selection, crossover and mutation process rather than the whole population? Basically, what is that x% rate called?

What I mean is that instead of using the whole population for say, a roulette-selection process, I only use the top x% (i.e. breed only amongst the best x% of the population)

---

The reason I ask is because I have noticed significant performance improvements (quicker convergence) when using, for example, the top 10-25% of the population for the selection, crossover and mutation processes for advancing the generation rather than using the full population.

Answer 1

A naive selection strategy in which you simply discard the weaker candidates is sometimes called Truncation Selection. For many problems it leads to premature convergence, though I have found it works quite well for the Travelling Salesman problem.

Sounds like you have a two phase strategy, firstly using truncation selection to eliminate the weak candidates and then applying a more sophisticated strategy (roulette wheel?) to finalise the selection.

Rather than completely eliminate the possibility of weak candidates surviving, it might be better to choose a selection strategy that allows you to tweak that probability. For example, with tournament selection you can adjust the threshold to determine how likely it is that a weak candidate survives instead of a stronger one.

Answer 2

It sounds like you're just talking about a specific selection methodology. You could do roughly the same thing by scaling your fitness function to increase at higher rates rather than linearly.

That said, I would caution against throwing out the bottom portions of your population each time. For smaller GA's this will allow you to converge more quickly but for real-world problems this will often strand you in local minima, degrading the quality of your solutions.

That said, there is a term called decimation. This is when you throw out the bottom X% of your population before crossover and mutation. This is generally not done each generation. You will typically start with an intractably large population in order to cover a greater search space and then decimate after X generations, as GA's often make their greatest gains in the first 100 gens or so. You then proceed with the smaller, more easily handled population.

Hope this helps.