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?"
now you get a faster computer that makes honey!
quite interested how such a tiny insect can figure it out on the fly
I thought we were talking about bees? I am so confused...
See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
Simulated annealing.
Yours In Akademgorodok,
Kilgore Trout.
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?
We need to expend more effort to recruit bees into computer science. Too many bees are wasting their lives solving these problems on the fly for a little nectar when they could be solving these problems in exchange for tenure at our nation's finest universities.
Was the Travelling Salesman presented with the completely connected graph the way the bees were? The bee isn't constrained to fly along predefined paths between nodes, the travelling salesman is.
I think you mean genetic algorithms. Genetic engineering is...something else.
Does this mean that B >= NP?
We have a lot yet to learn from our six-legged colleagues, from the sound of it. Recently some work was done on optimizing machine vision using an algorithm derived from the way the house fly's vision works. The termite's wood-digesting gut is a prime object of study for those seeking to manufacture fuel from biomass efficiently and cleanly. An insect virus (the baculovirus) is the new hotness for gene transduction in mammalian cells because it can't actually cause disease.
I think this might be the next step in bioengineering. We've been grabbing genes out of various organisms and sticking them in bacteria to produce useful biomolecules like insulin and factor VIII. Maybe the insect is our next stop.
First TFS and TFA both make reference to problems which "keep super computers busy for days." That's pretty misleading since the bees are only dealing with "a few hundred" flowers. At brute force that would take your cell phone maybe a couple minutes to solve.
But really no details are given. Do the bees still travel to all of the flowers? I'd imagine they might just decide to skip one or two if they don't fall close enough to the path to be worth it. They don't say what they did (probably nothing) to validate that the bees actually found the shortest path. Did the "graph" that they gave the bees include a section where a greedy algorithm would fail? What is more likely is the bees haven't solved it, but found a decent approximation.
I think this is what you get when you let bee researchers write math/computer science articles.
It's an abbreviation for Good Old Darwinism.
http://alternatives.rzero.com/
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.
Hulk smash traveling salesman!
(I assuming we can engineer Hulks.)
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?
This article is fundamentally misstating the TSP. If it were the TSP, the bees wouldn't get to choose their route.
As other bees come in and report their route taken and pollen collected, another bee will put bits of those routes together. (Which would be the surprisingly difficult part to me, since the bees are doing some pretty complicated vector algebra.) But a bee is going to have a budget of so much daylight and will attempt to maximize the amount of nectar it collects in that time, given the bits of routes collected by other bees and its own scouting. But it's not given a list of points it has to hit, it picks its list from a larger list of points. That's fundamentally different from the TSP, even solving it by heuristic.
Gosh, that is one hell of a bee if it has the brain of a piece of corn... or is corn not a grass anymore? At least when you take some idiotic comparison, take one that has a non-changing size. Penny is okay because all pennies at least within a country tend to stay the same. But grass seeds?
Next up is "brain the size of a pinhead". Oh okay, so there are many sizes of pin but at least we can assume some kind of standard. And that is FAR smaller then most grasses I know and see seeds of in Holland.
Otherwise intresting stuff but I loathe this "make it easier" by obuscating the facts.
Number of neurons in honey bee brain = 950,000 (from Menzel, R. and Giurfa, M., Cognitive architecture of a mini-brain: the honeybee, Trd. Cog. Sci., 5:62-71, 2001.)
Now THAT is a fact. We? We got 100 billion. So, while a bee has a tiny brain compared to ours, it is HARDLY simple. And because it is far smaller and far more primitive it doesn't need as as much intelligence to deal with things it doesn't need to. Listening and producing speech is complex, but bees don't bother with that. Living for half a century and remembring everything is complex. But bees don't do that.
This why computers can do math so fast despite being so stupid, because they only do math.
How can the bee do route calculation with close to a million neurons? I have no idea but didn't research show that far fewer rat neurons could fly a plane? I think some people fastly underestimate the complexity of the brain even small ones. We already know that a neuron is far more then a simple transistor so 1 million super transistors would make for a hell of a complex computer. Suddenly it doesn't seem to odd that a bee can do computations far more complex because THAT is what it is designed to do. You could just as easily marvle at the fact that the bee with its tiny brain can fly, while I with my large brain can't. And no I don't just mean I don't have wings, I mean that if you put me in a helicopter you would have a horrible crash in seconds and that is in the passenger seat.
Marvle at nature, learn from it but don't belittle it. It takes us year to program a robot to walk very very slowly. A deer learns it in minutes and this includes learning to control legs locked up in a womb for months. We can either accept that nature is amazing or we are very very poor programmers... as a developer, I choose to believe that nature is amazing.
MMO Quests are like orgasms:
You may solo them, I prefer them in a group.
Thereby substituting one guy with a beard who must be worshipped for another.
...or even simpler, the scent of the flowers themselves. those antennae on the bees' heads aren't just for a sense of fashion. so to all you NP-mathematicians out there: suppose our traveling salesman had a means to follow a concentration gradient to the nearest sales point?
The canonical traveling salesman problem usually is states that all cities must be visited. The bee is not under this constraint. This changes the problem from a do-or-fail NP hard problem to a more simple approximate optimization problem. The latter have many many many many many good solution paths in computers. Perhaps the newest and best approach that resembles the bee's agent based learning approach is called Probability Collectives (google it). You'll want to learn it since it works well on parallel computers, distributed computing, and most of all on systems composed on many dumb subunits on a sparsely connected network with no central command and control (think mobile devices).
Some drink at the fountain of knowledge. Others just gargle.
If you build a maze that has multiple routes through it, and two pieces of food in it, and drop a bunch of slime molds into the maze in various places, they will fairly rapidly coalesce into a single slime mold that extends through the maze on the shortest route between the two bits of food. Now, that's no traveling salesman problem -- but slime molds are single-celled animals, so they don't have *any* brains to do the calculations. They just rely on minimizing surface area and maximizing access to food. (And being able to stop being multiple organisms and start being a single organism, but that's an aside.)
Nostalgia's not what it used to be.
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.
What amazes me though is how they look at another bee and visualize it traveling to a set patch of flowers, by looking at its dance.
Are we discussing bumble bees or honey bees? The summary says bumble bees.
http://www.earthlife.net/insects/socbees.html states that bumble bees "...have not evolved any means of communicating information reguarding utilisable resources."
Oh, this one again. I've seen this claim made for neural nets back in the 1980s, and for DNA computers in the 2000s. It's bogus.
The guaranteed-optimum solution to the TSP is NP-hard. The "gets to the optimum 99% of the time and close to it all the time" solution is easy. It was developed at Bell Labs in the 1960s. Here it is:
This is a particularly efficient way to do it. I once coded this for a PC/AT, and it took less than a second for N=50. Almost any scheme which randomly breaks links and tries to improve the path will eventually converge on a near-optimum solution.
I think Slashdot needs a "+1, Atheist" now.
Gamingmuseum.com: Give your 3D accelerator a rest.
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.
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.
Don't tell my boss.
Prov 9:8 Do not rebuke mockers or they will hate you; rebuke the wise and they will love you.
Probability Collectives are interesting because they are one of very few optimization alogorithms born from first principles considerations. For example, Simmulated annealing comes from Metropolis/hastings search and that was a brilliant breakthrough that allowed rapid exploration in a way that guarentees detailed balance. Parallel Tempering is the parallel extension of that first-principles argument. Most other search and optimization algorithms are born from either heurisitics expected to align with a search domain or considerations based on efficient algorithmic implementation (such as genetic algorithms). While one can go back and try to develop rigorous theories around expedients and heuristics, and there's a whole industry of that, in the end it's better I think to start from first principles.
Probability collectives starts with the assumption that that a team of agents will be making decision independently that affect the search path and that each agent is bounded rational. That is, each agent not only can't know everything, but can't be relied on to make optimal choices every time. You then discover what game theory says is the best way to search in this situation. You might visualize a set of airliners trying to negotiate landing times under conditions were some of them have been delayed and you have to reprogram flights in real time with incomplete knowledge.
As the algorithm searches the bound on the rationallity is annealed towards perfect rationality since more information is learned.
The algorithm tends to very efficiently use past information (compared to a GA or simulated annealing) but the per-interation computation effort is higher. Thus it is best applied in cases where agents are distributed (no centralized optimizer) or where the cost of gathering data is high or where the agents have available computing time between samples. One example of it's use in dumb-ditributed systems was the control of wing flaps on UAVs. Many micro flaps were agents which, without a central processor, solve the problem of prevent turbulence instability. presently it has achieved the highest wing speed without turbulence of any method, even ones that try to solve detailed physics equations in a central flight computer.
Most research on this approach is still in academics of the basic theory. very little attention has been placed on efficient coding of the methods. There are no libraries for it available. This would make a great CS master's thesis project for someone or indeed many people since the theory at this point is large.
Those bees did not do an exhaustive search for the optimal path, only one that is 'good enough'.
How do you know this? I'm not seeing that stated in the article. In fact,
Scientists at Queen Mary, University of London and Royal Holloway, University of London have discovered that bees learn to fly the shortest possible route between flowers even if they discover the flowers in a different order.
This seems to directly contradict what you're saying, so I'll assume you have access to more information and will be linking likewise shortly...
That's a simple way of saying that evolution created a program in their brains that solves the TSP fairly efficiently under certain constraints.