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!

Improve this question
$\endgroup$
3
  • 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
    Commented Jun 13, 2013 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
    Commented Jun 13, 2013 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
    Commented Jun 13, 2013 at 18:48

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 14, 2013 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
    Commented Jun 14, 2013 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
    Commented Jun 14, 2013 at 20:06

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.