1
$\begingroup$

In a genetic algorithm, the order of the genes on a chromosome can have a significant effect on the performance (capacity to generate adaptation) 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 if there exists any known biological mechanism which is responsible for such a possible order of the genes on a chromosome.

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – nbro Jul 16 at 17:06
  • $\begingroup$ Two genes interact when their effect on individual fitness is non linear or epistatic. As for crossover by definition it is between two chromosomes. $\endgroup$ – Nick Jul 16 at 17:48
  • $\begingroup$ 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. $\endgroup$ – nbro Jul 16 at 18:24
  • $\begingroup$ 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. $\endgroup$ – Nick Jul 16 at 18:37
  • 1
    $\begingroup$ @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 $\endgroup$ – Nick Jul 16 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.