Genetic algorithm¶

Genetic evolves a population of giant tours. A chromosome is the tour without its depot, so every individual is a valid solution and its fitness is the problem objective itself — the plain tour cost, or the greedy/optimal-split cost when a working-time budget is given, so the multi-trip objective steers the population directly.

Each generation keeps the n_elite fittest parents, then fills the population with children: two parents by tournament selection, a real permutation crossover ("ox", order crossover, or "pmx", partially mapped crossover — the 1.0 "crossover" was a rotation), a mutation ("inversion", "swap" or "insertion"), one more mutation if the child exactly duplicates an individual already in the new generation, and optionally the memetic polish local_search=("two_opt",) or ("two_opt", "or_opt"), which runs the descents of skroute.local_search to convergence on every child. The plain GA is the weakest metaheuristic of the library on large instances (≈ 19 % above the optimum on qa194 with the defaults); the memetic configuration is competitive with IteratedLocalSearch.

Every random quantity of a generation is drawn beforehand from random_state and handed to the nogil kernel, so a fit is bit-identical for a given seed on a given machine.

>>> from skroute import Genetic
>>> from skroute.datasets import load_tsp
>>> dj = load_tsp("dj38")
>>> ga = Genetic(local_search=("two_opt",), random_state=0).fit(dj.distance_matrix(), labels=dj.labels)
>>> ga.cost_ / dj.optimal_tour_length < 1.05
True
>>> ga.stop_reason_ in {"patience", "max_iter"}
True

A truncation ("top X %") selection, requested in issue #37, is planned for 2.1 as Genetic(selection="truncation").

Genetic ¶

Genetic(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, random_state: Any = None, verbose: int = 0)

Bases: BaseRouter

Genetic algorithm over giant tours with OX/PMX crossover, elitism and an optional memetic polish.

A chromosome is the tour without its depot (tour[1:]), so every individual is a valid giant tour; its fitness is the problem objective (plain, greedy-split or optimal-split cost), which makes the multi-trip budget steer the population directly.

Parameters:

Name	Type	Description	Default
`pop_size`	`int >= 2`	Individuals per generation. The initial population is one individual from `init` plus `pop_size - 1` random permutations.	`100`
`n_generations`	`int >= 1`	Maximum number of generations (outer iterations).	`500`
`crossover`	`('ox', 'pmx')`	Order crossover (a segment of the first parent, the rest in the second parent's order) or partially mapped crossover (segment copy plus mapping repair).	`"ox"`
`p_crossover`	`float in [0, 1]`	Probability that a child is produced by crossover rather than copied from its first parent.	`0.9`
`mutation`	`('inversion', 'swap', 'insertion')`	Inversion reverses a random segment (a 2-opt move), swap exchanges two genes, insertion moves one gene to another position.	`"inversion"`
`p_mutation`	`float in [0, 1]`	Probability that a child is mutated.	`0.2`
`tournament_size`	`int >= 1`	Contestants of every tournament selection (drawn with replacement); the fittest wins.	`3`
`n_elite`	`int >= 0`	Best parents copied unchanged into the next generation. Must be smaller than `pop_size`.	`2`
`local_search`	`None, str or tuple of {"two_opt", "or_opt"}`	Memetic polish applied to every child: the listed descents run to convergence (2-opt and Or-opt with 10-nearest-neighbour candidate lists; the full-evaluation generic descent under a budget or on an asymmetric matrix). A single string is a 1-tuple. `("two_opt",)` is the "memetic" configuration of the benchmarks.	`None`
`patience`	`int >= 1 or None`	Generations without improvement of the best-so-far before stopping; `None` disables.	`100`
`init`	`('nearest_neighbour', 'random')`	The first individual: a nearest-neighbour tour, a random permutation, or the `tour_` / `route_` of another solver (warm start).	`"nearest_neighbour"`
`time_limit`	`float > 0 or None`	Wall-clock budget in seconds, checked once per generation. Breaks bit-exact reproducibility (the stopping generation depends on the machine).	`None`
`random_state`	`(None, int or Generator)`	Seed of the generator that draws every random quantity (pre-drawn per generation, D10).	`None`
`verbose`	`int`	0 is silent; 1 logs every `max(1, n_generations // 10)` generations; 2 logs every generation. 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 generation (non-increasing).
`n_iter_`	`int`	Generations actually run.
`stop_reason_`	`{'max_iter', 'patience', 'time_limit', 'callback'}`	Why the search stopped (`"callback"`: the `callback` of `fit` returned `True`).
`n_duplicates_`	`int`	Children that duplicated an individual of their generation and were mutated once more.
See `BaseRouter` for ``tour_``, ``route_``, ``trips_``, ``cost_`` and the
`other fitted attributes shared by every solver.`

Notes

Per generation: the n_elite fittest parents are copied; each of the other children picks two parents by tournament — the fitter winner is parent 1: it contributes the segment [a, b] of the crossover, the other contributes its order (OX) or positions (PMX), which lets a child inherit a block of the better solution —, is produced by crossover with probability p_crossover (else copied from parent 1), mutated with probability p_mutation, mutated once more if it exactly duplicates an individual already in the new generation, optionally polished by local_search and evaluated with the problem objective in one kernel call. Every random quantity of a generation is drawn beforehand from random_state and handed to the nogil kernel as arrays, so two fits with the same seed are bit-identical. Complexity: O(pop_size * n) per generation without polish; with polish the 2-opt/Or-opt descents dominate (O(pop_size * n * k) per generation, k = 10 candidates, more under a budget or on an asymmetric matrix where every move is re-evaluated in O(n)).

Callback events (D30): "start" carries the init individual as tour and the best of the initial population as best_tour, with generation=0 and n_evaluations=pop_size in extra; every generation emits one "iteration" whose tour is the generation's best individual and best_tour the run's best, with the extra keys generation (generations completed), n_evaluations (objective evaluations so far), mean_cost (mean objective of the population) and n_duplicates.

Supports: symmetric and asymmetric matrices, multi-trip objective; stochastic, iterative, budget-aware. A truncation ("top X %") selection is planned for 2.1 (issue #37).

References

.. [1] L. Davis, "Applying adaptive algorithms to epistatic domains", IJCAI 1985 (OX). .. [2] D. E. Goldberg and R. Lingle, "Alleles, loci, and the traveling salesman problem", ICGA 1985 (PMX). .. [3] P. Moscato, "On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms", Caltech report 826, 1989.

Examples:

>>> from skroute import Genetic
>>> from skroute.datasets import load_tsp
>>> wi = load_tsp("wi29")  # Western Sahara, optimum 27603
>>> C = wi.distance_matrix()
>>> ga = Genetic(random_state=0).fit(C, labels=wi.labels)
>>> ga.cost_ / wi.optimal_tour_length < 1.15  # the fast-tier tolerance of the plain GA
True
>>> int(ga.route_[0]) == int(ga.route_[-1]) == int(ga.depot_) == 1
True
>>> ga.n_iter_ == len(ga.history_) and ga.stop_reason_ in {"patience", "max_iter"}
True
>>> memetic = Genetic(local_search=("two_opt",), random_state=0).fit(C, labels=wi.labels)
>>> memetic.cost_ / wi.optimal_tour_length < 1.05
True