# Evolutionary algorithm for the Physical Travelling Salesman Problem

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?

• Are you talking about problem from ptsp-game.net?
Jun 6 '13 at 11:18
• not for that competion , but this game
– user2459338
Jun 6 '13 at 11:22

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]
• 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. Jun 6 '13 at 15:30
• 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? Jun 6 '13 at 15:40
• @deong True. I really missed OP's requirement on that. Anyway, I just remembered that nice survey so I put it up there. Jun 6 '13 at 15:51
• @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. Jun 6 '13 at 15:53
• ok thank! If someone has some suggestion i will glad to read... Jun 6 '13 at 15:56