# Evolutionary algorithm - Traveling Salesman -fitness function

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!

• 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? – Daniel Shapero Jun 13 '13 at 14:36
• 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. – Aron Ahmadia Jun 13 '13 at 15:19
• 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 – user2459338 Jun 13 '13 at 18:48

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.
• 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. – Wolfgang Bangerth Jun 14 '13 at 20:06