May 20th is World Bee Day
World Bee Day has been recognised by the UN for a few years now. It’s well known that bees are some of the most important pollinators, crucial for maintaining biodiversity. But you may not know how they also have changed some underlying technologies while they’re at it…
The travelling salesperson problem
The travelling salesperson problem (TSP) is a well-known mathematical problem. How do you get around a set of points on a map, ensuring they are all visited, in the least time or distance possible? The idea behind the algorithm is that each leg of the journey has a cost associated with it, so that cost should be minimised as much as possible.
This core problem has countless uses, from the routing algorithm in your delivery driver’s software to data centre algorithms that dynamically optimise which loads are placed on which servers. There are obvious costs involved with both of these: your parcel arrives later than planned and the delivery company have burned up lots of petrol; the data centre runs inefficiently, using too much power and potentially missing service SLAs.
However, problems like the TSP are not simple to solve. In fact, you could win $1M dollars from the Clay Mathematics Institute if you successfully submit proof of an algorithm that can manage the inherent complexity in a problem similar to the TSP. Before you rush off, it’s worth noting that with only 61 points to visit, there are more possible paths than there are atoms in the universe.
Such problems are described as “NP” problems – it is easy to check that a solution to a problem is correct, but the task of checking all solutions to find the best answer seems to be so hard as to be completely impractical, even with the biggest supercomputers.
The bees’ answer
This is where the scientific interest in bees comes in. They need to expend energy to gather enough nectar, and it’s a fine balance. They can’t travel too far or they won’t survive.
Scientists studying bees set up some experiments using artificial flowers and controlled portions of nectar. They found that at first their routes through the flowers were long and complex, but they quickly learned and refined their paths. They tried new routes, and if they were beneficial, they kept them. Academic papers are now popping up, which make use of what the bees have taught us, with wonderfully baffling abstracts like this: “Aiming at the link congestion and unbalanced load for data center network when scheduling the elephant flow by traditional methods, a load balancing algorithm based on artificial bee colony algorithm IALB (improved artificial bee colony load balancing) is proposed. […] “1.
What the bees teach us is that while the complete solution to some computing problems seems impossible or impractical, there may be heuristic solutions that are good enough. A heuristic solution may not give the precise and only correct answer, but is enough of an answer to be useful to us.
What else can you do today that’s not perfect, but just good enough to do? Thank you for all of your hard work, bees!
If you’d like to see more about the research into the bees algorithm, there’s an excerpt here from a BBC documentary called “The secret rules of modern living: Algorithms”.
1. Abstract taken from: Y. Guohao, W. Muqing and Y. Xu, “A Data Center Load Balancing Algorithm Based on Artificial Bee Colony Algorithm,” 2020 IEEE 6th International Conference on Computer and Communications (ICCC), 2020, pp. 1770-1775, doi: 10.1109/ICCC51575.2020.9345259.