Answers.Body: <p>Really you're entering the world in which you probably want to develop genetic operators that have meaning in your domain. You mention TSP, and correctly point out that the absolute position within the chromosome doesn't matter. There are other permutation problems where this isn't true. The Quadratic Assignment Problem (QAP) is one example. Like TSP, QAP solutions are represented as permutations of integers, and there are plenty of known recombination operators that work on permutations. But you need different operators for these cases. What works well for TSP won't be very good for QAP, and vice versa.</p>
  <p>For reference, a good place to start might be the Cycle Crossover (CX) operator. It's defined on permutations, and basically works by looking for &quot;cycles&quot; -- subsets of the indices where the two parents share the same values. For example, if you have parents</p>
  <pre><code>P1=&lt;2 3 7 1 4 6 5 8&gt; 
  P2=&lt;4 1 2 6 8 5 3 7&gt;
  </code></pre>
  <p>there's a cycle at the index set {0, 2, 4, 7}. Both parents contain the same four values at those positions in the string -- 2, 7, 4, and 8. You could create two new offspring by exchanging the values at those positions, yielding</p>
  <pre><code>C1=&lt;4 3 2 1 8 6 5 7&gt; 
  C2=&lt;2 1 7 6 4 5 3 8&gt;
  </code></pre>
  <p>This gives me two children, both of whom have the property that they inherited information from their parents related to the absolute position of each value in the string.</p>
  <p>That may or may not be exactly what you need for your problem. Maybe you don't have true permutations, or maybe something about that operator doesn't work well with your particular problem. The main point is that you need to build operators with intent. The idea has been called &quot;respectful recombination&quot;. Understanding what's important in your representation and devising operators that try to respect that property as they pass down information is the name of the game.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-02T19:14:43.880Z
Answers.Text: Thank you, I know the Cycle Crossover. I didn't think of it as a crossover method for solution vektors where indices play a role. But I can think of it as a solution where maybe the mutation is already included.
Answers.UserDisplayName: MrPlanck
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-02T13:57:38.887Z
Answers.LastActivityDate: 2021-09-02T13:57:38.887Z
Answers.UserDisplayName: deong
Body: <p>Is there a crossover that also considers that every index in the vector also influences the cost function?</p>
  <p>I have two vectors <span class="math-container">$v_1=[A_1, A_2, A_3, A_4, A_5]$</span> and <span class="math-container">$v_2=[A_5, A_3, A_2, A_1, A_4]$</span>.</p>
  <p>The fitness function considers the index where an element is located. So, basically, every vector represents a matching solution. Using a recombination method would deliver a new combination, but it won't be close to the previous solution, nor would they consider what makes the parents better than the other solution.</p>
  <p>In TSP, the indices don't really matter on the sequence of cities.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-02T11:16:56.910Z
