Ant Colony Optimization

Studies have shown that over time ants will be able to find the shortest path in between the location of their colony and their food source.
The mathematics behind this phenomenon is known as the ant colony optimization algorithm.
This algoritm is also a solution of the traveling salesman problem, which are both optimization problems.
Imagine a space which includes both an ant colony and food. The area is divided into a number of vertices. In the model, an ant is only able to walk
from vertex to vertex in order to reach the food. At each vertex, the ant has to choose via which route he continues.
The pheromone trail will evaporate over time. This causes the previous, less
optimal, path to fade when a shorter path is found. To model the decreasing
amount of pheromones a forgetting factor ρ is introduced, which decreases the
pheromone level in each iteration:

In the journey to the source of food, each ant will leave behind a pheromone trail. An ant which leaves from a vertex is more likely to choose the path with
the highest concentration of pheromone to continue his journey. Although, some ants won't choose the path with the highest pheromone concentration. This
encourages exploration of the area. If there exist a shorter path, eventually some ant will find it. The probability for an ant to move from some node *i* to
another node *j* is obtained:

In this equation, τ is the pheromone variable and η a heuristic variable. The heuristic variable represents a short term quality measure, in this case the distance between two vertices. The relative importance between the pheromone and heuristic variables are set by α and β.

In the above equation, the first term is the residual pheromone level after evaporation.
The last term is the pheromone level added by the ants who have just walked over route *ij*.