Ant Colony

Ant Colony Optimization (ACO) is an interesting way to obtain near-optimum solutions to the Travelling Salesman Problem (TSP). It involves utilizing multi-agent ants to explore all possible solutions and converge upon a short path with a combination of a priori knowledge and pheromone trails deposited by other ants


Click on the canvas in order to introduce/remove a node



Optimization Parameters:

Mechanism

Given a bunch of points, the travelling salesman problem involves finding the shortest path that visits all the points exactly once. Finding/verifying a solution absolutely requires a brute force search, whose time complexity scales as factorial. Ant Colony Optimization (ACO) is one way to go about finding near-optimal solutions for the travelling salesman problem.

ACO involves keeping two matrices: the pheromone matrix \(P\) such that \(P_{ij}\) represents the amount of pheromone between nodes \(i\) and \(j\), and the a priori knowledge matrix \(A\) such that \(A_{ij}\) represents the a priori knowledge of the distance between nodes \(i\) and \(j\). In this case, we set \(A_{ij} = 1/d_{ij}\) where \(d_{ij}\) is the distance between nodes \(i\) and \(j\). The pheromone matrix is initialized to 1 in the beginning.

When the \(n^{th}\) ant is at the \(i^{th}\) node, it can travel to any node which it hasn't visited yet. The probability that it will travel to the \(j^{th}\) node is given by \[ p_{ij}^{(n)} = \frac{P_{ij}^\alpha A_{ij}^\beta}{\sum_{k \in U_a} P_{ik}^\alpha A_{ik}^\beta} \]

Here, \(U_a\) is the set of nodes that the \(n^{th}\) ant has not visited yet, \(\alpha\) is the influence of the pheromones in the decision making process, and \(\beta\) is the influence of the a priori knowledge in the decision making process. During the simulation, the intensity of the line joining two edges is proportional to above probability

When a population of ants have visited all nodes exactly once, the pheromone matrices are updated as follows: \[ P_{ij} = (1 - \rho) P_{ij} + \sum_{n=1}^N \Delta P_{ij}^{(n)} \] \[ P_{ij}^{(n)} = \begin{cases} Q / L_k & \text{if the \(n^{th}\) ant travelled from \(i\) to \(j\) while moving}\\ 0 & \text{otherwise} \end{cases} \]

Here, \(\rho\) is the evaporation rate, or the fraction of the pheromone trail that would have evaporated by the next iteration. \(Q\) is a constant that determines the amount of pheromone deposited by each ant, and \(L_k\) is the length of the path taken by the \(k^{th}\) ant. After 200 iterations, the simulation will stop, and the path taken by the shortest any will be displayed.

Tweaking

  1. A lower population of ants will cause the approximated optimal solution to change rapidly between iterations.
  2. A high value of evaporation rate allows the population to explore more paths, but it may not necessarily return an optimal path at the end
  3. \( (\alpha, \beta) = (0, 1) \) is equivalent to using only the a priori knowledge. The solution given will be the nearest neighbor heuristic, which is the most straightforward way to optimize the travelling salesman problem. Basically, from each node, travel to the nearest unvisited node.
  4. \( \alpha = 0 \) and \( \beta > 1 \) makes the system collapse to a local minimum. But the solution will probably be far from optimum.
  5. \( \alpha > 0.5 \) will lock the ants into heavily favouring shorter edges. The simulation will then try to find the a way to connected these shorter edges in an optimal manner.
  6. When points are chosen randomly, \( (\alpha, \beta) = (1, 1) \) seem to give the best results.

  1. This simulation is computationally complex and will lag on lower-end devices
  2. You can change the evaporation factor, pheromone influence and a priori influence during the simulation to see how it affects the solution space.
  3. On the other hand, changing the number of ants during the simulation will cause it to restart
  4. Related: Solving TSP by brute force

Developed by ChanRT | Fork me at GitHub