Bees Beat Machines At 'Traveling Salesman' Problem 394
eldavojohn writes "Recent research on bumble bees has proven that the tiny bee is better than computers at the traveling salesman problem. As bees visit flowers to collect nectar and pollen they discover other flowers en route in the wrong order. But they still manage to quickly learn and fly the optimally shortest path between flowers. Such a problem is NP-Hard and keeps our best machines thinking for days searching for a solution but researchers are quite interested how such a tiny insect can figure it out on the fly — especially given how important this problem is to networks and transportation. A testament to the power of even the smallest batch of neurons or simply evidence our algorithms need work?"
Heuristic (Score:4, Insightful)
Is it possible that the honey bees aren't really solving the Traveling Salesmen problem at all, but rather employ some sort of unknown heuristic that leads to solutions that's close enough to optimal for it to look like that they've solved it? Maybe that's what we should be looking at rather than pondering if bees somehow have some sort of superior calculating ability over a supercomputer.
After all, when we're playing a game of baseball (right, right, I know, this is slashdot), and a ball is coming towards us, we aren't calculating in our heads the velocity, air resistance and other variables involved in catching the ball. We just reach out our arms and our brain makes its best guess based on some sort of heuristic or something to make the catch.
Re:Evidence (Score:3, Insightful)
who/what is god?
I doubt it (Score:3, Insightful)
First and foremost, how many nodes are we talking about here? I highly doubt that the bees are keeping track of hundreds of feeding spots from one trip out to the next but the article doesn't say.
The second problem is this "Computers solve it by comparing the length of all possible routes and choosing the shortest." Who on earth would try to solve the traveling salesman this way? Yeah, a brute force solution will get you the guaranteed best path, but the performance is horrible. There's lots and lots of shortcuts that can save a huge amount of time, things as simple as eliminating crossed paths can make a big difference. You can even use techniques like genetic engineering successfully on such a problem (though you might not reach the absolute best path that way).
p=np (Score:1, Insightful)
Re:I doubt it (Score:5, Insightful)
I think you mean genetic algorithms. Genetic engineering is...something else.
Re:Shortcuts (Score:5, Insightful)
Which makes the problem more difficult, not less. The way it is usually presented in CS the distance between the nodes is the minimum cost path, the bees would also have to 'calculate' that in addition to solving for the correct order. Think about it this way, imagine trying to solve the traveling salesman path between 100 cities, but you can take any route you want between cities. You could take all the back roads, the freeway, you could hop on a train or an airplane, you could kayak down the river between two cities. It doesn't make the problem any easier, in fact it adds a ton more variables to the mix, effectively increasing the number of routes that would need to be checked using a brute force solution.
Re:Heuristic (Score:2, Insightful)
your just playing word games... if i've developed a method of figuring out how to catch a ball without using newtonian physics, I've still solved the problem.
Different Spaces (Score:5, Insightful)
After all, when we're playing a game of baseball (right, right, I know, this is slashdot), and a ball is coming towards us, we aren't calculating in our heads the velocity, air resistance and other variables involved in catching the ball. We just reach out our arms and our brain makes its best guess based on some sort of heuristic or something to make the catch.
I think the problem with your analogy that there are an unlimited number of dimensions and responses where you could put your arm out to make the catch (well, not unlimited if you consider Planck distances to be the smallest possible distance). But when we are talking about computerized flowers with nectar, you pretty much can only go to one of the flowers next. I think they used RFID to track the bees (or at least this researcher has written about doing that before)? So we can sit there and do a star search on all paths of the 50 flowers and find the shortest one to connect all of them in three dimensions in a particular order (we assume the flight paths are straight lines). The difference is not that we have so many fewer things to search than in the ball catching example but that you take a very finite deterministic path (i.e. 2, 34, 23, 6, 18, etc) and the bees seem to be able to find and learn this very quickly. According to the researcher:
"In nature, bees have to link hundreds of flowers in a way that minimises travel distance, and then reliably find their way home - not a trivial feat if you have a brain the size of a pinhead! Indeed such travelling salesmen problems keep supercomputers busy for days. Studying how bee brains solve such challenging tasks might allow us to identify the minimal neural circuitry required for complex problem solving."
If this holds true for hundreds of flowers, I think we're talking about a serious search space with a definite path that is far more specific than the heuristics of moving your arm and hand around dynamically in space to collide with a ball. You could have tons of error when trying to catch a ball and still catch it. You (frequently) only have one optimal path in shortest distance problems. It's probably true these traveling salesman problems look obvious to a bee like catching a ball does to us but something particularly interesting is going on there if it is.
Let's say it is an unknown heuristic. I'd wager the network folks would kill to know how that heuristic is so cheaply computed.
Re:Heuristic (Score:3, Insightful)
I beg to differ. If it takes a supercomputer 4 days to solve it for 5 flowers... we have huge problems.
The computer isnt going to die (Score:3, Insightful)
The computer isn't going to die if it doesn't get the right path, the bee might. Death is a remarkably strong motivator to be efficient.
Re:Different Spaces (Score:3, Insightful)
I'd be interested to read the full paper... looks like it won't be published until this week.
I have to wonder if it's simply local optimization that the bees are using - i.e., "Fly to a close flower not yet visited" - that starts looking like they're solving a much more complex problem? Are they visiting *every* flower on the "map"? Are they ever skipping some? Do they visit the flowers in exactly the same order, or is there variance from bee to bee (or between two trips from the same bee?)
It seems to me that a few simple rules ("visit closest flower from current flower that you haven't visited yet") might approximate the correct TS solution for small maps & limited nodes, but that it would become quite a bit harder to generalize that solution to larger sets of nodes & longer distances.
Re:Heuristic (Score:1, Insightful)
This seems likely to me. If the answer were simply the power of neurons, one might expect that -we- would be better at solving the traveling salesman problem than we are.
Actually, the problem is probably that human salesmen over-think the problem. If only there was some form of zen-like meditations that would allow humans to stop trying to employ math and algorithms, I'm sure our salesmen would be breezing effortlessly from town to town in the shortest possible route just like the wise bees.
Re:Oh, really? (Score:5, Insightful)
100 flowers=100! possibilities. Using brute force on a 1 GHz processor and computing one solution per cycle (quite optimistic), it would take you 3 times 10 to the 141 years to complete. Even if your cellphone had a helaflop [slashdot.org] processor, it would still take longer than the age of the universe to compute this way.
Re:Bees have a guide (Score:3, Insightful)
So, you're arguing it's the algorithm that's wrong and not a better set of neurons.
Re:Evidence (Score:2, Insightful)
Sorry, I already substituted God for a different beard guy, Richard Stallman.
Re:Not the TSP (Score:2, Insightful)
So, actually the problem is fundamentally the same as TSP. It's a distance minimization problem. And just because they use a 'heuristic' doesn't mean that they don't have a solution to the TSP problem. An biologically-based genetic algorithm is no less valid than a computer algorithm.
Re:Evidence (Score:5, Insightful)
You mean millions of iterations of random chance have selected the most efficient pollen-gatherers.
Re:Evidence (Score:5, Insightful)
Anyone who thinks the bees solved NP-hard problem here does not know what they're talking about...
Those bees did not do an exhaustive search for the optimal path, only one that is 'good enough'. Computers can do the same with any decent algorithm. Only difference here i assume is that the bees have hardware that has gone through natural selection to produce a pretty good 'best effort' algorithm.
If those bees can produce the optimal path for all corner-case setups then I'll be rather impressed.
Re:Not the TSP (Score:2, Insightful)
http://en.wikipedia.org/wiki/Knapsack_problem [wikipedia.org]
Bullshit (Score:3, Insightful)
So they have proof that these bees solve the travelling salesman problem? Not just get a good approximation? Not just solve a slightly constrained version? Not just solve a slightly different problem? You know all the things that computers do just fine thank you very much, and aren't NP-hard.
I notice the journal is a Naturalist one and the researchers aren't are bioligists and chemists not computer scientists.
I have no difficulty believing bees have evolved (or been designed with if you must for those I don't feel like arguing with) a very efficient way of collecting pollen - it is after all fundamnental to their survival and reproduction. But that they happened to solve an NP-Hard problem that they have no need of solving (does an individual bee really visit *every* location on one trip? surely some imperfection would help in discovering new plants by having bees follow different paths?) - that seems a bit of a stretch.
Re:Evidence (Score:5, Insightful)
Question is...did the bees evolve to find the corner cases, or did the plants evolve so the damn bees could find them in the first place? After all, plants that are stupid enough to hide from bees while simultaneously needing them to reproduce would stand a good chance of not making it to the next generation ;-)
Re:Solving a different problem (Score:5, Insightful)
I suppose the exception is when competing against an intelligent adversary, who constantly strives to give you worst-case problems and where a small margin of victory is a victory nonetheless.
Re:It don't matter what you call it (Score:3, Insightful)
The travelling salesman problem is the problem of finding the shortest route between a set of points. It doesn't matter HOW you solve it. You could time all possible journey's, you could do a sorting routine or god knows what. But if you solve it, you solved it.
That is what the bee does. And maybe if we can learn HOW the bee does that, we might learn something from it. It might be a smarter way of solving things. Or maybe Bees have an additional variable from an unknown input that helps solve it.
That's not what the bee does. That is what someone _claims_ the bee does. Big, big difference. I imagine they found that the bees visit flowers faster than in random order, or faster than the order in which they were told about the flowers. I think a simple algorithm like "always visit the nearest flower that wasn't visited yet" would probably impress these "scientists" no end.
BTW. Bees shouldn't even try to solve the travelling salesman problem. Assume a single flower very far away - the best solution may not be to figure out the quickest path to visit is, but to ignore it.
As a programming exercise: The "Realtime Travelling Salesman" problem: Give the computer a list of places to visit, with a list of travelling times from each place to each other place. Then the computer starts calculating. As soon as it tells you the first destination, you go to that destination. The computer can continue calculating while you travel, but if it doesn't give the next destination when you arrived at the first destination, you have to wait. Obviously the total time from the start of the calculation until all places are visited needs to be optimised. That means optimising the calculation time as well, and picking a goal when further calculations likely waste more time than they could save.
Re:Not the TSP (Score:4, Insightful)
The questions this raises are:
1) Do bees always visit every flower (node) on the map?
2) Once they've calculated their "optimal" route, do they ever vary it?
3) If it's a heuristic - does it scale? Will it work for more than 100 flowers spread across something the size of my backyard? Or is the heuristic going to break down or become completely unworkable once the number of nodes reaches a certain point?
What we can say so far is that they "appear" to be solving the problem, for some limited subset of the problem space. In actuality, they may be using some very simple rules that approximate the solution for small numbers of nodes and distances, but which would result in inefficient or sub-optimal solutions on a larger scale.
In other words - I can catch a pop-fly to right field. Does that mean I can also use the same heuristics I'd use to catch a small object at low speeds over small distances to accurately launch a Patriot Missile to intercept an ICBM? The physics are the same, but a little jitter of a couple millimeters in my calculations when applied to a distance of several hundreds or thousands of kilometers will result in a pretty big miss.
Re:Evidence (Score:4, Insightful)
That's a simple way of saying that evolution created a program in their brains that solves the TSP fairly efficiently under certain constraints.
Re:Evidence (Score:3, Insightful)
Thanks - this is what I was thinking too. It seems like the hard part of TSP is to *prove* that the shortest solution is in fact shortest. I think it's relatively trivial to find a very short solution to the problem (even by hand for a reasonable # of nodes). Demonstrating that the proposed path is in fact the absolute best is where the headaches (NP time) come in?
Re:Solving a different problem (Score:1, Insightful)
Re:Solving a different problem (Score:2, Insightful)
Epic NP fail. You just described the classical greedy algorithm. Try that on the following:
A-B: 1
A-C: 2
A-D: 3
B-C: 10000000000000
B-D: 5
C-D: 5
Pinch at A. The vertices will hang in the order ABCD. Your algorithm gives an "optimal" route of weight 10000000000006. A drunken bee with a single wing would beat you there, choosing the path ABDC of weight 11.
Re:Evidence (Score:3, Insightful)
What Slashdot needs is a write-in moderation option so you can moderate (-1, Wrong) or (+1, Fucking Awesome).
Re:Evidence (Score:3, Insightful)
Sure, chemistry no one has been able to reproduce in the lab under any circumstances.
No, it's based on basic biochemical reactions which are demonstrated on a daily basis in any number of labs. Are you completely ignorant of that field, and simply repeating dogmatic statements with no correlation to reality?