Ensembles¶

skroute.ensemble runs a stochastic solver several times from independent seeds and keeps the best tour. The general tool is MultiStart(estimator, n_restarts=10, n_jobs=None): it clones the estimator once per restart, seeds every clone from a child of one numpy.random.SeedSequence, fits the clones on the shared RoutingProblem through joblib.Parallel and returns the cheapest result (ties go to the lowest restart index). The winner is the same for any n_jobs and backend, because the seeds are assigned by restart index before anything runs — random_state alone reproduces a run.

Threads are the default (prefer="threads"): the Cython kernels release the GIL and a large cost matrix is never pickled once per worker. They give a near-linear speed-up for SimulatedAnnealing, IteratedLocalSearch and TabuSearch and little for the Python-heavy Genetic and SOM; prefer="processes" is one keyword away and gives identical results. The tags of a MultiStart are its estimator's with kind="ensemble": wrapping a budget-aware solver keeps the multi-trip objective inside the search, wrapping SOM still needs coords=. A deterministic estimator is refused (ValueError), and MultiStart is not returned by all_solvers() because it needs an estimator.

EnsembleGenetic and EnsembleSimulatedAnnealing are the 1.0 ensembles kept as explicit-parameter wrappers over MultiStart (n_genetics / n_simulateds restarts, the inner knobs keyword-only with the 2.0 defaults). They return exactly what the equivalent MultiStart(Genetic(...)) / MultiStart(SimulatedAnnealing(...)) returns and will be removed in 3.0; new code should use MultiStart directly.

>>> import numpy as np
>>> from skroute import MultiStart, SimulatedAnnealing, EnsembleSimulatedAnnealing
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")  # Western Sahara, optimum 27603
>>> C = wi.distance_matrix()
>>> ms = MultiStart(SimulatedAnnealing(), n_restarts=4, random_state=0).fit(C, labels=wi.labels)
>>> ms.cost_ / wi.optimal_tour_length < 1.03  # the fast-tier tolerance of the wrapped solver
True
>>> len(ms.estimators_), ms.best_estimator_ is ms.estimators_[ms.best_index_]
(4, True)
>>> parallel = MultiStart(SimulatedAnnealing(), n_restarts=4, n_jobs=2, random_state=0).fit(C, labels=wi.labels)
>>> bool(np.array_equal(parallel.tour_, ms.tour_))  # the result never depends on n_jobs
True
>>> legacy = EnsembleSimulatedAnnealing(n_simulateds=4, random_state=0).fit(C, labels=wi.labels)
>>> bool(np.array_equal(legacy.tour_, ms.tour_))  # the wrapper is the MultiStart it builds
True
>>> ms.set_params(estimator__alpha=0.99).estimator.alpha  # inner knobs through the estimator__ prefix
0.99

MultiStart ¶

MultiStart(estimator: BaseRouter, n_restarts: int = 10, n_jobs: int | None = None, prefer: str | None = 'threads', random_state: Any = None, verbose: int = 0)

Bases: BaseRouter

Run a stochastic solver from n_restarts independent seeds and keep the best tour.

Every restart is a clone of estimator whose random_state is a numpy.random.Generator seeded from a child of one numpy.random.SeedSequence, so the restarts are statistically independent and the whole run is reproducible from random_state alone. The restarts are fitted on the shared RoutingProblem through joblib.Parallel; the result (which restart wins and its tour) is identical for any n_jobs and backend, because the seeds are assigned by restart index before anything runs.

Parameters:

Name	Type	Description	Default
`estimator`	`BaseRouter`	An unfitted stochastic solver (one with a `random_state` parameter). A deterministic estimator is refused at fit time with `ValueError`: restarting it would return the same tour `n_restarts` times.	required
`n_restarts`	`int >= 1`	Number of independent restarts (outer iterations).	`10`
`n_jobs`	`int or None`	Workers for `joblib.Parallel`: `None` runs the restarts one after another (unless an enclosing `joblib.parallel_config` says otherwise), `-1` uses every CPU, a positive int that many workers. Never changes the result. With a `callback` and `n_jobs` `None` or `1` the restarts run sequentially in the calling thread whatever an enclosing `parallel_config` says, so the callback is never invoked from a worker thread.	`None`
`prefer`	`('threads', 'processes')`	joblib backend hint. Threads are the default because the solver kernels release the GIL and a large cost matrix (900 MB at n = 10 639) must not be pickled once per worker; they give a near-linear speed-up for `SimulatedAnnealing`, `IteratedLocalSearch` and `TabuSearch` and little for the Python-heavy `Genetic` and `SOM`, for which `prefer="processes"` is one keyword away. `None` lets joblib choose.	`"threads"`
`random_state`	`(int, Generator or None)`	Seed of the restart seeds: one integer is drawn from it and spawns `n_restarts` child `SeedSequence` objects. The same seed on the same machine gives bit-identical results whatever `n_jobs`; a passed `Generator` is advanced by the fit.	`None`
`verbose`	`int`	`0` is silent; `1` logs every `max(1, n_restarts // 10)` finished restarts and a summary at INFO; `2` logs every restart. 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
`estimators_`	`list of BaseRouter`	The `n_restarts` fitted clones, in restart order.
`costs_`	`ndarray of shape (n_restarts,), float64`	`cost_` of every restart.
`best_index_`	`int`	Index of the winning restart (the lowest index on a tie).
`best_estimator_`	`BaseRouter`	`estimators_[best_index_]`; its `tour_` is the tour returned.
`history_`	`ndarray of shape (n_iter_,), float64`	Copied from `best_estimator_` when the estimator is iterative.
`n_iter_`	`int`	Copied from `best_estimator_` when the estimator is iterative.
`stop_reason_`	`str`	Copied from `best_estimator_` when the estimator is iterative; `"callback"` when the `callback` of `fit` stopped the ensemble (`estimators_` and `costs_` then hold only the restarts that ran).
See `BaseRouter` for ``tour_``, ``route_``, ``trips_``, ``cost_`` and
`the other fitted attributes shared by every solver.`

