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?"
hierarchical models (Score:2, Informative)
Re:Heuristic (Score:2, Informative)
Indeed - especially considering the fact that one of the major class of solutions based on simulated annealing is actually a heuristics based solution. It really doesnt matter how you solve it at all - any way is welcome - as long as it reaches close to the optimal solution.
Re:Heuristic (Score:4, Informative)
That's pretty much what I was going to post. The bees almost certainly aren't solving the Traveling Salesman problem, they're getting good enough approximations of a solution. Our computers don't chug for days trying to figure out the answer to TSPs, they chug for a couple of seconds and produce a close-to-optimal solution.
And the thing is, not all instances of the TSP are necessarily NP-Hard (for instance: if there was only one road between each city + 1 extra road between the first and last cities, the optimal solution is obvious), and the cases of it found in practical applications are generally far easier to handle than the cases found in more esoteric theoretical constructs (for instance: if you move east, you move closer to all the flowers in the east; this is not necessarily true in the general TSP). Most real instances of the TSP can be handled well enough with simple, quick greedy algorithms; they won't necessarily give you the best answer, but it'll be pretty close.
Solving a different problem (Score:5, Informative)
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).
Re:Bees have a guide (Score:5, Informative)
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 [earthlife.net] states that bumble bees "...have not evolved any means of communicating information reguarding utilisable resources."
Bogus claim (Score:5, Informative)
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.
Probability Collectives (Score:3, Informative)
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.
Re:great... (Score:5, Informative)
Re:Heuristic (Score:1, Informative)
But that's just it - finding "close to the optimal solution" for the Travelling Salesman Problem is not NP-hard.
Re:Shortcuts (Score:3, Informative)