Ant Colony Optimization Lab

Part 1 · Source of inspiration

Nature’s tiny problem-solvers

Each ant is a simple stimulus-response agent, yet the colony solves hard problems through stigmergy: indirect communication by marking the environment. Ants lay pheromone as they move and tend to follow stronger trails, so the trails become the colony’s shared memory.

Chapter 10 tells the story of stigmergy and compares real and artificial ant colonies feature by feature.

The bridge experiments

Two bridges link the nest to food. Ants on the shorter branch return sooner, so it is reinforced sooner and attracts more ants (equation 10.1). Choose an experiment and the length of branch 2, then press Run.

The book describes the original bridge experiments and the autocatalytic feedback they reveal.

Double bridge

Equation 10.1

Probability p₁ of choosing branch 1 per iteration.

Why evaporation matters

Evaporation (ρ) lets the colony forget stale trails. Change ρ and watch how the ants share out the three food piles.

Figure 10.4 in the book compares foraging runs at three evaporation rates and explains what goes wrong at each extreme.

Foraging colony

After the NetLogo Ants model

nestnear pilemiddle pilefar pilesearching antant carrying foodchemical (pheromone)

Food left in each pile over time.

Part 2 · The algorithm

ACO metaheuristics

Ants build solutions step by step on a graph, biased by pheromone τ (learned) and desirability η (usually 1/distance); then trails evaporate and good solutions are reinforced.

Algorithm: Ant colony optimization metaheuristic Set parameters, initialize pheromone trails while termination conditions not met do ConstructAntSolutions # each ant builds a path (eq. 10.6) ApplyLocalSearch # optional, e.g. 2-opt UpdatePheromones # evaporation and deposit (eqs. 10.2 to 10.5) end while

Chapter 10 explains each step, the stopping criteria, and how α and β in equation 10.6 trade experience against greed.

p_ij^k(t) = [τ_ij(t)]^α [η_ij(t)]^β / Σ_{l ∈ N_i^k} [τ_il(t)]^α [η_il(t)]^β if j ∈ N_i^k, otherwise 0(10.6)

α weights the pheromone and β the desirability η = 1/d.

τ_ij(t+1) = (1 − ρ) τ_ij(t)(10.2)

Δτ_ij^k(t) = Q / L^k(t) τ_ij(t+1) = τ_ij(t) + Σ_k=1^m Δτ_ij^k(t)(10.4, 10.5)

Three ways to deposit pheromone

Ants deposit pheromone while moving or after completing a path (Q / L^k).

The book compares the ant density, ant quantity and ant cycle rules and when to combine them.

Choosing the parameters

Parameter	Effect
Number of ants m	More exploration per iteration, at more cost.
Evaporation rate ρ	0 never forgets; 1 forgets everything.
α and β	Learned knowledge versus greedy local information.

Chapter 10 discusses how to set every parameter, including the initial pheromone τ₀ and the deposit constant Q.

Part 3 · Section 10.3.1

Simple ACO: the shortest path problem

SACO finds the shortest path from node 1 to node 5 on the book’s graph (Figure 10.7); edges show length : pheromone. Click Next decision to watch equation 10.6 choose each step.

Section 10.3.1 works through the first iteration by hand, ant by ant, up to Figure 10.10.

SACO, one decision at a time

Iteration 1 · ant 1

Decision table (equation 10.6)

Paths this iteration

The lab computes 0.24 on the reinforced edges where Figure 10.10 shows 0.59, and the colony converges on 1 → 2 → 5 (length 5) rather than 1 → 3 → 4 → 5.

Part 4 · Section 10.3

ACO variants

Several variants address the limitations of SACO. Four of them run in the labs below.

Ant system (AS)

Ants keep a tabu list of visited nodes, and all ants deposit pheromone.

Ant colony system (ACS)

Ants often take the best edge greedily, and only the global-best ant deposits.

Max-min ant system (MMAS)

Only the iteration-best ant deposits, and trails stay within [τ_min, τ_max].

Elitist ant system

Like AS, plus an extra deposit on the best path so far.

The ACS decision rule, at node 4

An ant at node 4 chooses between nodes 2 and 5. If a random r ≤ r₀ it exploits the best edge (equation 10.10); otherwise it explores with equation 10.6. Change r₀ and watch the probabilities.

Section 10.3 details each variant and several more; Section 10.3.3 works through this decision by hand.

