Body: <p>In a genetic algorithm, the order of the genes on a chromosome can have a significant effect on the performance (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.532.8900&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">capacity to generate adaptation</a>) of the genetic algorithm, where two or more genes interact to produce highly fit individuals. If we have a chromosome length of <span class="math-container">$100$</span> and genes <span class="math-container">$A$</span> and <span class="math-container">$B$</span> interact, then having them next to each other is strongly preferable than having them at opposing ends of the chromosome. In the former case, the probability of crossover breaking the genes apart is <span class="math-container">$1$</span> in <span class="math-container">$100$</span>, and in the latter it is one.</p>
  
  <p>What mechanisms have been tried to optimise the order of genes on a chromosome, so that interacting genes are best protected from crossover? Is it even possible? </p>
  
  <p>I've asked at <a href="https://biology.stackexchange.com/">Biology SE</a> if there exists any known biological mechanism which is responsible for such a possible order of the genes on a chromosome.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T17:06:42.463Z
Comments.Text: What do you mean by "interact"? Can you be more specific in your usage of the GA terminology? Are talking about the crossover between two chromosomes? Or which GA operator are you referring to when you say "interact"?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T17:48:10.763Z
Comments.Text: Two genes interact when their effect on individual fitness is non linear or epistatic. As for crossover by definition it is between two chromosomes.
Comments.UserDisplayName: Nick
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:24:01.407Z
Comments.Text: Can you give an example of such cases, where the vicinity of the genes in the chromosome determines the fitness of the individuals? Furthermore, note that the fitness of the individuals depends on the definition of the fitness function anyway.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:37:54.453Z
Comments.Text: I don't know who changed the question but the change is inaccurate. Genes are not similar they interact epistatically or in simple words they act in combination and not singly. The linkage problem which was in the initial question is a known problem. An efficient GA solution needs an efficient chromosome ordering, but this is often not known at design time. If we could evolve the ordering  while evolving a solution the performance as measured by the number of generations to reach an optima can be much reduced, but only if linkage evolution is significantly faster than solution evolution.
Comments.UserDisplayName: Nick
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:40:25.310Z
Comments.Text: I changed the title. The title was "linkage problem in GA". This is not a question. Edit your post and ask a question in the title like "How do I solve the linkage problem in GAs?" (if this is your question). I am sorry I changed the meaning of your post: I just tried to improve it, but this can happen.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:43:11.660Z
Comments.Text: Can you please link us to a paper or book that discusses the "linkage problem" you're referring to?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:44:03.157Z
Comments.Text: I didn't say the fitness is affected by the linkage. I just said that the fitness of an individual depends on the definition of the fitness function.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:46:45.133Z
Comments.Text: @nbro the fitness of any individual is unaffected by the ordering, but the likelihood that useful sequences or building blocks using John Hollands terms are disrupted by crossover is severely affected. See the very simple 100 gene chromosome example, or if the genes A B and C occur in the optima in that order the more efficient order places them together in a uninterrupted single sequence which is the least likely form to be broken by crossover
Comments.UserDisplayName: Nick
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:49:33.827Z
Comments.Text: So, your problem is related to the crossover operator. This is what I had initially asked about.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T18:57:46.470Z
Comments.Text: @nbro https://www.springer.com/gp/book/9783642128332 and others just search for linkage problem
Comments.UserDisplayName: Nick
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T19:03:48.187Z
Comments.Text: @nbro here's a more technical paper https://www.ncbi.nlm.nih.gov/pubmed/12689725
Comments.UserDisplayName: Nick
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-16T19:11:34.553Z
Comments.Text: @nbro no crossover is unchanged, think of the linkage map as a reordering of the chromosome before the fitness function is applied; crossover and mutation operate on the form before reordering.
Comments.UserDisplayName: Nick
Tags: <genetic-algorithms><evolutionary-algorithms><biology>
Title: How can I solve the linkage problem in genetic algorithms?
UserDisplayName: Nick
ThreadText: # How can I solve the linkage problem in genetic algorithms?
  
  (Asked by: username_0 on 2019-07-16)
  
  In a genetic algorithm, the order of the genes on a chromosome can have a significant effect on the performance ([capacity to generate adaptation](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.532.8900&rep=rep1&type=pdf)) of the genetic algorithm, where two or more genes interact to produce highly fit individuals. If we have a chromosome length of $100$ and genes $A$ and $B$ interact, then having them next to each other is strongly preferable than having them at opposing ends of the chromosome. In the former case, the probability of crossover breaking the genes apart is $1$ in $100$, and in the latter it is one.
  
  What mechanisms have been tried to optimise the order of genes on a chromosome, so that interacting genes are best protected from crossover? Is it even possible?
  
  I've asked at [Biology SE](https://biology.stackexchange.com/) if there exists any known biological mechanism which is responsible for such a possible order of the genes on a chromosome.
  
  **Tags:** genetic-algorithms, evolutionary-algorithms, biology
  
  > **Comments:**
  > **username_1**: What do you mean by "interact"? Can you be more specific in your usage of the GA terminology? Are talking about the crossover between two chromosomes? Or which GA operator are you referring to when you say "interact"?  
  > **username_0**: Two genes interact when their effect on individual fitness is non linear or epistatic. As for crossover by definition it is between two chromosomes.  
  > **username_1**: Can you give an example of such cases, where the vicinity of the genes in the chromosome determines the fitness of the individuals? Furthermore, note that the fitness of the individuals depends on the definition of the fitness function anyway.  
  > **username_0**: I don't know who changed the question but the change is inaccurate. Genes are not similar they interact epistatically or in simple words they act in combination and not singly. The linkage problem which was in the initial question is a known problem. An efficient GA solution needs an efficient chromosome ordering, but this is often not known at design time. If we could evolve the ordering  while evolving a solution the performance as measured by the number of generations to reach an optima can be much reduced, but only if linkage evolution is significantly faster than solution evolution.  
  > **username_1**: I changed the title. The title was "linkage problem in GA". This is not a question. Edit your post and ask a question in the title like "How do I solve the linkage problem in GAs?" (if this is your question). I am sorry I changed the meaning of your post: I just tried to improve it, but this can happen.  
  > **username_1**: Can you please link us to a paper or book that discusses the "linkage problem" you're referring to?  
  > **username_1**: I didn't say the fitness is affected by the linkage. I just said that the fitness of an individual depends on the definition of the fitness function.  
  > **username_0**: @username_1 the fitness of any individual is unaffected by the ordering, but the likelihood that useful sequences or building blocks using John Hollands terms are disrupted by crossover is severely affected. See the very simple 100 gene chromosome example, or if the genes A B and C occur in the optima in that order the more efficient order places them together in a uninterrupted single sequence which is the least likely form to be broken by crossover  
  > **username_1**: So, your problem is related to the crossover operator. This is what I had initially asked about.  
  > **username_0**: @username_1 https://www.springer.com/gp/book/9783642128332 and others just search for linkage problem  
  > **username_0**: @username_1 here's a more technical paper https://www.ncbi.nlm.nih.gov/pubmed/12689725  
  > **username_0**: @username_1 no crossover is unchanged, think of the linkage map as a reordering of the chromosome before the fitness function is applied; crossover and mutation operate on the form before reordering.  
  
  ---
  
  ## 0 answers
  
  