I want to solve the Physical Travelling Salesman Problem using an evolutionary algorithm.

The objective of the PTSP is to visit the maximum number of waypoints of the map in the minimum number of time steps. The map takes the form of a two-dimensional board, where ten waypoints are scattered around and multiple obstacles are present.

Now, I have a way to run random games and create "population" — a list of waypoints in the order we visit them. I need some idea how to do the crossover. I mean, how to create the next generation. I saw ideas, but they take in account that each gene contains all the waypoints on the map. (Take a random part from parent1 and take the waypoints that do not appear in parent1 from parent2 in the order they appear in parent2). What to do in case a gene contains just part of the waypoints?

  • $\begingroup$ Are you talking about problem from ptsp-game.net? $\endgroup$
    – Adam Stelmaszczyk
    Commented Jun 6, 2013 at 11:18
  • $\begingroup$ not for that competion , but this game $\endgroup$
    – user2459338
    Commented Jun 6, 2013 at 11:22

1 Answer 1


Have a look at this survey on crossover operators for TSP

It gives you the history of development on this area as well.

List of operators covered:

  • Partially Mapped Crossover (PMX) [Goldberg, 1985]
  • Order Crossover (OX) [Davis, 1985]
  • Edge Crossover (EX) [Whitley, 1989]
  • Subtour Exchange Crossover (SXX) [Yamamura, 1992]
  • Edge Exchange Crossover (EXX) [Maekawa, 1996]
  • Edge Assembly Crossover (EAX) [Nagata, 1997]
  • Partition Crossover (PX) [Whitley, 2009]
  • 1
    $\begingroup$ These mostly have the property he was trying to avoid -- they're permutation operators that rely on the fact that each parent contains all cities. However, often adapting a permutation operator for "incomplete" permutations can be a fruitful approach. $\endgroup$
    – deong
    Commented Jun 6, 2013 at 15:30
  • $\begingroup$ What I did is to choose 2 parents and then complete each with the waypoints he not have that exit in the other (I added the new points at the end of his path). Do you think it is agood idea? $\endgroup$ Commented Jun 6, 2013 at 15:40
  • $\begingroup$ @deong True. I really missed OP's requirement on that. Anyway, I just remembered that nice survey so I put it up there. $\endgroup$ Commented Jun 6, 2013 at 15:51
  • $\begingroup$ @user2459338 going by what is presented in that survey. I think your idea might be bad because "it introduces edges that does not exist in the parents". Basically, that's one of the main message I get from reading the survey. $\endgroup$ Commented Jun 6, 2013 at 15:53
  • $\begingroup$ ok thank! If someone has some suggestion i will glad to read... $\endgroup$ Commented Jun 6, 2013 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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