Pseudo-random proportional rule

Equation 10.10

Part 5 · Section 10.3.5 · Listing 10.1

Solving the open TSP with ACO

Visit 20 US cities once from New York City, without returning home. Press Run and watch pheromone gather on a good route.

Listing 10.1 in the book solves this open TSP from scratch and with ACOpy, and Section 10.3.5 discusses the route it finds.

Colony lab

Gold edges: pheromone · blue: best route so far

Best route so far (blue) and iteration mean (faint). Dashed: the book’s run and the optimum.

Variant comparison

Run every variant several times with the current settings and the same seeds, then compare their average convergence.

AS vs. elitist AS vs. ACS vs. MMAS

Mean of repeated runs

Run it in Python: Listing 10.1 Open TSP with ACO ACO Lab companion notebook From-scratch code ↓

Part 6 · Continuous optimization

ACO for a continuous variable

ACO handles a continuous variable by discretizing it: minimize f(x) = x² − 2x − 11 on [0, 3], where each of seven values of x is a path. Click Next iteration to watch four ants choose and reinforce paths.

Chapter 10 works through the first two iterations by hand and extends the idea to several variables.

Discretized ACO, iteration by iteration

Iteration 0

Part 7 · Adaptation

Adaptive ACO

Instead of fixing ρ, α, β and r₀, adapt them as the search progresses, for example by lowering evaporation or raising r₀ over time. Pick an Adaptation option in the colony lab to see the effect.

Chapter 10 describes more strategies, such as switching which ant deposits or tightening the MMAS limits.

Part 8 · Applications

Where ants go to work

ACO is used for routing, scheduling, assignment and set problems. Open a listing to try one.

Routing

Shortest routes on road networks.

Listing C.17

Reverse osmosis pump

Maximize a desalination pump’s power.

Listing C.18

Supply and demand

Planning with the ACO-based MIDACO solver.

Listing C.19

Chapter 10 also shows ACS planning robot paths on a MAKLINK graph and ants solving quadratic assignment.

Part 9 · Code

Python in Google Colab

Open the book’s notebooks in Colab, or the companion notebook with the from-scratch code below.

Notebooks

All examplesACO Lab companion notebookThe from-scratch code below, ready to run Open TSPListing 10.1 ACO20 US cities, from scratch and with ACOpy RoutingListing C.17Routing with ACO Continuous designListing C.18Reverse osmosis pump power Mixed integerListing C.19Supply and demand with MIDACO Same chapter · beesListing 10.2Artificial bee colony on the Rosenbrock function

From-scratch implementations

Open all three in Colab

# Simple ACO (SACO) on the shortest path problem of Chapter 10 (Figures 10.7 to 10.10)
import numpy as np

# edge lengths of the book's graph: source node 1, goal node 5
edges = {(1, 2): 4, (1, 3): 3, (2, 3): 5, (2, 4): 4, (3, 4): 2, (2, 5): 1, (4, 5): 6}
D = {}
for (a, b), d in edges.items():
    D[a, b] = D[b, a] = d
nbrs = {n: sorted(m for (k, m) in D if k == n) for n in range(1, 6)}


def transition(i, tau, visited, alpha=1.0, beta=1.0):
    """Equation 10.6: p_ij = tau_ij^alpha * eta_ij^beta / sum over feasible j, eta = 1/d."""
    cand = [j for j in nbrs[i] if j not in visited]
    w = np.array([tau[i, j] ** alpha * (1 / D[i, j]) ** beta for j in cand])
    return cand, w / w.sum()


tau = {e: 0.5 for e in D}
print("from node 1:", dict(zip(*transition(1, tau, {1}))))        # p12 = 0.43, p13 = 0.57
print("from node 3:", dict(zip(*transition(3, tau, {1, 3}))))     # p32 = 0.29, p34 = 0.71
print("from node 4:", dict(zip(*transition(4, tau, {1, 3, 4}))))  # p42 = 0.60, p45 = 0.40


