Simulated Annealing

Why Simulated Annealing Matters

A local optimizer that accepts only improvements can become trapped behind a barrier. Imagine a configuration with energy $0$ whose immediate neighbor has energy $4$, but the next states lead to energy $1$ and then $-5$. Pure descent cannot take the first step. Simulated annealing sometimes accepts that temporary increase, allowing exploration beyond the current basin.

The algorithm minimizes an objective called energy. It samples a candidate move, always accepts a non-worsening candidate, and sometimes accepts a worse one according to a positive temperature. Early, warmer iterations can cross barriers; later, cooler iterations make energy increases less likely. A separate best-ever state preserves good discoveries while the current state continues to wander.

The implementation uses a small finite energy table, a symmetric bounded proposal, one portable seeded generator, geometric cooling, and explicit resource limits. Every proposal and decision is recorded. It is a reproducible optimization heuristic; reaching a temperature or iteration limit does not establish that the global minimum has been found.

Core Concepts and Terminology

Let $S$ be the feasible states, $E(x)$ the energy to minimize, and $q(y\mid x)$ the probability of proposing candidate $y$ from current state $x$. Define the energy difference by candidate minus current:

$$\Delta E=E(y)-E(x).$$

For a symmetric proposal, $q(y\mid x)=q(x\mid y)$, the Metropolis acceptance probability at $T\gt0$ is

$$a_T(x,y)=\min\left(1,\exp\left(-\frac{\Delta E}{T}\right)\right).$$

Thus $\Delta E\le0$ is accepted, including equal-energy moves and self-proposals. For $\Delta E\gt0$, draw $U$ uniformly from $(0,1)$ in the ideal model and accept when $U\lt\exp(-\Delta E/T)$. Higher barriers and lower temperatures both reduce this probability. Temperature has the same scale as energy differences; it is not a probability.

The example states are integer indices. Propose a left or right unit step with equal probability; an outward step at an endpoint becomes a self-proposal. This produces symmetric adjacent transition probabilities, including at boundaries. Sampling uniformly from only the valid neighbors would instead be asymmetric at an endpoint and would require different acceptance logic for the usual Boltzmann interpretation.

The current state follows accepted proposals and can have increasing energy. The incumbent is the best state discovered; its energy never increases. The first three accepted moves in the landscape below are $0\to1\to2\to3$, with energies $0\to4\to1\to-5$.

How Simulated Annealing Works, Step by Step

1. Validate the model and schedule. Require a valid initial state, bounded integer energies, a positive finite starting temperature, a positive temperature floor at most the start, and finite cooling factor $0\lt\alpha\lt1$. Initialize one random generator for the whole run.
2. Evaluate the initial state. Spend one objective call and initialize both current and best. If the global evaluation budget is zero, return EVAL_LIMIT with no meaningful energy value. A zero proposal cap still allows this initial evaluation when budget permits.
3. Check stopping conditions before drawing a proposal. Stop first at the proposal cap, then if temperature is below the floor, then if floating-point cooling failed to change it, then if another evaluation would exceed budget. A blocked evaluation therefore consumes no proposal randomness.
4. Propose and evaluate one state. Draw a direction, clamp the unit step to $[0,n-1]$, evaluate the candidate, and count the call even for a self-proposal. Compute $\Delta E$ in signed 64-bit arithmetic in C++ and Java.
5. Make the acceptance decision. If $\Delta E\le0$, accept without an acceptance draw. Otherwise draw $U\in(0,1)$ and use the mathematically equivalent test

$$\log U\lt-\frac{\Delta E}{T}.$$

This avoids computing $\exp(-\Delta E/T)$, which can underflow to zero. If the quotient is too large to represent and becomes positive infinity before negation, the finite log draw cannot pass the resulting negative-infinity threshold. 6. Update current and best separately. On acceptance, replace current and its cached energy; update best only on a strict energy improvement. On rejection, current stays unchanged. Equal best energies keep the earliest best state. A rejected candidate is worse than current and therefore cannot beat the already no-worse incumbent. 7. Record the complete decision and cool. Save temperature used, old state/energy, direction, raw draws, candidate/energy, difference, acceptance, resulting current and best, and counters. Multiply temperature by $\alpha$ after every decision, including rejection and self-proposal. Record whether the new represented temperature equals the old one, then repeat.

With zero-based proposal index $k$, the ideal geometric schedule is $T_k=T_0\alpha^k$; proposal $1$ uses $T_0$. The programs multiply successively rather than recomputing a power. The returned temperature is the one prepared for a possible next decision, not the temperature used by the last recorded decision.

Reproducible random draws. Each call advances integer state $z$ by $z\leftarrow48271z\bmod2147483647$. Valid seeds lie in $[1,2147483646]$. For directions, parity of $z-1$ chooses left or right; its possible range has an even number of elements. For uphill acceptance, $U=z/2147483647$, which is strictly between zero and one. Only uphill trials consume that second draw. The generator is deterministic and its finite-resolution values approximate the ideal independent uniform model; a fixed seed is for reproducibility, not a proof of a stochastic convergence theorem.

flowchart TD
    A["Validate input and initialize one RNG"] --> B{"Initial evaluation budget available?"}
    B -->|No| C["Return EVAL_LIMIT; no value"]
    B -->|Yes| D["Evaluate start; initialize current and best"]
    D --> E{"Proposal cap reached?"}
    E -->|Yes| F["Return STEP_LIMIT"]
    E -->|No| G{"Temperature below floor?"}
    G -->|Yes| H["Return COOLED"]
    G -->|No| I{"Cooling previously stalled?"}
    I -->|Yes| J["Return TEMP_STALLED"]
    I -->|No| K{"Another evaluation fits budget?"}
    K -->|No| L["Return EVAL_LIMIT with best so far"]
    K -->|Yes| M["Draw unit direction; clamp; evaluate candidate"]
    M --> N{"Candidate energy no greater?"}
    N -->|Yes| O["Accept candidate"]
    N -->|No| P["Draw open-interval U"]
    P --> Q{"log U below negative delta over T?"}
    Q -->|Yes| O
    Q -->|No| R["Reject; current stays unchanged"]
    O --> S["Update best only if current improves it"]
    S --> T["Record decision; cool; detect rounded stall"]
    R --> T
    T --> E

