Slashdot Mirror
Bees Beat Machines At 'Traveling Salesman' Problem
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?"
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.
My postings are informational and does not constitute legal advice. Act on it at your risk.
who/what is god?
I think you mean genetic algorithms. Genetic engineering is...something else.
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.
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.
My work here is dung.
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 processor, it would still take longer than the age of the universe to compute this way.
You mean millions of iterations of random chance have selected the most efficient pollen-gatherers.
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.
- These characters were randomly selected.
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 ;-)
People replying to my sig annoy me. That's why I change it all the time.
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.
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.
That's a simple way of saying that evolution created a program in their brains that solves the TSP fairly efficiently under certain constraints.