Finding: Bees Solve The Traveling Salesman Problem

100! How would a supercomputer do with that? Um, without any problem? DiEb

This is from the original PhysOrg news item:

Professor Lars Chittka from Queen Mary's School of Biological and Chemical Sciences said: "In nature, bees have to link hundreds of flowers in a way that minimises travel distance, and then reliably find their way home - not a trivial feat if you have a brain the size of a pinhead! Indeed such travelling salesmen problems keep supercomputers busy for days.

100! How would a supercomputer do with that? PaV

PaV:

If this is true in nature, and there is reason to believe this is true, then how do bees out in nature solve a problem that would take a supercomputer days to solve?

From the conclusion of th 2006 paper: Bumble bees’ ability to approximate the shortest return route or the TSP solution also seemed constrained by the spatial configuration of flowers. The observed average length of return route was significantly closer to the TSP solution than were the lengths of null visit sequences in the positive and independent arrays, but not in the negative array. Moreover, the TSI decreased over time in the positive and independent arrays but not significantly so in the negative array. These trends seem consistent with our results that bees’ foraging routes included frequent straight paths in the positive and independent arrays, but not in the negative array. In other words, short return routes observed in the positive and independent arrays probably did not result from bees’ ability to solve the TSP, but simply from their directional movements. Perhaps bees are unable to solve the traveling salesman problem because they cannot remember enough locations, although they do not necessarily have to rely on their memory of flower locations in solving the traveling salesman problem (e.g., Linhares 1998). Even if the bees can remember all the flower locations, moreover, choosing the shortest routes may require a higher level of ability to ‘‘plan ahead’’ or ‘‘look ahead.’’ DiEb

PaV, have a look a this paper from 2006:Kazuharu Ohashi, James D. Thomson, and Daniel D’Souza: Trapline foraging by bumble bees: IV. Optimization of route geometry in the absence of competition (Behavioral Ecology, September 29, 2006) - I have linked to it earlier. Here, ten artificial flowers are used, and among the results you will find that bees generally don't use the optimal trapline. The authors show that bees preferred flying to the next neighbour about flying on a straight line... As for four flowers: if these are arranged as a quadrilateral, always visiting the next unvisited neighbour solves the TSP. The projects show that the bumble bees fly a reasonably good traplines - and this could be explained by the use of simple set of rules combined with a little bit of memory. BTW: the moderation lag is quite big at the moment... DiEb

Taking a second look at the paper--a very quick one--it appears that the bees were able to solve the TSP right away. Now the experiment included only four locations, but the implication is this: are bees that are out in the open, who perhaps are sampling dozens of locations on a particular day, able to solve that problem? It would appear they can. If this is true in nature, and there is reason to believe this is true, then how do bees out in nature solve a problem that would take a supercomputer days to solve? The question still appears to stand. And Darwinians still have to explain it. PaV

DiEb: I've looked at the paper; it's available online. Indeed, it was only four artificial flowers. In one of the popular reports I had read that they used ten artificial flowers, and that was the reason for the above calculation and and inferences. And, I must add, if it is only four flower locations, then, yes, indeed, this is somewhat on the trivial side since brute force techniques could solve it. I haven't read the entire article, and don't care to, but I suppose their conclusion is that brute force, random sampling is not how they solved it. Nevertheless, this is solving the problem on a smalls scale; and, yes, it would appear there's a lot of hyping done on the part of the non-scienctist reporter. The title of the PhysOrg item is misleading. So, my apologies. PaV

PaV

This makes me wonder why you have chosen to select such “simple situations” such as 4 different flower locations?

Again, here is an excerpt of the abstract (http://www.journals.uchicago.edu/doi/abs/10.1086/657042) of the paper Travel Optimization by Foraging Bumblebees through Readjustments of Traplines after Discovery of New Feeding Locations (Mathieu Lihoreau,Lars Chittka and Nigel E. Raine) the press-release was based on. Haven't you read it? "[..]We analyzed bee flight movements in an array of four artificial flowers maximizing interfloral distances. Starting from a single patch, we sequentially added three new patches so that if bees visited them in the order in which they originally encountered flowers, they would follow a long (suboptimal) route. [..]"

Are you trying to stack the deck? Or are you trying to search for the truth?

You could have answered these slightly slanderous questions by yourself just by reading the abstract... DiEb

I just posted this at "It's amazing what evolution can do": DiEb and TempHut: On Wiki, they say that the TSP can be classified as O(n!). In the experiment, 10 "artificial flowers" were used. 10! yields 3.6 million different permutations that have to be evaluated. Assuming a computer can evaluate 36 permutations per second, it will take 100,000 seconds of computing time to calculate the path of least distance by brute force. That's about 30 hours. If the computer can evaluate only 20 permutations per second, then it will need 54 hours to evaluate. This makes me wonder why you have chosen to select such "simple situations" such as 4 different flower locations? Are you trying to stack the deck? Or are you trying to search for the truth? How do you explain that bees can solve this problem? They don't have a computer. They have to deal with lots of locations. How do they do it? Do they do it perfectly? Apparently not. But how can they even approximate it? They obviously don't use 'brute force' methods. What do they do? How do they solve this problem? And, considering that their lives depend on it, it's rather important that they be able to solve it. What, then, are the implications here for putative random mutations leading to such a capability? PaV

Wasn't the same topic discussed a few days ago? Neil Rickert

Not again! Please read UD's thread It's amazing what evolution can do.... One of my comments over there is still awaiting moderation - though it fits here, too. DiEb