Worked Example with a Full Trace

Minimize the table

$$[E(0),E(1),E(2),E(3),E(4),E(5)]=[0,4,1,-5,0,2].$$

Use start $0$, seed $84$, $12$ proposal decisions, $T_0=5$, cooling factor $\alpha=0.85$, floor $T_{\min}=0.01$, and evaluation budget $1000$. This allows all $12$ decisions. Initial evaluation establishes current $0:0$ and best $0:0$, using one call and no random draws.

The first raw proposal draw is $4054764$. Since $(4054764-1)\bmod2=1$, propose direction $+1$, state $1$, energy $4$. The next raw draw is $306501167$, giving $U\approx0.142725728$. At $T=5$, uphill acceptance probability is $\exp(-4/5)\approx0.449328964$, so the move is accepted. Current becomes energy $4$ while the best remains energy $0$.

The full trace below records every decision. A state cell is index:energy. Temperatures, probabilities, and draws are displayed to nine decimal places; decisions use full precision. Probabilities are shown for explanation and are not explicitly evaluated by the code. A dash means no acceptance draw was needed because the proposal was non-worsening. Evaluations count the initial state plus one candidate per row; raw-draw counts include direction and any uphill acceptance draw.

For reproducibility, the raw draws behind those rows are:

After step $3$, state $3$ with energy $-5$ is saved as best. Step $8$ accepts a worsening move to energy $0$, and step $11$ accepts a rare worsening move to energy $1$. The current energy therefore does not decrease monotonically. The incumbent remains $3:-5$ through both excursions and the final rejection.

The final result is STEP_LIMIT, current state $2$ with energy $1$, best state $3$ with energy $-5$, $13$ evaluations, $6$ acceptances, $3$ accepted uphill moves, $6$ rejections, $6$ actual state changes, and $21$ raw draws. Final generator state is $2054271720$, and the temperature prepared for a possible next proposal is approximately $0.711208786$. A full scan of this tiny table independently confirms that $-5$ is its global minimum; the stopping status did not prove that.

Implementation in Python, C++, and Java

Each complete program implements the same bounded integer-state annealing policy. It proposes exactly one unit direction per decision, retains an outward boundary step as a self-proposal, and uses cached current energy for the difference. It deliberately evaluates a candidate even when it equals current, keeping the evaluation contract simple. The objective is an integer table; replacing it with an implicit evaluator requires retaining feasible proposals and handling its own errors and costs.

Input contract. The non-null energy collection has $1\le n\le256$ integer values in $[-10^9,10^9]$. Start is in $[0,n-1]$, seed in $[1,2147483646]$, requested proposal count in $[0,2000]$, and total evaluation budget in $[0,10^6]$. Temperatures and cooling must be finite, with $0\lt T_{\min}\le T_0\le10^9$ and $0\lt\alpha\lt1$. Invalid sizes, ranges, seeds, or schedule values are rejected. Energies are copied; the caller's input is preserved, and repeated calls reset the generator and all counters.

Result contains status, has_value, current state/energy, best state/energy, temperature prepared for the next proposal, six statistics, final generator state, and decision history. Statistics are [evaluations,accepted,uphill,rejected,changed,rng_draws]. Acceptances include equal-energy moves and self-proposals; changed counts only accepted moves to a different index. The uphill count includes accepted proposals with positive $\Delta E$. A zero-budget result has no meaningful energy: has_value is false, best index is $-1$, and zero energy fields are dummy values.

Each history row contains the temperature used, old state/energy, direction and its raw draw, candidate state/energy, difference, optional acceptance raw draw, decision, resulting current and incumbent, evaluation count, and raw-draw count. An acceptance raw draw of zero is a sentinel for “not used”; actual draws are strictly positive. The table's bounded differences and 64-bit C++/Java arithmetic avoid integer overflow in $\Delta E$ and in random-generator multiplication.

STEP_LIMIT means the requested number of proposal decisions finished. COOLED means the next temperature is strictly below the floor; equality with the floor still allows a decision. TEMP_STALLED means multiplication rounded back to the same positive temperature. EVAL_LIMIT means a required objective call is unavailable. After initialization, precedence is step count, floor, stalled cooling, then evaluation budget. Thus a final step can report STEP_LIMIT even when its cooling also crosses the floor. Underflow to zero is detected by the floor check before any division by temperature. None of these statuses certifies a local or global minimum.

Every initialized run with $I$ recorded decisions uses exactly $I+1$ objective calls. A zero-budget run uses none. Every decision consumes one raw direction draw; each positive-difference trial consumes one additional acceptance draw, so $I\le D_{\mathrm{rng}}\le2I$. If a candidate is worse, even a near-certain rejection consumes that draw. These rules are part of reproducibility; warm and cold runs with the same seed can diverge in both current states and later draw consumption.

Run Python 3, C++14 or newer, or Java 17 or newer, saving Java as Main.java. Compile C++ with -ffp-contract=off and without unsafe floating-point transformations for the tested arithmetic order. Java's explicit decimal formatting helper uses the exact binary64 value and half-even rounding so its printed scientific notation matches Python and C++, including subnormals. Acceptance and temperature calculations themselves remain binary64; logarithms are subject to the platform's numerical accuracy.

