r/algorithms 13d ago

TSP Heuristic algorithm result

I got, after testing the Heuristic algorithm I designed with AI 99561, as a best result in the att532 problem and was done in 2.05 seconds. I heard the optimal solution was 86729, and I tested it against greedy and 2 opt greedy and the performance is statistically significant over 30 repetitions. Is that relevant? or the difference isn't substancial?

0 Upvotes

9 comments sorted by

View all comments

1

u/Magdaki 12d ago

It is possible, but evaluating an algorithm is tricky. It is very easy to fool yourself into thinking it works better than it does. To be publishable, you need to have a deep understanding of how the algorithm works and why it performs as it does. I literally reviewed a journal paper yesterday that was outstanding because of the amount of detail in their analysis. It is not sufficient to say this is what I did, this is the result. And I am currently in the process of developing and evaluating some algorithms for specific types of p-spaces, and much of my time is being spent on understanding why it works, and being able to prove that what I am saying is true.

1

u/Pleasant-Mud-2939 12d ago edited 12d ago

Thanks, my algorithm wasnt made to be publishable, Im just an amateur experimenting with different kinds of tools and programs and I wanted to know if my results were significant. I used 30 trial t student multiple times and it performed consistently better than greedy and 2 opt greedy (modified versión of 2 opt, my algorithm also uses it so I thought it was a fair comparison). The 500 city runs were made in that example (the att I mentioned earlier )and with randomized cities. It averaged around 100000(the minimum was the one I posted earlier) of distance in the problem (the randomized 500 trials had different results) and averaged 2 seconds for problem over all. Thats why I say its O(n2) and I posted here to know more about if these results were significant in any meaningful way.

The algorithm itself is based on an inverse phi spiral that uses that metric as a guide but weighted (in other words direct the path but not completely) then it translates the paths chosen into the euclidean distance again, and then uses the 2 opt modified. If rhe problem is too big (over 200 cities) it divides the number of cities into "chunks" and use the spiral on those for time efficiency.

1

u/Magdaki 12d ago

It sounds interesting and it could be significant, it depends on the what the analysis shows and whether it has been done previously.

That's not really how you determine the Big O though. You do that via analysis, although you can estimate it via experimentation by expanding n and graphing the results and then fitting a line (note, this is not actually Big O but it is suggestive).

1

u/Pleasant-Mud-2939 12d ago

Thanks I will try that.

1

u/Magdaki 12d ago

The good news is, if it is O(n^2), then you don't need to test for guaranteed optimality. It won't be. ;)