Not All Who Wander Are Lost

How ants have solved the Traveling Salesman Problem. /

It’s a sunny Saturday afternoon, but you are venturing out into the world to pick up some food for your boss for a dinner party. (Running errands for the boss? On a weekend? Yeah, well, try saying “no” to her highness.) The children at home seem to be constantly hungry; they’ll probably need to be fed again soon. Oh, and I suppose you should probably pick up something for yourself while you’re at it. A trip to the grocery store sounds simple enough. There’s just one catch: the aisles aren’t labeled, because the food isn’t organized in aisles, because the grocery store isn’t a store at all but rather the entire outside world.

Did I mention you were an ant?

I’m amazed ants can find anything. My local grocery store completely reorganized its shelves a few months ago, and my mind is still catching up. The pears seem like they are in a different spot each week. Pizza nights send me in circles because the pizza crust and the pizza sauce are no longer neighbors. I still can’t find aluminum foil without help. At least the building is in the same spot, and it always has milk and eggs. Ants never know if they are going to find anything and what or where it might be. It seems like they should starve, and yet the Bible holds up ants as model food collectors.

One thing ants have going for them is that they are tiny, so a little food goes a long way. They don’t all have to fend for themselves; they can work together to share what one ant finds. The first ant to find food brings what it can carry back to the colony. On the way, it lays down a pheromone trail—a chemical road sign saying “This way to food.” Other ants follow the trail and bring back more food, reinforcing the route with their own pheromones. When the food is exhausted, ants get to the end of the trail, find no food, and start foraging all over again; meanwhile the disused trail evaporates to minimize fruitless following.

That ant navigation works at all is impressive; more impressive still is that the writer Agur was absolutely right to include ants in Proverbs 30 as an animal we can learn from. Remarkably, they can find the shortest route between food and the colony. Maybe you’ve noticed ants streaming back and forth on the sidewalk, tracing a straight line. The first foragers meander widely, but after a while the colony collectively works out the shortest path without maps, managers, or aisle markers.

Paradoxically, working out the shortest path is a matter of imperfection. Pheromones spread like smells, so ants following the trail don’t take exactly the same route. Sometimes they take a more meandering route, and sometimes they manage a shortcut. Later ants that follow the shortcuts will get back faster. Over time, more ants will be able to traverse that shorter path than any of the alternatives. That means a stronger pheromone trail, which means more ants, and so on. Conversely, the pheromones on the meandering routes fade and those paths stop being used. As long as the food source holds out, the most used paths will be continually refined until the fastest one is found.

Can the ants help me with my food-finding problems? Let’s go back to Saturday afternoon. My kids want to make pizza and watch an educational nature film. (Or maybe Ant-Man.) I need crust, sauce, cheese, pineapple, and pepperoni. I want to find the shortest route through the store that gets me to all the ingredients without repeating. The manager won’t allow me to set an actual ant colony loose in the store, but I can use virtual ants with the same navigational scheme to plan my route.

Mathematicians call this particular routing challenge the Traveling Salesman Problem. Variations of it show up everywhere from transportation to manufacturing to computer networking. So a good solution would be beneficial for lots of practical challenges. (Mathematicians are very good at recognizing when different problems with varying details actually have the same solution.) Unfortunately, the Traveling Salesman Problem is time-consuming to solve. If you want to get the absolute shortest route, you have to reckon with all the possible routes in some fashion. For five ingredients that’s a feasible number—24 different permutations—but for even just 11 ingredients you already have to consider millions of routes.

If you can’t wait for the absolute shortest route, you can try to find one that is short enough. For that, the method the ants use is one of the best possible. Simulated ants following simulated pheromone trails can find nearly optimal routes faster than many other algorithms developed for the same problem. Even better, they can adapt dynamically to changes in the destinations and paths—routes becoming blocked, destinations added, grocery stores being completely rearranged. Other methods have to completely start over when the problem changes, but the simulated ants adjust on the fly just like their real counterparts.

Finding fast routes is remarkable in itself, but what’s most striking is how the ants go about it. There are no supervisor ants that have to know what every ant is doing and coordinate appropriately. Each ant operates freely within its capacity, and the collective effort of the colony graciously covers over any missteps a particular ant might take. They each are called to follow the way set before them, trusting the cloud of pheromones that bears witness to the goodness of the path. It’s a good solution for finding bread, and for finding the bread of life.

Andy Walsh (@MadroxDupe42) is chief science officer at Health Monitoring Systems, Inc., a public health software company. He writes weekly on science for InterVarsity's Emerging Scholars Network.

Follow The Behemoth on Twitter and Facebook.

Also in this Issue

Issue 46 / April 14, 2016
  1. Editor's Note from April 14, 2016

    Issue 46: Gorgeous feathers, Cairo’s cave churches, ant trails, and clouds. /

  2. Simply Beautiful Feathers

    A display of birds’ useful adornments. /

  3. From Garbage to Glory

    The cave churches of Cairo offer sanctuary in the midst of squalor. /

  4. Under the Cloud

    Five amazing facts about the fluffy, immense formations above our heads. /

  5. Wonder on the Web

    Issue 46: Links to amazing stuff.

Issue Archives