vs

Bees are efficient pollinators, and play a critical role in agriculture and natural ecosystems. Recently, researchers at Queen Mary College London reported experiments suggesting that bees are even more efficient than previously thought. When faced with a new arrangement of flowers, a bumblebee is able to determine the shortest path linking the flowers. In effect, tiny bee-brains solve a complex Traveling Salesman Problem (TSP) in a matter of seconds on the fly. This is surpising because TSP is a notorious “hard” problem in optimization. A TSP with N nodes means finding the shortest out of O(N!) possible paths. For 30 flowers, thats about 10³² paths, most of which are very inefficient and a waste of bee energy.

Suppose the bumblebee arrives in the North-East corner of a flower bed which consists of 300 randomly distributed pink, orange and yellow flowers.

The shortest tour solution on the right was obtained using the fast and exact Concorde TSP solver. This took 5 seconds on a MacBook Pro 2.4GHz Intel Core 2 Duo. The optimal tour length ≈13 which is less than 10% the length of a typical randomly chosen tour.

The processor in this MacBook Pro weighs about 20g. A bumblebee weighs about 200mg, with a brain not more than 1% of that, say 2mg. If the bumblebee is really finding the optimal tour, then gramme for gramme, the humble bumblebee brain appears to outperform the MacBook by a factor of order 20,000!

To save the MacBook’s blushes, let’s hope the bee is doing something simpler. For example, using the nearest neighbour algorithm (visit the nearest flower not already visited). In the above example, the nearest-neighbour tour length is ≈16, which gets the bee most of the way there in terms of efficiency. This algorithm, while not exact, takes only 0.02 seconds on the MacBook Pro.

By the way, Charles Darwin was aware of the surprising power of small insect brains. “It is certain that there may be extraordinary activity with an extremely small absolute mass of nervous matter.. the brain of an ant is one of the most marvellous atoms of matter in the world, perhaps more so than the brain of man.“ – Charles Darwin, Origin of Species, 1859

Here is the R code used above.

library("TSP")
concorde_path("/usr/local/bin")
Nflowers <- 300
garden <- matrix(runif(Nflowers*2),Nflowers,2)
garden[1, ]<-c(1,1)
garden.dist <- dist(garden)
garden.tsp <- TSP(garden.dist)
garden.path <- solve_TSP(garden.tsp,method = "concorde")
garden.tour <- as.vector(TOUR(garden.path))
ex=par(mfrow=c(1,3))
plot(garden,xlab="flower garden",ylab="",pch=16,col=c("orange","pink","yellow"),xaxt="n",yaxt="n",cex=1.5)
points(garden, pch=1,cex=1.5)
plot(garden,xlab="concorde",ylab="",pch=16,col=c("orange","pink","yellow"),xaxt="n",yaxt="n",cex=1.5)
lines(garden[garden.tour,],col="black",lwd=2)
points(garden, pch=1,cex=1.5)
par(ex)


A handy script to help  with the external installation of concorde TSP on the Mac is available here. The TSP package also needs to be installed.