import math
from dataclasses import dataclass

P, A = 2_147_483_647, 48_271


class RandomSource:
    def __init__(self, seed):
        self.state, self.draws = seed, 0

    def next(self):
        self.state = A * self.state % P
        self.draws += 1
        return self.state


@dataclass
class Row:
    temperature: float
    old_state: int
    old_energy: int
    direction: int
    proposal_draw: int
    candidate: int
    candidate_energy: int
    delta: int
    acceptance_draw: int
    accepted: bool
    current: int
    energy: int
    best: int
    best_energy: int
    evaluations: int
    rng_draws: int


@dataclass
class Result:
    status: str
    has_value: bool
    current: int
    energy: int
    best: int
    best_energy: int
    temperature: float
    stats: list
    rng_state: int
    history: list


def anneal(energies, start, seed, steps=100, t0=5.0, cooling=0.85, tmin=0.01, budget=1000):
    if (not 1 <= len(energies) <= 256 or
            any(type(e) is not int or not -1_000_000_000 <= e <= 1_000_000_000 for e in energies) or
            type(start) is not int or not 0 <= start < len(energies) or
            type(seed) is not int or not 1 <= seed < P or
            type(steps) is not int or not 0 <= steps <= 2000 or
            type(budget) is not int or not 0 <= budget <= 1_000_000 or
            not all(math.isfinite(v) for v in (t0, cooling, tmin)) or
            not 0 < tmin <= t0 <= 1_000_000_000 or not 0 < cooling < 1):
        raise ValueError("invalid search parameters")
    values, rng = list(energies), RandomSource(seed)
    current, energy, best, best_energy = start, 0, -1, 0
    temperature, has_value, stagnant = float(t0), False, False
    evaluations = accepted_count = uphill_count = rejected_count = changed_count = 0
    history = []

    def finish(status):
        stats = [evaluations, accepted_count, uphill_count, rejected_count, changed_count, rng.draws]
        return Result(status, has_value, current, energy, best, best_energy,
                      temperature, stats, rng.state, history.copy())

    if budget == 0:
        return finish("EVAL_LIMIT")
    energy = best_energy = values[start]
    best, has_value, evaluations = start, True, 1
    while True:
        if len(history) >= steps:
            return finish("STEP_LIMIT")
        if temperature < tmin:
            return finish("COOLED")
        if stagnant:
            return finish("TEMP_STALLED")
        if evaluations >= budget:
            return finish("EVAL_LIMIT")
        proposal_draw = rng.next()
        direction = -1 if (proposal_draw - 1) % 2 == 0 else 1
        candidate = max(0, min(len(values) - 1, current + direction))
        trial = values[candidate]
        evaluations += 1
        delta, acceptance_draw = trial - energy, 0
        accepted = delta <= 0
        if delta > 0:
            acceptance_draw = rng.next()
            u = acceptance_draw / P  # Strictly inside (0,1).
            accepted = math.log(u) < -float(delta) / temperature
        old_state, old_energy = current, energy
        if accepted:
            accepted_count += 1
            uphill_count += delta > 0
            changed_count += candidate != current
            current, energy = candidate, trial
            if energy < best_energy:
                best, best_energy = current, energy
        else:
            rejected_count += 1
        history.append(Row(temperature, old_state, old_energy, direction, proposal_draw,
                           candidate, trial, delta, acceptance_draw, accepted, current, energy,
                           best, best_energy, evaluations, rng.draws))
        next_temperature = temperature * cooling
        stagnant = next_temperature == temperature
        temperature = next_temperature



def show(name, energies, start, seed, steps=12, t0=5.0, cooling=0.85, tmin=0.01, budget=1000):
    result = anneal(energies, start, seed, steps, t0, cooling, tmin, budget)
    current = f"{result.current}:{result.energy}" if result.has_value else "NONE"
    best = f"{result.best}:{result.best_energy}" if result.has_value else "NONE"
    print(f"{name}: {result.status}, current={current}, best={best}")
    labels = ("evaluations", "accepted", "uphill", "rejected", "changed", "rng_draws")
    print(", ".join(f"{k}={v}" for k, v in zip(labels, result.stats)) +
          f", next_T={result.temperature:.6e}, rng_state={result.rng_state}")
    if result.has_value:
        print(f"i=0, x={start}, E={energies[start]}")
    for i, row in enumerate(result.history, 1):
        u = f"{row.acceptance_draw / P:.6e}" if row.acceptance_draw else "-"
        print(f"i={i}, T={row.temperature:.6e}, candidate={row.candidate}:{row.candidate_energy}, " +
              f"delta={row.delta}, u={u}, accept={'YES' if row.accepted else 'NO'}, " +
              f"x={row.current}, E={row.energy}, best={row.best}:{row.best_energy}")


