Monte Carlo Simulations and an Ant Colony Algorithm
A project by Thomas Cannon and Kara MacPhaul
Ants are interesting little creatures - especially when it comes to finding the optimal route to a food source. With a web of pheromones a single ant alerts others nearby where the path to the food is. The other ants will follow suit and iterate on the path until they collectively find the most efficient route. It is possible to model this behavior with a modification to Monte Carlo Simulations - with applications in fields ranging from mechanical engineering to protein folding.
But here we keep it simple. We imagine a 2D grid that represents the (x,y) plane that an ant can travel over. Initially, there are two points on the grid - one marks the ant's start location, and the other is the food source. In each grid cell, we assign a probability to each of the 4 sides and 4 corners of the cell. That probability determines where the ant will randomly take its next step. We want to create obstacles for the ant, so some of these probabilities are set to zero to simulate an impassable barrier into another adjacent cell. This setup creates a memoryless simulation. Then we set the ants loose!
The first trial is in a small 10 x 10 grid with 5,000 ants. This is more than enough to saturate the grid with random walk paths and almost assuredly give us a global search. In the diagram below, we see all of the paths that the ants have taken. The green dot is where the ant starts at (2,2) and the red dot is the food located at (10,10). The black dots and the food source are absorbing states. These nodes are cells where once the ant enters, there is a probability of 0 for every direction exiting that cell, so the ant gets permanently stuck in that cell - or in the case of the food cell, achieves its goal. The lines in the diagram represent every transient and recurring state.
We run these simulations to take a look at the probability distribution that the ants collectively give when they reach the food (i.e. what is the probability that at any given step the ant will reach the food). Surprisingly, to move only a few grid cells in a random walk, it takes a lot of steps. In this case our Stationary Probability at step 100 is about 0.399, and at step 200 it is about 0.597
Now, imagine a grid that is much larger, or perhaps is in a high dimensional space. The computational power needed to globally search for the optimal route could be enormous. This is where the Any Colony Optimization Algorithm comes in. Instead of trying to run an enormous amount of simulations, we scale back the number and duration of simulations and then use the results of each simulation to then inform a new iteration of simulations. We implement a back propagation on our P-matrix between iterations so that the probabilities along paths that ants take that lead to food are reinforced, while the paths that do not lead to food are decayed. The paths that are reinforced are also weighted by the number of steps that it took to arrive at the food - so, for a smaller number of steps, the greater the reinforcement. Each iteration strengthens several paths towards the food until all of the ants converge onto one path.
We see the ants above searching for the food and finding as many paths as they can towards the food. Every now and then it looks like they are about to make up their mind before another ant will randomly stray off of a popular path and find a new, more efficient route. Below is a plot of convergence onto the final route. The plot represents the average number a steps it took to find food among all of the ants over each iteration. You can also clearly see that the average step max is 400. This is because in these simulations, we gave the ants a step limit. If an ant reached 400 steps, we considered that ant's iteration a failed attempt. It was exciting to watch all of the all of the various local minimums the ants discovered before deciding that the final route was most optimal.
Source Code for this project is available on GitHub.
