AWARDEES: John J. Bartholdi III, Sunil Nakrani, Thomas D. Seeley, Craig A. Tovey, and John Hagood Vande Vate
SCIENCE: The Honey Bee Algorithm
FEDERAL FUNDING AGENCIES: National Science Foundation, Office of Naval Research
Craig A. Tovey
Craig Tovey will never forget the day a 6’5” graduate student in Computation from Oxford University walked into his office at the Georgia Institute of Technology. Sunil Nakrani was looking for someone to work with him on a problem he had begun thinking about while working at IBM: what is the most efficient, and profitable, way to allocate computer servers to ever-changing internet traffic?
Over several years of exciting, and sometimes frustrating, research, supported in part by the National Science Foundation, the pair would adapt a decade-old model of how honey bee colonies allocate their foragers among sources of nectar into a novel algorithm for assigning computer servers – one that is now used by major web hosting companies in a rapidly growing global market worth over $50 billion.
But first, what if honey bees hired systems engineers as consultants?
John Hagood Vande Vate
Nearly 15 years earlier, Craig Tovey and his engineering colleagues at Georgia Tech – John J. Bartholdi III and John Hagood Vande Vate – stumbled into a study that would send them deep into the biology literature, connect them with a Cornell University biologist named Thomas D. Seeley, and ultimately change the paths of their careers. And it all began with a National Public Radio (NPR) piece Vande Vate heard on his morning commute.
On his way into work one morning in 1988, Vande Vate heard Cornell honey bee researcher Tom Seeley describing the organization of work in honey bee colonies on NPR. Seeley explained how the thousands of nectar foragers in a honey bee colony manage to distribute themselves wisely among local flower patches without any central authority.
John J. Bartholdi III
When an individual forager bee returns to the hive with nectar from her patch, all she knows is the “profitability” – in the currency of nectar – of her particular patch. She then learns how "needy" her colony is for nectar by assessing how easy or hard it is to find a hive bee ready to receive her nectar load and store it away. If she struggles to find a hive bee, she knows the nectar is flowing freely and she and her fellow foragers will thus be very choosey. If instead nectar is sparse and she has an easy time finding a hive bee, she will perform a vigorous “waggle dance,” recruiting other foragers to join her if her patch is even moderately profitable. Through the combined actions of every forager bee, the colony distributes its foragers among the flower patches in such a way that they maximize their honey production.
Over lunch that day in 1988, Vande Vate shared all this with his colleagues and mused, “I wonder if the bees would be more efficient if they hired us as consultants?” As systems engineers, they develop and test engineering ideas focused on optimally allocating resources and making systems operate as efficiently as possible.
Though they all initially laughed at the idea of a second career as honey bee consultants, the question lingered. And before they knew it, they were taking a systems engineering lens to biological research literature.
A systems engineer and a biologist walk into a b…iological research station
Over two years, supported by the National Science Foundation and the Office of Naval Research, the Georgia Tech engineers developed what they thought was “a theory worth testing” for how a honey bee colony’s foragers would be allocated. So John Vande Vate went to visit Tom Seeley at Cornell to propose that they collaborate. And that’s when they realized their theory still had a ways to go.
Over the course of the following year, Seeley worked with the engineers to refine their theory, eventually coming to a set of equations – a model – based on the foraging behaviors that Seeley had so elegantly analyzed. The model predicted how the forager bees would distribute themselves relative to available, variable resources, naturally driving toward a distribution where each forager bee accumulates nectar at the same rate.
According to this model, the bees did not distribute themselves “optimally” – a term with a very specific definition in systems engineering. In this context, “optimally distributed” would be if, at any given moment, should you add one new forager bee, that bee could go to any flower patch and get the same benefit to the colony in that moment. But this, according to the model, is not what the honey bees had evolved to do.
Thomas D. Seeley
In July 1991, Tovey – at the time actually on sabbatical in California – flew across the country, drove several hours, and rode a ferry boat to join Seeley at the Cranberry Lake Biological Station in upstate New York to test their model with a specially prepared research bee colony. They set up and varied artificial “nectar sources” and monitored the allocation of foragers from the research colony, in which each and every bee was labeled for individual identification. Each of 4,000 forager bees had its own unique combination of numbers and colors, meticulously applied by Seeley and his graduate students.
Over the course of a week at the bio station, Seeley and Tovey found that the honey bees followed the model quite nicely. Millions of years of evolution had driven them to distribute themselves in a way that constituted the best response to their changing environment – flower patches that vary constantly, coming in and going out of bloom according to the weather and the seasons.
With their systems engineering approach, the researchers were able to show that this mode of operation is highly effective at efficiently accumulating nectar for the colony across a wide range of conditions. In fact, under highly variable conditions, the honey bees’ approach actually does better than if they had evolved to find the “optimal” distribution in response to conditions at any given moment. But it would be a few years before they actually proved that.
Foraging is to honey bees as ____is to _____?
For over a decade, Tovey tried to find the perfect application for this newfound knowledge. He went down more than a few blind alleys along the way. He tried using it to model ant colonies; he tried applying it to highway traffic patterns. But each time, the honey bee model was not quite right. Then Sunil Nakrani walked into Tovey’s office and started talking about web hosting servers and the variable demands of internet traffic.
When Nakrani went to Tovey, he had no idea about his past work with honey bees. But after 20 minutes of conversations, and Tovey’s honey-bee-inspired questions, the Georgia Tech engineering professor came out with it: “This is just like the honey bee forager allocation problem!”
Sunil Nakrani
Nakrani walked out of that first meeting with a paper about honey bees, and feeling a bit mystified. But once he had mapped the problems onto one another for himself, Nakrani understood Tovey’s excitement.
In the web hosting problem, the servers are like the nectar foragers, while the dynamic community of clients asking to use the servers – anyone using the internet – is like the changing landscape of flower patches. The clients pay in money, while the flowers pay in nectar. Shared web hosting servers operate by switching from one application to the next based on demand for any given application. Each server can run only one application at a time (for security reasons), so switching applications – like a honey bee switching flower patches – incurs a time, and therefore revenue penalty as the server wipes itself clean and loads a new application. The best server allocation algorithm would need to respond to a highly dynamic environment and return the maximum total revenue – just like in a honey bee colony.
“Have you patented this?”
Over the next several years Nakrani and Tovey, with support from the U.K. government as well as the U.S. National Science Foundation, set out to prove that the honey bee algorithm could work for web hosting servers. They designed an algorithm in which servers assessed the profitability of their clients and did their own “waggle dances” to communicate that information to other servers. In a test against a then state-of-the-art algorithm and two other potential methods, the researchers showed that their honey bee algorithm beat the competition. In fact, when they compared the honey bee algorithm to a totally unrealistic, omniscient algorithm that knew where future web traffic would be in advance, they found that under highly variable conditions – which are realistic for many situations on the internet – the honey bee algorithm came out ahead.
At his dissertation defense, the first question Nakrani got was one he hadn’t prepared for: “Have you patented this?” And his dissertation was promptly shortlisted for the best computational dissertation in the United Kingdom that year. The paper he and Tovey wrote describing their work has been cited more than 230 times by researchers working on everything from optimal fuel utility to workload balancing to energy usage and distribution.
No, they hadn’t patented the honey bee algorithm. Guided by curiosity, they had been pursuing understanding over commercial gain, and they had published their work in the public domain.
Today, web hosting services are implementing biologically inspired algorithms like Tovey and Nakrani’s to drive larger revenues and more efficiently operate server farms in the rapidly growing $50 billion global market for web hosting services. And the field Tovey, Bartholdi, and Vande Vate stumbled into – self-organizing systems and biomimicry – is a burgeoning area of research that includes everything from biologically-derived adhesives and fluorescent proteins to systems engineering solutions inspired by bees, ants and other social insects.
So the next time you load up a webpage on your phone or laptop, you can thank the honey bees, and a team of federally funded researchers who let curiosity be their guide.