def saco(ants=5, iterations=5, tau0=0.5, rho=0.7, alpha=1.0, beta=1.0, Q=1.0, seed=0):
    rng = np.random.default_rng(seed)
    tau = {e: tau0 for e in D}
    best_path, best_len = None, np.inf
    for it in range(iterations):
        paths = []
        for k in range(ants):
            path = [1]
            while path[-1] != 5:                       # construct a path to the goal node
                cand, p = transition(path[-1], tau, set(path), alpha, beta)
                if not cand:                           # dead end: start again
                    path = [1]
                    continue
                path.append(cand[rng.choice(len(cand), p=p)])
            paths.append(path)
        for e in tau:                                  # evaporation (eq. 10.2)
            tau[e] *= (1 - rho)
        for path in paths:                             # online delayed update (eq. 10.4)
            L = sum(D[a, b] for a, b in zip(path, path[1:]))
            for a, b in zip(path, path[1:]):
                tau[a, b] += Q / L
                tau[b, a] += Q / L
            if L < best_len:
                best_path, best_len = path, L
        print(f"iteration {it + 1}: paths {[''.join(map(str, p)) for p in paths]}")
    return best_path, best_len, tau


best_path, best_len, tau = saco(seed=1)
print("best path:", " -> ".join(map(str, best_path)), "length", best_len)
print("pheromone on 1-2-5:", round(tau[1, 2], 3), round(tau[2, 5], 3),
      " on 1-3-4-5:", round(tau[1, 3], 3), round(tau[3, 4], 3), round(tau[4, 5], 3))

# Open TSP with ACO variants (Chapter 10, Section 10.3.5): AS, ACS and MMAS
# 20 major US cities, start at New York City, no return to the home city.
import numpy as np
import matplotlib.pyplot as plt

cities = {
    "New York City": (40.72, -74.00), "Philadelphia": (39.95, -75.17),
    "Baltimore": (39.28, -76.62), "Charlotte": (35.23, -80.85),
    "Memphis": (35.12, -89.97), "Jacksonville": (30.32, -81.70),
    "Houston": (29.77, -95.38), "Austin": (30.27, -97.77),
    "San Antonio": (29.53, -98.47), "Fort Worth": (32.75, -97.33),
    "Dallas": (32.78, -96.80), "San Diego": (32.78, -117.15),
    "Los Angeles": (34.05, -118.25), "San Jose": (37.30, -121.87),
    "San Francisco": (37.78, -122.42), "Indianapolis": (39.78, -86.15),
    "Phoenix": (33.45, -112.07), "Columbus": (39.98, -82.98),
    "Chicago": (41.88, -87.63), "Detroit": (42.33, -83.05),
}
names = list(cities)
lat, lon = np.radians(np.array(list(cities.values()))).T
a = (np.sin((lat[:, None] - lat) / 2) ** 2
     + np.cos(lat[:, None]) * np.cos(lat) * np.sin((lon[:, None] - lon) / 2) ** 2)
D = 2 * 6371.0088 * np.arcsin(np.sqrt(a))          # haversine distances in km
n = len(names)
eta = 1 / (D + np.eye(n))                           # desirability 1/d (diagonal unused)
length = lambda p: D[p[:-1], p[1:]].sum()           # open path: no return to the start


def run_aco(variant="AS", ants=30, iterations=100, alpha=1.0, beta=0.9, rho=0.5, Q=100,
            q0=0.9, xi=0.1, seed=0):
    rng = np.random.default_rng(seed)
    tau0 = 1.0 if variant == "AS" else 1 / (n * 8000)
    tau = np.full((n, n), tau0)
    if variant == "MMAS":
        tau_max = 1 / (rho * 8000); tau[:] = tau_max
    best_p, best_L, history = None, np.inf, []
    for it in range(iterations):
        paths = []
        for k in range(ants):
            p, free = [0], np.ones(n, bool); free[0] = False
            while free.any():
                i, cand = p[-1], np.flatnonzero(free)
                w = tau[i, cand] ** alpha * eta[i, cand] ** beta
                if variant == "ACS" and rng.random() <= q0:      # exploitation (eq. 10.10)
                    j = cand[np.argmax(w)]
                else:                                            # biased exploration (eq. 10.6)
                    j = rng.choice(cand, p=w / w.sum())
                if variant == "ACS":                             # ACS local update
                    tau[i, j] = tau[j, i] = (1 - xi) * tau[i, j] + xi * tau0
                p.append(j); free[j] = False
            paths.append(np.array(p))
        Ls = np.array([length(p) for p in paths])
        b = Ls.argmin()
        if Ls[b] < best_L:
            best_p, best_L = paths[b], Ls[b]
        if variant == "AS":                                      # every ant deposits Q / L
            tau *= (1 - rho)
            for p, L in zip(paths, Ls):
                tau[p[:-1], p[1:]] += Q / L; tau[p[1:], p[:-1]] += Q / L
        elif variant == "ACS":                                   # only the global-best ant
            e = (best_p[:-1], best_p[1:])
            tau[e] = (1 - rho) * tau[e] + rho / best_L
            tau[e[::-1]] = tau[e]
        else:                                                    # MMAS: iteration-best, bounded
            tau *= (1 - rho)
            p = paths[b]
            tau[p[:-1], p[1:]] += 1 / Ls[b]; tau[p[1:], p[:-1]] += 1 / Ls[b]
            tau_max = 1 / (rho * best_L); tau_min = tau_max / (2 * n)
            np.clip(tau, tau_min, tau_max, out=tau)
        history.append(best_L)
    return best_p, best_L, history


