The Travelling Antman
Solving TSP (Travelling Salesman Problem) using ACO (Ant Colony Optimisation) algorithm.
Demo of ACO algorithm solving TSP. Play with the algorithm by visiting this page! (Source code is available here).
The Travelling Salesman Problem
The Traveling Salesman Problem (TSP) seeks the shortest possible route that visits a given set of cities exactly once. The challenge is to find this unique tour, starting and ending in the same city, while minimizing the total travel distance or cost. Despite its simple description, finding the absolute optimal solution becomes computationally very difficult as the number of cities increases.
The Ant Colony Optimisation Algorithm for TSP
Ant Colony Optimization (ACO) is a metaheuristic algorithm inspired by the foraging behavior of real ants, used to find good paths through graphs. Artificial ants build solutions probabilistically, influenced by pheromone trails deposited on path segments by previous ants, with stronger pheromone indicating better-quality solutions found earlier. Over time, this collective behavior reinforces shorter or more optimal paths, leading the colony to converge towards good solutions for complex optimization problems.
To solve the TSP using ACO, represent cities as nodes and distances as edge weights in a graph where artificial ants construct tours. Ants probabilistically choose the next city based on distance and existing pheromone trails, depositing more pheromone on shorter routes they complete. Over time, this process reinforces edges belonging to shorter overall tours, guiding the colony towards near-optimal solutions for the shortest possible route.
Underlying principles
At its core, ACO leverages positive feedback through pheromone trails: better solutions attract more pheromone, increasing their likelihood of being chosen. Negative feedback is implicitly present as pheromone evaporates over time, preventing premature convergence on suboptimal paths and encouraging exploration of new routes. This balance of exploitation and exploration drives ACO's effectiveness.
Pheromone Matrix and Probability:
The pheromone matrix stores the intensity of pheromone on each path between cities. Initially, all paths have a small, equal amount. When an ant in city i decides its next city j, it uses a probability formula. This formula considers both the pheromone intensity on the edge (i, j) and the heuristic information (typically the inverse of the distance between i and j). Cities with higher pheromone and shorter distances are more likely to be chosen.
Iterative Steps:
Initialization: Initialize the pheromone matrix with small values and place all ants randomly on cities.
Ant Colony Construction: Each ant independently constructs a complete tour by iteratively selecting the next unvisited city using the probability formula.
Pheromone Update: After all ants have completed their tours, the pheromone trails are updated. First, existing pheromone on all edges evaporates by a certain factor. Then, each ant deposits pheromone on the edges it traversed, with the amount of pheromone proportional to the quality (shorter length) of its tour.
Iteration: Repeat steps 2 and 3 for a predetermined number of iterations or until a satisfactory solution is found. Over time, the pheromone trails on the edges belonging to shorter tours will be reinforced, guiding subsequent ants towards better solutions.
Probability of Choosing the Next City (j) from Current City (i) by Ant k:
Pheromone Update Rule
What’s next?
In the next blog post we will look at step by step guide for ACO algorithm for travelling salesman problem in Python.
 | A guest post by
|