Sci-hype: the traveling salesman problem, now with bees (again)
Over at slate there's an article about how the birds and the bees do it (solve the Traveling Salesman Problem). By now, this should be a genre of pop-sci article I think. "Here's this incredibly difficult problem; humans struggle with it, massive computers are needed to solve it, yet these simple beings do it so efficiently".
And it's uniformly crud, an example of the bad pop-sci that so annoys me.
The one good thing with the slate article is the lukewarm response it received in the comments section, so there's hope for humanity yet.
The article starts with the question "who would you ask to plan your commute (between several goals of interest), a bee or a mathematician?" So provocative! So catchy! So stupid, because a pretty good answer to the question is- "yourself".
The travelling salesman problem (aka, TSP) is about finding the lowest cost route between a collection of points, when given the distances/costs to move between them. It asks that all points of interest be visited once and only once. And yes, the hype has it right in one respect- it's a genuinely tough problem.
Since every point needs to be visited once and only once, the only thing that determines a solution is the order of the visits. So for n points, then all permutations of those points are possible solution candidates; which is, n! permutations (n*(n-1)*(n-2)*...), and n! grows very fast with n. What makes finding the right solution tough is that, in general, there's no easy way to eliminate large swaths of those possibilities from consideration.
To further complicate matters, if someone shows you a claimed shortest path, there's no easy way to check that it is actually so; you need to run another, fairly complex algorithm to obtain a yes/no answer to the question "is there a path shorter than this?"
So then, let's look at the claims made by the "TSP by bees" genre. It doesn't have to be bees, it could be birds, or colonies of mold, or soap water.
"TSP is hard": as said, that much is true.
"TSP is difficult to solve by computers", "TSP is difficult to solve by humans": here the pop-sci slips in a double standard. Bees can compute allegedly optimal paths to five flowers, so it is claimed they are efficient at TSP. A five-point TSP however is nigh-trivial for a computer; even brute force suffices, as there are a mere 5!=120 paths to check. In fact, there are a whole host of methods, some of them exact, to solve TSPs for thousands of points and the wikipedia article gives a good summary of them.
Humans aren't too shabby with TSP either. The first issue of the fifth volume of the Journal of Problem Solving presents some studies on humans vs. TSP, and if the problem doesn't have too many points, it's easily solved. Which is why the best answer for the question in the slate article is, yourself.
"There are no known methods to solve TSP": usually qualified because the statement as mentioned here is too extreme. It would be said, "there are no efficient methods" or "there are no exact methods".
Both are wrong. One can either use an exact method on a computer, of which we have a few, or a heuristic which, while not guaranteed to get THE best solution, will get a pretty good one and do so reasonably fast.
Meanwhile, the magical abilities of bees are touted on problems that are small, and the abilities of birds are touted on problems where apparently nobody bothered to check that the birds really got the best, or even a good, solution. The slate article mentions that birds can navigate between thousands of pits where they stored seeds. Good for them. Not once does it mention that someone bothered to check that their paths were the best, or even close to the best.
It's the double standard hitting again. Yes, you can make problem instances that exact algorithms will run for millennia (or more) while trying to solve for the best solution. Nobody then mentions that those aren't the problems the birds, or whatever, are solving, and nobody actually brings a comparison with what a heuristic, or a human, would do.
Such a comparison would be illuminating, but nobody in the TSP-by-bees genre does it. It's not just time, there's also the quality of the proposed solution that matters. It's very likely that the birds use heuristics, and it would be genuinely interesting to pit birds and human designed heuristics against each other on different problem instances, timing to see who's fastest, while comparing the solutions to see how good they are are.
When seriously pursued, such a study would show on which instances one heuristic, say the birds', performs "better", and in which instances the particular heuristic implemented on the computer is better. Heuristics don't work equally well on every possible instance; they sacrifice general performance for efficiency in a subclass that's likely to be the one most often encountered.
So why does crud like TSP-by-bees get published? I suppose it's always inspiring to read about the wonder of the natural world, and animal cognition, like all cognition, is simply a nifty field to study. There's probably a dose of provocation, of appeal to humility, which isn't a misplaced intention. The results however are very poor, even on the level of pop-sci. They fail to present the science they invoke. And that should be a capital sin.
And it's uniformly crud, an example of the bad pop-sci that so annoys me.
The one good thing with the slate article is the lukewarm response it received in the comments section, so there's hope for humanity yet.
The article starts with the question "who would you ask to plan your commute (between several goals of interest), a bee or a mathematician?" So provocative! So catchy! So stupid, because a pretty good answer to the question is- "yourself".
The travelling salesman problem (aka, TSP) is about finding the lowest cost route between a collection of points, when given the distances/costs to move between them. It asks that all points of interest be visited once and only once. And yes, the hype has it right in one respect- it's a genuinely tough problem.
Since every point needs to be visited once and only once, the only thing that determines a solution is the order of the visits. So for n points, then all permutations of those points are possible solution candidates; which is, n! permutations (n*(n-1)*(n-2)*...), and n! grows very fast with n. What makes finding the right solution tough is that, in general, there's no easy way to eliminate large swaths of those possibilities from consideration.
To further complicate matters, if someone shows you a claimed shortest path, there's no easy way to check that it is actually so; you need to run another, fairly complex algorithm to obtain a yes/no answer to the question "is there a path shorter than this?"
So then, let's look at the claims made by the "TSP by bees" genre. It doesn't have to be bees, it could be birds, or colonies of mold, or soap water.
"TSP is hard": as said, that much is true.
"TSP is difficult to solve by computers", "TSP is difficult to solve by humans": here the pop-sci slips in a double standard. Bees can compute allegedly optimal paths to five flowers, so it is claimed they are efficient at TSP. A five-point TSP however is nigh-trivial for a computer; even brute force suffices, as there are a mere 5!=120 paths to check. In fact, there are a whole host of methods, some of them exact, to solve TSPs for thousands of points and the wikipedia article gives a good summary of them.
Humans aren't too shabby with TSP either. The first issue of the fifth volume of the Journal of Problem Solving presents some studies on humans vs. TSP, and if the problem doesn't have too many points, it's easily solved. Which is why the best answer for the question in the slate article is, yourself.
"There are no known methods to solve TSP": usually qualified because the statement as mentioned here is too extreme. It would be said, "there are no efficient methods" or "there are no exact methods".
Both are wrong. One can either use an exact method on a computer, of which we have a few, or a heuristic which, while not guaranteed to get THE best solution, will get a pretty good one and do so reasonably fast.
Meanwhile, the magical abilities of bees are touted on problems that are small, and the abilities of birds are touted on problems where apparently nobody bothered to check that the birds really got the best, or even a good, solution. The slate article mentions that birds can navigate between thousands of pits where they stored seeds. Good for them. Not once does it mention that someone bothered to check that their paths were the best, or even close to the best.
It's the double standard hitting again. Yes, you can make problem instances that exact algorithms will run for millennia (or more) while trying to solve for the best solution. Nobody then mentions that those aren't the problems the birds, or whatever, are solving, and nobody actually brings a comparison with what a heuristic, or a human, would do.
Such a comparison would be illuminating, but nobody in the TSP-by-bees genre does it. It's not just time, there's also the quality of the proposed solution that matters. It's very likely that the birds use heuristics, and it would be genuinely interesting to pit birds and human designed heuristics against each other on different problem instances, timing to see who's fastest, while comparing the solutions to see how good they are are.
When seriously pursued, such a study would show on which instances one heuristic, say the birds', performs "better", and in which instances the particular heuristic implemented on the computer is better. Heuristics don't work equally well on every possible instance; they sacrifice general performance for efficiency in a subclass that's likely to be the one most often encountered.
So why does crud like TSP-by-bees get published? I suppose it's always inspiring to read about the wonder of the natural world, and animal cognition, like all cognition, is simply a nifty field to study. There's probably a dose of provocation, of appeal to humility, which isn't a misplaced intention. The results however are very poor, even on the level of pop-sci. They fail to present the science they invoke. And that should be a capital sin.
Comments
Post a Comment