How to deal with crossover when sequence matters?

Question

How does one go about crossing over two parents when the children must have a particular ordering?

For example, when applying genetic algorithms to the Travelling Salesman Problem on a fixed graph of vertices / edges, you must contend with the fact that not all vertices can travel to other vertices. This makes crossover much more difficult because unlike the TSP in which all vertices may travel to all other vertices, when a crossover is performed it must be done at a point that produces a legal path. The alternative is to just crossover anyway and reject illegal paths, but the risk is great computational expensive and few to no legal paths.

I've read about permutation crossover but I'm not entirely sure how this solves the issue. Can someone point me in the right direction or advise?

Answer 1

Ordering should, as far as possible, not be a constraint in genetic programming. Maybe you should contemplate to pick up another format for your solutions. For example, in your TSP, consider the codon A->B.

Instead of the meaning 'take the edge from A to B', you could consider 'take the shortest path from A to B'. This way, your solutions are always feasible. You just have to pre-compute a shortest path matrix as a pre-processing.

Now, this does not guarantee that candidates will be feasible solutions after your crossover. Your crossover should be tuned in order to guarantee that your solution are still feasible. For example, for the TSP, consider the sequences :

1 : A B C D E F G H

2 : A D E G C B F H

Choose a pivot randomly (E in our example). This leads to the following sequences to be completed :

1' : A B C D E . . .

2' : A D E . . . . .

All the vertices have to be visited in order to have a valid solution. In 1', F, G and H have to be visited. We order them as they are in sequence 2. In 2', G, C, B, F and H are re-ordered as in 1 :

1' : A B C D E G F H

2' : A D E B C F G H

Hope this helps.