def main():
    landscape = [0, 4, 1, -5, 0, 2]
    show("worked", landscape, 0, 84)
    show("cold", landscape, 0, 84, t0=1e-9, tmin=1e-12)
    show("cooled", landscape, 0, 84, steps=10, t0=1.0, cooling=0.5, tmin=0.6)
    show("evaluation cap", landscape, 0, 84, budget=3)
    show("zero steps", landscape, 0, 84, steps=0)
    show("zero budget", landscape, 0, 84, budget=0)
    show("singleton", [7], 0, 84, steps=2)
    show("temperature stall", [7], 0, 84, steps=3, t0=math.ulp(0.0), cooling=0.75, tmin=math.ulp(0.0))
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <locale>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;
const long long P=2147483647,A=48271;
struct RandomSource {
    long long state,draws=0;
    explicit RandomSource(long long seed):state(seed) {}
    long long next() { state=A*state%P; ++draws; return state; }
};
struct Row {
    double temperature;
    int old_state; long long old_energy;
    int direction; long long proposal_draw;
    int candidate; long long candidate_energy,delta,acceptance_draw;
    bool accepted;
    int current; long long energy;
    int best; long long best_energy,evaluations,rng_draws;
};
struct Result {
    string status; bool has_value;
    int current; long long energy;
    int best; long long best_energy;
    double temperature;
    vector<long long> stats;
    long long rng_state;
    vector<Row> history;
};
Result anneal(const vector<long long>& energies,int start,long long seed,int steps=100,double t0=5.0,double cooling=0.85,double tmin=0.01,long long budget=1000) {
    if(energies.empty() || energies.size()>256 || start<0 || start>=static_cast<int>(energies.size()) || seed<1 || seed>=P ||
       steps<0 || steps>2000 || budget<0 || budget>1000000 || !isfinite(t0) || !isfinite(cooling) || !isfinite(tmin) ||
       !(0<tmin && tmin<=t0 && t0<=1000000000) || !(0<cooling && cooling<1)) throw invalid_argument("invalid search parameters");
    for(long long e:energies) if(e < -1000000000 || e>1000000000) throw invalid_argument("invalid energy");
    vector<long long> values=energies;
    RandomSource rng(seed);
    int current=start,best=-1; long long energy=0,best_energy=0;
    double temperature=t0; bool has_value=false,stagnant=false;
    long long evaluations=0,accepted_count=0,uphill_count=0,rejected_count=0,changed_count=0;
    vector<Row> history;
    auto finish=[&](const string& status)->Result {
        return {status,has_value,current,energy,best,best_energy,temperature,
                {evaluations,accepted_count,uphill_count,rejected_count,changed_count,rng.draws},rng.state,history};
    };
    if(budget==0) return finish("EVAL_LIMIT");
    energy=best_energy=values[start]; best=start; has_value=true; evaluations=1;
    while(true) {
        if(static_cast<int>(history.size())>=steps) return finish("STEP_LIMIT");
        if(temperature<tmin) return finish("COOLED");
        if(stagnant) return finish("TEMP_STALLED");
        if(evaluations>=budget) return finish("EVAL_LIMIT");
        long long proposal_draw=rng.next();
        int direction=(proposal_draw-1)%2==0 ? -1 : 1;
        int candidate=max(0,min(static_cast<int>(values.size())-1,current+direction));
        long long trial=values[candidate]; ++evaluations;
        long long delta=trial-energy,acceptance_draw=0;
        bool accepted=delta<=0;
        if(delta>0) {
            acceptance_draw=rng.next();
            double u=static_cast<double>(acceptance_draw)/static_cast<double>(P);
            accepted=log(u)<-static_cast<double>(delta)/temperature;
        }
        int old_state=current; long long old_energy=energy;
        if(accepted) {
            ++accepted_count; uphill_count+=delta>0; changed_count+=candidate!=current;
            current=candidate; energy=trial;
            if(energy<best_energy) { best=current; best_energy=energy; }
        } else ++rejected_count;
        history.push_back({temperature,old_state,old_energy,direction,proposal_draw,candidate,trial,delta,acceptance_draw,
                           accepted,current,energy,best,best_energy,evaluations,rng.draws});
        double next_temperature=temperature*cooling;
        stagnant=next_temperature==temperature; temperature=next_temperature;
    }
}
string scientific6(double x) {
    ostringstream out; out.imbue(locale::classic()); out<<scientific<<setprecision(6)<<x; return out.str();
}
void show(const string& name,const vector<long long>& energies,int start,long long seed,int steps=12,double t0=5.0,double cooling=0.85,double tmin=0.01,long long budget=1000) {
    Result r=anneal(energies,start,seed,steps,t0,cooling,tmin,budget);
    cout<<name<<": "<<r.status<<", current=";
    if(r.has_value) cout<<r.current<<':'<<r.energy; else cout<<"NONE";
    cout<<", best=";
    if(r.has_value) cout<<r.best<<':'<<r.best_energy; else cout<<"NONE";
    cout<<'\n';
    vector<string> labels={"evaluations","accepted","uphill","rejected","changed","rng_draws"};
    for(size_t i=0;i<labels.size();++i) { if(i) cout<<", "; cout<<labels[i]<<'='<<r.stats[i]; }
    cout<<", next_T="<<scientific6(r.temperature)<<", rng_state="<<r.rng_state<<'\n';
    if(r.has_value) cout<<"i=0, x="<<start<<", E="<<energies[start]<<'\n';
    for(size_t i=0;i<r.history.size();++i) {
        const Row& row=r.history[i];
        string u=row.acceptance_draw ? scientific6(static_cast<double>(row.acceptance_draw)/static_cast<double>(P)) : "-";
        cout<<"i="<<i+1<<", T="<<scientific6(row.temperature)<<", candidate="<<row.candidate<<':'<<row.candidate_energy
            <<", delta="<<row.delta<<", u="<<u<<", accept="<<(row.accepted ? "YES" : "NO")
            <<", x="<<row.current<<", E="<<row.energy<<", best="<<row.best<<':'<<row.best_energy<<'\n';
    }
}
int main() {
    vector<long long> landscape={0,4,1,-5,0,2};
    show("worked",landscape,0,84);
    show("cold",landscape,0,84,12,1e-9,0.85,1e-12);
    show("cooled",landscape,0,84,10,1.0,0.5,0.6);
    show("evaluation cap",landscape,0,84,12,5.0,0.85,0.01,3);
    show("zero steps",landscape,0,84,0);
    show("zero budget",landscape,0,84,12,5.0,0.85,0.01,0);
    show("singleton",{7},0,84,2);
    show("temperature stall",{7},0,84,3,numeric_limits<double>::denorm_min(),0.75,numeric_limits<double>::denorm_min());
    cout<<"checks = PASS\n";
}

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

