Why only 10 to 12 waypoints for optimization?

Communications Center General Discussion
61

@Mark_O_Helm Ive gotten up to 15 waypoints that have computed in an okay time before but thats my record. And yeah it gets bad above 12-13.

I used @Steve_Ronuken s ideas a lot in calculating my routes. Making 10-12 jump sections and then trying to tie the tails together to get a feasible efficiency. Took me making 3 general sections to get what I needed out of it. So total of 36 stops. Took me a good freaking while to do and memorize to do what I need to do in game.

Love the work and ideas going into this topic though. But its way above my pay grade as for knowledge lol.

1 Like
62

I made few tests now myself. Here are the results.

wp=waypoints
j=jumps
Calculation time in s=second

11wp = 120j > 106j= 4.5s
11wp = 144j > 106j = 5s
12wp = 124j > 110j = 28s
12wp = 152j > 110j = 28.5s
13wp = 132j > 112j = 134s
13wp = 163j > 112j = 140s

18wp = 18j > 18j = 77s

The results may vary if you do it yourself, but the times tell me, that the results of the optimization matter for the calculation time, rather than the stargate jump count, and that the server is willing to calculate the optimal route, how long it may take. Long term tests may fail. Time will tell.

2 Likes
63

I would suggest a contest, ā€œwho comes up with the best solutionā€, but there are many out there so someone will inevitably cheat. :confused:

64

Multiple cpu cores, or a single one, or on the GPU?
In which language?

65

I thought the consens here was that it is not hard to calculate, but takes longer than to watch every youtube video ever uploaded in past, present and future.

Did i understand it incorrectly? Wouldnā€™t be the first time. :thinking:

66

The usual term is ā€œit does not scaleā€. Whatever that means (typically there is a threshold after which itā€™s not practical)

1 Like
67

It depends on the amount of cities and the approach. Whenever someone finds a better way, the amount of time it takes to compute the solution decreases. Doesnā€™t really change anything about the problem per se, though, because in the end all thatā€™s needed is increasing the amount of cities and weā€™re back to square one.

That ends only once someone finds a way of solving problems, like the TSP, in a way that decouples the solution from the amount of cities. Not sure thatā€™s worded properly. Different:

When thereā€™s a solution that works equally fast for any amount of cities, or at least not turns exponentially slower with every added city, then thatā€™s the end of it and the respective holy grail has been found.

2 Likes
68

No, you canā€™t do that.

Solving a complexified problem(that is, the same problem but with increased solution space) takes always more time on average.

So basically you canā€™t have generic algorithms in constant time (unless the solution is trivial), there will always be a little factor on the size.

so that

is actually impossible (because the solution of TSP are not trivial) (assuming you meant algorithm instead of solution).

Well. The goal is to have real algorithms that work on real infrastructures.
eg one could store all the possible definitions of TSP for integer values and their optimal solution, eg up to 100 towns and distance from 1 to 1000 . With this table, the search algorithm would be in constant time ; however that means for n towns n * (n-1) /2 distances to define, thus 1000 ^(n * (n-1) /2 ) possible distance configurations ( actually less since we need to respect the triangle rule dist(a, b)+dist(b, c) >= dist(a, c) ). basically for n town the memory footprint would be in o(1000^nĀ²) which is impractical.

So itā€™s a bit more than time. In this case memory footprint for 20 towns would be 10^1200 bits, that is more than 10^50 times what the world produces in one year, ie with current production rate we would need 10^40 earth lifecycles to produce it

Just for the information, this memorization of a problem is actually a very common solution.
Dynamically storing the result of a costly operation is called caching it, and itā€™s so efficient at doing so that itā€™s been embedded in many chipsets ( eg CPUs have several layers of caches even though the algorithm is just ā€œfetch data from RAM at adress Xā€). Even your web browser know that the algorithm to fetch an image will be faster if the image is already stored in memory !!

2 Likes
69

Albert reads this thread:
image

1 Like
70

No I didnt code anything or have the computer calculate a huge trip, I just broke it down into smaller chunks so its not optimal but close enough for what Im doing. I certainly didnt solve any problem except my own.

1 Like
71

I threw together the genetic algorithm I described above, and it works quite well.

Was important to design the distances from waypoint to waypoint such that the optimal solution is known (since I canā€™t find it in reasonable time if unknown, as discussed here in depth). First, each waypoint is assigned a number such that the set of all points is {0, 1, 2, ā€¦, n-1}. The distance between 2 waypoints, say p1 and p2, is then defined as:
distance = abs( p1 - p2 )

Each waypoint is defined to be a distance from the start point equal to its label.

Thus the optimal total distance is n.

Each individual is just an ordered list of all waypoints, with the initial population consisting of randomized individuals.

The optimal individual is [0, 1, ā€¦, n-1]

For 20 waypoints and 20k evaluations (2k epochs with 10 offspring per) it takes just a few runs on average to get the optimal solution. On my computer each run takes seconds.

Increasing the number of waypoints to 50, it fails to find the optimal solution. At this size itā€™s usually about 2x-3x more total distance than optimal of 50. Here adjusting the mutation mechanism to swap ranges of waypoints rather than single points seems to help.

2 Likes
72

Been sadly neglecting this thread.
Too busy coding other things.
Right now Iā€™m wondering how to do this on the gfx card.

1 Like
73

