1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$
    – Sanyou
    Sep 2 at 11:16
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 2 at 12:36
  • $\begingroup$ 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 $\endgroup$
    – Sanyou
    Sep 2 at 13:07
  • $\begingroup$ @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. $\endgroup$
    – MrPlanck
    Sep 2 at 16:37
  • $\begingroup$ 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. $\endgroup$
    – Sanyou
    Sep 4 at 11:07
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – MrPlanck
    Sep 2 at 19:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.