public class Main {
    static final long P=2_147_483_647L,A=48_271L;
    static final class RandomSource {
        long state,draws=0;
        RandomSource(long seed) { state=seed; }
        long next() { state=A*state%P; ++draws; return state; }
    }
    static final class Row {
        final double temperature;
        final int oldState,direction,candidate,current,best;
        final long oldEnergy,proposalDraw,candidateEnergy,delta,acceptanceDraw,energy,bestEnergy,evaluations,rngDraws;
        final boolean accepted;
        Row(double t,int os,long oe,int dir,long pd,int candidate,long ce,long delta,long ad,boolean accepted,
            int current,long energy,int best,long be,long ev,long rd) {
            temperature=t; oldState=os; oldEnergy=oe; direction=dir; proposalDraw=pd; this.candidate=candidate;
            candidateEnergy=ce; this.delta=delta; acceptanceDraw=ad; this.accepted=accepted; this.current=current;
            this.energy=energy; this.best=best; bestEnergy=be; evaluations=ev; rngDraws=rd;
        }
    }
    static final class Result {
        final String status; final boolean hasValue; final int current,best;
        final long energy,bestEnergy,rngState; final double temperature;
        final long[] stats; final List<Row> history;
        Result(String status,boolean hv,int current,long energy,int best,long be,double t,long[] stats,long rs,List<Row> history) {
            this.status=status; hasValue=hv; this.current=current; this.energy=energy; this.best=best; bestEnergy=be;
            temperature=t; this.stats=stats.clone(); rngState=rs; this.history=new ArrayList<>(history);
        }
    }
    static final class Runner {
        final long[] values; final int steps; final double cooling,tmin; final long budget;
        final RandomSource rng; int current,best=-1; long energy=0,bestEnergy=0;
        double temperature; boolean hasValue=false,stagnant=false;
        long evaluations=0,acceptedCount=0,uphillCount=0,rejectedCount=0,changedCount=0;
        final List<Row> history=new ArrayList<>();
        Runner(long[] energies,int start,long seed,int steps,double t0,double cooling,double tmin,long budget) {
            if(energies.length<1 || energies.length>256 || start<0 || start>=energies.length || seed<1 || seed>=P ||
               steps<0 || steps>2000 || budget<0 || budget>1_000_000 || !Double.isFinite(t0) || !Double.isFinite(cooling) || !Double.isFinite(tmin) ||
               !(0<tmin && tmin<=t0 && t0<=1_000_000_000) || !(0<cooling && cooling<1)) throw new IllegalArgumentException("invalid search parameters");
            for(long e:energies) if(e < -1_000_000_000L || e>1_000_000_000L) throw new IllegalArgumentException("invalid energy");
            values=energies.clone(); current=start; this.steps=steps; temperature=t0; this.cooling=cooling; this.tmin=tmin; this.budget=budget; rng=new RandomSource(seed);
        }
        Result finish(String status) {
            return new Result(status,hasValue,current,energy,best,bestEnergy,temperature,
                              new long[]{evaluations,acceptedCount,uphillCount,rejectedCount,changedCount,rng.draws},rng.state,history);
        }
        Result run() {
            if(budget==0) return finish("EVAL_LIMIT");
            energy=bestEnergy=values[current]; best=current; hasValue=true; evaluations=1;
            while(true) {
                if(history.size()>=steps) return finish("STEP_LIMIT");
                if(temperature<tmin) return finish("COOLED");
                if(stagnant) return finish("TEMP_STALLED");
                if(evaluations>=budget) return finish("EVAL_LIMIT");
                long proposalDraw=rng.next();
                int direction=(proposalDraw-1)%2==0 ? -1 : 1;
                int candidate=Math.max(0,Math.min(values.length-1,current+direction));
                long trial=values[candidate]; ++evaluations;
                long delta=trial-energy,acceptanceDraw=0; boolean accepted=delta<=0;
                if(delta>0) {
                    acceptanceDraw=rng.next(); double u=(double)acceptanceDraw/(double)P;
                    accepted=Math.log(u)<-(double)delta/temperature;
                }
                int oldState=current; long oldEnergy=energy;
                if(accepted) {
                    ++acceptedCount; if(delta>0) ++uphillCount; if(candidate!=current) ++changedCount;
                    current=candidate; energy=trial;
                    if(energy<bestEnergy) { best=current; bestEnergy=energy; }
                } else ++rejectedCount;
                history.add(new Row(temperature,oldState,oldEnergy,direction,proposalDraw,candidate,trial,delta,acceptanceDraw,
                                    accepted,current,energy,best,bestEnergy,evaluations,rng.draws));
                double nextTemperature=temperature*cooling; stagnant=nextTemperature==temperature; temperature=nextTemperature;
            }
        }
    }
    static Result anneal(long[] energies,int start,long seed,int steps,double t0,double cooling,double tmin,long budget) {
        return new Runner(energies,start,seed,steps,t0,cooling,tmin,budget).run();
    }
    static String scientific6(double x) {
        if(x==0) return "0.000000e+00";
        BigDecimal rounded=new BigDecimal(x).round(new MathContext(7,RoundingMode.HALF_EVEN));
        int exponent=rounded.precision()-rounded.scale()-1;
        String mantissa=rounded.scaleByPowerOfTen(-exponent).setScale(6,RoundingMode.HALF_EVEN).toPlainString();
        return mantissa+"e"+String.format(Locale.ROOT,"%+03d",exponent);
    }
    static void show(String name,long[] energies,int start,long seed,int steps,double t0,double cooling,double tmin,long budget) {
        Result r=anneal(energies,start,seed,steps,t0,cooling,tmin,budget);
        System.out.println(name+": "+r.status+", current="+(r.hasValue ? r.current+":"+r.energy : "NONE")+", best="+(r.hasValue ? r.best+":"+r.bestEnergy : "NONE"));
        String[] labels={"evaluations","accepted","uphill","rejected","changed","rng_draws"};StringBuilder out=new StringBuilder();
        for(int i=0;i<labels.length;++i) { if(i>0) out.append(", ");out.append(labels[i]).append('=').append(r.stats[i]); }
        System.out.println(out.append(", next_T=").append(scientific6(r.temperature)).append(", rng_state=").append(r.rngState));
        if(r.hasValue) System.out.println("i=0, x="+start+", E="+energies[start]);
        for(int i=0;i<r.history.size();++i) {
            Row row=r.history.get(i);String u=row.acceptanceDraw!=0 ? scientific6((double)row.acceptanceDraw/(double)P) : "-";
            System.out.println("i="+(i+1)+", T="+scientific6(row.temperature)+", candidate="+row.candidate+":"+row.candidateEnergy+
                               ", delta="+row.delta+", u="+u+", accept="+(row.accepted ? "YES" : "NO")+
                               ", x="+row.current+", E="+row.energy+", best="+row.best+":"+row.bestEnergy);
        }
    }
    public static void main(String[] args) {
        long[] landscape={0,4,1,-5,0,2};
        show("worked",landscape,0,84,12,5.0,0.85,0.01,1000);
        show("cold",landscape,0,84,12,1e-9,0.85,1e-12,1000);
        show("cooled",landscape,0,84,10,1.0,0.5,0.6,1000);
        show("evaluation cap",landscape,0,84,12,5.0,0.85,0.01,3);
        show("zero steps",landscape,0,84,0,5.0,0.85,0.01,1000);
        show("zero budget",landscape,0,84,12,5.0,0.85,0.01,0);
        show("singleton",new long[]{7},0,84,2,5.0,0.85,0.01,1000);
        show("temperature stall",new long[]{7},0,84,3,Double.MIN_VALUE,0.75,Double.MIN_VALUE,1000);
        System.out.println("checks = PASS");
    }
}

