🐜 Ant Colony Optimization for the Travelling Salesman Problem

A Swarm Intelligence Approach to NP-Hard Combinatorial Optimization

Bio-inspired stochastic optimization leveraging emergent collective intelligence of artificial ant colonies to converge on near-optimal Hamiltonian cycles in polynomial-bounded runtime.

---

Author · Built by AG — Chief AI Officer @ Google

📋 Table of Contents

• Problem Statement
• Theoretical Foundation
• Algorithm Architecture
• Mathematical Formulation
• Convergence Analysis
• Implementation Details
• Getting Started
• Configuration & Hyperparameters
• Results & Visualization
• Computational Complexity
• References
• Contributing
• License

---

🧩 Problem Statement

The Travelling Salesman Problem (TSP) is one of the most intensively studied problems in computational optimization. Given a set of $n$ cities and pairwise distances between them, the objective is to find the shortest possible route that visits each city exactly once and returns to the origin city — a minimum-weight Hamiltonian cycle.

Why TSP Matters

Aspect	Details
Complexity Class	NP-hard (decision version is NP-complete)
Search Space	$(n-1)!/2$ unique tours for $n$ cities
Brute Force	Intractable for $n > 20$ — factorial growth
Real-World Impact	Logistics, VLSI design, DNA sequencing, telescope scheduling

For our 20-city instance, the search space contains $\approx 6.08 \times 10^{16}$ possible tours — far beyond exhaustive enumeration. This motivates the use of metaheuristic approaches that trade guaranteed optimality for tractable near-optimal solutions.

---

🔬 Theoretical Foundation

Swarm Intelligence & Stigmergy

Ant Colony Optimization (ACO), first introduced by Marco Dorigo (1992), belongs to the family of swarm intelligence algorithms. It draws inspiration from the foraging behavior of real ant colonies, where individual agents with limited cognitive ability collectively solve complex optimization problems through stigmergy — indirect communication via chemical pheromone trails deposited on the environment.

┌─────────────────────────────────────────────────────────────────────┐
│                    SWARM INTELLIGENCE TAXONOMY                     │
├─────────────────────────────────────────────────────────────────────┤
│                                                                     │
│   Nature-Inspired Metaheuristics                                    │
│   ├── Evolutionary Algorithms                                       │
│   │   ├── Genetic Algorithm (GA)                                    │
│   │   ├── Differential Evolution (DE)                               │
│   │   └── Evolution Strategy (ES)                                   │
│   ├── Swarm Intelligence            ◄── THIS PROJECT               │
│   │   ├── Ant Colony Optimization (ACO)  ◄━━━━━━━━━━━━━━━━━━━━━━   │
│   │   ├── Particle Swarm Optimization (PSO)                         │
│   │   └── Bee Colony Optimization (BCO)                             │
│   └── Physics-Based                                                 │
│       ├── Simulated Annealing (SA)                                  │
│       └── Gravitational Search (GSA)                                │
│                                                                     │
└─────────────────────────────────────────────────────────────────────┘

The Biological Analogy

Biological System	Computational Model
Ant	Constructive solution agent
Pheromone trail	Learned desirability values on edges
Trail evaporation	Forgetting mechanism (exploration)
Shorter path → faster trips → more pheromone	Positive feedback loop for better solutions
Colony convergence	Algorithm convergence to near-optimal tour

---

🏗 Algorithm Architecture

The algorithm operates through a construct-update loop across discrete generations:

                    ┌──────────────────────┐
                    │   INITIALIZATION     │
                    │  • Distance Matrix   │
                    │  • Pheromone Matrix   │
                    │    τ(i,j) = 0.1 ∀i,j │
                    └──────────┬───────────┘
                               │
                    ┌──────────▼───────────┐
              ┌────►│   GENERATION LOOP    │
              │     │   g = 1, 2, ..., G   │
              │     └──────────┬───────────┘
              │                │
              │     ┌──────────▼───────────┐
              │     │   ANT CONSTRUCTION   │
              │     │  For each ant k:     │
              │     │  • Start random city │
              │     │  • Build full tour   │
              │     │    via probabilistic  │
              │     │    city selection     │
              │     └──────────┬───────────┘
              │                │
              │     ┌──────────▼───────────┐
              │     │  PHEROMONE UPDATE     │
              │     │  • Deposit: Δτ ∝     │
              │     │    1/√(tour_cost)     │
              │     │  • Evaporate: τ -=ρ  │
              │     └──────────┬───────────┘
              │                │
              │     ┌──────────▼───────────┐
              │     │  BEST TOUR TRACKING  │
              │     │  Update global best  │
              │     │  if improved         │
              │     └──────────┬───────────┘
              │                │
              │        ┌───────▼───────┐
              └────────┤  g < G ?  YES │
                       └───────┬───────┘
                               │ NO
                    ┌──────────▼───────────┐
                    │   RETURN BEST TOUR   │
                    └──────────────────────┘

