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.

Improve this question
$\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
    CommentedSep 2, 2021 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$
    – Neil Slater
    CommentedSep 2, 2021 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
    CommentedSep 2, 2021 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
    CommentedSep 2, 2021 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
    CommentedSep 4, 2021 at 11:07

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    CommentedSep 2, 2021 at 19:14

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.