Ant colony¶

AntColony is a MAX–MIN Ant System (Stützle & Hoos, 2000). Every iteration a colony of n_ants ants builds tours from the depot: at each step an ant picks the next node by a roulette wheel over the unvisited nodes of its n_candidates nearest-neighbour list (all unvisited nodes once the list is exhausted), weighting node j by tau[i, j] ** alpha * (1 / C[i, j]) ** beta. Each tour is polished by the descents listed in local_search (2-opt by default) and priced with the problem objective, so a working-time budget steers the colony. The pheromone then evaporates (rho) and the iteration-best ant — the best-so-far ant every fifth iteration — deposits 1 / cost on its arcs; the trail is clipped to [tau_max / (2 n), tau_max] with tau_max = 1 / (rho * L_best), which keeps the colony from stagnating.

The trail is stored as an (n, n) matrix (pheromone_ after the fit); the heuristic desirability (1 / C) ** beta and the transition weights, recomputed once per iteration, are two more (n, n) matrices — three float64 matrices besides the cost matrix, all updated in place — so the practical ceiling is a few thousand nodes. On an asymmetric matrix the trail is directional. Zero off-diagonal costs (coincident points) are floored to a thousandth of the smallest positive cost in the heuristic, and the same floor bounds every 1 / L of the trail, so an instance whose optimum is a zero-cost tour is returned with a finite trail.

>>> from skroute import AntColony
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")
>>> aco = AntColony(random_state=0).fit(wi.distance_matrix(), labels=wi.labels)
>>> aco.cost_ / wi.optimal_tour_length < 1.08
True
>>> int(aco.route_[0]) == int(aco.route_[-1]) == 1
True

AntColony ¶

AntColony(n_ants: int | None = None, alpha: float = 1.0, beta: float = 2.0, rho: float = 0.02, n_iter: int = 200, n_candidates: int | None = 20, local_search: Any = ('two_opt',), patience: int | None = 50, time_limit: float | None = None, random_state: Any = None, verbose: int = 0)

Bases: BaseRouter

MAX-MIN Ant System (MMAS) over candidate lists, with an optional local-search polish per ant.

Every iteration n_ants ants build a tour from the depot by a roulette wheel over the unvisited candidates of their current node; each tour is optionally polished by the listed descents and priced with the problem objective (plain, greedy-split or optimal-split cost), then the pheromone evaporates and the iteration-best ant — the global-best one every fifth iteration — deposits 1 / cost on its arcs. The trail is kept inside [tau_min, tau_max] so the colony never stagnates completely.

Parameters:

Name	Type	Description	Default
`n_ants`	`int >= 1 or None`	Ants per iteration; `None` means `min(n, 50)`.	`None`
`alpha`	`float >= 0`	Exponent of the pheromone in the transition weights `tau ** alpha * (1 / C) ** beta`.	`1.0`
`beta`	`float >= 0`	Exponent of the heuristic desirability `1 / C`.	`2.0`
`rho`	`float in (0, 1)`	Evaporation rate: `tau = 1 - rho` every iteration; also scales the trail bounds `tau_max = 1 / (rho L_best)` and `tau_min = tau_max / (2 n)`.	`0.02`
`n_iter`	`int >= 1`	Maximum number of iterations (outer iterations).	`200`
`n_candidates`	`int >= 1 or None`	Size of the nearest-neighbour candidate lists the ants choose from (all unvisited nodes once a list is exhausted); `None` uses the full neighbourhood.	`20`
`local_search`	`None, str or tuple of {"two_opt", "or_opt"}`	Polish applied to every ant's tour: the listed descents run to convergence with the same candidate lists (the full-evaluation generic descent under a budget or on an asymmetric matrix). A single string is a 1-tuple; `None` disables the polish.	`("two_opt",)`
`patience`	`int >= 1 or None`	Iterations without improvement of the best-so-far before stopping; `None` disables.	`50`
`time_limit`	`float > 0 or None`	Wall-clock budget in seconds, checked once per iteration. Breaks bit-exact reproducibility (the stopping iteration depends on the machine).	`None`
`random_state`	`(None, int or Generator)`	Seed of the generator; one uniform per construction step is pre-drawn per iteration (D10).	`None`
`verbose`	`int`	0 is silent; 1 logs every `max(1, n_iter // 10)` iterations; 2 logs every iteration. 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
`history_`	`ndarray of shape (n_iter_,), float64`	Best-so-far objective after each iteration (non-increasing).
`n_iter_`	`int`	Iterations actually run.
`stop_reason_`	`{'max_iter', 'patience', 'time_limit', 'callback'}`	Why the search stopped (`"callback"`: the `callback` of `fit` returned `True`).
`pheromone_`	`ndarray of shape (n, n), float64`	The trail matrix at the end of the search (index space, matrix row order).
See `BaseRouter` for ``tour_``, ``route_``, ``trips_``, ``cost_`` and the
`other fitted attributes shared by every solver.`

Notes

The trail starts at 1 / (rho * L_NN) with L_NN the objective of the nearest-neighbour tour; the bounds follow the best-so-far cost. Transition weights are computed once per iteration as a dense (n, n) matrix, so an iteration costs O(n^2 + n_ants * n * k) plus the polish (O(n k) per ant on a symmetric plain instance, more under a budget or on an asymmetric matrix where every move is re-evaluated in O(n)). Memory: three (n, n) float64 matrices besides the cost matrix — the heuristic desirability (1 / C) ** beta, the trail (pheromone_) and the transition weights, all updated in place — plus the transient copy RoutingProblem.neighbours makes.

Zero off-diagonal costs (coincident points) are floored to a thousandth of the smallest positive cost in the heuristic; the same floor bounds every 1 / L of the trail, so a zero-cost tour (all nodes coincident, a zero-cost cycle) is returned with a finite trail.

Callback events (D30, D31): "start" has no tour (the nearest-neighbour tour only seeds the trail) and carries extra["n_ants"]; every iteration emits one "iteration" whose tour is the iteration-best ant and best_tour the colony's best, with the extra keys n_ants, iteration_best (the ant's cost), deposit ("global" or "iteration": whose tour reinforced the trail), edges — the strongest min(3 n, n (n - 1) / 2) trails after the update as (label, label) pairs, strongest first (upper triangle only on a symmetric matrix; on an asymmetric one every arc competes and the cap is min(3 n, n (n - 1))) — and edge_weights, parallel to edges, each trail divided by the current tau_max so the values lie in (0, 1] (the bound itself is 1). Selecting the trails is O(n²) per iteration and happens only when a callback is set.

Supports: symmetric and asymmetric matrices (the trail is directional on the latter), multi-trip objective; stochastic, iterative, budget-aware.

References

.. [1] T. Stützle and H. H. Hoos, "MAX-MIN Ant System", Future Generation Computer Systems 16(8), 2000, 889-914. .. [2] M. Dorigo and T. Stützle, Ant Colony Optimization, MIT Press, 2004.

Examples:

>>> from skroute import AntColony
>>> from skroute.datasets import load_tsp
>>> dj = load_tsp("dj38")  # Djibouti, optimum 6656
>>> C = dj.distance_matrix()
>>> aco = AntColony(random_state=0).fit(C, labels=dj.labels)
>>> aco.cost_ / dj.optimal_tour_length < 1.08  # the fast-tier tolerance of §6
True
>>> int(aco.route_[0]) == int(aco.route_[-1]) == int(aco.depot_) == 1
True
>>> aco.n_iter_ == len(aco.history_) and aco.stop_reason_ in {"patience", "max_iter"}
True
>>> aco.pheromone_.shape == (38, 38)
True