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

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 popula开发者_如何学Gotion 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.

---

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.

---

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.

---

There's no specific term for restricting selection to the top x% elements, it's just one of the factors you have to set when implementing a selection strategy.

You may get faster convergence in some cases restricting that x% figure, but I would suggest trying with strings of different length and see how this affects convergence. I've done this before (see this and this projects, both on evolving strings), and if you make the gene pool too small when selecting individuals the probability of getting stuck may skyrocket in relation to the length of the string, the reason being that you're seriously compromising diversity.