Archive for the ‘Optimization myths’ Category
A paper on solving combinatorial optimization problems with biological organisms made it into Science. The paper “Rules for Biologically Inspired Adaptive Network Design” by Atsushi Tero, Seiji Takagi, Tetsu Saigusa, Kentaro Ito, Dan P. Bebber, Mark D. Fricker, Kenji Yumiki, Ryo Kobayashi, and Toshiyuki Nakagaki explains that under certain circumstances, a certain microbe can reconstruct a version of the Tokyo rail system. From the abstract:
Transport networks are ubiquitous in both social and biological systems. Robust network performance involves a complex trade-off involving cost, transport efficiency, and fault tolerance. Biological networks have been honed by many cycles of evolutionary selectionpressure and are likely to yield reasonable solutions to such combinatorial optimization problems. Furthermore, they develop without centralized control and may represent a readily scalable solution for growing networks in general. We show that the slime mold Physarum polycephalum forms networks with comparable efficiency, fault tolerance, and cost to those of real-world infrastructure networks—in this case, the Tokyo rail system. The core mechanisms needed for adaptive network formation can be captured in a biologically inspired mathematical model that may be useful to guide network construction in other domains.
Whereas the authors do not claim any real (i.e., mathematical) optimality etc. and probably the solution quality is similar to solutions that one would obtain with simulated annealing or ant colony optimization, i.e., sub-optimal solutions in many cases, a well-read website, Spiegel Online belonging to the Spiegel magazine run a story about the article a couple of days ago giving the whole thing a slightly different touch – this reminded me very much of a blog post of Mike. The article starts with (in German – I will provide a hopefully faithful translation afterwards):
Was Ingenieure mit großem Aufwand versuchen, scheint für den Schleimpilz Physarum polycephalum eine Kleinigkeit: Verkehrswege möglichst effizient zu bauen.
Translation: What Engineers try to achieve with a lot of effort, is a trivial task for the slime mold Physarum polycephalum: The construction of efficient (traffic-) networks.
Here, the witty author already gives a first indication and an executive-style summary of his opinion. And just in case you haven’t got the point that engineers and in particular discrete optimization people are superfluous, money-eating artifacts of times where excess capital had to be burnt in order to keep inflation low, the author stresses his point even further by making clear that the microbe is really dumb.
Er gehört zu den ältesten Lebensformen – und Intelligenz würde man dem schleimigen Winzling wohl kaum zusprechen.
Translation: It (the microbe) belongs to one of the oldest life forms on earth and this little slimy thing is far from being intelligent.
If one takes a closer look at the article and especially the graph of the underlying network that the magic microbes reconstructed, the graph is almost trivial (from Fresh Photos):
If you checkout the spiegel online article which also provides pictures (I didn’t want to include those for obvious reasons), the time scale shows that obtaining the final solution took the magic microbe 26 hours. Needless to say that probably trivial branch-and-bound would do the job in less than 10 secs.
In times where it is chic to suck at mathematics, a stupid microbe outperforming a whole branch of engineering and mathematics provides perfect justification for dismissing mathematics as the most decadent form of barrenness. And what is really questionable, is that in times where mathematical illiteracy is responsible to a large extent (together with greed and dismissal of the principle of universality) for the latest financial meltdown there are still authors that somewhat give the impression that the underlying mathematical problems are trivial and provide a jaded view.
We need a wikipedia page for that, distinguishing folklore optimization (yeah, every pseudo-consulting outlet does optimization) and mathematical optimization. Something that really distilles the point. Unfortunately, this page here is not really informative for the non-expert!!