1
$\begingroup$

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?

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

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]
Improve this answer
$\endgroup$
5
  • 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 Jun 6 '13 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$ – user2459338 Jun 6 '13 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$ – Apiwat Chantawibul Jun 6 '13 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$ – Apiwat Chantawibul Jun 6 '13 at 15:53
  • $\begingroup$ ok thank! If someone has some suggestion i will glad to read... $\endgroup$ – user2459338 Jun 6 '13 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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