HMC Bee Lab: Ant-Salesman: Simulationmania

Have you ever wondered why ants walk in lines? Why do they follow each other? Are they just really big fans of queuing? As numerous pest control websites will tell you, ants walk in lines because they are following pheromones set down by other ants which tell them where to go to find sources of food, leading to disastrous results when your roommate is always littering crumbs all over the room. Not only do these pheromones help ants to follow each other, but they also help them choose the best way to get to something. In Deneubourg’s Double Bridge Experiment, ants were given the choice between two paths to get to a food source, one which was much longer than the other. Initially, the number of ants on each path was the same, but as time went on most of the ants ended up moving over to the shorter path. The ants that took the shorter path were able to make more trips than those that took the longer path, which resulted in them laying down more pheromone on the shorter path. Because the short path had more pheromone on it, even more ants chose to take it. This created a feedback loop which caused the ants to end up on the shorter and better path to the food. While this was a fairly simple test, it demonstrates that ants use pheromones to find optimal paths to food sources. Can we use ants to solve some of humanity’s problems related to finding shortest paths? It turns out that we can, and the field of study surrounding it is called Ant Colony Optimization. Before we go into more depth, let’s describe a problem we would like to solve using ants.

In the image on the left [1], we see a column of ants. On the right [2], we see an implementation of Ant Colony Optimization being used to produce a solution to the traveling salesman problem. How are they connected?

The Traveling Salesman Problem

The problem is as follows. You are given a list of cities and a map of the roads connecting them, and are tasked with finding the shortest route that goes through all of them exactly once and connects back to its starting point. It turns out that this is actually really hard to do for any large number of cities. There have been entire books written on the topic and there is even a one million dollar prize up for grabs for whomever can prove (or disprove) that it and questions like it are impossible to solve “quickly”. A number of ways to approach this problem exist, but the one this post will focus on is a simplified version of Ant System, which was introduced by Dorigo et al. in 1997. This all seems very interesting, but how do we get from watching ants walking around in lines to an algorithm that tells us the best way to visit a list of cities?

Mathematical Ants and Modeling

As mentioned earlier, ant colonies are pretty good at figuring out the best path to use to get places, which in this case means the shortest one. Although it would be fun to build a tiny model of the cities and roads we need to visit and set the ants loose on it, we would have a hard time explaining to them that they need to visit every one of our miniature cities exactly once before returning to their starting point, not to mention the difficulty we would have forcing them to use the roads. Instead, we can use mathematical modeling to transform our cities, roads, and ants into something we can simulate on a computer. First, we take our map and turn it into a graph in which each of our cities becomes a vertex and each road becomes an edge. An example of this is seen below. The cities are the red squares and the capital is the star.

Notice that each edge has a number next to it. This number is the length of the original road. It still looks about the same, but it allows us to ignore pesky details like the exact path of each road and just focus on what matters, the length. With the map out of the way, how are we going to model our ants? Earlier, we mentioned that ants do a couple things very well:

They follow pheromones and when they reach a junction, they decide where to go next based on how much pheromone is on each trail
They lay down pheromones

In the same spirit as turning our complex map into a simpler graph, let's turn our ants into something a bit more manageable that a computer could understand.

Ants follow pheromones

To model our situation, have each of our simulated mathematical ants start at one of the vertices (cities) on our graph and let it choose which vertex to go to next based on which edge (road) has the most pheromones on it. We don’t want our mathematical ants to always follow the edge with the most pheromones (ants like exploring), but we would like them to most of the time. Let’s instead make ants choose which edge randomly, but make them more likely to choose trails that have more pheromone on them. If you are interested in the exact math that is going on behind the scenes, a good place to start is here.
Remember how we couldn’t tell real ants that we want them to visit each city once and they need to come back to where they started? Well, we are able to tell our mathematical ants this. We just make the probability of choosing any edges that lead us to a city we have already visited 0. That is, we make it so that our mathematical ants can never choose a path that leads to a city it has already visited. The ants will stop when they either make it back to where they started or when there is nowhere for them to go that they haven’t already been.

Ants lay down pheromones

We know that ants choose which path to take by following pheromones and that shorter paths will have more pheromone on them. In this step, we add pheromone to an edge if it was part of a successful ant’s tour. If the total length of the ant’s tour were long, we would add a small amount of pheromone and a large amount if it were short. However, pheromones don’t last forever, they evaporate. We also have to take this into account by decreasing the amount of pheromone on each trail by a small amount after we add all the pheromone as described above. We can choose to model this evaporation by saying that a proportion is lost every time we update our pheromone values. As we can’t always be sure that all the ants will make it back to their starting point, we will only consider the mathematical ants that made it back to the starting point when we model laying down pheromones. Fortunately, we have chosen not to give our mathematical ants emotions so the ones which fail won’t feel bad for having done so. Once again, if you would like to look at the details of the math, here is a good place to start.

With the modeling out of the way, you are now ready to understand the Ant Colony Optimization algorithm! Let’s walk through an example as we go:

Ant Colony Optimization Algorithm

First, we turn our cities and roads into vertices and edges on a graph. Below I’ve got a map of the hypothetical country of Antlandia and its 5 biggest cities as well as the graph representing this map; this is the same one you saw above.

Next, we create as many mathematical ants as we want. We will use 3 for this example: Angela, Barbara, and Cameron, but you could use as many as you desire (think millions or billions of ants – no need to worry about an infestation since these ants don’t actually exist).

With everything set up, we simulate the mathematical ants wandering around the graph as described above. Since there aren’t any pheromones to start, our 3 ants will just wander around aimlessly at first. We will have them start at Antopia, the capital of Antlandia. The paths each of them took can be seen below (they all start at the star and stop at the red octagon).

After the ants have finished wandering around, look at the ones that finished their tour and update the pheromones on the trails they took accordingly. In our example only Cameron successfully completed their tour with length 29. Let’s also say that 10% of the pheromone evaporates after each simulation. Using the pheromone updating process detailed above and the actual equations as described here, we find that the new pheromone levels are as shown below in parentheses next to the edges with pheromone on them. Notice that only the trails that Cameron took have pheromone on them because Angela failed to visit every vertex and Barbara did not make it back to the start so we did not add pheromone for their trails.

Now we just repeat steps 3 and 4 until our 3 ants have settled on a solution. That is, when they all end up taking the same (hopefully shortest) path every time.

That’s it! Congratulations for making it to the end. Not only did we learn a bit about how Ant Colony Optimization works, but we also learned how we can take advantage of mathematical modeling to turn complex, real-world phenomena like cities, roads, and ants into something we can simulate on a computer much more easily than we could run experiments in the real world. We also got to see a great example of biomimicry – using nature as technological inspiration. If you are interested in another example of using biomimicry to produce algorithms, I recommend you check out this post by Angela Zhou on the Artificial Bee Colony algorithm. As an exercise to the reader, I encourage you to see where else you can find inspiration from nature, whether that’s in art, engineering, computer science, or something else!

HMC Bee Lab

Pages

Friday, April 28, 2023

Ant-Salesman: Simulationmania

No comments:

Post a Comment