Enough Already: Bees Haven’t Solved the Traveling Salesman Problem
This past week, we’ve been doing our best to ignore a perniciously misleading science story that’s been making its way through both blogs and mainstream media. According to these reports, bees have managed to solve an NP-hard problem in mathematics and computer science known as the Traveling Salesman Problem, which consists, when “given a collection of cities and the cost of travel between each pair of them,” of “find[ing] the cheapest [lowest-distance] way of visiting all of the cities and returning to your starting point.”
Many news stories about this, which stem from research done by scientists at Queen Mary, University of London and Royal Holloway, University of London, take the angle that this somehow proves that humble bumblebees have beaten computers and those egghead scientists that rely on them. “Bees’ tiny brains beat computers, study finds” proclaims The Guardian‘s headline.
As a writer who regularly attempts to cover scientific developments in a way that’s easily understandable by a broad readership, I can understand the appeal of this strategy: It takes the forbidding topic of the Traveling Salesman Problem, to which volumes of arcane computer science literature have been devoted, and makes it into an emotionally resonant populist narrative. “See, bees can beat computers after all!” Read that headline and you don’t have to know or care what the Traveling Salesman Problem is or what the research consists of; you just know that the bees have bested machines. Sadly, this isn’t true.
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. Studying how bee brains solve such challenging tasks might allow us to identify the minimal neural circuitry required for complex problem solving.”
The team used computer controlled artificial flowers to test whether bees would follow a route defined by the order in which they discovered the flowers or if they would find the shortest route. After exploring the location of the flowers, bees quickly learned to fly the shortest route.
As well as enhancing our understanding of how bees move around the landscape pollinating crops and wild flowers, this research, which is due to be published in The American Naturalist this week, has other applications. Our lifestyle relies on networks such as traffic on the roads, information flow on the web and business supply chains. By understanding how bees can solve their problem with such a tiny brain we can improve our management of these everyday networks without needing lots of computer time.
OK. There’s a key difference, though, between what the bees did — finding the shortest distance between a set of flowers — and producing a general solution for the mathematical problem known as the Traveling Salesman Problem. To wit: The formal definition of the TSP is, “We are given a complete undirected graph G that has a nonnegative integer cost (weight) associated with each edge, and we must find a hamiltonian cycle (a tour that passes through all the vertices) of G with minimum cost.”
Even if we had exceptionally tireless bees map a route between a million flowers, would we be able to say that we found a general solution for this? How would we know that they had really found the shortest possible route between flowers and not merely an approximation of the shortest route? Why, we’d have to mathematically set up a Traveling Salesman problem and sic supercomputers on it for days. Even if the supercomputer’s solution and the bees’ solution wound up syncing up perfectly, how would we know that the bees’ solution would be optimal if it was a million and one flowers instead of a million? And so on. It should be clear that the practical application is not and cannot be a mathematical solution.
This isn’t to say that what the bees did isn’t impressive, especially given their limited hardware: And as the press release notes, there are likely to be practical applications to this research, perhaps comparable to the research done by the Japanese and British scientists who discovered that slime molds could uncannily approximate the Tokyo rail system. But very good, very fast approximations of the TSP have existed for a long time. Per Wikipedia, “Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution.” (The link goes into more detail.)
Why does any of this matter? Because it trivializes the hard work done by math and science professionals. Imagine being a researcher who’s dove deep into the arcana of the TSP only to hear from some relative that they read in the newspaper that bees solved it. You could try to explain that the newspaper was wrong, and why, but their eyes might glaze over. The stakes are higher than hurt feelings, though: Pop-science stories that wildly misreport basic facts in the headlines serve to push science literacy deeper into the mud. And yes, there are potentially millions of grant dollars hanging in the balance, which could wind up not going to researchers whose work could lead to promising, useful applications because the basics of what they’re all about are misunderstood by the populace and by government officials. Science can and should be popularized, but when media outlets misrepresent the facts in favor of soundbites and narratives, they’re doing more harm than good.
If you didn’t click it before, see that SMBC comic again, because it really nails it.
Have a tip we should know? [email protected]