Ant Colony Optimization

in reviewThis lesson is complete and being validated before release - details may still change.

Ant colony optimization

Loading interactive demo…

Cities on a plane, every pair joined by an edge that carries a pheromone trail; an edge is drawn as wide as its trail, on the scale of the strongest trail the run reaches. Each iteration every ant walks a closed tour, choosing its next city by a roll weighted by trail to the alpha times closeness to the beta. Then every trail evaporates by rho and each ant lays Q over its tour's length on the edges it walked, so short tours leave more. Q is fixed at 10 and the starting trail at 1.Take the tour, or press and explore. Legend:

The panel beside the stage is the real AntSystem class from the published library executing in your browser, with the current line highlighted.

Edges, widened by their trail; cities as points. An edge whose trail has faded below 15 percent of the strongest drops to the grid tone.
At a choice: the followed ant's path so far, and dashed edges to the unvisited cities labelled with its chances.
The tour an ant just finished.
The shortest tour so far, solid; the run's final best, faint.
The followed ant's city, and the ant the step is about on the strip.

best is the shortest tour any ant has walked, roundthe shortest of the iteration under way, strongest the edge with the most pheromone, evaporated the share every trail loses each iteration, iteration the round under way. The ant strip shows each ant's tour length this round, shaded by closeness to the best, with a bar under the followed ant; tap an ant to trace its choices. The lower strip plots the best length after each iteration as a share of the first.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A tour, one gamble at a time. An ant starts at a random city and must visit every other city once before it returns. Standing at city $i$ with a set of unvisited cities, it picks the next one, $j$ , with probability

p_{ij} = \frac{\tau_{ij}^{\alpha}\,\eta_{ij}^{\beta}}{\sum_{l \in \text{allowed}} \tau_{il}^{\alpha}\,\eta_{il}^{\beta}}, \qquad \eta_{ij} = \frac{1}{d_{ij}}

Two things attract: the trail $\tau_{ij}$ , the pheromone on the edge, and the closeness $\eta_{ij}$ , one over the distance. The exponents are the knobs. With $\alpha = 0$ the trails do not count and every ant is a noisy nearest-neighbour walk; with $\beta = 0$ distance does not count and the colony has only its memory. The dashed edges at a choose step are these probabilities, scaled to sum to one, and the roll in the narration is the single random number that picks among them. The stage traces one ant's choices; the others roll the same way off screen, and which ant is followed never changes the draws, so the run is the same whichever ant you tap.

When every ant is home, the trails change. First every trail evaporates:

\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij}

then each ant $k$ lays $Q / L_k$ on every edge of its tour, where $L_k$ is the tour's length. A short tour lays more on each of its edges than a long one, and an edge that several short tours share gains several deposits, so the colony's belief concentrates on edges that good tours have in common. Evaporation is what keeps early luck from being permanent: an edge no ant walks again is multiplied by $1 - \rho$ every iteration, halved at the default $\rho = 0.5$ , and fades toward nothing. Without it the first round's deposits would stay forever and the colony could never change its mind.

A steady state to read off. If every one of $m$ ants walked the same edge every round, its trail would settle where evaporation balances the deposits: $(1 - \rho)\tau + mQ/L = \tau$ , so $\tau = mQ/(\rho L)$ . At the defaults, four ants and tours near 24, that is about 3.3. The strongest readout climbs toward it as the colony agrees, and the edge widths on the plane are drawn on the scale of the strongest trail the run reaches, so the picture starts as a flat web and sharpens into a loop.

Exploration and exploitation. Raise $\alpha$ or lower $\rho$ and the colony commits sooner: the strip of best lengths drops early and then flattens, often above the best this seed allows, because every ant is walking the same loop and nobody tries the alternatives. Lower $\alpha$ or raise $\rho$ and the ants keep gambling; the best keeps falling, slowly. That is the same trade as the annealing schedule in the previous lesson, with the colony's memory playing the part of the temperature. Ant Colony System and MAX-MIN Ant System, in the history panel, are two ways of tuning the trade: let only the best ant deposit so the memory is sharper, and bound the trails so no edge can become certain.

Cost. Each ant's tour is $n$ choices over up to $n$ candidates, so an iteration of $m$ ants costs $O(m n^2)$ and the run $O(I\,m\,n^2)$ , plus $O(n^2)$ for the pheromone matrix. The best readout is the minimum over every tour the run has produced, so the strip, the best after each iteration, never rises. Nothing guarantees it reaches the optimum: with 8 cities the exhaustive answer is checkable by hand, and a seed where the colony settles on a crossing tour is easy to find.

