Efficiency of crossover in genetic algorithms

Question

I've implemented a number of genetic algorithms to solve a variety of a problems. However I'm still skeptical of the usefulness of crossover/recombination.

I usually first implement mutation before implementing crossover. And after I implement crossover, I don't typically see a significant speed-up in the rate at which a good candidate solution is generated compared to simply using mutation and introducing a few random individuals in each generation to ensure genetic .

Of course, this may be attributed to poor choices of the crossover function and/or the probabilities, but I'd like to get some concrete explanation/evidence as to why/whether or not crossover improves GAs. Have there been any studies regarding this?

I understand the reasoning behind it: crossover allows the strengths of two individuals to be combined into one individual. But to me that's like saying we can mate a scientist and a jaguar to get a smart and fast hybrid.

EDIT: In mcdowella's answer, he mentioned how finding a case where cross-over can improve upon hill-climbing from multiple start points is non-trivial. Could someone elaborate upon this point?

Lucais

This kind of question might get a better answer at cstheory.SE. – Yaakov

1) what crossover did you use? random? one point? two points? 2) what exactly are you looking for? a reference to an article discussing the influence of crossover on solution's quality? – Meloniemelony

A "reference to an article" would be nice. I'm not looking to improve my crossover functions (I've used all sorts) in particular, but rather for a concrete reason/evidence that it improves the efficiency of GAs. – Lucais

It's always going to be problem-dependent, and provably so. There is no technique that works in general. Any effective search algorithm is effective only to the extent that its biases are in some sense aligned with salient features of the search space. Hill climbing works best when you have relatively few large hills. Simulated annealing works best when most barriers between optima are shallow. There will be situations where a particular crossover operator works well, and situations where it doesn't. – Ranch

@deong: Yes but I'm looking for an examples/cases where crossover works well. – Lucais

The problem is that "crossover" is enormously vague. Let's say you're working on a one-max problem with mutation only. Here's a crossover operator: take any 1-bit from either parent. I would certainly expect my algorithm to outperform yours. From your experience, all you can really say is that the crossover operators you tried didn't seem to help on the particular instances of the particular problem you were working on. I suspect that for any particular problem, there exists a crossover operator that helps, purely because the space of operators is so large. – Ranch

There's a lot of "depends" here. It depends what type of crossover operator you use and how well the individual parts of the chromosome combine (see building block hypothesis). – Fifth

Answer 1

You are correct in being skeptical about the cross-over operation. There is a paper called "On the effectiveness of crossover in simulated evolutionary optimization" (Fogel and Stayton, Biosystems 1994). It is available for free at 1.

By the way, if you haven't already I recommend looking into a technique called "Differential Evolution". It can be very good at solving many optimization problems.

Hylozoism

Answer 2

It strongly depends on the smoothness of your search space. Perverse example if every "geneome" was hashed before being used to generate "phenomes" then you would just be doing random search.

Less extreme case, this is why we often gray-code integers in GAs.

You need to tailor your crossover and mutation functions to the encoding. GAs decay quite easily if you throw unsympathetic calculations at them. If the crossover of A and B doesn't yield something that's both A-like and B-like then it's useless.

Example:

The genome is 3 bits long, bit 0 determines whether it's land-dwelling or sea-dwelling. Bits 1-2 describe digestive functions for land-dwelling creatures and visual capabilities for sea-dwelling creatures.

Consider two land-dwelling creatures.

    | bit 0 | bit 1 | bit 2
----+-------+-------+-------
Mum | 0     | 0     | 1
Dad | 0     | 1     | 0

They might crossover between bits 1 and 2 yielding a child whose digestive function is some compromise between Mum's and Dad's. Great.

This crossover seems sensible provided that bit 0 hasn't changed. If is does then your crossover function has turned some kind of guts into some kind of eyes. Er... Wut? It might as well have been a random mutations.

Begs the question how DNA gets around this problem. Well, it's both modal and hierarchial. There are large sections which can change a lot without much effect, in others a single mutation can have drastic effects (like bit 0 above). Sometimes the value of X affects the behaviour tiggered by Y, and all values of X are legal and can be explored whereas a modification to Y makes the animal segfault.

Theoretical analyses of GAs often use extremely crude encodings and they suffer more from numerical issues than semantic ones.

Gentleness

In your example, each of the bits are independent of each other. However I find that typically the quality of the individual also depends on relationships between each "part" of their encoding. It just seems to me that crossover has a very low probability of creating a better individual given these intricate relationships. But of course you're right that it heavily depends on the search space and the particular cross over function (which as you also mentioned should be tailored to the problem at hand). – Lucais

Answer 3

My impression is that hill-climbing from multiple random starts is very effective, but that trying to find a case where cross-over can improve on this is non-trivial. One reference is "Crossover: The Divine Afflatus in Search" by David Icl˘anzan, which states

