Travelling Ant Colony

This is an ant colony optimisation algorithm for quickly finding a good solution to the travelling salesman problem. Rather than finding the best solution (which is NP-hard; in other words, we know of no solution in polynomial time), it will very quickly find a good solution, using inspiration from how an ant colony behaves when foraging. Ants are remarkable in the sence that they are extremely efficient in what they do, despite being almost blind, have no means of direct communication and lack leaders.

Ants deposit volatile pheromones as they move, and these will evaporate in time. A trail with a higher level of pheromones will attract more ants, meaning that good trails will be picked over bad ones. In the Travelling Ant Colony program, artificial ants will move along the edges in the travelling salesman graph, and deposit artificial pheromones as they move. Each edge $e_{ij}\,$ is associated with a pheromone level $\tau_{ij}\,$ . The outline of the algorithm is as follows, if there are nodes and artificial ants:

Initialize the pheromone levels.
$\tau_{ij} = \frac{N}{D^{\textrm{nn} } }, \:\:\: \forall i,j \in [1,n]$
where $D^{\textrm{nn} }\,$ is the length of the nearest neighbour path, i.e. the path one gets when always going to the nearest unvisted city. Performing this step will set the pheromone levels of all edges to the same value, thus creating an equal likelihood of the ants taking any path.
Let denote the so called tabu list, which contain the nodes already visited. This list is used to make sure the same node is not visited multiple times. For each ant , select a random start node, and add it to the initially empty tabu list. The next step is to build the tour . In each step of the tour, select the move from node to node probabilistically based on the pheromone levels and the distance between the nodes, according to:
$p(e_{ij} | S) = \frac{\tau_{ij}^\alpha \eta_{ij}^\beta}{\sum\limits_{v_l \notin L_T(S)} \tau_{lj}^\alpha \eta_{lj}^\beta}\,$
In the equation, $\eta_{ij}\,$ is the visibility of node from node , and here has the value $\eta_{ij} = {}^1\!/_{d_{ij} }\,$ , where $d_{ij}\,$ is the euclidean distance betwen node and node . The constants $\alpha$ and $\beta$ determine the relative importance of the pheromone trails and the distance between the nodes. They have the values 1.0 and 4.0 respectively.
In each step of the movement, the node that the ant is currently visiting is added to . When all cities have been visited in this manner, return to the first city again.
Update the pheromone levels. Let denote the length of . In other words, is the length of the entire tour for ant .
1. For each ant (out of the total of ants), compute
  $\Delta \tau_{ij}^{[k]} = \begin{cases} {}^1\!/_{D_k} & \textrm{if ant $k$ traversed $e_{ij}$} \ 0 & \textrm{otherwise}\end{cases}\,$
2. For each edge $\tau_{ij}\,$ , calculate the total increase of the pheromone level that the ants have deposited:
  $\Delta \tau_{ij} = \sum_{k=1}^N \Delta \tau_{ij}^{[k]}\,$
3. As the previous step would lead to an indefinate increase of the pheromone levels, the concept of evaporation is used. Thus, $\tau_{ij}\,$ is modified as follows:
  $\tau_{ij} \leftarrow (1 - \rho)\tau_{ij} + \Delta \tau_{ij}\,$ .
  Here, $\rho$ is the evaporation rate, and is a constant with a value between 0 and 1. If no ant has traversed an edge $e_{ij}\,$ , then the pheromone update for that edge consist only of evaporation.
Repeat steps 2 to 3 until a solution that is deemed good enough is found.

The code is available at my GitHub account.

Screenshot of Matlab running the program:

Wikimedia contributions

Travelling Ant Colony