Bee vs MacBook Pro
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 1032 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.
October 28, 2010
Posted in: Uncategorized 
No Comments
Extreme conditions in Russian croplands
Heatwave and drought have caused severe damage to Russia’s grain crop. Yields are expected to fall by up to 40%[1]. Russia announced a ban on wheat exports from August 15, causing a sharp rise in global grain prices.
How severe are conditions in 2010 compared to previous Russian droughts and heat waves?
The plot[2] shows monthly growing season precipitation versus temperature anomalies for wheat croplands 1948-2010. A positive index value indicates high cropland precipitation or temperature. June and July this year are clear outliers.
Gridded 200km climate data (NCEP Reanalysis) were re-projected[1] to an equal area projection and standardized[4]. Then a weighted average over the harvested area for the year 2000 (data from C. Monfreda et al) was carried out.
__________________________________________________
[1] USDA World Agriculture Report, August 2010 http://www.fas.usda.gov/psdonline/circulars/production.pdf
[2] made using smoothScatter() base R graphics.
[3] raster map calculations using raster package by Robert J. Hijmans & Jacob van Etten.
[4] Monthly standardized precipitation and standardized temperature indices.
August 17, 2010
Posted in: Agriculture, Climate 2 Comments
