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!
Simulated annealing.
Yours In Akademgorodok,
Kilgore Trout.
Does this mean that B >= NP?
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.
It's an abbreviation for Good Old Darwinism.
http://alternatives.rzero.com/
Hulk smash traveling salesman!
(I assuming we can engineer Hulks.)
Many researchers are worried that the baculovirus isn't as benign as first thought. Some even claim it killed the Star Trek franchise.
No folly is more costly than the folly of intolerant idealism. - Winston Churchill
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.
Oh, beehave.
Rampant carbon sequestration destroyed the Dinosaurs' tropical paradise. I'm here to help repair the damage.
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.
I dunno. If only we had a word for this....something like the line that a bee would travel...
It's called Ruby, and it's not a problem, it's a feature, a trendy one.
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.
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."
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.