5 ms·

Ant Colony Optimization Visualization for the Travelling Salesman Problem

90 points by jonbaer 7y ago

toolslive 7y ago
"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)
- jeremysalwen 7y ago
  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#Heuristic_and_approximation_algorithms https://en.wikipedia.org/wiki/Travelling_salesman_problem#He...
  - toolslive 7y ago
    at least you should specify which brute force approach you're comparing it with.
    - thaumasiotes 7y ago
      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.
  - 7thaccount 7y ago
    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.
- thaumasiotes 7y ago
  > 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.
  - toolslive 7y ago
    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)}
    - thaumasiotes 7y ago
      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.
      - toolslive 7y ago
        So your view is that the heuristic methods (NN, 2-opt,...) do not yield a solution?
        thaumasiotes 7y ago
        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?"
secretdark 7y ago
Neat! A while ago I did something similar using genetic algorithms. https://vimeo.com/666317 https://vimeo.com/666317
- caiobegotti 7y ago
  "A while ago" being like 12 years was actually funny, great work, thanks for sharing it :-)
account73466 7y ago
If you will even need to solve TSP, this guy solved it almost optimally for millions of cities http://webhotel4.ruc.dk/~keld/ http://webhotel4.ruc.dk/~keld/ This is from my experience of dealing with it more than a decade ago.
cheeko1234 7y ago
Any way to run these offline?
MayeulC 7y ago
Nice visualization! I wish there was a way to share the graphs. An interesting thing to notice is how the previous (hard to find) optimal solution is lost when adding a node at the opposite side of the graph (which is far enough to be irrelevant in most cases). I would therefore just insert the new point between the two closest nodes, and keep the same path as the starting point for the optimization. Of course, the risk with that methodology is to fall into a hard-to-escape local maxima. There is probably a way to infer how much a new point will affect every given node, so maybe a better way to proceed would be to identify those that are likely to be affected, and only re-run the optimization from scratch for those. Of course, where you position the limit itself is an optimization problem... (edit: or just persist pheromones, regardless of the new points?)
- MayeulC 7y ago
  One idea crosses my mind: are there examples where this algorithm can pass by a drastically better solution without finding it? Is there a way to deterministically find these families of solutions (even if not directly the optimal among that family?)

90 points by jonbaer 7y ago

"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)

jeremysalwen 7y ago
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#Heuristic_and_approximation_algorithms https://en.wikipedia.org/wiki/Travelling_salesman_problem#He...
- toolslive 7y ago
  at least you should specify which brute force approach you're comparing it with.
  - thaumasiotes 7y ago
    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.
- 7thaccount 7y ago
  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.
thaumasiotes 7y ago
> 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.
- toolslive 7y ago
  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)}
  - thaumasiotes 7y ago
    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.
    - toolslive 7y ago
      So your view is that the heuristic methods (NN, 2-opt,...) do not yield a solution?
      - thaumasiotes 7y ago
        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?"

secretdark 7y ago

Neat! A while ago I did something similar using genetic algorithms. https://vimeo.com/666317 https://vimeo.com/666317

caiobegotti 7y ago
"A while ago" being like 12 years was actually funny, great work, thanks for sharing it :-)

account73466 7y ago

If you will even need to solve TSP, this guy solved it almost optimally for millions of cities http://webhotel4.ruc.dk/~keld/ http://webhotel4.ruc.dk/~keld/ This is from my experience of dealing with it more than a decade ago.

cheeko1234 7y ago

Any way to run these offline?

MayeulC 7y ago

Nice visualization! I wish there was a way to share the graphs. An interesting thing to notice is how the previous (hard to find) optimal solution is lost when adding a node at the opposite side of the graph (which is far enough to be irrelevant in most cases). I would therefore just insert the new point between the two closest nodes, and keep the same path as the starting point for the optimization. Of course, the risk with that methodology is to fall into a hard-to-escape local maxima. There is probably a way to infer how much a new point will affect every given node, so maybe a better way to proceed would be to identify those that are likely to be affected, and only re-run the optimization from scratch for those. Of course, where you position the limit itself is an optimization problem... (edit: or just persist pheromones, regardless of the new points?)

MayeulC 7y ago
One idea crosses my mind: are there examples where this algorithm can pass by a drastically better solution without finding it? Is there a way to deterministically find these families of solutions (even if not directly the optimal among that family?)