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?"
Simulated annealing.
Yours In Akademgorodok,
Kilgore Trout.
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.
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.
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.
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.
Irony: Agile development has too much intertia to be abandoned now.
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.