2
$\begingroup$

I'm trying to solve this problem using genetic algorithms and am having difficulty choosing the fitness function. My problem is a little different than the original Traveling Salesman Problem, since the population and maybe also the win unit do not necessarily contain all the cities.

So, I have 2 values for each unit: the amount of cities he visits, the total time and the order he visits the cities. I tried 2-3 fitness function but they don't give good solutions.

I need an idea of a good fitness function which takes into account the amount of cities he visited and also the total time.

EDIT: more accurate description

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. The following image is an example of a map with obstacles and waypoints

Thanks!

$\endgroup$
  • 1
    $\begingroup$ You might want to clarify your question a little more to get a good answer. The usual travelling salesman problem means finding the path which visits every city in the least total time. From what I gather, your problem is slightly different, in that the salesman is allowed to skip some cities, and you're trying to optimize for the greatest number of cities and the least time. Is that correct? $\endgroup$ – Daniel Shapero Jun 13 '13 at 14:36
  • 1
    $\begingroup$ Also, genetic algorithms really aren't well-suited to TSP-style problems, which usually benefit from taking advantage of the underlying geometric structure of the graph. $\endgroup$ – Aron Ahmadia Jun 13 '13 at 15:19
  • $\begingroup$ Yes , you right. My target is that at end , the result will be most of the cities with the least time. The game is taken from here ptsp-game.net (I don't participate in the competition. This is for a project I do). Thanks $\endgroup$ – user2459338 Jun 13 '13 at 18:48
1
$\begingroup$

You have a multi-objective optimization problem: you want to maximize the number of cities but also minimize the amount of time. This is, by itself, not a well posed problem since you need to say which of two solutions $(N_1,T_1)$ and $(N_2,T_2)$ is better if two paths visit $N_i$ cities and take $T_i$ time units. What you need to do, then, is to first define a partial ordering of such tuples that describes which of the two you consider better. Once you have that, coming up with an objective function will become mostly obvious.

$\endgroup$
  • $\begingroup$ Thanks. As I write in my post "The objective of the PTSP is to visit the maximum number of waypoints of the map in the minimum number of time steps." I assume amount of waypoint is more important than the time but I still want to give the time is place.. $\endgroup$ – user2459338 Jun 14 '13 at 14:43
  • $\begingroup$ For example , I prefer 20 points in 300 seconds per point rather then 30 points but 500 seconds per point. I need some idea how to do it smart... $\endgroup$ – user2459338 Jun 14 '13 at 16:07
  • $\begingroup$ Well, but that's exactly the point of concisely stating what's of interest to you. Given your example, the objective function could be $f(N,T)=-15N+T$ which you would want to minimize. This satisfies the verbal description you have in the second comment. But whether that's what you really want is something that only you can answer. $\endgroup$ – Wolfgang Bangerth Jun 14 '13 at 20:06

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.