Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 36 ยท Swarm and Other Metaheuristics

Ant Colony Optimization

Understand ant colony optimization (ACO): pheromone trails, heuristic information and evaporation. Build an Ant System for the traveling salesman problem in Python.

Real ants find short paths between their nest and food without any leader and without any map. Each ant lays a chemical trail called pheromone as it walks. Later ants prefer paths with stronger pheromone. Short paths get walked more often per hour, so they collect more pheromone, which attracts yet more ants. Long paths are walked less and their trail evaporates. Soon almost all ants use the shortest path.

Ant colony optimization (ACO), introduced by Marco Dorigo in the early 1990s, turns this behavior into an algorithm for combinatorial problems such as routing, scheduling and assignment. It is the natural partner of genetic algorithms for tour-like problems.

The Ant System algorithm

We will apply it to the traveling salesman problem (TSP): visit every city once and come back, as short as possible. In each iteration:

  1. Each of m ants builds a complete tour, one city at a time.
  2. At city i, an ant picks an unvisited city j with probability proportional to tau[i][j]^alpha * eta[i][j]^beta:
    • tau is the pheromone on the edge (learned experience).
    • eta = 1 / distance is the heuristic (closer is more attractive).
    • alpha and beta weigh the two. A typical choice is alpha = 1, beta = 2 to 5.
  3. Pheromone evaporates: tau = (1 - rho) * tau, with rho around 0.1 to 0.5.
  4. Every ant deposits pheromone on the edges of its tour, in an amount Q / tour_length, so shorter tours deposit more.
flowchart TD
    I["Initialize pheromone tau"] --> B["Each ant builds a tour using tau and 1/distance"]
    B --> L["Compute tour lengths"]
    L --> E["Evaporate: tau = (1 - rho) * tau"]
    E --> D["Deposit: tau += Q / length on each tour edge"]
    D --> T{"Enough iterations?"}
    T -- no --> B
    T -- yes --> R["Return best tour found"]

Evaporation forgets bad paths; deposits reinforce good ones.

Python Ant System for a 20-city TSP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best-so-far length falls quickly and the iteration mean approaches it: the colony converges onto good edges.

The parameters

  • alpha controls how strongly ants follow pheromone. Too high and the colony locks onto an early tour (stagnation).
  • beta controls greediness toward short edges. With beta = 0, ants ignore distances and can take many generations to learn anything.
  • rho is the evaporation rate. Small rho means long memory and slow convergence; large rho forgets quickly.
  • Number of ants m: often equal to the number of cities.

Improved variants

  • Elitist Ant System: the best-so-far tour deposits extra pheromone each iteration.
  • Rank-based Ant System: only the best few ants deposit, weighted by rank.
  • MAX-MIN Ant System (MMAS): only the best ant deposits, and pheromone values are clamped between tau_min and tau_max. This avoids stagnation and is the most widely used variant.
  • Ant Colony System (ACS): a greedy choice with probability q0, plus local evaporation as ants walk, which spreads the ants out.
Python MAX-MIN style: only the best ant deposits, with bounds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

ACO versus GA

ACO builds a solution constructively, edge by edge, guided by shared memory (the pheromone matrix). A GA changes whole solutions by recombination. ACO is naturally good at graph problems (TSP, vehicle routing, network routing) and handles dynamic problems well, since pheromone adapts when distances change. GAs are more general. Both can be combined, for example by seeding a GA population with ant tours.

Beyond routing

ACO has been applied to scheduling, graph colouring, feature selection and even to continuous optimization (ACO_R). The key requirement is that you can phrase a solution as a path of choices, each with an attractiveness number.

Common mistakes

  • Zero pheromone or zero heuristic. If a weight can be zero for all candidates, the probability division fails. Keep pheromone strictly positive.
  • Evaporation too weak. Early random tours keep their influence and the colony stagnates.
  • Ignoring the heuristic. Pure pheromone learning is much slower than guided construction.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In ACO, what role does pheromone evaporation play?

    Evaporation lowers all trails each iteration so reinforcement must keep earning its place.
  2. 2. How is the probability of choosing the next city in Ant System computed?

    Pheromone and distance heuristics are combined and normalized.
  3. 3. What makes MAX-MIN Ant System resist stagnation?

    Bounds keep every edge selectable and the best-only update keeps pressure on.
  4. 4. Which kind of problem is ACO especially natural for?

    Solutions are paths built from step-by-step choices.

Summary

  • Ants deposit pheromone proportional to solution quality; pheromone evaporates over time.
  • Each ant builds a solution using pheromone (tau) and a distance heuristic (eta).
  • alpha, beta and rho balance learning, greediness and forgetting.
  • MAX-MIN and Ant Colony System variants fight stagnation.
  • ACO suits constructive path problems and adapts to changing graphs.

Next: Genetic Programming: Evolving Programs