News for hackers. Stuff that matters.
Re:Ant Colony Optimization Visualization for the Travelling ... by toolslive on Friday December 13, 2019 @03:02AM (#21779907)
"The ACO algorithm is used to solve the problem more efficiently than a brute-force approach". That's rather misleading as it's not a problem at all to find a solution (fe try the nearest neighbour heuristic). The problem with TSP is that you want to prove that your solution IS the optimum. If you're interested in the optimum, you need something like `branch-and-bound`. Anyway, I did the exact same visualization as part of my master's in 1996 (but using distributed memetic algorithms iso ACO)
Re:Ant Colony Optimization Visualization for the Travelling ... by jeremysalwen on Friday December 13, 2019 @04:37AM (#21780307)
Obviously finding good tours with a limited computational budget is an interesting problem[1]. So, no, it's not misleading, as this method is more efficient at finding good tours than brute-force (as claimed), and is even better than the NN heuristic.

[1] https://en.wikipedia.org/wiki/Travelling_salesman_problem#He...

Re:Ant Colony Optimization Visualization for the Travelling ... by 7thaccount on Friday December 13, 2019 @08:37AM (#21781368)
Branch-and-bound MIP isn't very computationally intensive. I run models with millions of variables and constraints on my laptop.

The commercial solvers (fast and best) are very expensive though. So you're kind of right in a eay.

Re:Ant Colony Optimization Visualization for the Travelling ... by toolslive on Friday December 13, 2019 @07:30AM (#21780977)
at least you should specify which brute force approach you're comparing it with.
Re:Ant Colony Optimization Visualization for the Travelling ... by thaumasiotes on Friday December 13, 2019 @08:39AM (#21781381)
What do you imagine the different brute force approaches are? I would assume the brute force approach is to calculate the cost of every possible route and choose the one that had the lowest cost.
Re:Ant Colony Optimization Visualization for the Travelling ... by thaumasiotes on Friday December 13, 2019 @07:45AM (#21781059)
> The problem with TSP is that you want to prove that your solution IS the optimum.

This can't be right? The whole definition of an NP problem is that while the solution may or may not be hard to find, it's always easy to verify the correct solution if somebody gives it to you.

As applied to "you want to prove that your solution is the optimum", that means there is a polynomial-time algorithm to do exactly that. That's what verifying the solution means.

The problem with TSP is that it's hard to determine what the solution is, not that it's hard to determine that the correct solution really is correct.

Re:Ant Colony Optimization Visualization for the Travelling ... by LeonB on Friday December 13, 2019 @08:40AM (#21781398)
I just read up on this. If what I read is true, TSP is NP-hard not NP complete. You can’t trivially prove that the solution is optimum.

Reference: https://eklitzke.org/the-traveling-salesman-problem-is-not-n...

Re:Ant Colony Optimization Visualization for the Travelling ... by thaumasiotes on Friday December 13, 2019 @08:49AM (#21781453)
There is a conversion between the decision problem I mentioned ("is there a path of length less than some fixed L?") and the general problem "what is the minimum path length?".

If a solution exists, it will have length less than or equal to the product of (1) the maximum edge cost and (2) the number of nodes in the graph.[1]

You can then find the actual minimum length by doing a binary search on the threshold below which there is no solution.

And it's very easy to show that the decision problem is in NP -- given a candidate path, it is trivial to verify that its cost is less than a constant L.

So we have the results that (1) the decision problem is NP-complete; (2) the general problem can be solved in polynomial time if you can solve the decision problem in polynomial time. That's enough to show the general problem is NP-complete.

[1] Under the assumption that the graph is complete and has no edges of infinite cost. Without that assumption, multiply (1) the maximum finite edge cost; (2) the number of finite-cost edges in the graph; (3) the number of nodes in the graph.

Re:Ant Colony Optimization Visualization for the Travelling ... by toolslive on Friday December 13, 2019 @08:18AM (#21781234)
with the TSP, any permutation of the list of cities is a correct solution. They just differ in length of the tour.

An optimal solution S has len(S) = min {len(P) | P in Perm(cities)}

Re:Ant Colony Optimization Visualization for the Travelling ... by thaumasiotes on Friday December 13, 2019 @08:24AM (#21781269)
No, the correct solution is the one that achieves the minimum travel cost[1]. If any route at all was a correct solution, the problem wouldn't be NP-complete -- it would be the much easier problem of "determine whether a path exists between two nodes in a graph".

[1] It's actually easier to analyze the version of the problem which asks you to find any solution of length less than some constant L.

Re:Ant Colony Optimization Visualization for the Travelling ... by toolslive on Friday December 13, 2019 @08:36AM (#21781354)
So your view is that the heuristic methods (NN, 2-opt,...) do not yield a solution?
Re:Ant Colony Optimization Visualization for the Travelling ... by thaumasiotes on Friday December 13, 2019 @08:42AM (#21781406)
They do not necessarily yield a correct solution. For example, under a heuristic approach, if you ask "is there a path of length < L?", you may get the answer "no" when the actual answer is "yes".

You seem to be confused over the difference between "solution", in the sense of the answer to a well-defined mathematical problem, and "solution", in the sense of "what do I say to my boss?"

Re:Ant Colony Optimization Visualization for the Travelling ... by toolslive on Friday December 13, 2019 @09:03AM (#21781556)
At least Wikipedia disagrees with your view.

https://en.wikipedia.org/wiki/Travelling_salesman_problem#He...

I'm not confused. For the ACO, Genetic algorithms,... approaches you still need to show that the tour that was found has the lowest possible length... which you cannot without iterating all tours (or doing a branch and bound, which is the same but you prune bad partial tours early).

Obviously, people typically work with well known problems where the best tour is already known. They then typically determine the quality of their 'solution' as the relative difference to the best tour in some metric.

Re:Ant Colony Optimization Visualization for the Travelling ... by thaumasiotes on Friday December 13, 2019 @09:04AM (#21781565)
> At least Wikipedia disagrees with your view.

This is a strange thing to say, given the definition provided in the link you cite:

> The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?"