Expected standard output, identical in all three languages:

• worked: STEP_LIMIT, current=2:1, best=3:-5
• evaluations=13, accepted=6, uphill=3, rejected=6, changed=6, rng_draws=21, next_T=7.112088e-01, rng_state=2054271720
• i=0, x=0, E=0
• i=1, T=5.000000e+00, candidate=1:4, delta=4, u=1.427257e-01, accept=YES, x=1, E=4, best=0:0
• i=2, T=4.250000e+00, candidate=2:1, delta=-3, u=-, accept=YES, x=2, E=1, best=0:0
• i=3, T=3.612500e+00, candidate=3:-5, delta=-6, u=-, accept=YES, x=3, E=-5, best=3:-5
• i=4, T=3.070625e+00, candidate=2:1, delta=6, u=9.339408e-01, accept=NO, x=3, E=-5, best=3:-5
• i=5, T=2.610031e+00, candidate=2:1, delta=6, u=4.327046e-01, accept=NO, x=3, E=-5, best=3:-5
• i=6, T=2.218527e+00, candidate=4:0, delta=5, u=4.550459e-01, accept=NO, x=3, E=-5, best=3:-5
• i=7, T=1.885748e+00, candidate=2:1, delta=6, u=7.275398e-02, accept=NO, x=3, E=-5, best=3:-5
• i=8, T=1.602885e+00, candidate=4:0, delta=5, u=3.598873e-03, accept=YES, x=4, E=0, best=3:-5
• i=9, T=1.362453e+00, candidate=3:-5, delta=-5, u=-, accept=YES, x=3, E=-5, best=3:-5
• i=10, T=1.158085e+00, candidate=4:0, delta=5, u=6.372478e-01, accept=NO, x=3, E=-5, best=3:-5
• i=11, T=9.843720e-01, candidate=2:1, delta=6, u=1.785655e-03, accept=YES, x=2, E=1, best=3:-5
• i=12, T=8.367162e-01, candidate=1:4, delta=3, u=9.565948e-01, accept=NO, x=2, E=1, best=3:-5
• cold: STEP_LIMIT, current=0:0, best=0:0
• evaluations=13, accepted=7, uphill=0, rejected=5, changed=0, rng_draws=17, next_T=1.422418e-10, rng_state=1368479165
• i=0, x=0, E=0
• i=1, T=1.000000e-09, candidate=1:4, delta=4, u=1.427257e-01, accept=NO, x=0, E=0, best=0:0
• i=2, T=8.500000e-10, candidate=1:4, delta=4, u=8.953473e-01, accept=NO, x=0, E=0, best=0:0
• i=3, T=7.225000e-10, candidate=0:0, delta=0, u=-, accept=YES, x=0, E=0, best=0:0
• i=4, T=6.141250e-10, candidate=0:0, delta=0, u=-, accept=YES, x=0, E=0, best=0:0
• i=5, T=5.220062e-10, candidate=0:0, delta=0, u=-, accept=YES, x=0, E=0, best=0:0
• i=6, T=4.437053e-10, candidate=0:0, delta=0, u=-, accept=YES, x=0, E=0, best=0:0
• i=7, T=3.771495e-10, candidate=1:4, delta=4, u=4.550459e-01, accept=NO, x=0, E=0, best=0:0
• i=8, T=3.205771e-10, candidate=0:0, delta=0, u=-, accept=YES, x=0, E=0, best=0:0
• i=9, T=2.724905e-10, candidate=0:0, delta=0, u=-, accept=YES, x=0, E=0, best=0:0
• i=10, T=2.316169e-10, candidate=1:4, delta=4, u=3.598873e-03, accept=NO, x=0, E=0, best=0:0
• i=11, T=1.968744e-10, candidate=0:0, delta=0, u=-, accept=YES, x=0, E=0, best=0:0
• i=12, T=1.673432e-10, candidate=1:4, delta=4, u=6.372478e-01, accept=NO, x=0, E=0, best=0:0
• cooled: COOLED, current=0:0, best=0:0
• evaluations=2, accepted=0, uphill=0, rejected=1, changed=0, rng_draws=2, next_T=5.000000e-01, rng_state=306501167
• i=0, x=0, E=0
• i=1, T=1.000000e+00, candidate=1:4, delta=4, u=1.427257e-01, accept=NO, x=0, E=0, best=0:0
• evaluation cap: EVAL_LIMIT, current=2:1, best=0:0
• evaluations=3, accepted=2, uphill=1, rejected=0, changed=2, rng_draws=3, next_T=3.612500e+00, rng_state=1102988074
• i=0, x=0, E=0
• i=1, T=5.000000e+00, candidate=1:4, delta=4, u=1.427257e-01, accept=YES, x=1, E=4, best=0:0
• i=2, T=4.250000e+00, candidate=2:1, delta=-3, u=-, accept=YES, x=2, E=1, best=0:0
• zero steps: STEP_LIMIT, current=0:0, best=0:0
• evaluations=1, accepted=0, uphill=0, rejected=0, changed=0, rng_draws=0, next_T=5.000000e+00, rng_state=84
• i=0, x=0, E=0
• zero budget: EVAL_LIMIT, current=NONE, best=NONE
• evaluations=0, accepted=0, uphill=0, rejected=0, changed=0, rng_draws=0, next_T=5.000000e+00, rng_state=84
• singleton: STEP_LIMIT, current=0:7, best=0:7
• evaluations=3, accepted=2, uphill=0, rejected=0, changed=0, rng_draws=2, next_T=3.612500e+00, rng_state=306501167
• i=0, x=0, E=7
• i=1, T=5.000000e+00, candidate=0:7, delta=0, u=-, accept=YES, x=0, E=7, best=0:7
• i=2, T=4.250000e+00, candidate=0:7, delta=0, u=-, accept=YES, x=0, E=7, best=0:7
• temperature stall: TEMP_STALLED, current=0:7, best=0:7
• evaluations=2, accepted=1, uphill=0, rejected=0, changed=0, rng_draws=1, next_T=4.940656e-324, rng_state=4054764
• i=0, x=0, E=7
• i=1, T=4.940656e-324, candidate=0:7, delta=0, u=-, accept=YES, x=0, E=7, best=0:7
• checks = PASS