No free lunch. Wolpert and Macready showed in 1997 that averaged over all possible objectives no search method beats another, so a colony of ants is good only relative to a family of problems; its family is routing, where a solution is a sequence of edges and good solutions share edges, which is exactly what a trail can remember.

Where this goes next. The whale optimization lesson keeps the population but swaps the trail for a pull toward the best member, and asks what a new metaphor adds when the operators underneath it are old.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Two static rules, one loop. chances and updated are the two formulas as pure functions, so the tests pin them on the four corners of a rectangle; run is the loop that calls them. The update is split into evaporated and deposited so the trace can show the matrix between the two halves.
The roll is always drawn. Each choice draws one rng.next() and walks the cumulative chances until the roll falls inside a slot; the last allowed city takes any rounding remainder. Every ant's start is rng.index(n). Nothing about tracing touches the stream, so traced changes which ant's choices are emitted and nothing else, which is what lets the strip's tap switch ants without changing the run.
The matrix is symmetric. A deposit lands on both [a][b] and [b][a], the diagonal stays zero, and strongest scans only above the diagonal, lowest i then j on a tie, so the readout names one edge.
Rounded payloads, raw results. Every number in the trace is rounded to three decimals, matrices included, so the stage can compare and render them without float noise; the returned result keeps the raw values. An improve fires only when the best falls by more than 1e-9, so the same tour walked from another start city is not an improvement.
The caps are the library's. ACO_MAX_ANTS and ACO_MAX_ITERATIONS bound the colony at 8 and 15, and TourProblem allows 3 to 10 cities, so the longest trace, 10 cities by 8 ants by 15 iterations, stays near 300 events.

Real ants find short paths without a map: each lays pheromone as it walks, the ants on a shorter route get back sooner and walk it more often, so its trail builds while the others evaporate. Marco Dorigo turned that loop into Ant System in his 1992 thesis: artificial ants build a tour city by city, each step a roll weighted by trail and closeness, and when every ant is home the trails fade and each ant lays a deposit in inverse proportion to its tour's length. Later variants let only the best ant deposit and bounded the trails, and the ants went on to route packets and vehicles.

1989Goss, Aron, Deneubourg and Pasteels - Their work on the collective behaviour of Argentine ants, colonies that settle on a route through the trails their foragers lay, gives the idea of ant colony optimization.source
1992Marco Dorigo - Proposes Ant System, the first ant colony optimization algorithm, in his PhD thesis at the Politecnico di Milano, 'Optimization, Learning and Natural Algorithms'.source
1996Dorigo, Maniezzo and Colorni - 'Ant System: Optimization by a Colony of Cooperating Agents' in IEEE Transactions on Systems, Man, and Cybernetics, Part B: the journal paper on Ant System, the colony this stage runs.source
1997Marco Dorigo and Luca Gambardella - 'Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem' in IEEE Transactions on Evolutionary Computation: choices biased toward exploitation, a local pheromone update as each ant walks, and only the best ant updating the trails at the end of an iteration.source
2000Thomas Stützle and Holger Hoos - MAX-MIN Ant System in Future Generation Computer Systems: the trail on every edge is kept inside a maximum and a minimum, every edge starts at the maximum to force exploration, and only the global best or the iteration's best tour deposits.source

Used today

Vehicle routing - Fleets with capacities, time windows, pickups and deliveries: a tour is a route and the pheromone sits on the legs between stops, so good legs are reused across many routes.
Network routing - AntNet controls a communications network with artificial ants that lay stigmergic trails as they travel, so routing follows what the ants have recently found to work.
Scheduling - Job-shop and open-shop schedules, where a tour is an order of jobs on the machines and the trail says which job should follow which.

Did you know

A paper on the ants, 'Distributed Optimization by Ant Colonies', appeared at the first European conference on artificial life in Paris in 1991, the year before Dorigo's thesis was published.source
The word for what the ants do, stigmergy, is older than the algorithm: Pierre-Paul Grassé invented the theory in 1959 to explain how termites build their nests.source
The ants were put to work on telephone and data traffic: AntNet, in the Journal of Artificial Intelligence Research in 1998, controls a communications network by distributed stigmergy, as its title says.source
Marco Dorigo went from artificial ants to real robots: he coordinated Swarm-bots and Swarmanoid, two European Commission projects on swarms of self-assembling robots, and co-directs IRIDIA, the artificial intelligence lab of the Université libre de Bruxelles.source