for variant in ["AS", "ACS", "MMAS"]:
    p, L, hist = run_aco(variant, seed=1)
    print(f"{variant:5s} {L:9.1f} km  " + " -> ".join(names[i] for i in p))
    plt.plot(hist, label=variant)
plt.axhline(7937.115, ls="--", c="gray", label="book's run (7,937 km)")
plt.xlabel("iteration"); plt.ylabel("best open-route length (km)"); plt.legend(); plt.show()

# ACO for continuous optimization: minimize f(x) = x^2 - 2x - 11 on [0, 3]
# The range is discretized into 7 values; each value is a path from home to food.
import numpy as np

f = lambda x: x**2 - 2 * x - 11
xs = np.arange(0, 3.01, 0.5)                    # x11 ... x17 = 0.0, 0.5, ..., 3.0


def aco_continuous(randoms=None, ants=4, iterations=3, rho=0.5, zeta=2.0, seed=0):
    rng = np.random.default_rng(seed)
    tau = np.ones(len(xs))                      # equal pheromone on every path
    for it in range(iterations):
        p = tau / tau.sum()                     # selection probabilities
        cum = np.cumsum(p)
        r = randoms[it] if randoms and it < len(randoms) else rng.random(ants)
        chosen = np.searchsorted(cum, r)        # roulette wheel
        fx = f(xs[chosen])
        best, worst = fx.min(), fx.max()
        n_best = np.sum(fx == best)
        tau *= (1 - rho)                        # evaporation
        tau[chosen[fx == best][0]] += n_best * zeta * best / worst   # best ants deposit
        print(f"iteration {it + 1}: x = {xs[chosen]}, f = {fx}, tau = {np.round(tau, 4)}")
    return xs[np.argmax(tau)]


# the worked example's random numbers for iterations 1 and 2
x_best = aco_continuous(randoms=[[0.3122, 0.8701, 0.4729, 0.6190], [0.3688, 0.8577, 0.0776, 0.5791]])
print("most reinforced path: x =", x_best, " f =", f(x_best))   # x = 1.0, f = -12

Run each cell in Colab, or paste a tab’s code into any notebook.

Part 10 · Summary

What to remember

Stigmergy

Pheromone is a collective memory, reinforced by success and erased by evaporation.

Construction plus learning

Each ant builds a solution with equation 10.6, guided by the colony’s trails.

Exploration vs. exploitation

ρ, α, β and r₀ set the balance; MMAS bounds trails to avoid stagnation.

Strengths

ACO shines on combinatorial problems, especially with local search.

References: P.-P. Grassé, 1959 (stigmergy). J.-L. Deneubourg, S. Aron, S. Goss and J. M. Pasteels, “The self-organizing exploratory pattern of the Argentine ant,” 1990. M. Dorigo, V. Maniezzo and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” 1996. M. Dorigo and L. M. Gambardella, “Ant colony system,” 1997. T. Stützle and H. H. Hoos, “MAX-MIN ant system,” 2000. S. S. Rao, Engineering Optimization: Theory and Practice, 2009. A. Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning, 2024, Chapter 10.

Part 11 · Quiz

Check your understanding

Two quick questions on Chapter 10. Pick an answer to check it.

Q1. In the double-bridge experiment with unequal branches, why does the colony end up on the shorter branch?

Q2. What happens to an ACO colony if the evaporation rate ρ is set to 0?

For more exercises with full solutions, see Appendix C, “Exercises and solutions,” in Optimization Algorithms. The coding solutions are also on GitHub (Chapter 10).