Comments.Text: Firstly, Do you mean close in the solution space or close in the objective space?
  Secondly, CMIIW I don't think what you're looking for is recombination operators, because they are not meant to consider how to generate offspring that is better than the parents. You might want to incorporate improvement operator or local search as a replacement for mutation operator after the recombination is done that fulfill your goals (repair the offspring so that it's better than the parents, or close to the parents)
Comments.UserDisplayName: Sanyou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-02T12:36:45.653Z
Comments.Text: I am sure I have seen at least one smart genome design that allows recombination and mutation to be effective in GAs for combinatorial optimisation. And there are papers on this issue if searched. I may be able to ansewer later
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-02T13:07:54.760Z
Comments.Text: you are right, just a brief googling produced several results, at least for continuous solution representation, might need better key words for discrete problem. I might have ignorantly persisted on my old GA comprehension in which offspring is only evaluated after mutation, and improvement is done after that e.g. with local search and on the Elitist generation update. 
  Btw please excuse my shameless request, @NeilSlater if you have another spare time can you please take a look at my question on how to represent terminating action on RL? I've seen you answer similar question on crossvalidated
Comments.UserDisplayName: Sanyou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-02T16:37:15.763Z
Comments.Text: @Sanyou I mean rather that the children should reflect the properties of the parents. As far as I know, the intention of selecting best solutions and apply a crossover is to produce a better solution. But my Problem is that swapping the subelements of the parent would assing different indices to the elements. But the place of the solution in the solution vector is important.
Comments.UserDisplayName: MrPlanck
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-04T11:07:56.527Z
Comments.Text: Well, if I may ask you to put all aside first and advise some formatting so the problem is clearer? You can mention the problem you are solving with GA first instead of just mentioning a fun fact of TSP at the very end. It's not clear whether you are solving TSP or other similar problem. Secondly, you still did not clearly explain what this closeness between parent and offspring solution that you're aiming is (properties)? is it in the objective or solution space? How will you perhaps quantify this closeness after the offspring is generated? An example of fitness calculation is helpful too.
Comments.UserDisplayName: Sanyou
Tags: <genetic-algorithms><crossover-operators><fitness-functions><travelling-salesman-problem><chromosomes>
Title: Is there a crossover that also considers that every index in the vector also influences the fitness function?
UserDisplayName: MrPlanck
ThreadText: # Is there a crossover that also considers that every index in the vector also influences the fitness function?
  
  (Asked by: username_0 on 2021-09-02)
  
  Is there a crossover that also considers that every index in the vector also influences the cost function?
  
  I have two vectors $v\_1=[A\_1, A\_2, A\_3, A\_4, A\_5]$ and $v\_2=[A\_5, A\_3, A\_2, A\_1, A\_4]$.
  
  The fitness function considers the index where an element is located. So, basically, every vector represents a matching solution. Using a recombination method would deliver a new combination, but it won't be close to the previous solution, nor would they consider what makes the parents better than the other solution.
  
  In TSP, the indices don't really matter on the sequence of cities.
  
  **Tags:** genetic-algorithms, crossover-operators, fitness-functions, travelling-salesman-problem, chromosomes
  > **Comments:**
  > **username_1**: Firstly, Do you mean close in the solution space or close in the objective space? Secondly, CMIIW I don't think what you're looking for is recombination operators, because they are not meant to consider how to generate offspring that is better than the parents. You might want to incorporate improvement operator or local search as a replacement for mutation operator after the recombination is done that fulfill your goals (repair the offspring so that it's better than the parents, or close to the parents)  
  > **username_2**: I am sure I have seen at least one smart genome design that allows recombination and mutation to be effective in GAs for combinatorial optimisation. And there are papers on this issue if searched. I may be able to ansewer later  
  > **username_1**: you are right, just a brief googling produced several results, at least for continuous solution representation, might need better key words for discrete problem. I might have ignorantly persisted on my old GA comprehension in which offspring is only evaluated after mutation, and improvement is done after that e.g. with local search and on the Elitist generation update.  Btw please excuse my shameless request, @NeilSlater if you have another spare time can you please take a look at my question on how to represent terminating action on RL? I've seen you answer similar question on crossvalidated  
  > **username_0**: @Sanyou I mean rather that the children should reflect the properties of the parents. As far as I know, the intention of selecting best solutions and apply a crossover is to produce a better solution. But my Problem is that swapping the subelements of the parent would assing different indices to the elements. But the place of the solution in the solution vector is important.  
  > **username_1**: Well, if I may ask you to put all aside first and advise some formatting so the problem is clearer? You can mention the problem you are solving with GA first instead of just mentioning a fun fact of TSP at the very end. It's not clear whether you are solving TSP or other similar problem. Secondly, you still did not clearly explain what this closeness between parent and offspring solution that you're aiming is (properties)? is it in the objective or solution space? How will you perhaps quantify this closeness after the offspring is generated? An example of fitness calculation is helpful too.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2021-09-02. Score: 2
  
  Really you're entering the world in which you probably want to develop genetic operators that have meaning in your domain. You mention TSP, and correctly point out that the absolute position within the chromosome doesn't matter. There are other permutation problems where this isn't true. The Quadratic Assignment Problem (QAP) is one example. Like TSP, QAP solutions are represented as permutations of integers, and there are plenty of known recombination operators that work on permutations. But you need different operators for these cases. What works well for TSP won't be very good for QAP, and vice versa.
  For reference, a good place to start might be the Cycle Crossover (CX) operator. It's defined on permutations, and basically works by looking for "cycles" -- subsets of the indices where the two parents share the same values. For example, if you have parents
  P1=<2 3 7 1 4 6 5 8> 
  P2=<4 1 2 6 8 5 3 7>
  
  there's a cycle at the index set {0, 2, 4, 7}. Both parents contain the same four values at those positions in the string -- 2, 7, 4, and 8. You could create two new offspring by exchanging the values at those positions, yielding
  C1=<4 3 2 1 8 6 5 7> 
  C2=<2 1 7 6 4 5 3 8>
  
  This gives me two children, both of whom have the property that they inherited information from their parents related to the absolute position of each value in the string.
  That may or may not be exactly what you need for your problem. Maybe you don't have true permutations, or maybe something about that operator doesn't work well with your particular problem. The main point is that you need to build operators with intent. The idea has been called "respectful recombination". Understanding what's important in your representation and devising operators that try to respect that property as they pass down information is the name of the game.
  
  > **Comments:**
  > **username_0**: Thank you, I know the Cycle Crossover. I didn't think of it as a crossover method for solution vektors where indices play a role. But I can think of it as a solution where maybe the mutation is already included.  
  
  ---
  
  