Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-11T14:06:30.360Z
Answers.LastActivityDate: 2016-08-11T14:19:54.063Z
Answers.LastEditDate: 2016-08-11T14:19:54.063Z
Answers.UserDisplayName: Franck Dernoncourt
Answers.Body: <p>When thinking about crossover its important to think about the fitness landscape. </p>
  
  <p>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).</p>
  
  <p>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. </p>
  
  <p>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).</p>
  
  <p><a href="https://i.sstatic.net/bsVBEm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bsVBEm.png" alt="enter image description here"></a></p>
  
  <p>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. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-11T15:54:29.973Z
Answers.Text: If (as should be the case) the mutation operator is *global* (i.e. capable of expressing all points in the search space) it is *always* possible to express the results of crossover via (some sequence of) mutations. However (as per my answer) the converse is not the case.
Answers.UserDisplayName: NietzscheanAI
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-11T18:20:45.430Z
Answers.Text: That is true, I just wished to illustrate the point made by you and Franck with an example :)
Answers.UserDisplayName: Tim Atkinson
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-11T14:45:52.773Z
Answers.LastActivityDate: 2016-08-11T15:38:11.613Z
Answers.LastEditDate: 2016-08-11T15:38:11.613Z
Answers.UserDisplayName: Tim Atkinson
Answers.Body: <p>Mutation is usually defined to be a <em>global</em> 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'.</p>
  
  <p>Regarding the motivation for crossover - from <a href="https://cs.gmu.edu/~sean/book/metaheuristics/" rel="noreferrer">Essentials of Metaheuristics</a>, p42:</p>
  
  <blockquote>
    <p>Crossover was originally based on the premise that highly fit individuals often share certain traits, called <em>building blocks</em>, in common.
    For example, in the boolean individual 10110101, perhaps
    ***101*1 might be a building block </p>
  </blockquote>
  
  <p>(where * means "either 0 or 1") </p>
  
  <p>So the idea is that crossover works by spreading building blocks quickly throughout the population.</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>Also note that <em>crossover is not a global operator</em>. If the only operator is crossover then (also from p42):</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>For this reason, crossover is generally used together with some global mutation operator.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-11T14:40:33.810Z
Answers.LastActivityDate: 2016-08-11T15:57:27.610Z
Answers.LastEditDate: 2016-08-11T15:57:27.610Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>Genetic Algorithms has come to my attention recently when trying to correct/improve computer opponents for turn-based strategy computer games.</p>
  <p>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:</p>
  <p><strong>Why is cross-over a part of genetic algorithms? Wouldn't mutation be enough?</strong></p>
  <p><sub>This is from a data dump on an old AI site. The asker had the UID of 7. </sub></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-08T13:53:27.017Z
Comments.Text: The user that asked the original question was probably [hwlau](https://area51.stackexchange.com/users/43238/hwlau) according to [this](https://area51.stackexchange.com/proposals/57719?page=3&phase=beta&users=reputation#tab-top), so that, if you really want to give credit, we are giving credit to an actual person/account.
Comments.UserDisplayName: nbro
Tags: <genetic-algorithms><evolutionary-algorithms><crossover-operators><genetic-operators><mutation-operators>
Title: Why is cross-over a part of genetic algorithms?
UserDisplayName: Mithical
ThreadText: # Why is cross-over a part of genetic algorithms?
  
  (Asked by: username_0 on 2016-08-11)
  
  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.
  
  **Tags:** genetic-algorithms, evolutionary-algorithms, crossover-operators, genetic-operators, mutation-operators
  
  > **Comments:**
  > **username_1**: The user that asked the original question was probably [hwlau](https://area51.stackexchange.com/users/43238/hwlau) according to [this](https://area51.stackexchange.com/proposals/57719?page=3&phase=beta&users=reputation#tab-top), so that, if you really want to give credit, we are giving credit to an actual person/account.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_4 on 2016-08-11. Score: 7 | Accepted answer
  
  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](https://cs.gmu.edu/~sean/book/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.
  
  
  ---
  
  ### Answer by username_2 on 2016-08-11. Score: 5
  
  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.
  
  
  ---
  
  ### Answer by username_3 on 2016-08-11. Score: 4
  
  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 username_2'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).
  
  [![enter image description here](https://i.sstatic.net/bsVBEm.png)](https://i.sstatic.net/bsVBEm.png)
  
  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.
  
  > **Comments:**
  > **username_4**: If (as should be the case) the mutation operator is *global* (i.e. capable of expressing all points in the search space) it is *always* possible to express the results of crossover via (some sequence of) mutations. However (as per my answer) the converse is not the case.  
  > **username_3**: That is true, I just wished to illustrate the point made by you and username_2 with an example :)  
  
  ---
  
  