Simulated Annealing

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

Simulated annealing

Loading interactive demo…

A walker on a landscape seen from above, bright where the ground is low. Each iteration proposes a random Gaussian step and reads the height there: downhill or level moves are always taken, uphill moves pass with chance exp of minus the rise over the temperature, and the temperature shrinks by the cooling factor after every iteration. At temperature 0 it is hill climbing. Take the tour, or press and explore. Legend:

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

The walker, where it stands now.
The start ring, and the open proposal while its verdict is pending.
The best ring, and a downhill move just taken.
An uphill move just taken on a roll, and the temperature curve on the plot.
A refused move, dashed, with its candidate hollow.
The path walked so far; the finished path's points show faintly ahead of it.

temperature is the current temperature, here the height where the walker stands, best the lowest height it has stood on, verdicts how many moves went down, up, or were refused, and iteration how far the run is. The plot is the best so far as a share of the start height, with the temperature as a share of its start beneath it; the strip holds the last twelve verdicts. Tap the field to place the start.

The library's own default temperature is 2; the stage opens at 12 because a step of 1 on Rastrigin lands a basin away, where the ridges rise by tens, and at 2 almost no uphill move passes.

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 walker that cannot see the slope. Gradient descent, the prerequisite, measures the slope under the ball and steps against it. Simulated annealing never asks for a slope: it reads only the height $f(x)$ at points it chooses to visit, which is all that many real objectives offer, a schedule's clash count or a circuit's wire length having no derivative to take. Each iteration proposes a neighbour $x'$ by a random Gaussian step of radius step, reads $f(x')$ , and decides.

