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?"
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.
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.
"Beowulf" is a kenning, a poetic analogy in Old English. It already means bee-wolf, a sort of pun for bear, which is what the name translates to in modern English.
No OS on the planet can protect itself from a user with the admin password. - Yvan256