Notes

Tags delegate to the estimator's (budget_aware, requires_symmetric, requires_coords, iterative, max_nodes...) with kind="ensemble" and stochastic=True: a MultiStart of a budget-aware solver is budget-aware, a MultiStart of SOM still needs coordinates.

Seeding (D10, D17). seed = rng.integers(2**63 - 1); restart k receives np.random.default_rng(np.random.SeedSequence(seed).spawn(n_restarts)[k]). The base class recomputes cost_ from the winning tour (D2) and copies nothing else from the inner solvers except the three iterative attributes.

Parameter protocol. get_params(deep=True) exposes the inner knobs as estimator__<name>; set_params(estimator__alpha=0.99) reaches them; clone copies the estimator; repr prints it.

Callback events (D30). MultiStart emits "start" (no tour, extra["n_restarts"]) and "end" (iteration = the winning restart's n_iter_) under its own name. When n_jobs is None or 1 the restarts run one after another in the calling thread, whatever an enclosing joblib.parallel_config says, and every event of every inner fit is forwarded to the callback under the inner class's name with extra["restart"] (the restart index); a True answer stops the running restart and no further restart is launched (a True at the outer "start" lets exactly one restart run). Parallel runs (any other n_jobs) forward nothing and a True answer to the two outer events changes nothing: the drawing libraries behind the usual callbacks are not thread-safe. Wrapping a wrapper (a MultiStart of a MultiStart or of an Ensemble) is legal but pointless — it equals one MultiStart with more restarts — and the forwarded events then carry the outermost restart index only.

Supports: whatever the estimator supports; stochastic; iterative iff the estimator is.

Examples:

>>> import numpy as np
>>> from skroute import MultiStart, SimulatedAnnealing
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")  # Western Sahara, optimum 27603
>>> ms = MultiStart(SimulatedAnnealing(), n_restarts=4, random_state=0)
>>> ms = ms.fit(wi.distance_matrix(), labels=wi.labels)
>>> ms.cost_ / wi.optimal_tour_length < 1.03  # the fast-tier tolerance of the wrapped solver
True
>>> len(ms.estimators_), ms.costs_.shape, ms.cost_ == float(ms.costs_.min())
(4, (4,), True)
>>> ms.best_estimator_ is ms.estimators_[ms.best_index_]
True
>>> int(ms.route_[0]) == int(ms.route_[-1]) == int(ms.depot_) == 1
True
>>> ms.n_iter_ == len(ms.history_) and ms.stop_reason_ == "converged"
True

The result does not depend on the number of workers:

>>> C = wi.distance_matrix()
>>> a = MultiStart(SimulatedAnnealing(), n_restarts=4, n_jobs=1, random_state=0).fit(C)
>>> b = MultiStart(SimulatedAnnealing(), n_restarts=4, n_jobs=2, random_state=0).fit(C)
>>> bool(np.array_equal(a.tour_, b.tour_)) and a.best_index_ == b.best_index_
True

The inner knobs are reachable with the estimator__ prefix:

>>> ms.set_params(estimator__alpha=0.99).estimator.alpha
0.99
>>> ms
MultiStart(estimator=SimulatedAnnealing(alpha=0.99), n_restarts=4, random_state=0)

EnsembleGenetic ¶

EnsembleGenetic(n_genetics: int = 10, n_jobs: int | None = None, random_state: Any = None, verbose: int = 0, *, pop_size: int = 100, n_generations: int = 500, crossover: str = 'ox', p_crossover: float = 0.9, mutation: str = 'inversion', p_mutation: float = 0.2, tournament_size: int = 3, n_elite: int = 2, local_search: Any = None, patience: int | None = 100, init: Any = 'nearest_neighbour', time_limit: float | None = None)

Bases: _EnsembleBase

n_genetics independent Genetic runs in parallel; the best wins.

.. deprecated:: 2.0 Kept for 1.0 users (skroute.metaheuristics.genetics.EnsembleGenetic); it is a thin wrapper over MultiStart(Genetic(...), n_restarts=n_genetics) and will be removed in 3.0. New code should use MultiStart directly. No warning is emitted at runtime.

Parameters:

Name	Type	Description	Default
`n_genetics`	`int >= 1`	Number of independent genetic runs (the `n_restarts` of `MultiStart`).	`10`
`n_jobs`	`int or None`	Workers for `joblib.Parallel` (threads); `None` runs the runs one after another, `-1` uses every CPU. Never changes the result.	`None`
`random_state`	`(int, Generator or None)`	Seed of the run seeds. The same seed on the same machine gives bit-identical results whatever `n_jobs`; a passed `Generator` is advanced by the fit.	`None`
`verbose`	`int`	`0` is silent; `1` logs the finished runs and a summary at INFO; `2` logs every run. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`
`pop_size`	`int >= 2`	Individuals per generation of every run.	`100`
`n_generations`	`int >= 1`	Maximum number of generations of every run.	`500`
`crossover`	`('ox', 'pmx')`	Permutation crossover.	`"ox"`
`p_crossover`	`float in [0, 1]`	Probability that a child is produced by crossover.	`0.9`
`mutation`	`('inversion', 'swap', 'insertion')`	Mutation operator.	`"inversion"`
`p_mutation`	`float in [0, 1]`	Mutation probability per child.	`0.2`
`tournament_size`	`int >= 1`	Tournament size of the parent selection.	`3`
`n_elite`	`int >= 0`	Best parents copied unchanged into the next generation.	`2`
`local_search`	`None, str or tuple of {"two_opt", "or_opt"}`	Memetic polish applied to every child (`None` = plain genetic algorithm).	`None`
`patience`	`int >= 1 or None`	Generations without improvement before a run stops (`"patience"`).	`100`
`init`	`('nearest_neighbour', 'random')`	Starting individual of every run.	`"nearest_neighbour"`
`time_limit`	`float > 0 or None`	Wall-clock budget in seconds of every run (`"time_limit"`). Breaks bit-exact reproducibility across machines.	`None`

Attributes:

Name	Type	Description
`estimators_`	`list of Genetic`	The `n_genetics` fitted runs.
`costs_`	`ndarray of shape (n_genetics,), float64`	`cost_` of every run.
`best_index_`	`int`	Index of the winning run (the lowest index on a tie).
`best_estimator_`	`Genetic`	`estimators_[best_index_]`.
`history_`	`ndarray of shape (n_iter_,), float64`	Best-so-far cost per generation of the winning run.
`n_iter_`	`int`	Generations run by the winning run.
`stop_reason_`	`{'max_iter', 'patience', 'time_limit', 'callback'}`	Why the winning run stopped (`"callback"`: the `callback` of `fit` stopped the ensemble).
See `BaseRouter` for ``tour_``, ``route_``, ``trips_``, ``cost_`` and
`the other fitted attributes shared by every solver.`

Notes

Every knob after verbose is keyword-only and takes the 2.0 default of Genetic (1.0 defaulted to pop=400, gen=1000). The parameters are explicit so that get_params/set_params/clone work without a nested estimator; EnsembleGenetic(n_genetics=k, random_state=s, **knobs) returns exactly what MultiStart(Genetic(**knobs), n_restarts=k, random_state=s) returns.

Callback events (D30). "start" (no tour, extra["n_restarts"]) and "end" under this class's name, the inner MultiStart's own pair, and — when n_jobs is None or 1 — every event of every inner run under "Genetic" with extra["restart"]; a True answer stops the running restart and the launch of the next ones.

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

Examples:

>>> from skroute import EnsembleGenetic
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")  # Western Sahara, optimum 27603
>>> eg = EnsembleGenetic(n_genetics=4, random_state=0).fit(wi.distance_matrix(), labels=wi.labels)
>>> eg.cost_ / wi.optimal_tour_length < 1.15  # the fast-tier tolerance of the plain GA
True
>>> len(eg.estimators_) == 4 and eg.cost_ == float(eg.costs_.min())
True
>>> int(eg.route_[0]) == int(eg.route_[-1]) == int(eg.depot_) == 1
True
>>> eg.n_iter_ == len(eg.history_) and eg.stop_reason_ in {"patience", "max_iter"}
True

EnsembleSimulatedAnnealing ¶

EnsembleSimulatedAnnealing(n_simulateds: int = 10, n_jobs: int | None = None, random_state: Any = None, verbose: int = 0, *, 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)

Bases: _EnsembleBase

n_simulateds independent SimulatedAnnealing runs; the best wins.

.. deprecated:: 2.0 Kept for 1.0 users (skroute.metaheuristics.simulated_annealing.EnsembleSimulatedAnnealing); it is a thin wrapper over MultiStart(SimulatedAnnealing(...), n_restarts=n_simulateds) and will be removed in 3.0. New code should use MultiStart directly. No warning is emitted at runtime.

Parameters:

Name	Type	Description	Default
`n_simulateds`	`int >= 1`	Number of independent annealing runs (the `n_restarts` of `MultiStart`). 1.0 defaulted to 20.	`10`
`n_jobs`	`int or None`	Workers for `joblib.Parallel` (threads); `None` runs the runs one after another, `-1` uses every CPU. Never changes the result.	`None`
`random_state`	`(int, Generator or None)`	Seed of the run seeds. The same seed on the same machine gives bit-identical results whatever `n_jobs`; a passed `Generator` is advanced by the fit.	`None`
`verbose`	`int`	`0` is silent; `1` logs the finished runs and a summary at INFO; `2` logs every run. Records go to the `skroute` logger at INFO; enable them with `logging.basicConfig(level=logging.INFO)` or `skroute.set_log_level("INFO")`.	`0`
`t0`	`float > 0 or 'auto'`	Initial temperature of every run (`"auto"` calibrates it on the initial tour).	`"auto"`
`t_min`	`float > 0 or 'auto'`	Final temperature (`"auto"` is `1e-4 * t0`).	`"auto"`
`alpha`	`float in (0, 1)`	Geometric cooling factor.	`0.995`
`n_moves`	`int >= 1 or None`	Proposals per temperature level; `None` means `10 * n`.	`None`
`moves`	`tuple of {"two_opt", "or_opt", "swap"}`	Move types proposed.	`("two_opt", "or_opt", "swap")`
`patience`	`int >= 1 or None`	Levels without improvement before a run stops, counted once the current cost has fallen below the initial cost (`"patience"`); `None` disables.	`None`
`init`	`('nearest_neighbour', 'random')`	Starting tour of every run.	`"nearest_neighbour"`
`time_limit`	`float > 0 or None`	Wall-clock budget in seconds of every run (`"time_limit"`). Breaks bit-exact reproducibility across machines.	`None`

Attributes:

Name	Type	Description
`estimators_`	`list of SimulatedAnnealing`	The `n_simulateds` fitted runs.
`costs_`	`ndarray of shape (n_simulateds,), float64`	`cost_` of every run.
`best_index_`	`int`	Index of the winning run (the lowest index on a tie).
`best_estimator_`	`SimulatedAnnealing`	`estimators_[best_index_]`.
`history_`	`ndarray of shape (n_iter_,), float64`	Best-so-far cost per temperature level of the winning run.
`n_iter_`	`int`	Temperature levels run by the winning run.
`stop_reason_`	`{'converged', 'patience', 'time_limit', 'callback'}`	Why the winning run stopped (`"callback"`: the `callback` of `fit` stopped the ensemble).
See `BaseRouter` for ``tour_``, ``route_``, ``trips_``, ``cost_`` and
`the other fitted attributes shared by every solver.`

Notes

Every knob after verbose is keyword-only and takes the 2.0 default of SimulatedAnnealing (1.0 defaulted to temp=12.0, neighbours=250, delta=0.78, tol=1.29). EnsembleSimulatedAnnealing(n_simulateds=k, random_state=s, **knobs) returns exactly what MultiStart(SimulatedAnnealing(**knobs), n_restarts=k, random_state=s) returns.

Callback events (D30). "start" (no tour, extra["n_restarts"]) and "end" under this class's name, the inner MultiStart's own pair, and — when n_jobs is None or 1 — every event of every inner run under "SimulatedAnnealing" with extra["restart"]; a True answer stops the running restart and the launch of the next ones.

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

Examples:

>>> from skroute import EnsembleSimulatedAnnealing
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")  # Western Sahara, optimum 27603
>>> es = EnsembleSimulatedAnnealing(n_simulateds=4, random_state=0)
>>> es = es.fit(wi.distance_matrix(), labels=wi.labels)
>>> es.cost_ / wi.optimal_tour_length < 1.03  # the fast-tier tolerance of SimulatedAnnealing
True
>>> len(es.estimators_) == 4 and es.cost_ == float(es.costs_.min())
True
>>> int(es.route_[0]) == int(es.route_[-1]) == int(es.depot_) == 1
True
>>> es.n_iter_ == len(es.history_) and es.stop_reason_ == "converged"
True