8

Most of the literature I've read about GAs suggests using a crossover value of around 0.7, so you take the first 70% of one chromosome's genes, and the last 30% of the other to produce one new chromosome.

If you are picking the parent chromosomes by taking the top two (ranked by fitness), then I can see the logic here, as you are giving more weight to the genes of the higher-rated chromosome. However, if you're using a stochastic method (such as a roulette wheel) to pick the parents, then what's the point of using anything other than 0.5 as the crossover value? Given that you have picked chromosomes A and B as the parents, you're just as likely to pick A first and B second as B first and A second aren't you?

I've only actually written one GA so far (still way down at the bottom of the learning curve, but moving up fast thanks to some great help here!), but experiments on that show that 0.5 gives a faster convergence to the solution than any other value.

Or am I missing something?

  • 2
    Most of the literature I've read about GAs suggests using a crossover value of around 0.7 <-- one thing to keep in mind is a lot of these types of values in heuristic optimization are derived more or less based on what values seemed to lead to good results (rather than an empirical derivation). I'm less familiar with GA but I know in other population based optimization methods the constants were fairly arbitrarily determined, in that some researchers did some basic experiments, found values that worked better, and then those values got adopted by the optimization community at large. – enderland Dec 22 '16 at 17:12
  • 1
    Also, I'm not really sure why this question got downvoted - it seems perfectly on topic and in scope. – enderland Dec 22 '16 at 17:17
  • 1
    I wouldn't worry about the downvote... I get one on almost every post I make here. – Robert Harvey Dec 22 '16 at 17:20
  • 2
    @enderland: would you go so far to say as those values are randomly mutated and the fittest combinations survive? ;-) – Jörg W Mittag Dec 22 '16 at 17:49
  • 2
    I'd also add that your crossover value doesn't necessarily have to remain static- since part of the goal of GA's is to get a lot of variance to explore many paths, it could be an option to pick a random crossover value between, say, 0.5 and 0.8. Especially if you aren't necessarily using deterministic picking. – Delioth Dec 22 '16 at 18:48
5

The ideal crossover operation depends very much on the problem space. The underlying assumptions of evolutionary and genetic algorithms is that two good solutions can sometimes be combined into a better solution – good solutions look similar to other good solutions. This intuitively makes sense if the problem space has a single optimum to which each successive generation will converge.

When there are multiple optima, the space in between these optima is by definition not optimal. If we take a chromosome A that is near one optimum and combine it with a chromosome B from near another optimum, we'll land in between, and will likely have a resulting chromosome c that is worse than its parents. Staying closer to one or the other parents increases the likelihood of getting a chromosome d that is better or at least not much worse than the parents.

     _                d         ^ fitness
    / \              d \        |
   /   A            B   \       |
__/     \___ccc___dd     \____  |
-----------------------------------> chromosome space
     |                |
     |     valley     |
     |     of "meh"   |
1. optimum         2. optimum

The crossover value is just one algorithm parameter you can tune to suit your problem structure. Sometimes you'll see faster convergence with a low crossover value, sometimes with a very high crossover value. But for very high values, this would be less like a crossover but only a very little change like a mutation. So instead of using a value near 1.0, you'd rather reduce the crossover rate and increase the mutation rate.

| improve this answer | |
  • @amon Thanks for the explanation. I guess like with most of this stuff, it's a case of playing around to see what works in the particular situation – Avrohom Yisroel Dec 22 '16 at 18:11
  • This makes me think that perhaps the crossover rate should be randomly selected each time. – Ask About Monica Dec 23 '16 at 18:06
2

Confusingly, crossover rate and mutation rate are, while being named similarly, typically interpreted differently.

Mutation rate of x% ==> You perform the mutation operator with probability 1.0, and each application of that operator will change x% of the bits of the mutated individual.

Crossover rate of x% ==> You choose to perform crossover at all with probability x.

So a crossover rate of 70% doesn't mean you take 70% of the bits from parent 1 and 30% from parent 2. It means that you'll perform whatever crossover operator you have chosen 70% of the time. The remaining 30% of the time, you'll pass the parents unmodified into the offspring pool.

| improve this answer | |
  • Thanks for the reply. Maybe I didn't explain myself clearly, but this is how I understood the two. I wasn't asking about mutation at all, only about crossover. – Avrohom Yisroel Dec 25 '16 at 14:32

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.