Simulated annealing¶

SimulatedAnnealing walks the space of giant tours with random 2-opt, Or-opt and swap proposals: a downhill move is always accepted, an uphill move with probability exp(-delta / T), and the temperature cools geometrically from t0 (calibrated on the initial tour by default) down to t_min. One outer iteration is one temperature level of n_moves proposals; history_ records the best cost seen after every level and the best tour lives in its own buffer, so fit never returns a tour that does not match its cost.

The same estimator solves plain symmetric TSPs (O(1) move deltas), asymmetric matrices and the multi-trip objective (full evaluation of every proposal under the chosen split rule). All randomness comes from random_state: the same seed on the same machine gives bit-identical results, and MultiStart runs several seeds in parallel.

>>> from skroute import SimulatedAnnealing
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")
>>> sa = SimulatedAnnealing(random_state=0).fit(wi.distance_matrix(), labels=wi.labels)
>>> sa.cost_ / wi.optimal_tour_length < 1.03
True

SimulatedAnnealing ¶

SimulatedAnnealing(t0: float | str = 'auto', t_min: float | str = 'auto', alpha: float = 0.995, n_moves: int | None = None, moves: tuple[str, ...] | str = ('two_opt', 'or_opt', 'swap'), patience: int | None = None, init: Any = 'nearest_neighbour', time_limit: float | None = None, random_state: Any = None, verbose: int = 0)

Bases: BaseRouter

Simulated annealing over the giant tour with 2-opt, Or-opt and swap proposals.

One outer iteration is one temperature level of n_moves Metropolis proposals; the temperature then cools geometrically (T *= alpha) until it drops below t_min. Every proposal is a random move drawn uniformly from moves: a downhill move is always accepted, an uphill move with probability exp(-delta / T). The best tour seen is kept in its own buffer and is what fit returns; history_ records its cost per level.

Parameters:

