By studying the behavior of bees, a group of researchers at Queen Mary University of London has documented and modeled the way in which the insects can fly from flower to flower and then come back to their hives expending the least amount of time and energy. The findings might lead to better, much more flexible ways to deal with problems ranging from building faster computer networks to creating more powerful microchips.
The traveling salesman
Consider the following problem: you are a door-to-door salesman whose prospects for the day are scattered over a large number of cities. You know the exact distance between any two cities, and you want to find the shortest possible route that visits each city once and then returns to the comfort of your hometown, from where you first set off.
In computer science, this is known as the "traveling salesman problem" – it's a classic, and its applications are countless. Among other things, it's employed by all courier companies in day-to-day operations to deliver and pick up goods using the least amount of time and fuel while still visiting all the required destinations; electronics manufacturers use it to create better and more powerful microchips; and geneticists use it to sequence DNA.
Computationally, this problem is as hard as they come. The most direct, "brute force" approach to finding a solution would be to try out every possible combination but, in practice, this is unfeasible: with just 20 cities on the itinerary, there would already be 60.8 quadrillion comparisons to carry out* – impractical even for today's computers.
Fortunately, with a bit of human ingenuity, computer scientists have come up with ways to dramatically improve on the "brute force" approach. Nowadays, solving the problem for 20 cities takes somewhere in the order of millions of comparisons – a huge improvement, but still not a scalable solution. If we want to do better, we need to look elsewhere.
The birds and the bees
Whenever researchers are stumped by a problem, looking at nature's solutions is often a good option. Computer science is no exception: the animal world has had hundreds of millions of years to evolve simple and effective solutions to the very same navigational problems we face today. Birds have been studied for their ability to follow familiar routes to navigate between important locations, such as the nest and feeding sites, and ant colonies have inspired new techniques to quickly find near-optimal solutions to the traveling salesman problem.Now, judging from the recently announced findings, it looks like individual bees might also be able to contribute something to the field. A group of researchers from the Queen Mary, University of London has recently shown that the common bumblebee can solve a problem analogous to the traveling salesman's by using a simple iterative approach that requires no real number-crunching – only a tiny bee's brain.
Unlike our salesman, animals do not know the distances between the various locations in advance, but must gather that information gradually. Therefore, many animals navigating between multiple locations – humans included – are thought to find efficient routes using heuristic strategies, such as linking the nearest unvisited sites or planning a few steps ahead.
To test their assumptions, the researchers set up five artificial flowers in a small field and then tracked the individual bees' flight paths to see how they moved from one flower to the next.
Once the data was collected, the results turned out to be quite surprising. On average, each bee managed to find the shortest path between the five flowers and come back to the hive after they had tried just 20 out of the 120 possible routes. Even more surprisingly, they seemed to refine their routes through trial and error – a complex behavior that was previously only attributed to much larger-brained animals.
The researchers showed that the bees' behavior could be explained by a simple system. After discovering all the flowers in a given area, the bee would occasionally try a new route and, if the new path was the shortest yet, then it would increase the probability of trying it again in the future. Hence, through a positive feedback loop, some flight vectors were reinforced in memory over time, while others were forgotten, allowing the bee to quickly select a short, often optimal route.
The process is remarkably similar to the widely adopted ant colony optimization algorithms, in which the increased probability of updating the shortest route is substituted by a stronger pheromone trail.
Compared with the ant colony approach, however, there were a few key differences in the way the actual bees behaved. For instance, when one of the five flowers was moved from its original place or removed altogether, the bees engaged in a search pattern to find nearby flowers, often successfully. Simple as it is, when modeled appropriately, this adaptation could result in an algorithm that is more generalized, much more flexible and well-suited to situations in which the number of resources, their spatial configuration and their reward values are changing over time.
"Ultimately, characterizing the neural-computational implementation of functional multi-destination routing solutions in small-brained animals holds considerable promise for identifying simple solutions to dynamic combinatorial problems in situations lacking central control," says Mathieu Lihoreau, main author of the study.
An open-access paper describing the study was published on the journal PLOS Biology.
Source: Queen Mary University of London
*If we have n cities, then the number of combinations is (n-1)!/2. We have (n-1) choices for our second city, (n-2) for our third city, and so on. Multiplying these yields the factorial of (n-1), or (n-1)!. Since travel costs don't depend on direction, the number must then be halved.