---

📐 Mathematical Formulation

1. Distance Metric

The pairwise Euclidean distance between cities $i$ and $j$:

$$d(i,j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$

2. Probabilistic Transition Rule

At each construction step, ant $k$ at city $i$ selects the next city $j$ from the set of unvisited cities $\mathcal{N}_i^k$ with probability:

$$P_{ij}^k = \frac{\tau_{ij} \cdot \eta_{ij}}{\displaystyle\sum_{l \in \mathcal{N}_i^k} \tau_{il} \cdot \eta_{il}}, \quad j \in \mathcal{N}_i^k$$

Where:

• $\tau_{ij}$ — pheromone intensity on edge $(i,j)$
• $\eta_{ij} = \frac{1}{d_{ij}}$ — heuristic visibility (inverse distance)
• $\mathcal{N}_i^k$ — feasible neighborhood (unvisited cities for ant $k$)

Note: This implementation uses $\alpha = 1, \beta = 1$ implicitly, weighting pheromone and heuristic information equally.

3. Pheromone Update

After each ant completes a tour, pheromone is deposited on all traversed edges:

$$\tau_{ij} \leftarrow \tau_{ij} + \Delta\tau_{ij}^k$$

Where the pheromone deposit is proportional to the inverse square root of tour cost:

$$\Delta\tau_{ij}^k = \sqrt{\frac{1}{C(T^k)}}$$

This non-linear deposit function amplifies the reward signal for shorter tours more aggressively than the classical $\frac{1}{C(T^k)}$ formulation.

4. Pheromone Evaporation

After all ants complete their tours, global evaporation reduces all pheromone values:

$$\tau_{ij} \leftarrow \max\left(\tau_{ij} - \rho, ; \epsilon\right)$$

Where $\rho = 0.0008$ is the evaporation rate and $\epsilon = 10^{-6}$ is the minimum pheromone threshold preventing premature stagnation.

---

📊 Convergence Analysis

The ACO algorithm exhibits characteristic convergence behavior driven by positive feedback:

Cost ▲
     │ ╲
     │  ╲╲
     │    ╲╲
     │     ╲╲╲
     │       ╲╲╲╲
     │          ╲╲╲╲╲╲
     │              ╲╲╲╲╲╲╲╲╲
     │                    ╲╲╲╲╲╲╲╲╲╲╲╲╲╲
     │                              ╲╲╲╲╲╲╲╲╲╲╲╲╲╲────────
     │
     └──────────────────────────────────────────────────────► Generation
     0        32        64        96       128       160

Phase	Generations	Behavior
Exploration	0 – 30	High entropy; diverse tours; rapid cost decrease
Exploitation	30 – 100	Pheromone trails strengthen; convergence accelerates
Refinement	100 – 160	Marginal improvements; near-optimal plateau reached

---

🛠 Implementation Details

Project Structure

solving-TSP-problem-with-ACO-Heuristic-Algorithm-in-python/
│
├── ACO.py                  # Core algorithm: ACO solver + visualization
├── Cities List.txt         # Input dataset: 20 cities with (index, x, y)
├── README.md               # This document
├── CONTRIBUTING.md         # Contribution guidelines
├── CITATION.cff            # Citation metadata (CFF format)
├── requirements.txt        # Python dependencies
├── LICENSE                 # MIT License
└── .gitignore              # Git ignore rules

Class Design

class Draw              # Visualization engine — renders city plots & route arrows
class ACO               # Core solver — pheromone management, tour construction, optimization loop

Method	Purpose	Complexity
initialDistances()	Build $n \times n$ distance & pheromone matrices	$O(n^2)$
getDistance()	Euclidean distance between two cities	$O(1)$
getNextCity()	Probabilistic city selection via roulette wheel	$O(n)$
updatePheromone()	Deposit pheromone on edges of completed tour	$O(n)$
applyEvaporatio()	Global pheromone evaporation with floor clamping	$O(n^2)$
getRouteCost()	Sum edge weights along a tour	$O(n)$
solve()	Main optimization loop across $G$ generations	$O(G \cdot m \cdot n^2)$

---

🚀 Getting Started

Prerequisites

• Python 3.8+
• matplotlib for visualization

Installation

# Clone the repository
git clone https://github.com/Elktrn/solving-TSP-problem-with-ACO-Heuristic-Algorithm-in-python.git
cd solving-TSP-problem-with-ACO-Heuristic-Algorithm-in-python

# Install dependencies
pip install -r requirements.txt

# Run the solver
python ACO.py

Custom City Configuration

Edit Cities List.txt with one city per line in the format:

<index> <x_coordinate> <y_coordinate>

Coordinates can be in any numeric range. The algorithm automatically computes the Euclidean distance matrix.

---

⚙ Configuration & Hyperparameters

Parameter	Default	Description	Tuning Guidance
cityCount	20	Number of cities (auto-detected from file)	Scale antCount and generations accordingly
antCount	15	Number of ants per generation	Typically $0.5n$ to $n$
evaporationRate	0.0008	Pheromone decay per generation ($\rho$)	Lower → stronger memory; higher → more exploration
generations	160	Number of optimization iterations ($G$)	Increase for larger instances
Initial pheromone	0.1	$\tau_0$ for all edges	Should be > 0 to avoid cold-start issues
Pheromone floor	$10^{-6}$	Minimum $\tau$ to prevent stagnation	Keep small but non-zero

Hyperparameter Sensitivity

                    evaporationRate (ρ)
                    
        Low (0.0001)         High (0.01)
        ┌──────────┐         ┌──────────┐
        │ Strong   │         │ Weak     │
        │ memory   │         │ memory   │
        │ Risk:    │         │ Risk:    │
        │ premature│         │ slow     │
        │ converge │         │ converge │
        └──────────┘         └──────────┘
              ▲                    ▲
              │    SWEET SPOT      │
              │   ρ ≈ 0.0008      │
              │  ◄────────────►   │
              │   Balance of      │
              │   exploration &   │
              │   exploitation    │
              └────────────────────┘

---

📈 Results & Visualization

The algorithm produces real-time matplotlib visualizations at every $G/10$ generation interval, demonstrating progressive route optimization through emergent pheromone-guided behavior.

Random Initial Solution

Baseline: unoptimized random permutation of cities

Optimization Progression (20 cities, 15 ants, 160 generations)

Generation	Route Visualization	Observation
16		Early exploration — crossings still present
48		Pheromone trails forming; major crossings resolved
96		Near-optimal structure emerging
160		Converged — clean, crossing-free tour

---

🧮 Computational Complexity

Component	Time Complexity	Space Complexity
Distance matrix initialization	$O(n^2)$	$O(n^2)$
Single ant tour construction	$O(n^2)$	$O(n)$
Pheromone update (per ant)	$O(n)$	—
Pheromone evaporation	$O(n^2)$	—
Total per generation	$O(m \cdot n^2)$	$O(n^2)$
Total algorithm	$O(G \cdot m \cdot n^2)$	$O(n^2)$

Where: $n$ = cities, $m$ = ants, $G$ = generations.

For our configuration: $O(160 \times 15 \times 400) = O(960{,}000)$ distance lookups — completing in under 1 second on modern hardware.

---

📚 References

1. Dorigo, M. (1992). Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano.
2. Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
3. Stützle, T., & Hoos, H. H. (2000). MAX–MIN Ant System. Future Generation Computer Systems, 16(8), 889-914.
4. Blum, C. (2005). Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2(4), 353-373.
5. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.

---

🤝 Contributing

Contributions are welcome. Please read CONTRIBUTING.md for guidelines on how to submit improvements.

---

📄 License

This project is licensed under the MIT License — see the LICENSE file for details.

---

Built with curiosity and purpose.

Exploring the intersection of biological intelligence and computational optimization.