How to deal with crossover when sequence matters?

Question

How to pass through two parents when children must have a certain order?

For example, when applying genetic algorithms to the problem of a traveling salesman on a fixed graph of vertices / edges, you must struggle with the fact that not all vertices can move to other vertices. This makes the crossover a lot more complicated, because unlike the TSP, in which all vertices can move to all other vertices when the crossover is done, this must be done at the point that creates the legal path. The alternative is just a crossover in any case and rejection of illegal paths, but the risk is high computational costly, and few - no legal paths.

I read about crossover permutations, but I'm not quite sure how this solves the problem. Can someone point me in the right direction or advise?

Answer 1

Ordering should, as far as possible, not be limited to genetic programming. Perhaps you should consider choosing a different format for your solutions. For example, in your TSP, consider codon A-> B.

Instead of taking the edge from A to B, you might consider taking the shortest path from A to B. Thus, your decisions are always possible. You just need to pre-calculate the shortest path matrix as preprocessing.

Now this does not guarantee that candidates will become possible solutions after your crossover. Your crossover must be tuned to ensure that your solution is still possible. For example, for TSP, consider the sequences:

1: ABCD E FGH

2: AD E GCBFH

Choose our case randomly ( E in our example). This leads to the following sequences:

1 ': ABCD E .,.

2 ': AD E. ,,.

All peaks must be visited in order to have the right decision. In 1 ', you should visit F, G and H. We order them as they are in sequence 2. In 2', G, C, B, F and H are reordered, as in 1:

1 ': ABCD E GFH

2 ': AD E BCFGH

Hope this helps.