5
$\begingroup$

My questions concern the use of crossovers in genetic algorithms. The three basic ingredients of genetic algorithms are:

  • selection
  • mutation
  • crossover

If we think of genetic algorithm acting on binary strings…

Crossover is the process by which two parent strings get mixed to give born to offspring strings. For example: 11000 and 00010 can create the offspring 11010 by crossover only.

In some genetic algorithm people authorize double-crossover. For example the two parents: 110011 and 001100 can give birth to 111111.

I don't fully understand the advantageous of crossovers! It seems to me that one can obtain similar results with algorithms that do not contain crossover.

My questions

  • Under what conditions is the use of crossover in genetic algorithm beneficial? why?

  • Under what conditions is the use of double-crossover more beneficial than single crossover? why? What about triple crossover?

When I say "Under what conditions", I mean "for what fitness landscape" or "for what problem type".

By fitness landscape, I mean a mapping of each possibility to fitness (reproductive success) in a hyperspace of $n+1$ dimensions where $n$ is the length of the string (the additional dimension being the fitness).

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions. If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then crossover will increase performance of GAs. For example, if there is a function f(x,y)=g(x)+h(y), and x and y are encoded consequently in the genome, and e.g. g(x) has larger influence, then the part of genome that stands for x will be optimized in the first place, and it will become nearly the same for the whole population thanks to crossover. After this, h(y) term will be optimized. That is, crossover helps to loosely decompose the task into subtasks without prior knowledge (but dependent on the encoding scheme), if it is possible (otherwise it will yield no benefit, or even will make search less efficient). This is actually the main additional metaheuristic of GAs in comparison with other metaheuristic optimization methods.

Double-point crossover (or other more “clutter” types of crossover) can be more beneficial, if the most crucial parts of solutions are encoded in the middle of the genome or if they are placed in separate locations. The simplest example is the function f(x,y,z)=h(x,z)+r(y)+g(z), where h(x,z) has the highest influence, and genes encode the string xyz. Single-point crossover will prefer to take x from one parent, and z from another parent. However, (x,z) determine the solution quality together. If one individual will occasionally have optimal components (x*,z*), they will not appear simultaneously in its children after single-point crossover, so it will be more difficult for these parts of the genome to stabilize.

Improve this answer
$\endgroup$
1
$\begingroup$

You may have a look at the article "The Analysis of Evolutionary Algorithms — A Proof That Crossover Really Can Help" published in 2002 by Jansen and Wegener in the journal Algorithmica. This might not really answer your two questions, but at least it shows that your statement ("It seems to me that one can obtain similar results with algorithms that do not contain crossover.") does not hold and that crossover can have an important impact in evolutionary algorithms.

Improve this answer
$\endgroup$
0
0
$\begingroup$

It depends. Evolutionary algorithms are highly sensitive to the state space of the fitness function. In general crossover gives you nothing better than flipping a random coin. On some fitness functions like maximize the number of 1 bits, crossover speeds convergence at an amazing rate.

If you know little about your fitness function, keep track of how many times crossover(A,B) has yielded a fitter result than A or B. Report this result as part of your analysis of the fitness landscape.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting. Is there any kind of rule allowing to know for which "type" of fitness function and fitness landscape are crossover beneficial or detrimental/useless? $\endgroup$
    – Remi.b
    Jan 30, 2014 at 21:07
  • 1
    $\begingroup$ In general no, because you run into the halting problem. Usually the best GA model is an encoding of the fitness landscape that is smooth to your genetic operators (mutation/crossover/....) For example if you are sorting things you might want a sensible permutation encoding of the landscape instead of assigning a random bitstring to a random permutation. Try reading Ashlock's book. caronte.dma.unive.it/~paolop/papers/ashlock_book.pdf $\endgroup$
    – Chad Brewbaker
    Jan 30, 2014 at 21:25

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.