The traditional GA theory is pillared on the Building Block Hypothesis (BBH) which states that Genetic Algorithms (GAs) work by discovering, emphasizing and recombining low order schemata in high-quality strings, in a strongly parallel manner. Historically, attempts to capture the topological fitness landscape features which exemplify this intuitively straight-forward process, have been mostly unsuccessful. Population-based recombinative methods had been repeatedly outperformed on the special designed abstract test suites, by different variants of mutation-based algorithms.

A related paper is "Overcoming Hierarchical Difficulty by Hill-Climbing the Building Block Structure" by David Iclănzan and Dan Dumitrescu, which states

The Building Block Hypothesis suggests that Genetic Algorithms (GAs) are well-suited for hierarchical problems, where efficient solving requires proper problem decomposition and assembly of solution from sub-solution with strong non-linear interdependencies. The paper proposes a hill-climber operating over the building block (BB) space that can efficiently address hierarchical problems.

Deepsix

Exactly! Hill-climbing, to me, seems significantly more likely to produce better results than crossover so I'm wondering why should we bother using CPU cycles doing crossover at all. I'll take a look at those references since I would like to know more about how to use crossover effectively. – Lucais

@Lucais Well, we have at least one existence proof that crossover works better in some environments. ;) – Stevestevedore

Answer 4

John Holland's two seminal works "Adaptation in Natural and Artificial Systems" and "Hidden Order" (less formal) discuss the theory of crossover in depth. IMO, Goldberg's "Genetic Algorithms in Search, Optimization, and Machine Learning" has a very approachable chapter on mathematical foundations which includes such conclusions as:

With both crossover and reproduction....those schemata with both above-average performance and short defining lengths are going to be sampled at exponentially increasing rates.

Another good reference might be Ankenbrandt's "An Extension to the Theory of Convergence and a Proof of the Time Complexity of Genetic Algorithms" (in "Foundations of Genetic Algorithms" by Rawlins).

I'm surprised that the power of crossover has not been apparent to you in your work; when I began using genetic algorithms and saw how powerfully "directed" crossover seemed, I felt I gained an insight into evolution that overturned what I had been taught in school. All the questions about "how could mutation lead to this and that?" and "Well, over the course of so many generations..." came to seem fundamentally misguided.

Gristmill

Thanks! I'll see if I can get a hold of those books. – Lucais

Both of those books are seminal references that are now very outdated. There have been theoretical studies that showed that crossover was provably beneficial, but like most all GA theory, the paring back of realistic assumptions needed to allow the math to be tractable makes it highly questionable that the results hold for realistic problems. – Ranch

@Ranch Can you clarify -- are you saying that the theoretical benefits of GAs have weakened as theory advanced or that the practicality of GAs has (remained) challenging? – Gristmill

What's mostly happened is that the schema theorem advocated in those early works as a justification for how GAs worked (including the benefits of crossover) has been found to be overly simplistic. The replacement theories are more accurate, but don't currently admit practical predictions to be made from them in most cases, and in general, can't tell you much about the performance of an algorithm on a given realistic problem. We're mostly back to "it works pretty well on some problems, but we can't say much about when or why." – Ranch

@deong: So using GAs to solve problems is a stab in the dark? Picking a good crossover operator is a matter of luck and chance? There has to be some way of characterizing when GAs are effective, even if it's merely a guideline and not a theorem. – Lucais

Well, that's I think an overly critical view of things. I wouldn't say that designing an elegant coffee table is a completely random stab in the dark, but I don't have a good mathematical theorem for describing what people like either. Designing an effective metaheuristic is a complex task that has some degree of "art" vs. "science" involved. Experience helps in recognizing useful approaches, and there are decent guidelines that often work well as starting points. But as of today, there's no predictive theory anyone has found to describe if/when a crossover operator will help in general. – Ranch

Most guidelines for designing heuristics are just empirical -- people report parameters that worked for them. That's OK as a starting point, but we really don't know how to characterize the effects of crossover on a deep fundamental level yet. And that's true for pretty much everything in metaheuristics. The question of "what algorithm will work best on my problem" is still open, and it's probably not too unreasonable to call it the "P=NP?" question of that field. – Ranch

Answer 5

The crossover and mutation!! Actually both of them are necessary. Crossover is an explorative operator, but the mutation is an exploitive one. Considering the structure of solutions, problem, and the likelihood of optimization rate, its very important to select a correct value for Pc and Pm (probability of crossover and mutation).

Check this GA-TSP-Solver, it uses many crossover and mutation methods. You can test any crossover alongside mutations with given probabilities.

Minium

Answer 6

it mainly depends on the search space and the type of crossover you are using. For some problems I found that using crossover at the beginning and then mutation, it will speed up the process for finding a solution, however this is not very good approach since I will end up on finding similar solutions. If we use both crossover and mutation I usually get better optimized solutions. However for some problems crossover can be very destructive.

Also genetic operators alone are not enough to solve large/complex problems. When your operators don't improve your solution (so when they don't increase the value of fitness), you should start considering other solutions such as incremental evolution, etc..

Trevelyan