8

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?

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
user2341412
  • 413
  • 2
  • 8
  • 14
  • In Dawrinian evolution, what happens if a new organism isn't valid? How does nature deal with this? – San Jacinto May 08 '13 at 19:06
  • 4
    It gets rejected, but Darwinian evolution doesn't have to worry about exponential rises in computation. – user2341412 May 08 '13 at 19:14
  • Not sure why all the close-votes, this is a perfectly valid (and on-topic) question – BlueRaja - Danny Pflughoeft May 08 '13 at 23:01
  • The same question, phrased differently : [Crossover operator for permutations](http://stackoverflow.com/questions/14420411/crossover-operator-for-permutations/14420887#14420887), has already been answered previously: [What you are looking for is ordered crossover](http://stackoverflow.com/questions/14420411/crossover-operator-for-permutations?answertab=votes#tab-top). – CmdNtrf May 09 '13 at 15:26
  • By the way, you have never validated any answer to your questions. You might consider reading the [about](http://stackoverflow.com/about) page in order to learn how to behave on the website. – JonasVautherin May 23 '13 at 09:43

1 Answers1

4

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.

David
  • 1,138
  • 5
  • 15