Name	Type	Description	Default
`t0`	`float > 0 or 'auto'`	Initial temperature (finite). `"auto"` prices 1000 random proposals on the initial tour and sets `t0 = -median(uphill deltas) / ln(0.5)`, so the median uphill move is accepted with probability one half at the start (`t0 = 1.0` if no proposal goes uphill).	`"auto"`
`t_min`	`float > 0 or 'auto'`	Final temperature (finite); the search stops (`"converged"`) once `T < t_min`. `"auto"` is `1e-4 * t0`, i.e. about `ln(1e4) / -ln(alpha)` levels (1838 at the default `alpha`); a `t0` so small that `1e-4 * t0` underflows to zero is rejected.	`"auto"`
`alpha`	`float in (0, 1)`	Geometric cooling factor applied after every level.	`0.995`
`n_moves`	`int >= 1 or None`	Proposals per temperature level; `None` means `10 * n`. An invalid random draw (see Notes) is a rejected proposal and counts towards `n_moves`.	`None`
`moves`	`tuple of {"two_opt", "or_opt", "swap"}`	The move types proposed, each with the same probability; a name must not repeat. A single name is accepted.	`("two_opt", "or_opt", "swap")`
`patience`	`int >= 1 or None`	Levels without improvement of the best-so-far before stopping (`"patience"`). The count starts only once the current cost has first fallen below the initial cost: with `t0="auto"` the hot phase is non-improving by design (the current cost first drops below a nearest-neighbour start after several hundred levels on the Waterloo instances), so a small patience applied from level 0 would return the start tour. `None` disables the rule.	`None`
`init`	`('nearest_neighbour', 'random')`	Starting tour: the greedy nearest-neighbour construction, a random permutation, or the `tour_`/`route_` of another solver (labels; the depot may repeat).	`"nearest_neighbour"`
`time_limit`	`float > 0 or None`	Wall-clock budget in seconds, checked once per level (`"time_limit"`). Breaks bit-exact reproducibility across machines; `None` disables.	`None`
`random_state`	`(int, Generator or None)`	Seed of every random draw. The same seed on the same machine gives bit-identical results; a passed `Generator` is advanced by the fit.	`None`
`verbose`	`int`	`0` is silent; `1` logs every `max(1, n_levels // 10)` levels at INFO; `2` logs every level. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`

Attributes:

Name	Type	Description
`t0_`	`float`	The initial temperature actually used (the calibrated value under `t0="auto"`).
`history_`	`ndarray of shape (n_iter_,), float64`	Best-so-far cost after each temperature level (monotone non-increasing); `history_[-1]` equals `cost_` exactly.
`n_iter_`	`int`	Temperature levels run.
`stop_reason_`	`{'converged', 'patience', 'time_limit', 'callback'}`	Why the search stopped (`"callback"`: the `callback` of `fit` returned `True`).
See `BaseRouter` for ``tour_``, ``route_``, ``trips_``, ``cost_`` and
`the other fitted attributes shared by every solver.`

Notes

Algorithm. Per level the randomness is pre-drawn in Python (u ~ U[0, 1), ri, rj ~ U{1..n-1}, mv ~ U{moves}) and handed to a nogil kernel (D10). The draw -> move mapping is fixed: 2-opt and swap use i, j = min(ri, rj), max(ri, rj) and are invalid when i == j; Or-opt moves the segment tour[i..i+L-1] with i = ri, L = 1 + (rj % 3) after the node at position j = rj (never reversed) and is invalid when the segment leaves the tour (i + L - 1 > n - 1) or j in [i-1, i+L-1]. An invalid draw is a rejected proposal: it consumes its u and changes nothing, so n_moves means "proposals per level" everywhere.

Two evaluation paths. On a symmetric plain TSP every proposal is priced with the O(1) deltas of the core and applied in place; under a budget (multi-trip) or with an asymmetric matrix the move is applied on a scratch copy and priced with the full objective (O(n) per proposal, O(n L) under split="optimal"), so the search sees the decoded trips and their fixed charges. The best tour is a separate buffer written only on strict improvement (new < best - 1e-9 * max(1, |best|)).

Complexity. O(levels * n_moves) proposals; with the defaults about 1838 * 10 n O(1) evaluations for a symmetric TSP, O(n) each otherwise.

Callback events (D30). "start" carries the init tour with extra["temperature"] equal to t0_; every level emits one "iteration" whose tour is the walker and best_tour the best buffer, with extra keys temperature (the level's), accepted (proposals accepted in the level) and n_moves.

Supports: symmetric and asymmetric matrices, the multi-trip objective (both split rules); stochastic, iterative, budget-aware.

References

.. [1] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, "Optimization by simulated annealing", Science 220 (1983) 671-680. .. [2] D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization", in Local Search in Combinatorial Optimization, Wiley, 1997.

Examples:

>>> import numpy as np
>>> from skroute import SimulatedAnnealing
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")
>>> sa = SimulatedAnnealing(random_state=0).fit(wi.distance_matrix(), labels=wi.labels)
>>> sa.cost_ / wi.optimal_tour_length < 1.03  # the fast-tier tolerance of SPEC §6
True
>>> int(sa.route_[0]) == int(sa.route_[-1]) == int(sa.depot_) == 1
True
>>> sa.n_iter_ == len(sa.history_) and sa.stop_reason_ == "converged" and sa.t0_ > 0
True
>>> bool(np.all(np.diff(sa.history_) <= 0))  # best-so-far per level
True

A multi-trip instance: eight Spanish towns, a per-trip budget and a fixed charge per extra trip, two people. The search itself prices the decoded trips.

>>> from skroute.datasets import load_alicante_murcia
>>> d = load_alicante_murcia()
>>> budget = 1.5 * float((d.time[0] + d.time[:, 0]).max())
>>> sa = SimulatedAnnealing(random_state=0).fit(
...     d.cost,
...     time_matrix=d.time,
...     labels=d.labels,
...     depot=d.depot,
...     max_time_work=budget,
...     extra_cost=10.0,
...     people=2,
... )
>>> bool(np.all(sa.trip_times_ <= budget)) and sa.n_trips_ == len(sa.trips_)
True