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?"
Bees have a guide (Score:2, Interesting)
After the genetic vector is put in, all the bees have to do is keep track of the sun. 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.
In Other ( Two ) Words: ( +1, Helpful ) (Score:5, Interesting)
Simulated annealing [wikipedia.org].
Yours In Akademgorodok,
Kilgore Trout.
Shortcuts (Score:5, Interesting)
Entomoengineering? (Score:5, Interesting)
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. [uwyo.edu] 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.
Oh, really? (Score:4, Interesting)
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.
Re:Heuristic (Score:3, Interesting)
Re:Heuristic (Score:3, Interesting)
Nope. You've solved one small set of problems, which is related to the bigger problem. Does your method work for just balls? What about anvils? Churches? Very small rocks? How about when thrown through water, or over a hill? Can it be applied to every situation where Newtonian physics works?
The travelling salesman problem is a very specific definition of a problem. Solving it for one specific set (a given graph, size, or even geometry) does not solve the whole problem. Similarly, I know of no non-euclidean bees, so this research still doesn't solve the traveling salesman problem. As the grandparent said, the bees are likely employing some new rule we haven't thought of yet. The research might lead to new insight, though, and for that it's valuable.
Not the TSP (Score:5, Interesting)
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.
Re:Heuristic (Score:5, Interesting)
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.
You should read "On Intelligence" if you're at all interested in that subject. Jeff Hawkins (Palm inventor) proposes a fascinating theory of the inner workings of the brain.
Re:Wild Guess (Score:4, Interesting)
Kinda reminds me (Score:1, Interesting)
Kinda reminds me of the Geek shopping team [xkcd.com]. If you want perfect you'll never get close enough to pull the trigger but shoot for close enough and you're off to the races.
Slime molds do something similar (Score:5, Interesting)
Re:165 million years of evolution, anyone? (Score:3, Interesting)
Re:Solving a different problem (Score:2, Interesting)
Yes, it's easy to solve outside of a computer- tie a bunch of strings together representing your routes.
Any two points are easily resolved by picking holding the points in each hand and pulling it taught.
The taught strings are your route.
Re:Evidence (Score:4, Interesting)
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...
Re:Solving a different problem (Score:4, Interesting)
I believe the bee's have an advantage over the typical traveling salesman problem in that the bee's are finding the shortest path on a fully connected or complete graph. The traveling salesman problem is hard because the graph is not necessarily fully connected so all paths have to be examined individually. The bee presumably also has a predetermined starting node, the one closes to where it is released.
I believe the shortest path on a fully connected graph is found by always choosing the closest non-visited neighbor from the current node. The difference in calculation is O(n!) vs. O(n^2).
Massively Multithreaded Genetic Algorithm (Score:3, Interesting)
I'd be willing to bet it has something to do with the fact that you have an entire hive of bees each attempting to find the shortest path and then sharing their experience via that 'bee dance' thing (http://www.youtube.com/watch?v=-7ijI-g4jHg). Each bee is a thread with its own particular solution to the problem. Each bee's behavior contributes random heuristic alterations to the nectar-gathering path based on bee instincts evolved over millions of years. The bees periodically exchange solutions via the bee dance. It's a classic Genetic Algorithm.
Re:Oh, really? (Score:2, Interesting)
Re:Different Spaces (Score:3, Interesting)
That's true, although you could still reduce it back to the TSP easily enough - optimize for 'minimal energy expenditure' instead of 'minimal distance,' since distance traveled factors into the energy expended. Of course, even that still varies in 'real world' conditions - breezes come and go and change direction, birds come by looking for a snack, a lawnmower destroys a dozen of the flowers you were 'planning' to visit; turns out that what looked like an optimal route 20 minutes ago may put you facing a hurricane-force headwind on the return trip, with half the flowers you planned to visit initially destroyed and no longer options for stopping.
If they're somehow choosing each leg in an attempt to visit a consistent set of nodes every time, in the same order, then I'd say there's some basis to say they're 'solving' this problem; if they're not doing that, it would be more like telling the Traveling Salesmen, "visit some cities until you get tired, and skip some if you just don't feel like going to them, or if a nuclear attack destroys them while you're en route."
My initial impulse is to say that it sounds like researchers are angling for a little crossover press & grant money by using a buzzword like "biomimetics." Doesn't mean there's nothing to the story, but I'm skeptical that it maps as well to the problem domain as TFS & TFA suggest.