The Metropolis test. Let $\Delta = f(x') - f(x)$ . A move that goes down or stays level is always taken. A move that goes up is taken with probability

P(\text{accept}) = e^{-\Delta / T}

where $T$ is the temperature. The library draws a roll $r$ uniform in $[0, 1)$ and takes the move when $r < P$ . A rise of 1 at temperature 2 passes with chance $e^{-1/2} \approx 0.61$ ; a rise of 2 at temperature 1 with $e^{-2} \approx 0.14$ ; at $T = 0$ the chance is 0 for any rise, and the walker is a plain hill climber that stops in the first basin it falls into. The ratio matters, not the rise alone: double both and nothing changes.

Cooling. After every iteration $T$ is multiplied by the cooling factor $\alpha$ , so after $k$ iterations

T_k = T_0 \, \alpha^k

With $\alpha = 0.9$ , ten coolings leave $0.9^{10} \approx 0.35$ of the start, and thirty leave about 0.04. Early, while $T$ is high, rises of the size the landscape offers pass often, and the walker wanders out of small basins; late, only descents pass, and it settles. That is the whole trick: one knob, the temperature, that turns a random walk into a hill climber over the course of the run. The step radius is held fixed in this implementation so that the temperature alone decides what passes.

Why the stage opens hot. Rastrigin's local basins sit at every whole-number point and are separated by ridges of about 20 units, so a step of 1 from one basin lands on a ridge and the typical rise is in the tens. The library's own default of $T_0 = 2$ would pass almost none of them; the stage starts at 12 so the uphill moves the lesson is about actually appear. Set the temperature by the rises your landscape offers, not by habit.

What it costs and what it promises. Each iteration is one evaluation of $f$ , so a run of $I$ iterations costs $O(I)$ evaluations and $O(I)$ memory for the path; the best position seen is the answer, since the walker may have left it. In theory a slow enough logarithmic schedule reaches the global minimum with probability approaching 1, but that schedule takes longer than trying every point, so in practice annealing is a heuristic: good answers in bounded time, with no certificate. No Free Lunch (Wolpert and Macready, 1997) says that averaged over all possible objectives no search method beats any other, so annealing is only good relative to a family of problems, those where nearby points have related heights and a basin is worth exploring.

Where this goes next. The meta-heuristics unit keeps the gradient-free walker and changes what stands in for the temperature: a genetic algorithm trades one walker for a population, and ant colonies trade the roll for a trail of pheromone.

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

The roll is always drawn. Whenever a move goes uphill the library draws roll even at temperature 0, where it cannot pass. The random stream then does not depend on the temperature, so the same seed proposes the same steps at every setting and the only thing a colder run changes is the verdicts.
acceptance is a static. exp(-delta / t) with the two guards, 1 for a level or downhill move and 0 at temperature 0, lives on the class so the checkpoints and the tests can read the chance without running a walk.
A fixed step radius. gaussianPair draws two normals by Box-Muller from two uniforms and the step is step times them, never scaled by the temperature. Many implementations shrink the step as they cool; this one keeps the two effects apart so the temperature is the only thing to watch.
Clamped, not rejected. A proposal past the domain's edge is pulled back onto it by landscape.clamp, so a walker near a wall still gets a proposal every iteration and the trace stays 2 + 3I events long.
The best is kept separately. best and bestValue are updated on every accepted move, because the walker may take an uphill move away from the lowest point it stood on, and verdict reports the best, not where the walker ended.
Payloads are rounded, results are not. Every number in a trace event is rounded to three decimals for the stage; the returned path and values keep the raw doubles.

The acceptance test is older than the optimizer. In 1953 a Los Alamos group sampling a gas of particles on the MANIAC proposed a random move and took it always when the energy fell, and with probability exp of minus the rise over the temperature when it rose. Thirty years later Kirkpatrick, Gelatt, and Vecchi saw that lowering that sampler's temperature turns it into a search for the lowest energy, named it after the slow cooling of metal, and placed circuits and routed a salesman with it; Cerny found the same idea independently.

1953Nicholas Metropolis, Arianna and Marshall Rosenbluth, Augusta and Edward Teller - 'Equation of State Calculations by Fast Computing Machines' in the Journal of Chemical Physics: a Monte Carlo method that proposes a random move and accepts it by the Boltzmann factor, run on the MANIAC.source
1970W. K. Hastings - 'Monte Carlo Sampling Methods Using Markov Chains and Their Applications' in Biometrika extends the Metropolis method to proposals that are not symmetric, giving the Metropolis-Hastings algorithm its second name.source
1983Scott Kirkpatrick, C. Daniel Gelatt, Mario Vecchi - 'Optimization by Simulated Annealing' in Science: the Metropolis sampler with a falling temperature as an optimizer, applied to circuit placement and the travelling salesman problem, and the name that stuck.source
1984Stuart Geman and Donald Geman - 'Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images' brings the first proof that simulated annealing converges, alongside the Gibbs sampler it introduced.source
1985Vladimir Cerny - 'Thermodynamical approach to the traveling salesman problem' in the Journal of Optimization Theory and Applications: the same annealing idea, found independently.source

Used today

Placing and routing chips - Kirkpatrick's first application was placing circuit blocks and routing their wires; annealing stayed a standard placer in VLSI layout tools for decades.
Scheduling and timetabling - Job-shop schedules, exam timetables, and rosters: a swap of two assignments is a proposal, the number of clashes is the height, and uphill swaps let the schedule unknot itself.
Protein structure - Sampling the folded shapes of a protein is the 1953 problem in another costume: moves on a chain of atoms, accepted by the energy rise and the temperature.
Travelling salesman tours - The problem Kirkpatrick and Cerny both chose to show the method: reverse a stretch of the tour, accept by the change in length.

Did you know

The name is borrowed from metallurgy, where annealing heats a metal and cools it slowly so its atoms settle into a low-energy crystal instead of freezing into whatever strained arrangement they were in.source
The 1953 calculation ran on the MANIAC at Los Alamos, finished in 1952 under Metropolis, who said he chose the name in the hope of stopping the rash of silly acronyms for machines; it did not work.source
Marshall Rosenbluth later said that he and his wife Arianna did the work on the 1953 paper, Arianna writing the program from scratch, and that Metropolis contributed little beyond computer time; for years the method was known simply as the Metropolis algorithm.source
Monte Carlo methods got their name from Stanislaw Ulam's relatives and their fondness for the casinos of Monte Carlo; the annealing walker's rolls are the same dice.source

field

temp12

cooling0.90

step1.0

iterations30

temperature: 0.51
here: 11.16
best: 11.16
verdicts: 5 down, 5 up, 20 no
iteration: 30 of 30

simulated-annealing.ts

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";import { Landscape } from "./landscape";/** The most iterations one run takes, so a trace stays short enough to step through. */export const SA_MAX_ITERATIONS = 40;/** The starting temperature when none is given. */export const SA_DEFAULT_TEMPERATURE = 2;/** The factor the temperature shrinks by after every iteration when none is given. */export const SA_DEFAULT_COOLING = 0.9;/** The Gaussian radius of a proposed move when none is given. */export const SA_DEFAULT_STEP = 1;/** The iterations one run takes when none is given. */export const SA_DEFAULT_ITERATIONS = 30;export interface AnnealingOptions {  /** The landscape the walker descends. */  landscape: Landscape;  /** Seeds the start (when none is given), the proposals, and the Metropolis rolls. */  seed: number;  /** Where the walker begins; default a uniform random point of the landscape. */  start?: readonly number[];  /** The starting temperature, at least 0; 0 is hill climbing, since no uphill move can pass. Default 2. */  temperature?: number;  /** The temperature's factor per iteration, in (0, 1]; 1 never cools. Default 0.9. */  cooling?: number;  /** The Gaussian radius of a proposal, above 0; fixed, so the temperature acts only in the acceptance test. Default 1. */  step?: number;  /** How many proposals to make, a whole number in [1, SA_MAX_ITERATIONS]. Default 30. */  iterations?: number;}export interface AnnealingResult {  /** The lowest position the walker stood on. */  best: number[];  /** The landscape's height at `best`. */  bestValue: number;  /** Every position the walker stood on, the start first and one more per accepted move. */  path: number[][];  /** The height at each position of the path. */  values: number[];  /** Downhill or level moves taken. */  accepted: number;  /** Uphill moves taken, each on a roll under its chance. */  uphill: number;  /** Uphill moves refused. */  rejected: number;  /** Proposals made: `accepted + uphill + rejected`. */  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;const roundPoint = (point: readonly number[]): number[] => point.map(round);/** * Simulated annealing on a two-dimensional landscape: a walker proposes * a random Gaussian step each iteration, always takes it when the * ground is lower or level, and takes it uphill with chance * `exp(-delta / T)`, the Metropolis test, where the temperature `T` * shrinks by a fixed factor after every proposal. Early, while `T` is * high, uphill moves pass often and the walker escapes small basins; * late, as `T` nears zero, only descents pass and it settles in the * basin it is in. At temperature 0 every uphill move is refused and the * walk is plain hill climbing. Proposals are clamped to the landscape's * domain. The step radius is fixed, so the temperature acts only in the * acceptance test, and the random stream is the same at every * temperature: the roll is drawn whenever a move goes uphill, even when * it cannot pass. * * Time: O(I) landscape evaluations for I iterations. Space: O(I) for the path. */export class SimulatedAnnealing {  readonly landscape: Landscape;  readonly seed: number;  readonly start: readonly number[] | undefined;  readonly temperature: number;  readonly cooling: number;  readonly step: number;  readonly iterations: number;  constructor(options: AnnealingOptions, private readonly tracer?: Tracer) {    const { landscape, seed, start, temperature = SA_DEFAULT_TEMPERATURE, cooling = SA_DEFAULT_COOLING, step = SA_DEFAULT_STEP, iterations = SA_DEFAULT_ITERATIONS } = options;    if (!Number.isFinite(seed)) throw new RangeError(`seed ${seed} must be finite`);    if (!Number.isFinite(temperature) || temperature < 0) throw new RangeError(`temperature ${temperature} must be a finite number of at least 0`);    if (!(cooling > 0 && cooling <= 1)) throw new RangeError(`cooling ${cooling} must lie in (0, 1]`);    if (!Number.isFinite(step) || step <= 0) throw new RangeError(`step ${step} must be positive`);    if (!Number.isInteger(iterations) || iterations < 1 || iterations > SA_MAX_ITERATIONS) throw new RangeError(`iterations ${iterations} must be a whole number in [1, ${SA_MAX_ITERATIONS}]`);    if (start !== undefined && (start.length !== 2 || !landscape.contains(start))) throw new RangeError(`start ${start} must be a point inside the landscape's domain`);    this.landscape = landscape;    this.seed = seed;    this.start = start === undefined ? undefined : [...start];    this.temperature = temperature;    this.cooling = cooling;    this.step = step;    this.iterations = iterations;  }  /** The chance an uphill move of `delta` passes at temperature `t`: 1 when `delta <= 0`, 0 when `t` is 0, else `exp(-delta / t)`. */  static acceptance(delta: number, t: number): number {  static acceptance(heightChange: number, t: number): number {    if (delta <= 0) return 1;    if (heightChange <= 0) return 1;    if (t === 0) return 0;    return Math.exp(-delta / t);    return Math.exp(-heightChange / t);  }  /** The temperature after `k` coolings from `t0`: `t0 * cooling^k`. */  static temperatureAt(t0: number, cooling: number, k: number): number {    return t0 * cooling ** k;  }  /** Runs the walk from scratch; the same seed gives the same walk every time. */  run(): AnnealingResult {    const rng = new Mulberry32(this.seed);    const landscape = this.landscape;    let position = this.start === undefined ? landscape.random(rng) : [...this.start];    let value = landscape.value(position);    let best = position.slice();    let bestValue = value;    let temperature = this.temperature;    const path: number[][] = [position.slice()];    const values: number[] = [value];    let accepted = 0;    let uphill = 0;    let rejected = 0;    // ▸ stand at the start and read the ground's height there    this.tracer?.emit("init", { landscape: landscape.kind, position: roundPoint(position), temperature: round(temperature), value: round(value) });    for (let iteration = 1; iteration <= this.iterations; iteration++) {      const [dx, dy] = this.gaussianPair(rng);      const candidate = landscape.clamp([position[0]! + this.step * dx, position[1]! + this.step * dy]);      const candidateValue = landscape.value(candidate);      const delta = candidateValue - value;      const heightChange = candidateValue - value;      // ▸ propose a random gaussian step and read the height there      this.tracer?.emit("propose", { candidate: roundPoint(candidate), delta: round(delta), iteration, value: round(candidateValue) });      this.tracer?.emit("propose", { candidate: roundPoint(candidate), heightChange: round(heightChange), iteration, value: round(candidateValue) });      let taken: boolean;      if (delta <= 0) {      if (heightChange <= 0) {        taken = true;        accepted++;        // ▸ downhill or level: always take the move        this.tracer?.emit("accept", { iteration, position: roundPoint(candidate), value: round(candidateValue) });      } else {        // The roll is drawn whenever the move goes uphill, even at temperature 0, so the stream does not depend on the temperature.        const chance = SimulatedAnnealing.acceptance(delta, temperature);        const passChance = SimulatedAnnealing.acceptance(heightChange, temperature);        const roll = rng.next();        const diceRoll = rng.next();        taken = roll < chance;        taken = diceRoll < passChance;        if (taken) {          uphill++;          // ▸ uphill, but the roll came in under the chance: climb          this.tracer?.emit("accept-worse", { chance: round(chance), iteration, position: roundPoint(candidate), roll: round(roll), value: round(candidateValue) });          this.tracer?.emit("accept-worse", { passChance: round(passChance), iteration, position: roundPoint(candidate), diceRoll: round(diceRoll), value: round(candidateValue) });        } else {          rejected++;          // ▸ uphill, and the roll missed the chance: stay put          this.tracer?.emit("reject", { chance: round(chance), iteration, roll: round(roll) });          this.tracer?.emit("reject", { passChance: round(passChance), iteration, diceRoll: round(diceRoll) });        }      }      if (taken) {        position = candidate;        value = candidateValue;        path.push(position.slice());        values.push(value);        if (value < bestValue) {          best = position.slice();          bestValue = value;        }      }      temperature *= this.cooling;      // ▸ shrink the temperature by the cooling factor      this.tracer?.emit("cool", { iteration, temperature: round(temperature) });    }    // ▸ the lowest ground the walker stood on is the answer    this.tracer?.emit("verdict", { best: roundPoint(best), iterations: this.iterations, value: round(bestValue) });    return { best, bestValue, path, values, accepted, uphill, rejected, iterations: this.iterations };  }  /** Two standard normal draws by Box-Muller from two uniforms, `u1` then `u2`. */  private gaussianPair(rng: Mulberry32): [number, number] {    const u1 = rng.next();    const u2 = rng.next();    const r = Math.sqrt(-2 * Math.log(1 - u1));    return [r * Math.cos(2 * Math.PI * u2), r * Math.sin(2 * Math.PI * u2)];  }}

value =: 11.16
best =: (2.91, 1.02)
accepted =: 5
uphill =: 5
rejected =: 20

5 downhill moves and 5 uphill moves taken, 20 refused; the best is 11.16 at (2.91, 1.02).

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";import { Landscape } from "./landscape";/** The most iterations one run takes, so a trace stays short enough to step through. */export const SA_MAX_ITERATIONS = 40;/** The starting temperature when none is given. */export const SA_DEFAULT_TEMPERATURE = 2;/** The factor the temperature shrinks by after every iteration when none is given. */export const SA_DEFAULT_COOLING = 0.9;/** The Gaussian radius of a proposed move when none is given. */export const SA_DEFAULT_STEP = 1;/** The iterations one run takes when none is given. */export const SA_DEFAULT_ITERATIONS = 30;export interface AnnealingOptions { /** The landscape the walker descends. */ landscape: Landscape; /** Seeds the start (when none is given), the proposals, and the Metropolis rolls. */ seed: number; /** Where the walker begins; default a uniform random point of the landscape. */ start?: readonly number[]; /** The starting temperature, at least 0; 0 is hill climbing, since no uphill move can pass. Default 2. */ temperature?: number; /** The temperature's factor per iteration, in (0, 1]; 1 never cools. Default 0.9. */ cooling?: number; /** The Gaussian radius of a proposal, above 0; fixed, so the temperature acts only in the acceptance test. Default 1. */ step?: number; /** How many proposals to make, a whole number in [1, SA_MAX_ITERATIONS]. Default 30. */ iterations?: number;}export interface AnnealingResult { /** The lowest position the walker stood on. */ best: number[]; /** The landscape's height at `best`. */ bestValue: number; /** Every position the walker stood on, the start first and one more per accepted move. */ path: number[][]; /** The height at each position of the path. */ values: number[]; /** Downhill or level moves taken. */ accepted: number; /** Uphill moves taken, each on a roll under its chance. */ uphill: number; /** Uphill moves refused. */ rejected: number; /** Proposals made: `accepted + uphill + rejected`. */ 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;const roundPoint = (point: readonly number[]): number[] => point.map(round);/** * Simulated annealing on a two-dimensional landscape: a walker proposes * a random Gaussian step each iteration, always takes it when the * ground is lower or level, and takes it uphill with chance * `exp(-delta / T)`, the Metropolis test, where the temperature `T` * shrinks by a fixed factor after every proposal. Early, while `T` is * high, uphill moves pass often and the walker escapes small basins; * late, as `T` nears zero, only descents pass and it settles in the * basin it is in. At temperature 0 every uphill move is refused and the * walk is plain hill climbing. Proposals are clamped to the landscape's * domain. The step radius is fixed, so the temperature acts only in the * acceptance test, and the random stream is the same at every * temperature: the roll is drawn whenever a move goes uphill, even when * it cannot pass. * * Time: O(I) landscape evaluations for I iterations. Space: O(I) for the path. */export class SimulatedAnnealing { readonly landscape: Landscape; readonly seed: number; readonly start: readonly number[] | undefined; readonly temperature: number; readonly cooling: number; readonly step: number; readonly iterations: number; constructor(options: AnnealingOptions, private readonly tracer?: Tracer) { const { landscape, seed, start, temperature = SA_DEFAULT_TEMPERATURE, cooling = SA_DEFAULT_COOLING, step = SA_DEFAULT_STEP, iterations = SA_DEFAULT_ITERATIONS } = options; if (!Number.isFinite(seed)) throw new RangeError(`seed ${seed} must be finite`); if (!Number.isFinite(temperature) || temperature < 0) throw new RangeError(`temperature ${temperature} must be a finite number of at least 0`); if (!(cooling > 0 && cooling <= 1)) throw new RangeError(`cooling ${cooling} must lie in (0, 1]`); if (!Number.isFinite(step) || step <= 0) throw new RangeError(`step ${step} must be positive`); if (!Number.isInteger(iterations) || iterations < 1 || iterations > SA_MAX_ITERATIONS) throw new RangeError(`iterations ${iterations} must be a whole number in [1, ${SA_MAX_ITERATIONS}]`); if (start !== undefined && (start.length !== 2 || !landscape.contains(start))) throw new RangeError(`start ${start} must be a point inside the landscape's domain`); this.landscape = landscape; this.seed = seed; this.start = start === undefined ? undefined : [...start]; this.temperature = temperature; this.cooling = cooling; this.step = step; this.iterations = iterations; } /** The chance an uphill move of `delta` passes at temperature `t`: 1 when `delta <= 0`, 0 when `t` is 0, else `exp(-delta / t)`. */ static acceptance(delta: number, t: number): number { static acceptance(heightChange: number, t: number): number { if (delta <= 0) return 1; if (heightChange <= 0) return 1; if (t === 0) return 0; return Math.exp(-delta / t); return Math.exp(-heightChange / t); } /** The temperature after `k` coolings from `t0`: `t0 * cooling^k`. */ static temperatureAt(t0: number, cooling: number, k: number): number { return t0 * cooling ** k; } /** Runs the walk from scratch; the same seed gives the same walk every time. */ run(): AnnealingResult { const rng = new Mulberry32(this.seed); const landscape = this.landscape; let position = this.start === undefined ? landscape.random(rng) : [...this.start]; let value = landscape.value(position); let best = position.slice(); let bestValue = value; let temperature = this.temperature; const path: number[][] = [position.slice()]; const values: number[] = [value]; let accepted = 0; let uphill = 0; let rejected = 0; // ▸ stand at the start and read the ground's height there this.tracer?.emit("init", { landscape: landscape.kind, position: roundPoint(position), temperature: round(temperature), value: round(value) }); for (let iteration = 1; iteration <= this.iterations; iteration++) { const [dx, dy] = this.gaussianPair(rng); const candidate = landscape.clamp([position[0]! + this.step * dx, position[1]! + this.step * dy]); const candidateValue = landscape.value(candidate); const delta = candidateValue - value; const heightChange = candidateValue - value; // ▸ propose a random gaussian step and read the height there this.tracer?.emit("propose", { candidate: roundPoint(candidate), delta: round(delta), iteration, value: round(candidateValue) }); this.tracer?.emit("propose", { candidate: roundPoint(candidate), heightChange: round(heightChange), iteration, value: round(candidateValue) }); let taken: boolean; if (delta <= 0) { if (heightChange <= 0) { taken = true; accepted++; // ▸ downhill or level: always take the move this.tracer?.emit("accept", { iteration, position: roundPoint(candidate), value: round(candidateValue) }); } else { // The roll is drawn whenever the move goes uphill, even at temperature 0, so the stream does not depend on the temperature. const chance = SimulatedAnnealing.acceptance(delta, temperature); const passChance = SimulatedAnnealing.acceptance(heightChange, temperature); const roll = rng.next(); const diceRoll = rng.next(); taken = roll < chance; taken = diceRoll < passChance; if (taken) { uphill++; // ▸ uphill, but the roll came in under the chance: climb this.tracer?.emit("accept-worse", { chance: round(chance), iteration, position: roundPoint(candidate), roll: round(roll), value: round(candidateValue) }); this.tracer?.emit("accept-worse", { passChance: round(passChance), iteration, position: roundPoint(candidate), diceRoll: round(diceRoll), value: round(candidateValue) }); } else { rejected++; // ▸ uphill, and the roll missed the chance: stay put this.tracer?.emit("reject", { chance: round(chance), iteration, roll: round(roll) }); this.tracer?.emit("reject", { passChance: round(passChance), iteration, diceRoll: round(diceRoll) }); } } if (taken) { position = candidate; value = candidateValue; path.push(position.slice()); values.push(value); if (value < bestValue) { best = position.slice(); bestValue = value; } } temperature *= this.cooling; // ▸ shrink the temperature by the cooling factor this.tracer?.emit("cool", { iteration, temperature: round(temperature) }); } // ▸ the lowest ground the walker stood on is the answer this.tracer?.emit("verdict", { best: roundPoint(best), iterations: this.iterations, value: round(bestValue) }); return { best, bestValue, path, values, accepted, uphill, rejected, iterations: this.iterations }; } /** Two standard normal draws by Box-Muller from two uniforms, `u1` then `u2`. */ private gaussianPair(rng: Mulberry32): [number, number] { const u1 = rng.next(); const u2 = rng.next(); const r = Math.sqrt(-2 * Math.log(1 - u1)); return [r * Math.cos(2 * Math.PI * u2), r * Math.sin(2 * Math.PI * u2)]; }}