6
$\begingroup$

There are two potential approaches when performing cross-over operation in genetic algorithms.

  1. Use only the elites in the pool, probably the ones that are also going to be directly transferred to the next generation.

  2. Use all the population present in the pool.

Is there any certain belief that cross-over on only elites of the population, converges the solutions faster? I guess in order to escape from local minima, cross-over on all the population is needed. On the other hand, I also say why performing cross over on weak population?

Any idea?

$\endgroup$
  • $\begingroup$ if you can I feel its best to strike a balance as is done with the reproduction in the neat algorithm, where the more a elite a species or individual genome the more they reproduce and vice versa the less elite the less they reproduce $\endgroup$ – nickw Feb 10 at 15:30
1
$\begingroup$

First of all the answer to your question is largely dependent on the problem you are trying solve, the size of your population, the size of your problem's search space and the rest of your GA's hyper-parameters such as your mutation rate.

  • If the problem has a large search space, then applying the elites strategy you described above will most likely cause your algorithm to never reach the optimal solution or reach it after too many iterations. The reason for this being that if your search space is big, then since the initialization of your initial population is random, the chances is that the "fittest" individual(s) in the first few iterations are not necessarily the gonna lead you to the optimal solution. Hence applying the elites strategy too early might make you get stuck on a local optima forever or for too long. The way I have personally found to be effective for this kind of situations is to allow your algorithm to explore as large a search space as possible earlier on(i.e use "all the population present in the pool") and then gradually introduce the elite strategy you described above(this is an idea similar to momentum in neural networks). In short, you want to explore earlier on, and then when you gradually start exploiting what you have found.
  • If the search space is relatively small, I think the elites strategy would be a very good idea. What you might also try to do, if you really want to stick to using elitism, you can try to mutate the elite individual(this kinda allows you to explore a little bit), or choose a higher elitism rate(i.e the number of individuals to be elite).

Now to answer you other questions:

Is there any certain belief that cross-over on only elites of the population, converges the solutions faster?

No, but I don't have reference for this so I guess I speak under correction, but I will explain why I said no:

The problem with pure elitism is that it causes the genetic algorithm to converge to local maxima instead of the global maxima. Basically pure elitism is just a race to the nearest local maxima and and as soon as you get to the local maxima, if you continue with elitism, you get almost no improved from there.

I guess in order to escape from local minima, cross-over on all the population is needed; on the other hand I also say why performing cross over on weak population?

"why perform cross-over on weaker individuals in the population?" - to explore. The hope is that applying a cross-over or a mutation on a weaker individual will produce a fitter individual.

| improve this answer | |
$\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.