Complexity, Correctness, and Invariants

Let $I$ be completed proposal decisions, $C_q$ proposal-generation cost, $C_E$ objective-evaluation cost, and $C_s$ the cost of applying or copying a state. The core runtime is $O(I(C_q+C_E+C_s+1))$ plus one initial evaluation; unlike steepest descent, a decision does not scan every neighbor. If objective differences can be computed incrementally, charge their actual cost and verify that cached energy stays consistent.

For this table adapter, input validation and copying take $O(n)$, proposals and lookups take constant time, and each decision uses at most two fixed-width random updates plus one logarithm. In the usual machine-arithmetic cost model, actual runtime is $O(n+I)$, and the retained history makes additional space $O(n+I)$. Without logging, the active annealing state is constant-size beyond the energy representation. General configurations and their saved best copies can be much larger.

The requested proposal cap $K$ and evaluation budget $B$ give $I\le\min(K,\max(0,B-1))$ once initialization is accounted for. In exact geometric cooling, with $T_0\ge T_{\min}\gt0$, the number of proposals whose temperatures are at least the floor is

$$J=\left\lfloor\frac{\log(T_{\min}/T_0)}{\log\alpha}\right\rfloor+1.$$

So the ideal floor also bounds $I$ by $J$. The code checks actual successive binary64 products and can stop earlier on rounded stagnation; it does not use the logarithmic formula to choose its iteration count.

Best, average, worst. A zero-budget request performs no objective evaluations but still validates/copies the input. An initialized zero-step request performs one evaluation. For a fixed executed decision count, this adapter's work is linear regardless of acceptances, with one extra draw/logarithm on uphill trials. There is no distribution-free average time to reach a global optimum. In the worst finite run, every allowed proposal is used and the best found state can still be suboptimal. Counters bound search work, not the elapsed time of an expensive evaluator.

The implementation invariants. Current is always a feasible state with its exact cached energy. Every candidate is feasible; a non-worsening candidate is accepted, and an uphill candidate is accepted exactly when the implemented log comparison passes. Rejection changes neither current nor its cached energy. Best energy equals the smallest energy evaluated so far and never increases: any candidate better than best is also better than current and is therefore accepted, while a rejected uphill candidate cannot improve best. Cooling advances once per completed proposal, independent of acceptance. These invariants justify the result and accounting; they do not make current energy monotone or prove global convergence.

Why symmetry appears in the theory. Under ideal independent random draws, exact comparisons, and a fixed positive temperature, define the Boltzmann weights

$$\pi_T(x)=\frac{\exp(-E(x)/T)}{Z_T},\qquad Z_T=\sum_{s\in S}\exp(-E(s)/T).$$

For symmetric $q$, the off-diagonal probability flow satisfies

$$\pi_T(x)q(y\mid x)a_T(x,y)=\frac{q(y\mid x)}{Z_T}\min\bigl(\exp(-E(x)/T),\exp(-E(y)/T)\bigr),$$

which is unchanged when $x$ and $y$ are exchanged. This is detailed balance. For a connected finite state graph with appropriate aperiodicity, the fixed-temperature chain has this stationary distribution. The clamped proposal on the finite line is connected and has boundary self-proposals, giving aperiodicity in that ideal model. No partition function is computed by the code.

