Traveling Salesman Problem solved – by a non-human lifeform


The Traveling Salesman Problem goes like this … if a chap has a set of cities he needs to make calls in, then how does he calculate the optional route such that he only calls into each city once? The solution is known of course because it has been one of the most intensively studied problems in optimization and has been used as a benchmark for many optimization methods. Even though the problem is computationally difficult, its possible to solve instances with tens of thousands of cities.

So why does this matter? Well basically because its a common problem, the solution is a pattern that can be applied in many different contexts. For example, when thinking across a range of different things such as dealing with customers, soldering points, or DNA fragments, it can be applied. The variables may be travelling times or costs, or a similarity measure between DNA fragments. Ah, but its never that simple and is not a one-to-one mapping because often additional constraints such as limited resources or time windows make the problem considerably harder to crack, but still the solution pattern to the core abstract problem can and has been adopted as required.

OK, so far … so what?

Now, this is the part where we get to the interesting bit, because apparently the problem has been successfully cracked by non-humans in a far smarter way.

Scientists at Royal Holloway, University of London and Queen Mary, University of London have discovered that bees learn to fly the shortest possible route between flowers even if they discover the flowers in a different order.

Now that is simply fascinating, the humble brainless bee beats our fastest supercomputers when faced with this dilemma.

Dr Nigel Raine, from the School of Biological Sciences at Royal Holloway explains: “Foraging bees solve travelling salesman problems every day. They visit flowers at multiple locations and, because bees use lots of energy to fly, they find a route which keeps flying to a minimum.”

Well, yes of course, natural selection will favor bees that are best at cracking this problem, so millions of years of evolution will have picked out the bees that are best at doing this. But then this begs the question, how the heck did these smart boffins work out that the bees were doing this?

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.

Are you still tempted to think, “so what”. Well consider the implication. Today we crack this problem using brute force by throwing technology at it and comparing all possible routes until the shortest has been identified. If the bees can crack the same problem on a daily basis using a brain the size of a grass seed, then there must be a smarter way of doing this. Finding a cooler smarter way is very desirable because it has so many potential applications. In addition to those I previously mentioned, we can also apply it to so many other practical areas that involve dynamic traffic flow management. Thats not just cars, but can be planes, trains, bus routes, data packets across the Internet, postal or parcel deliveries, and numerous other areas.

So what short cuts have they evolved that we have yet to discover? We simply don’t know, but it is intriguing isn’t it.

Do you still think we are the smartest on the planet? Well think again, because when it comes to cracking this problem, the cookies in their tiny little jars are a lot sweeter than ours.

You can read the original article by clicking here.

Leave a Reply