cities8

ants4

iterations10

alpha1.0

beta2.0

rho0.5

best: 24.1
round: 24.1
strongest: c1-c3 at 2.76
evaporated: 50%
iteration: 10 of 10

ant-system.ts

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";import type { TourProblem } from "./tour-problem";/** The most ants in one colony, so a round of tours stays traceable. */export const ACO_MAX_ANTS = 8;/** The most iterations one run takes. */export const ACO_MAX_ITERATIONS = 15;export interface AntSystemOptions {  /** The cities to tour. */  problem: TourProblem;  /** Seeds every start city and every roll, so a run repeats. */  seed: number;  /** Ants per iteration, 1 to ACO_MAX_ANTS. Default 4. */  ants?: number;  /** Iterations, 1 to ACO_MAX_ITERATIONS. Default 10. */  iterations?: number;  /** The weight of the trail, >= 0. Default 1. */  alpha?: number;  /** The weight of closeness, >= 0. Default 2. */  beta?: number;  /** The share of every trail that evaporates each iteration, in (0, 1]. Default 0.5. */  rho?: number;  /** The pheromone one ant spreads over its tour, divided by the tour's length, > 0. Default 10. */  q?: number;  /** The starting pheromone on every edge, > 0. Default 1. */  tau0?: number;  /** The ant whose choices are traced, 0 to ants - 1. Default 0. */  traced?: number;}export interface AntSystemResult {  /** The shortest tour any ant walked, as a city order. */  readonly best: readonly number[];  /** Its length. */  readonly length: number;  /** The pheromone matrix after the last deposit, symmetric with a zero diagonal. */  readonly pheromone: readonly (readonly number[])[];  /** The global best length after each iteration. */  readonly history: readonly number[];  /** How many iterations ran. */  readonly iterations: number;}/** Payload numbers are shown to three decimals; the result keeps the raw values. */const round = (value: number): number => Math.round(value * 1000) / 1000;/** A fall in the best length smaller than this is float noise, the same tour walked from another city, not an improvement. */const ACO_IMPROVE_TOLERANCE = 1e-9;const roundMatrix = (matrix: readonly (readonly number[])[]): number[][] => matrix.map((row) => row.map(round));/** * Ant System for the travelling salesman, as Dorigo, Maniezzo and * Colorni described it in 1996. Every edge carries a pheromone trail, * `tau0` to begin with. Each iteration every ant starts at a random city * and walks to an unvisited city with chance proportional to * `tau^alpha * (1 / d)^beta`: strong trails and short hops both attract. * When all the ants are home, every trail evaporates by the share `rho` * and each ant lays `q / length` on every edge of its tour, so the edges * of short tours gain more than the edges of long ones and the colony * drifts towards the best tours it has seen. Alpha 0 ignores the trails * (a greedy random walk), beta 0 ignores distance (the trails alone). * * The random draws are the same whether or not an ant is traced, so * `traced` changes the trace and nothing else. * * Time: O(I m n^2) for I iterations, m ants and n cities. Space: O(n^2) * for the pheromone matrix. */export class AntSystem {  readonly problem: TourProblem;  readonly seed: number;  readonly ants: number;  readonly iterations: number;  readonly alpha: number;  readonly beta: number;  readonly rho: number;  readonly q: number;  readonly tau0: number;  readonly traced: number;  constructor(options: AntSystemOptions, private readonly tracer?: Tracer) {    const { problem, seed, ants = 4, iterations = 10, alpha = 1, beta = 2, rho = 0.5, q = 10, tau0 = 1, traced = 0 } = options;    if (!Number.isInteger(ants) || ants < 1 || ants > ACO_MAX_ANTS) throw new RangeError(`ants must be a whole number in [1, ${ACO_MAX_ANTS}]`);    if (!Number.isInteger(iterations) || iterations < 1 || iterations > ACO_MAX_ITERATIONS) throw new RangeError(`iterations must be a whole number in [1, ${ACO_MAX_ITERATIONS}]`);    if (!(alpha >= 0)) throw new RangeError(`alpha ${alpha} must be at least 0`);    if (!(beta >= 0)) throw new RangeError(`beta ${beta} must be at least 0`);    if (!(rho > 0 && rho <= 1)) throw new RangeError(`rho ${rho} must lie in (0, 1]`);    if (!(q > 0)) throw new RangeError(`q ${q} must be positive`);    if (!(tau0 > 0)) throw new RangeError(`tau0 ${tau0} must be positive`);    if (!Number.isInteger(traced) || traced < 0 || traced >= ants) throw new RangeError(`traced must be a whole number in [0, ${ants})`);    this.problem = problem;    this.seed = seed;    this.ants = ants;    this.iterations = iterations;    this.alpha = alpha;    this.beta = beta;    this.rho = rho;    this.q = q;    this.tau0 = tau0;    this.traced = traced;  }  /**   * The chance of each allowed city as the next stop from `from`:   * `tau^alpha * (1 / d)^beta` over the allowed cities, scaled to sum to   * one. Parallel to `allowed`.   */  static chances(    from: number,    allowed: readonly number[],    tau: readonly (readonly number[])[],    trail: readonly (readonly number[])[],    distance: (a: number, b: number) => number,    alpha: number,    beta: number,  ): number[] {    const weights = allowed.map((city) => Math.pow(tau[from]![city]!, alpha) * Math.pow(1 / distance(from, city), beta));    const weights = allowed.map((city) => Math.pow(trail[from]![city]!, alpha) * Math.pow(1 / distance(from, city), beta));    const total = weights.reduce((sum, weight) => sum + weight, 0);    // Only when every weight underflows: then no city is preferred.    if (!(total > 0)) return allowed.map(() => 1 / allowed.length);    return weights.map((weight) => weight / total);  }  /**   * The pheromone matrix after one iteration's update: every entry   * evaporates to `(1 - rho) tau`, then every ant lays `q / length` on   * both directions of every edge of its tour. The input is left alone.   */  static updated(    tau: readonly (readonly number[])[],    trail: readonly (readonly number[])[],    tours: readonly (readonly number[])[],    lengths: readonly number[],    rho: number,    q: number,  ): number[][] {    return AntSystem.deposited(AntSystem.evaporated(tau, rho), tours, lengths, q);    return AntSystem.deposited(AntSystem.evaporated(trail, rho), tours, lengths, q);  }  /** A copy of the matrix with `q / length` laid on both directions of every edge of every tour. */  private static deposited(    tau: readonly (readonly number[])[],    trail: readonly (readonly number[])[],    tours: readonly (readonly number[])[],    lengths: readonly number[],    q: number,  ): number[][] {    const next = tau.map((row) => row.slice());    const next = trail.map((row) => row.slice());    tours.forEach((tour, ant) => {      const deposit = q / lengths[ant]!;      for (let i = 0; i < tour.length; i++) {        const a = tour[i]!;        const b = tour[(i + 1) % tour.length]!;        next[a]![b] = next[a]![b]! + deposit;        next[b]![a] = next[b]![a]! + deposit;      }    });    return next;  }  /** Runs the colony from scratch and reports the best tour it found. */  run(): AntSystemResult {    const n = this.problem.size;    const rng = new Mulberry32(this.seed);    const rolls = new Mulberry32(this.seed);    let tau: number[][] = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : this.tau0)));    let trail: number[][] = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : this.tau0)));    let best: number[] = [];    let bestLength = Infinity;    const history: number[] = [];    // ▸ every edge starts with the same trail, tau0, and no tour is known    this.tracer?.emit("init", { ants: this.ants, cities: n, pheromone: roundMatrix(tau) });    this.tracer?.emit("init", { ants: this.ants, cities: n, pheromone: roundMatrix(trail) });    for (let iteration = 1; iteration <= this.iterations; iteration++) {      const tours: number[][] = [];      const lengths: number[] = [];      let roundBest = -1;      let bestThisRound = -1;      for (let ant = 0; ant < this.ants; ant++) {        const order = this.walk(ant, iteration, tau, rng);        const order = this.walk(ant, iteration, trail, rolls);        const length = this.problem.length(order);        tours.push(order);        lengths.push(length);        if (roundBest < 0 || length < lengths[roundBest]!) roundBest = ant;        if (bestThisRound < 0 || length < lengths[bestThisRound]!) bestThisRound = ant;        // ▸ an ant is home: its closed tour is measured        this.tracer?.emit("tour", { ant, iteration, length: round(length), order: order.slice() });      }      if (lengths[roundBest]! < bestLength - ACO_IMPROVE_TOLERANCE) {      if (lengths[bestThisRound]! < bestLength - ACO_IMPROVE_TOLERANCE) {        bestLength = lengths[roundBest]!;        bestLength = lengths[bestThisRound]!;        best = tours[roundBest]!.slice();        best = tours[bestThisRound]!.slice();        // ▸ the shortest tour yet: remember it        this.tracer?.emit("improve", { ant: roundBest, iteration, length: round(bestLength), order: best.slice() });        this.tracer?.emit("improve", { ant: bestThisRound, iteration, length: round(bestLength), order: best.slice() });      }      history.push(bestLength);      tau = AntSystem.evaporated(tau, this.rho);      trail = AntSystem.evaporated(trail, this.rho);      // ▸ every trail loses the share rho, so old choices fade      this.tracer?.emit("evaporate", { iteration, pheromone: roundMatrix(tau), rho: this.rho });      this.tracer?.emit("evaporate", { iteration, pheromone: roundMatrix(trail), rho: this.rho });      tau = AntSystem.deposited(tau, tours, lengths, this.q);      trail = AntSystem.deposited(trail, tours, lengths, this.q);      // ▸ each ant lays q over its length on every edge it walked      this.tracer?.emit("deposit", { iteration, pheromone: roundMatrix(tau), strongest: AntSystem.strongest(tau) });      this.tracer?.emit("deposit", { iteration, pheromone: roundMatrix(trail), strongest: AntSystem.strongest(trail) });    }    // ▸ the shortest tour any ant walked, after every iteration    this.tracer?.emit("verdict", { iterations: this.iterations, length: round(bestLength), order: best.slice() });    return { best, length: bestLength, pheromone: tau, history, iterations: this.iterations };    return { best, length: bestLength, pheromone: trail, history, iterations: this.iterations };  }  /** One ant's closed tour: a random start, then a roll per step through the cumulative chances. */  private walk(ant: number, iteration: number, tau: readonly (readonly number[])[], rng: Mulberry32): number[] {  private walk(ant: number, iteration: number, trail: readonly (readonly number[])[], rolls: Mulberry32): number[] {    const n = this.problem.size;    const order = [rng.index(n)];    const order = [rolls.index(n)];    const visited = new Set<number>(order);    while (order.length < n) {      const at = order[order.length - 1]!;      const allowed: number[] = [];      for (let city = 0; city < n; city++) if (!visited.has(city)) allowed.push(city);      const chances = AntSystem.chances(at, allowed, tau, (a, b) => this.problem.distance(a, b), this.alpha, this.beta);      const chances = AntSystem.chances(at, allowed, trail, (a, b) => this.problem.distance(a, b), this.alpha, this.beta);      const roll = rng.next();      const roll = rolls.next();      // The last allowed city takes any rounding remainder.      let next = allowed[allowed.length - 1]!;      let cumulative = 0;      for (let k = 0; k < allowed.length; k++) {        cumulative += chances[k]!;        if (roll < cumulative) {          next = allowed[k]!;          break;        }      }      if (ant === this.traced) {        // ▸ the next city is a roll weighted by trail to the alpha and closeness to the beta        this.tracer?.emit("choose", { allowed: allowed.slice(), ant, at, chances: chances.map(round), iteration, next, roll: round(roll) });      }      order.push(next);      visited.add(next);    }    return order;  }  /** A copy of the matrix with every entry scaled by `1 - rho`. */  private static evaporated(tau: readonly (readonly number[])[], rho: number): number[][] {  private static evaporated(trail: readonly (readonly number[])[], rho: number): number[][] {    return tau.map((row) => row.map((value) => value * (1 - rho)));    return trail.map((row) => row.map((value) => value * (1 - rho)));  }  /** The largest entry above the diagonal as `[i, j, tau]`, the lowest i then j on a tie. */  private static strongest(tau: readonly (readonly number[])[]): [number, number, number] {  private static strongest(trail: readonly (readonly number[])[]): [number, number, number] {    let edge: [number, number, number] = [0, 1, tau[0]![1]!];    let edge: [number, number, number] = [0, 1, trail[0]![1]!];    for (let i = 0; i < tau.length; i++) {    for (let i = 0; i < trail.length; i++) {      for (let j = i + 1; j < tau.length; j++) {      for (let j = i + 1; j < trail.length; j++) {        if (tau[i]![j]! > edge[2]) edge = [i, j, tau[i]![j]!];        if (trail[i]![j]! > edge[2]) edge = [i, j, trail[i]![j]!];      }    }    return [edge[0], edge[1], round(edge[2])];  }}