As $T$ tends to zero, the mathematical equilibrium distribution concentrates on global minima, but a cooling chain is not automatically at equilibrium at each temperature. Global convergence results require additional hypotheses and sufficiently slow cooling. Classical finite-state results include logarithmic schedules $T_k=c/\log(k+k_0)$ with a sufficiently large, landscape-dependent barrier constant. A short geometric schedule, a positive floor, finite random precision, and a finite budget do not inherit that asymptotic guarantee. In particular, repeated rejection does not prove that no improving neighbor exists, because the algorithm samples one proposal rather than completing a neighborhood scan.

Variants, Pitfalls, and Optimizations

Keep the energy sign consistent. Here lower is better and $\Delta E=E_{\mathrm{candidate}}-E_{\mathrm{current}}$. The uphill exponent is negative. Using $\exp(+\Delta E/T)$ makes uphill values exceed one and reverses the intended preference. For maximizing a score $f$, one consistent transformation is $E=-f$, which gives uphill-energy acceptance $\exp(\Delta f/T)$ when $\Delta f\lt0$.

Return best, not merely the last state. In the worked run, current ends at energy $1$ despite having visited $-5$. Preserve the incumbent separately, and copy it safely if states are mutable. An in-place proposal must also be undone on rejection, including all cached deltas, feasibility metadata, and random-key bookkeeping. The sample avoids that mutation problem by evaluating an integer candidate before assigning current.

Do not silently change proposal symmetry. On three indices, choosing uniformly among only valid adjacent neighbors gives $q(1\mid0)=1$ but $q(0\mid1)=1/2$. Even on a flat energy table, that walk does not have a uniform stationary distribution. The code instead leaves half the endpoint proposals as self-proposals, making the off-diagonal probabilities symmetric. For a general asymmetric proposal, the Boltzmann-target Metropolis-Hastings rule is

$$a_T(x,y)=\min\left(1,\exp(-\Delta E/T)\frac{q(x\mid y)}{q(y\mid x)}\right),$$

with the required proposal support and model assumptions. Resampling until feasible or applying a many-to-one repair can change those probabilities. A heuristic may still explore with such a proposal, but the simple symmetric-proposal stationary-distribution argument no longer follows automatically.

Numerical stability and random resolution are separate issues. Log space avoids explicitly underflowing the exponential. It cannot create arbitrarily small random draws: this teaching generator's acceptance values are $z/P$, so the smallest is $1/P\approx4.66\times10^{-10}$. An uphill acceptance probability below that cannot pass a draw in this implementation, even though the ideal continuous-uniform rule assigns a positive chance. Finite precision also affects logs and the final comparison near a threshold. Use a suitable higher-resolution random source and precision policy when those effects matter; reproducibility tests do not establish independent sampling.

Choose and scale temperatures deliberately. If a representative uphill change is $d\gt0$ and a desired initial acceptance is $p_0\in(0,1)$, the ideal calibration is $T_0=-d/\log p_0$. Adding a constant to all energies leaves acceptance unchanged; multiplying energies by a positive constant requires scaling temperatures by the same constant to preserve the ratios. Excessive initial temperature may spend most time wandering, while a very low start or rapid cooling can trap the chain. The cold fixture at $T_0=10^{-9}$ never leaves the initial basin in its twelve decisions.

Cooling is a policy, not a proof. Geometric schedules are convenient finite heuristics. Multiple proposals at each temperature, reheating, independent restarts, adaptive proposals, and logarithmic cooling are different policies with different assumptions and costs. Count rejected proposals in the cooling clock if that is the chosen schedule. Do not accept a temperature of zero and divide by it; the implementation requires a positive floor and reports both underflow-driven cooling and rounded temperature stalls honestly.

The objective and constraints must remain meaningful. Proposals should preserve feasibility or use an explicitly analyzed feasibility policy. A penalty objective does not automatically make the returned incumbent feasible for hard constraints. Noisy energy estimates can corrupt both acceptance and the best-ever comparison; the deterministic exact-energy reasoning then needs replacement. Likewise, a tiny energy change or a long rejection streak is not a general certificate of convergence.

Practice Problems and Real-World Use

Start with the six-state energy table and compare each acceptance against an independent high-precision probability calculation. Record rejected proposals as well as accepted moves, verify the current-state cache, and check that the incumbent never becomes worse. Include negative energies, equal moves to different states, boundary self-proposals, zero budgets, exact budget exhaustion, underflow, and temperature stagnation.

The programs were checked on 8,592 inputs per language: $8{,}565$ valid cases and $27$ invalid requests. The corpus includes $6{,}564$ exhaustive combinations of energy arrays over $\{-1,0,1\}$ of lengths $1$ through $5$, every starting state, two seeds, and two starting temperatures, plus randomized and boundary fixtures. An independent oracle used jump-ahead modular RNG values, high-precision exponential comparisons, and exact rational temperature products. It checked $131{,}395$ temperature updates and incumbent-preservation steps, $52{,}492$ high-precision acceptance comparisons, and $11{,}814$ safely rejected large-ratio trials; it observed $9{,}320$ accepted uphill proposals. Separately, $22{,}959$ ideal transition-matrix entries were checked for proposal symmetry and detailed balance. Python, C++, and Java matched all outcomes, complete histories, counters, raw RNG states, and binary64 temperatures on the corpus and repeated runs, preserved inputs, and the C++ corpus passed address/undefined-behavior instrumentation.

For primary background, see Carnegie Mellon's simulated-annealing notes. For the distinction between practical cooling and asymptotic global convergence, see Bruce Hajek's paper on cooling schedules. The exact proposal, draw-consumption rules, schedule, finite-precision limitations, resource contract, and trace in this lesson are specified directly here.