Genetic Algorithms has come to my attention recently when trying to correct/improve computer opponents for turn-based strategy computer games.
I implemented a simple Genetic Algorithm that didn't use any cross-over, just some random mutation. It seemed to work in this case, and so I started thinking:
Why is cross-over a part of genetic algorithms? Wouldn't mutation be enough?
This is from a data dump on an old AI site. The asker had the UID of 7.
Mutation is usually defined to be a global operator, i.e. iterated mutation is (eventually) capable of reaching every point in the vector space defined by the geneome. In that sense, mutation alone is certainly 'enough'.
Regarding the motivation for crossover - from Essentials of Metaheuristics, p42:
Crossover was originally based on the premise that highly fit individuals often share certain traits, called building blocks, in common. For example, in the boolean individual 10110101, perhaps ***101*1 might be a building block
(where * means "either 0 or 1")
So the idea is that crossover works by spreading building blocks quickly throughout the population.
Crossover methods also assume that there is some degree of linkage between genes on the chromosome: that is, settings for certain genes in groups are strongly correlated to fitness improvement. For example, genes A and B might contribute to fitness only when they’re both set to 1: if either is set to 0, then the fact that the other is set to 1 doesn’t do anything.
Also note that crossover is not a global operator. If the only operator is crossover then (also from p42):
Eventually the population will converge, and often (unfortunately) prematurely converge, to copies of the same individual. At this stage there’s no escape: when an individual crosses over with itself, nothing new is generated.
For this reason, crossover is generally used together with some global mutation operator.
Crossover allows to combine two parents (vs. mutation, which only uses one parent). In some cases, it is useful (e.g., if you train a FPS bot, if one parent is good at shooting and another parent is good at moving, it makes sense to combine them). In some other cases, it is not.
When thinking about crossover its important to think about the fitness landscape.
Consider a hypothetical scenario where we are applying a genetic algorithm to find a solution that performs well at 2 tasks. This could be from Franck's example (moving and shooting) for an AI, or perhaps it could be predicted 2 outputs in a genetic machine learning scenario, but really most scenarios where GAs are applied are synonymous (even at solving a single task, there may be different aspects of the task to be addressed).
Suppose we had an individual, 1, that was performing reasonably well at both tasks, and we found a series of mutations which produced 2 new individuals, 2 and 3, which performed better than Individual 1 at tasks 1 and 2 respectively. Now while both of these are improvements, ideally we want to find a generally good solution, so we want to combine the features that we have been found to be beneficial.
This is where crossover comes in; by combining the genomes of Individuals 2 and 3, we may find some new individual which produces a mixture of their performances. While it is possible that such an individual could be produced by a series of mutations applied to Individual 2 or Individual 3, the landscape may simply not suit this (there may be no favorable mutations in that direction, for example).
You are partially right therefore; it may sometimes be the case that the benefits of crossover could be replicated with a series of mutations. Sometimes this may not be the case and crossover may smooth the fitness landscape of your GA, speeding up optimization and helping your GA escape local optima.