iterations =: 10
order =: c4 c3 c1 c2 c0 c7 c6 c5
length =: 24.1
strongest =: c1-c3 at 2.76

10 iterations: the best tour c4 c3 c1 c2 c0 c7 c6 c5 is 24.1 long, and the strongest trail is c1-c3 at 2.76.

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";import type { TourProblem } from "./tour-problem";/** The most ants in one colony, so a round of tours stays traceable. */export const ACO_MAX_ANTS = 8;/** The most iterations one run takes. */export const ACO_MAX_ITERATIONS = 15;export interface AntSystemOptions { /** The cities to tour. */ problem: TourProblem; /** Seeds every start city and every roll, so a run repeats. */ seed: number; /** Ants per iteration, 1 to ACO_MAX_ANTS. Default 4. */ ants?: number; /** Iterations, 1 to ACO_MAX_ITERATIONS. Default 10. */ iterations?: number; /** The weight of the trail, >= 0. Default 1. */ alpha?: number; /** The weight of closeness, >= 0. Default 2. */ beta?: number; /** The share of every trail that evaporates each iteration, in (0, 1]. Default 0.5. */ rho?: number; /** The pheromone one ant spreads over its tour, divided by the tour's length, > 0. Default 10. */ q?: number; /** The starting pheromone on every edge, > 0. Default 1. */ tau0?: number; /** The ant whose choices are traced, 0 to ants - 1. Default 0. */ traced?: number;}export interface AntSystemResult { /** The shortest tour any ant walked, as a city order. */ readonly best: readonly number[]; /** Its length. */ readonly length: number; /** The pheromone matrix after the last deposit, symmetric with a zero diagonal. */ readonly pheromone: readonly (readonly number[])[]; /** The global best length after each iteration. */ readonly history: readonly number[]; /** How many iterations ran. */ readonly iterations: number;}/** Payload numbers are shown to three decimals; the result keeps the raw values. */const round = (value: number): number => Math.round(value * 1000) / 1000;/** A fall in the best length smaller than this is float noise, the same tour walked from another city, not an improvement. */const ACO_IMPROVE_TOLERANCE = 1e-9;const roundMatrix = (matrix: readonly (readonly number[])[]): number[][] => matrix.map((row) => row.map(round));/** * Ant System for the travelling salesman, as Dorigo, Maniezzo and * Colorni described it in 1996. Every edge carries a pheromone trail, * `tau0` to begin with. Each iteration every ant starts at a random city * and walks to an unvisited city with chance proportional to * `tau^alpha * (1 / d)^beta`: strong trails and short hops both attract. * When all the ants are home, every trail evaporates by the share `rho` * and each ant lays `q / length` on every edge of its tour, so the edges * of short tours gain more than the edges of long ones and the colony * drifts towards the best tours it has seen. Alpha 0 ignores the trails * (a greedy random walk), beta 0 ignores distance (the trails alone). * * The random draws are the same whether or not an ant is traced, so * `traced` changes the trace and nothing else. * * Time: O(I m n^2) for I iterations, m ants and n cities. Space: O(n^2) * for the pheromone matrix. */export class AntSystem { readonly problem: TourProblem; readonly seed: number; readonly ants: number; readonly iterations: number; readonly alpha: number; readonly beta: number; readonly rho: number; readonly q: number; readonly tau0: number; readonly traced: number; constructor(options: AntSystemOptions, private readonly tracer?: Tracer) { const { problem, seed, ants = 4, iterations = 10, alpha = 1, beta = 2, rho = 0.5, q = 10, tau0 = 1, traced = 0 } = options; if (!Number.isInteger(ants) || ants < 1 || ants > ACO_MAX_ANTS) throw new RangeError(`ants must be a whole number in [1, ${ACO_MAX_ANTS}]`); if (!Number.isInteger(iterations) || iterations < 1 || iterations > ACO_MAX_ITERATIONS) throw new RangeError(`iterations must be a whole number in [1, ${ACO_MAX_ITERATIONS}]`); if (!(alpha >= 0)) throw new RangeError(`alpha ${alpha} must be at least 0`); if (!(beta >= 0)) throw new RangeError(`beta ${beta} must be at least 0`); if (!(rho > 0 && rho <= 1)) throw new RangeError(`rho ${rho} must lie in (0, 1]`); if (!(q > 0)) throw new RangeError(`q ${q} must be positive`); if (!(tau0 > 0)) throw new RangeError(`tau0 ${tau0} must be positive`); if (!Number.isInteger(traced) || traced < 0 || traced >= ants) throw new RangeError(`traced must be a whole number in [0, ${ants})`); this.problem = problem; this.seed = seed; this.ants = ants; this.iterations = iterations; this.alpha = alpha; this.beta = beta; this.rho = rho; this.q = q; this.tau0 = tau0; this.traced = traced; } /** * The chance of each allowed city as the next stop from `from`: * `tau^alpha * (1 / d)^beta` over the allowed cities, scaled to sum to * one. Parallel to `allowed`. */ static chances( from: number, allowed: readonly number[], tau: readonly (readonly number[])[], trail: readonly (readonly number[])[], distance: (a: number, b: number) => number, alpha: number, beta: number, ): number[] { const weights = allowed.map((city) => Math.pow(tau[from]![city]!, alpha) * Math.pow(1 / distance(from, city), beta)); const weights = allowed.map((city) => Math.pow(trail[from]![city]!, alpha) * Math.pow(1 / distance(from, city), beta)); const total = weights.reduce((sum, weight) => sum + weight, 0); // Only when every weight underflows: then no city is preferred. if (!(total > 0)) return allowed.map(() => 1 / allowed.length); return weights.map((weight) => weight / total); } /** * The pheromone matrix after one iteration's update: every entry * evaporates to `(1 - rho) tau`, then every ant lays `q / length` on * both directions of every edge of its tour. The input is left alone. */ static updated( tau: readonly (readonly number[])[], trail: readonly (readonly number[])[], tours: readonly (readonly number[])[], lengths: readonly number[], rho: number, q: number, ): number[][] { return AntSystem.deposited(AntSystem.evaporated(tau, rho), tours, lengths, q); return AntSystem.deposited(AntSystem.evaporated(trail, rho), tours, lengths, q); } /** A copy of the matrix with `q / length` laid on both directions of every edge of every tour. */ private static deposited( tau: readonly (readonly number[])[], trail: readonly (readonly number[])[], tours: readonly (readonly number[])[], lengths: readonly number[], q: number, ): number[][] { const next = tau.map((row) => row.slice()); const next = trail.map((row) => row.slice()); tours.forEach((tour, ant) => { const deposit = q / lengths[ant]!; for (let i = 0; i < tour.length; i++) { const a = tour[i]!; const b = tour[(i + 1) % tour.length]!; next[a]![b] = next[a]![b]! + deposit; next[b]![a] = next[b]![a]! + deposit; } }); return next; } /** Runs the colony from scratch and reports the best tour it found. */ run(): AntSystemResult { const n = this.problem.size; const rng = new Mulberry32(this.seed); const rolls = new Mulberry32(this.seed); let tau: number[][] = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : this.tau0))); let trail: number[][] = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : this.tau0))); let best: number[] = []; let bestLength = Infinity; const history: number[] = []; // ▸ every edge starts with the same trail, tau0, and no tour is known this.tracer?.emit("init", { ants: this.ants, cities: n, pheromone: roundMatrix(tau) }); this.tracer?.emit("init", { ants: this.ants, cities: n, pheromone: roundMatrix(trail) }); for (let iteration = 1; iteration <= this.iterations; iteration++) { const tours: number[][] = []; const lengths: number[] = []; let roundBest = -1; let bestThisRound = -1; for (let ant = 0; ant < this.ants; ant++) { const order = this.walk(ant, iteration, tau, rng); const order = this.walk(ant, iteration, trail, rolls); const length = this.problem.length(order); tours.push(order); lengths.push(length); if (roundBest < 0 || length < lengths[roundBest]!) roundBest = ant; if (bestThisRound < 0 || length < lengths[bestThisRound]!) bestThisRound = ant; // ▸ an ant is home: its closed tour is measured this.tracer?.emit("tour", { ant, iteration, length: round(length), order: order.slice() }); } if (lengths[roundBest]! < bestLength - ACO_IMPROVE_TOLERANCE) { if (lengths[bestThisRound]! < bestLength - ACO_IMPROVE_TOLERANCE) { bestLength = lengths[roundBest]!; bestLength = lengths[bestThisRound]!; best = tours[roundBest]!.slice(); best = tours[bestThisRound]!.slice(); // ▸ the shortest tour yet: remember it this.tracer?.emit("improve", { ant: roundBest, iteration, length: round(bestLength), order: best.slice() }); this.tracer?.emit("improve", { ant: bestThisRound, iteration, length: round(bestLength), order: best.slice() }); } history.push(bestLength); tau = AntSystem.evaporated(tau, this.rho); trail = AntSystem.evaporated(trail, this.rho); // ▸ every trail loses the share rho, so old choices fade this.tracer?.emit("evaporate", { iteration, pheromone: roundMatrix(tau), rho: this.rho }); this.tracer?.emit("evaporate", { iteration, pheromone: roundMatrix(trail), rho: this.rho }); tau = AntSystem.deposited(tau, tours, lengths, this.q); trail = AntSystem.deposited(trail, tours, lengths, this.q); // ▸ each ant lays q over its length on every edge it walked this.tracer?.emit("deposit", { iteration, pheromone: roundMatrix(tau), strongest: AntSystem.strongest(tau) }); this.tracer?.emit("deposit", { iteration, pheromone: roundMatrix(trail), strongest: AntSystem.strongest(trail) }); } // ▸ the shortest tour any ant walked, after every iteration this.tracer?.emit("verdict", { iterations: this.iterations, length: round(bestLength), order: best.slice() }); return { best, length: bestLength, pheromone: tau, history, iterations: this.iterations }; return { best, length: bestLength, pheromone: trail, history, iterations: this.iterations }; } /** One ant's closed tour: a random start, then a roll per step through the cumulative chances. */ private walk(ant: number, iteration: number, tau: readonly (readonly number[])[], rng: Mulberry32): number[] { private walk(ant: number, iteration: number, trail: readonly (readonly number[])[], rolls: Mulberry32): number[] { const n = this.problem.size; const order = [rng.index(n)]; const order = [rolls.index(n)]; const visited = new Set<number>(order); while (order.length < n) { const at = order[order.length - 1]!; const allowed: number[] = []; for (let city = 0; city < n; city++) if (!visited.has(city)) allowed.push(city); const chances = AntSystem.chances(at, allowed, tau, (a, b) => this.problem.distance(a, b), this.alpha, this.beta); const chances = AntSystem.chances(at, allowed, trail, (a, b) => this.problem.distance(a, b), this.alpha, this.beta); const roll = rng.next(); const roll = rolls.next(); // The last allowed city takes any rounding remainder. let next = allowed[allowed.length - 1]!; let cumulative = 0; for (let k = 0; k < allowed.length; k++) { cumulative += chances[k]!; if (roll < cumulative) { next = allowed[k]!; break; } } if (ant === this.traced) { // ▸ the next city is a roll weighted by trail to the alpha and closeness to the beta this.tracer?.emit("choose", { allowed: allowed.slice(), ant, at, chances: chances.map(round), iteration, next, roll: round(roll) }); } order.push(next); visited.add(next); } return order; } /** A copy of the matrix with every entry scaled by `1 - rho`. */ private static evaporated(tau: readonly (readonly number[])[], rho: number): number[][] { private static evaporated(trail: readonly (readonly number[])[], rho: number): number[][] { return tau.map((row) => row.map((value) => value * (1 - rho))); return trail.map((row) => row.map((value) => value * (1 - rho))); } /** The largest entry above the diagonal as `[i, j, tau]`, the lowest i then j on a tie. */ private static strongest(tau: readonly (readonly number[])[]): [number, number, number] { private static strongest(trail: readonly (readonly number[])[]): [number, number, number] { let edge: [number, number, number] = [0, 1, tau[0]![1]!]; let edge: [number, number, number] = [0, 1, trail[0]![1]!]; for (let i = 0; i < tau.length; i++) { for (let i = 0; i < trail.length; i++) { for (let j = i + 1; j < tau.length; j++) { for (let j = i + 1; j < trail.length; j++) { if (tau[i]![j]! > edge[2]) edge = [i, j, tau[i]![j]!]; if (trail[i]![j]! > edge[2]) edge = [i, j, trail[i]![j]!]; } } return [edge[0], edge[1], round(edge[2])]; }}