not sure about this, but what about programing it in a scalar model ?
You anyhow need the matrix of distances, so it may become a viable solution. However GPGPU are not efficient when your algorithm has a high ratio of conditional operation per size of the vector operation. The pipeline is not as efficient as the pipeline of CPUs so conditional actually take much more cycles to process. (while on a normal cpu, the possible operation after the condition can be pre-executed simultaneously and their result retrieved only when the result of the conditional is known).

an evaluation
a github project using both genetic and GPGPU

1 Like
74

I wrote this tool in python. Itā€™s similar to what I suggested in my previous reply.
route_optimizer
This tool will optimize your route for a given set of waypoints. You can enter as many waypoints as you would like. There is no limit.

The tool does not attempt to incorporate your return to the starting point in the optimization and therefore does not involve the TSP. It will find the best route to visit all of your waypoints, but may leave you far from your starting point. Setting your destination to home will give you the best route back from your last waypoint.

It might be possible to include the TSP and attempt to find the best route including a return path to the origin. I will keep looking at it. If anyone wants to help with it, let me know. As of now, it does not do this, nor does it handle repeated trips to the same system throughout the planned trip.

Here is the program and the source code.

75

Ahh, finally someone is mentioning the difference between TSP and all pairs shortest path (or some derivative), the latter being firmly in P.
In the end, though, I am not sure you would not want to come back to your original start system and still want the trip to be optimal. :wink:

76

Thatā€™s not the only differenceā€¦ all pairs shortest path doesnā€™t give a shortest tour through all waypoints, just shortest paths/distances from any one point to another. It would be a first step in solving TSP for a set of waypoints if you didnā€™t already have said distances.

Removing the requirement to return to starting point does not reduce the time complexity in TSP. The start and end point in standard TSP are set, so they are not the source of the large search space. This arises from the large number of possible combinations of the waypoints between.

77

Iā€™m not sure I see the wisdom in solving, even if it were possible, this problem. Most of the problems I have getting away from gate camping ā€˜huntersā€™ in my little buzzard is because you are able to predict where Iā€™m going to have to go. Chokepoints, and shortest distance stuff. The assumption is that we all have to be ā€˜optimal.ā€™

I tend to just look at the starmap, and set a waypoint in the general direction I want to go, then look for another with the stats I like, add that to the list, and then another, and another, until I get where I sorta want to be. Iā€™m sure my list is a little longer than it has to be. Who cares?

This is a great intellectual puzzle and all, but Iā€™ve noticed that I actually die a lot less by being sub-optimal, because Iā€™m not traversing through very many chokepoints. Those are glaring red on the starmap if you select certain stats, and you can just avoid them.

You could say, hey, Iā€™m not an exploration dweeb - time is money, to me in my freighter! Same thing, though. If you get popped, did you make any money?

78

I think in this case, the route created is called a minimum length Hamiltonian path. The real problem is that in the EvE client, if you select 20 waypoints and click ā€œoptimizeā€, you will get a warning ā€œIt can take a ridiculous amount of time to calculate the optimal route when waypoints are more than 12.ā€ If you decide to proceed, the entire program hangs until itā€™s finished and you canā€™t do anything because the task does not run in the background.

I tried this not long ago and the game was unresponsive for so long, I just force quit the client and restarted it. This happens even if your waypoints do not include a trip back to the original system. At the moment, the tool I made should be able to do this in the background and give you an optimized route for well over 12 systems without interrupting your game. It just canā€™t calculate an optimized route if you include a trip back to the origin. I think that is when you have to deal with the TSP.

79

The standard TSP problem attempts to find a minimum length cycle that visits all points in a provided set of points. Say our set of points is: { A, B, C, ā€¦, Z }.

Another way to phrase this, if we want to start/end at point A, is: A -> { B, C, ā€¦, Z } -> A.
So our task is to find an ordering of the set between the Aā€™s ( { B, C, ā€¦, Z } ) that minimizes the total distance travelled. This is the TSP problem.

If we remove the requirement to return to the start point (make a cycle), then it becomes:
A -> { B, C, ā€¦, Z }
This is technically not the TSP problem. A minimum distance solution for this problem may not be the same as that for the true TSP problem. But, it should be clear that the size of the space we are searching to optimize ( { B, C, ā€¦, Z } ) remains unchanged. So the problem is not easier.

In terms of EVE, I donā€™t think itā€™s a minimum Hamiltonian path problem (MHP) either (although similar). Our shortest paths from any one point to another may go through another point in the list, which could technically violate the MHP problem. Also, MHP is NP-complete, so itā€™s not easier than TSP.

I donā€™t have time at the moment to fully trace the logic of your code, but at a glance I find it hard to believe that you are guaranteeing an optimal path. Have you checked your results against those provided in-game for routes of 10-12 waypoints? For an implementation that takes arbitrary length sets of waypoints I expect to see recursive function calls (maybe I just missed that?). I have no experience writing programs to interface with EVE in this way, so maybe you are outsourcing part of the algorithm to the server in a way I missed. A description/reference of the algorithm you are using would be easier to understand.

If your program is completing on waypoint lists of 20+, itā€™s almost certainly not guaranteeing an optimal result.

1 Like
80

Ooooohhhhhhh, something for me to optimize!

*clicks*

Why do you use threading, instead of multiprocessing? I understand that threading in python still helps as long as your code waits for IO, but in the end multiprocessing will always be superior due to not suffering from the GIL at all.

Iā€™ll have to shove free time into my day somehow.

Oh btw ā€¦ Windows or Linux?

1 Like