Ant Colony Optimization - Dorigo, Birattari, Stutzle (2006)

Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique

Authors: Marco Dorigo, Mauro Birattari, Thomas Stützle — Université Libre de Bruxelles Published: IEEE Computational Intelligence Magazine, November 2006

Summary

ACO is a metaheuristic for combinatorial optimization inspired by the foraging behavior of ant colonies. Artificial ants build solutions by traversing a construction graph and deposit pheromone proportional to solution quality; pheromone evaporation prevents stagnation and keeps the search adaptive. The technique has been successfully applied to NP-hard problems (TSP, vehicle routing, scheduling, protein folding) and is state-of-the-art for dynamic routing in telecommunication networks.

Key points

• Biological basis: the double bridge experiment (Deneubourg et al.) shows ants collectively find the shortest path through positive feedback — shorter paths accumulate pheromone faster, attracting more ants
• Stigmergy: indirect, environment-mediated communication — ants share information by modifying their environment, not by direct contact
• ACO metaheuristic loop: ConstructAntSolutions → ApplyLocalSearch (optional) → UpdatePheromones
• Three main variants:
  • Ant System (AS) — all ants deposit pheromone each iteration; pheromone update: τ_ij ← (1−ρ)·τ_ij + Σ τ^k_ij
  • MAX-MIN Ant System (MMAS) — only the best ant updates; pheromone bounded between [τ_min, τ_max] to prevent premature convergence
  • Ant Colony System (ACS) — adds a local pheromone update after each step to diversify search; uses a pseudorandom proportional decision rule
• Convergence: proven for ACS and MMAS; theoretical results also link ACO to reinforcement learning and stochastic gradient ascent
• Applications: routing (TSP, vehicle routing), assignment (quadratic assignment), scheduling, bioinformatics (protein folding, drug docking), telecom networks (AntNet)
• Active research areas: dynamic/stochastic optimization, multi-objective ACO, continuous optimization, parallel implementations

My notes

Add your own notes here.