## Definition **Ant Colony Optimization (ACO)** is a population-based metaheuristic inspired by ants' foraging behaviour. Artificial "ants" construct solutions by walking on a problem graph; they deposit "pheromone" trails on good paths; subsequent ants probabilistically prefer high-pheromone paths. Introduced by Marco Dorigo (1992). ## The Biological Inspiration Real ants find shortest paths between nest and food source by deposting pheromone on their route. Shorter paths complete faster → more pheromone laid per unit time → more attractive to subsequent ants. Positive feedback converges the colony onto the shortest path. ## The Algorithmic Idea Apply this idea to combinatorial problems where solutions are paths on a graph: ``` initialise pheromone τ on all graph edges while not done: for each ant k = 1, ..., m: construct solution by traversing the graph at each step, pick next edge probabilistically: P(j | i) ∝ τ_ij^α · η_ij^β record path length pheromone evaporation: τ_ij ← (1 - ρ) · τ_ij pheromone deposit: τ_ij ← τ_ij + Σ_k Δτ_ij^k for ants k using edge (i,j) best_path ← shortest path found return best_path ``` - $\tau_{ij}$ — pheromone on edge $(i, j)$. - $\eta_{ij}$ — heuristic desirability (typically $1 / d_{ij}$, inverse distance). - $\alpha, \beta$ — hyperparameters controlling pheromone vs heuristic influence. - $\rho$ — evaporation rate. ## The Three Mechanisms 1. **Probabilistic construction.** Each ant builds a solution stochastically. 2. **Positive feedback.** Better solutions reinforce their paths. 3. **Evaporation.** Old information decays; allows the colony to forget bad paths. ## Where ACO Wins - **Travelling Salesman Problem.** The original ACO application; competitive with specialised algorithms. - **Vehicle Routing Problem.** - **Quadratic Assignment Problem.** - **Job-shop scheduling.** - **Network routing** in telecommunications. ## Strengths - **Natural for graph-based problems** with a clear notion of "edge traversal". - **Distributed by construction** — ants are independent during construction. - **Combines exploration (stochasticity) and exploitation (pheromone) gracefully.** ## Weaknesses - **Slow.** Many iterations and ants needed. - **Hyperparameter-sensitive.** $\alpha, \beta, \rho$, ant count, pheromone bounds. - **Less effective on continuous problems** (variants exist but PSO and CMA-ES usually win). ## Variants - **Max-Min Ant System (MMAS).** Bounds pheromone values to prevent stagnation. - **Ant Colony System (ACS).** Adds local pheromone updates and elitism. - **Population-based ACO.** Maintains an elite population instead of pure pheromone state. ## Hybrid Methods ACO often combines well with: - **Local search.** Apply 2-opt or 3-opt to each ant's solution. - **Cutting planes / MILP** for partial problem decomposition. Hybrids dominate the strongest ACO results. ## When to Reach For ACO - **Combinatorial problem with rich graph structure.** - **Need for solutions that respect non-local constraints.** - **When you can afford many evaluations** (the cost of population × generations is real). For most problems, specialised algorithms outperform ACO. Its appeal is the elegance of the metaphor and the natural fit to graph problems. ## Related - [[Genetic Algorithms]] - [[Simulated Annealing]] - [[Particle Swarm Optimization]] - [[Combinatorial Optimization]]