Skip to content

Population and swarm methods

Methods that evolve many solutions at once: on item sequences, on random keys, with continuous optimisers, and with the update rules of swarm methods.

dispatchatlas.solvers.population

Population metaheuristics: methods that evolve many solutions at once.

Two representations are used:

  • Sequences. The genetic, memetic, scatter-search, and ant-colony methods work on the precedence-feasible item sequences and mode settings of SequenceSpace, the space the trajectory methods move through, and share its moves and local searches.
  • Random keys. The biased random-key genetic algorithm and the univariate marginal distribution algorithm search real vectors decoded by the random-key rule, through EncodedSolver, like the continuous optimisers of dispatchatlas.solvers.continuous.

Solver ids:

  • genetic-algorithm, GeneticAlgorithm: tournament selection, order crossover, and insert, swap, or mode mutation (Holland 1992; Davis 1985);
  • memetic-algorithm, MemeticAlgorithm: the genetic algorithm with an insertion local search on every child (Moscato 1989);
  • brkga, Brkga: elite, mutants, and biased crossover of random-key chromosomes (Gonçalves and Resende 2011);
  • umda, Umda: an independent normal model per key, estimated from the best members (Mühlenbein and Paaß 1996; Larrañaga and Lozano 2002);
  • scatter-search, ScatterSearch: a reference set of good and diverse solutions, combined pairwise and improved (Glover 1998; Martí, Laguna and Glover 2006);
  • ant-colony-optimization, AntColonyOptimization: the MAX-MIN Ant System with pheromone on (task, position) pairs (Stützle and Hoos 2000).

register

register(registry: SolverRegistry) -> None

Add the population metaheuristics to registry.

dispatchatlas.solvers.population.genetic

Genetic and memetic algorithms over task sequences and mode settings.

GeneticAlgorithm dataclass

GeneticAlgorithm(population_size: int = 30, crossover_rate: float = 0.9, mutation_rate: float = 0.2, tournament_size: int = 2, elites: int = 2)

A generational genetic algorithm over task sequences (Holland 1992).

Solutions are those of the trajectory methods' SequenceSpace: a precedence-feasible sequence of items (tasks, or whole jobs in permutation problems) and a mode setting for every multi-mode task, either a fixed mode or AUTO, the earliest-finishing mode when the task is placed. This is the activity-list representation that Hartmann (1998) evolves with the serial schedule-generation scheme. The initial population holds random feasible sequences with every multi-mode task on AUTO. Each generation builds a new population:

  1. elitism: the elites best members pass unchanged, without a new evaluation;
  2. selection: each further child has two parents, each the best of tournament_size members drawn uniformly with replacement;
  3. crossover: with probability crossover_rate, the order crossover of Davis (1985) and a uniform crossover of the mode settings (see recombine()); otherwise a copy of the first parent;
  4. mutation: with probability mutation_rate, one random move of the space: an item inserted elsewhere, two items swapped, or a task's mode setting changed, always keeping precedence.

A child identical to one of its parents inherits the parent's score without a new evaluation. One generation is one iteration.

Attributes:

Name Type Description
population_size int

Members per generation, at least 2.

crossover_rate float

Probability that a child is a crossover of its parents.

mutation_rate float

Probability that a child receives one random move.

tournament_size int

Members drawn per tournament.

elites int

Best members copied into the next generation, fewer than population_size.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Evolve the population until a stop criterion fires.

MemeticAlgorithm dataclass

MemeticAlgorithm(population_size: int = 20, crossover_rate: float = 0.9, mutation_rate: float = 0.2, tournament_size: int = 2, elites: int = 2, local_search_rate: float = 1.0)

Bases: GeneticAlgorithm

A memetic algorithm: the genetic algorithm with local search on offspring (Moscato 1989).

Every evaluated child is improved, with probability local_search_rate, by the insertion local search of descend(), the iterative improvement of Ruiz and Stützle (2007) extended to modes: each item is reinserted at its best position and each of its multi-mode tasks tries its other mode settings, passes repeating until one changes nothing. The population therefore holds local optima, and crossover and mutation move between their basins. The rest follows GeneticAlgorithm.

Attributes:

Name Type Description
local_search_rate float

Probability that an evaluated child is improved.

recombine

recombine(items: Items, first: Solution, second: Solution, rng: Random) -> tuple[list[int], tuple[int, ...] | None]

Cross two solutions: order crossover of the sequences, uniform crossover of the modes.

The order crossover of Davis (1985) copies a random slice of first's sequence and fills the other positions with the missing items in the order they appear in second, from the end of the slice onwards. The result is repaired so that every item follows its predecessors, keeping the crossed order as far as precedence allows. Each task takes its mode setting from either parent with equal probability.

dispatchatlas.solvers.population.brkga

The biased random-key genetic algorithm (Gonçalves and Resende 2011).

Brkga dataclass

Brkga(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys', population_size: int | None = None, elite_fraction: float = 0.2, mutant_fraction: float = 0.15, inheritance: float = 0.7)

Bases: EncodedSolver

The biased random-key genetic algorithm of Gonçalves and Resende (2011).

A chromosome is a vector of random keys in the unit cube, decoded into a schedule as random-key genetic algorithms do (Bean 1994). Each generation ranks the population and builds the next one from three parts:

  1. the elite, the elite_fraction best members, copied unchanged and never evaluated again;
  2. mutants, mutant_fraction of new uniform random chromosomes;
  3. offspring for the remaining places, each crossing a parent drawn uniformly from the elite with one drawn uniformly from the non-elite members: every key comes from the elite parent with probability inheritance and from the other parent otherwise.

Each part keeps at least one member. The published recommendations are a population of a n members for a chromosome of n keys and some a >= 1, an elite of 10 to 25 %, mutants of 10 to 30 %, and an inheritance probability above 0.5, up to 0.8. With seeded the initial population holds the heuristic schedule's keys.

Attributes:

Name Type Description
population_size int | None

Members per generation, at least 3. None uses the chromosome length n (a = 1), and at least 3.

elite_fraction float

Fraction of the population kept as the elite.

mutant_fraction float

Fraction of the population replaced by mutants.

inheritance float

Probability that a key of a child comes from its elite parent.

partition

partition(size: int) -> tuple[int, int]

Return the elite and mutant counts of a population of size members.

The elite keeps at least one member and the offspring at least one place.

optimize

optimize(run: Run[F], rng: Random) -> None

Evolve the chromosomes until the run is exhausted.

dispatchatlas.solvers.population.umda

The continuous univariate marginal distribution algorithm with Gaussian marginals.

Umda dataclass

Umda(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys', population_size: int = 100, selection_fraction: float = 0.5, elites: int = 1)

Bases: EncodedSolver

UMDA with Gaussian marginals, an estimation of distribution algorithm.

The univariate marginal distribution algorithm of Mühlenbein and Paaß (1996) in its continuous form, UMDA_c with normal densities (Larrañaga and Lozano 2002). The search model is a product of independent normal distributions, one per coordinate. Each generation:

  1. selection: the selection_fraction best members are selected (truncation selection);
  2. estimation: each coordinate's normal distribution gets the maximum likelihood mean and standard deviation of the selected members;
  3. sampling: the next population holds the elites best members, kept without a new evaluation, and new members sampled from the model.

The model ignores interactions between coordinates, and its spread shrinks with every truncation, so the search concentrates quickly around good regions. On a strict box samples are clipped to the box; random keys need no clipping. The initial population is uniform in the box. The mean standard deviation of the last model appears in the result's extras as spread.

Attributes:

Name Type Description
population_size int

Members per generation, at least 2.

selection_fraction float

Fraction of the population that estimates the model.

elites int

Best members kept in the next population, fewer than population_size.

optimize

optimize(run: Run[F], rng: Random) -> None

Estimate and sample the model until the run is exhausted.

dispatchatlas.solvers.population.scatter

Scatter search over task sequences (Glover 1998; Martí, Laguna and Glover 2006).

ScatterSearch dataclass

ScatterSearch(population_size: int = 20, reference_size: int = 8, quality_size: int = 4, max_failures: int = 50)

Scatter search (Glover 1998) in the basic design of Martí, Laguna and Glover (2006).

Solutions are the item sequences and mode settings of SequenceSpace. The search combines five methods:

  1. diversification: new sequences are built position by position, each next item drawn among the eligible ones with probability proportional to 1 / (1 + f), where f counts how often the item has held that position in the sequences built so far;
  2. improvement: the first-improvement climb of climb(), which stops after max_failures consecutive random neighbours fail to improve;
  3. reference set: reference_size solutions, the quality_size best of the improved population and then, one at a time, the solution whose smallest distance() to those already chosen is largest;
  4. subset generation: every pair of reference solutions of which at least one entered the set since the last round;
  5. combination: combine(), whose result is improved in turn.

Each round combines the new pairs, then keeps the reference_size best distinct solutions among the reference set and the improved combinations. When a round adds nothing, the set is rebuilt: its quality_size best stay, and a newly diversified and improved population supplies the rest by the distance rule. One round is one iteration.

Attributes:

Name Type Description
population_size int

Solutions diversified and improved to build or rebuild the reference set.

reference_size int

Solutions in the reference set, at least 2.

quality_size int

Reference solutions chosen by quality, the rest by diversity; at least 1 and at most reference_size.

max_failures int

Consecutive non-improving neighbours that end an improvement.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Combine and improve reference solutions until a stop criterion fires.

reference_set

reference_set(candidates: Sequence[Solution], kept: Sequence[Solution]) -> list[Solution]

Complete kept into a reference set, first by quality, then by diversity.

Returns the set sorted from best to worst. It is smaller than reference_size when there are too few distinct solutions.

distance

distance(first: Solution, second: Solution) -> int

Return how far apart two solutions are.

The sum over items of the difference between their positions in the two sequences (Spearman's footrule), plus the number of tasks whose mode settings differ.

combine

combine(items: Items, first: Solution, second: Solution, rng: Random) -> tuple[list[int], tuple[int, ...] | None]

Combine two solutions into a new sequence and mode settings.

Scatter search combines reference solutions linearly and rounds the result back to a solution. Here the combined vector is the convex combination w p_first + (1 - w) p_second of the two position vectors, with w uniform in [0, 1), and the rounding sorts the items by it, ties by their position in first. Every precedence relation holds in both parents, hence in the combination. Each task takes its mode setting from first with probability w.

dispatchatlas.solvers.population.colony

Ant colony optimisation: the MAX-MIN Ant System (Stützle and Hoos 2000).

HEURISTICS module-attribute

HEURISTICS: Mapping[str, Callable[[Problem], list[float]]] = MappingProxyType({'upward-rank': upward_ranks, 'longest-tail': longest_tails, 'earliest-due-date': lambda problem: [-due for due in effective_due_dates(problem)], 'shortest-processing-time': lambda problem: [-time for time in min_durations(problem)]})

Task priorities the ants' desirability can follow, larger first, from priorities: the upward rank of HEFT, the longest path to the end, the earliest due date, and the shortest duration.

Trails

Trails(widths: Sequence[int], evaporation: float, best_probability: float, decisions: int, choices: float)

Pheromone trails with the bounds of the MAX-MIN Ant System.

Each row holds the trails of one decision's options: the positions an item may take, or the modes of a task. Trails start at the upper bound. An update evaporates every trail by the factor 1 - evaporation, adds one unit to the options of the depositing solution, and clips every trail to [lower, upper].

With a unit deposit a trail reinforced at every update tends to upper = 1 / evaporation, the tau_max of Stützle and Hoos (2000) for this deposit. The lower bound follows their rule. Once the trails have converged, those of one solution's options at upper and all others at lower, an ant guided by the trails alone rebuilds that solution with probability best_probability, given decisions decisions of choices options on average. This gives lower = upper (1 - r) / ((choices - 1) r) with r = best_probability ** (1 / decisions). When that exceeds upper, as for very few decisions, lower = upper and the trails carry no information. A unit deposit, rather than the published inverse objective value, keeps the bounds independent of the objective's scale and sign.

Parameters:

Name Type Description Default
widths Sequence[int]

Options of each decision.

required
evaporation float

Fraction of every trail lost per update, in (0, 1).

required
best_probability float

The p_best of the lower bound, in (0, 1).

required
decisions int

Decisions that build one solution.

required
choices float

Mean options per decision.

required

Attributes:

Name Type Description
values

The trails, by decision, then option.

lower

Lower bound of every trail.

upper

Upper bound of every trail.

reinforce

reinforce(options: Iterable[tuple[int, int]]) -> None

Evaporate every trail, deposit one unit on each (decision, option), and clip.

AntColonyOptimization dataclass

AntColonyOptimization(ants: int = 10, alpha: float = 1.0, beta: float = 1.0, heuristic: str = 'auto', evaporation: float = 0.1, best_probability: float = 0.05, deposit: Literal['iteration-best', 'best-so-far'] = 'iteration-best', modes: Literal['builder', 'pheromone'] = 'builder')

The MAX-MIN Ant System of Stützle and Hoos (2000) over task sequences.

Ants build item sequences (tasks, or whole jobs in permutation problems) one position at a time, as in the ant colony optimisation of Merkle, Middendorf and Schmeck (2002) for project scheduling, which builds on the ant system of Dorigo, Maniezzo and Colorni (1996). At position j an ant draws the next item among the eligible ones, whose predecessors are placed, with probability proportional to tau(i, j)^alpha eta(i)^beta, where tau(i, j) is the pheromone of item i at position j and eta(i) its desirability() under a priority rule (see heuristic_rule()), or 1 without one. The default rule depends on the primary objective, as heuristic information does in the ant colony methods of the scheduling literature: the earliest due date for due-date objectives, the shortest duration for completion-time objectives, and the upward rank of HEFT (Topcuoglu, Hariri and Wu 2002) otherwise. The desirability spans ranks from 1 / k to 1, so the default beta = 1 lets the pheromone, not the rule, dominate once trails differ.

Multi-mode tasks run in the mode the builder finds earliest-finishing (modes="builder"), or in a mode each ant draws with probability proportional to tau(t, m)^alpha, a pheromone on (task, mode) (modes="pheromone").

After all ants of an iteration are evaluated, one solution deposits pheromone on its (item, position) pairs and, with mode pheromone, on its (task, mode) pairs: the iteration's best, or the best found so far. The trails obey the bounds of Trails, which keep every option possible. One iteration is one colony of ants solutions.

Attributes:

Name Type Description
ants int

Solutions built per iteration.

alpha float

Weight alpha of the pheromone.

beta float

Weight beta of the desirability.

heuristic str

The priority rule of the desirability: "auto", "none", or a key of HEURISTICS.

evaporation float

Fraction of pheromone lost per iteration.

best_probability float

The p_best that sets the lower trail bound.

deposit Literal['iteration-best', 'best-so-far']

"iteration-best" or "best-so-far": whose solution deposits pheromone.

modes Literal['builder', 'pheromone']

"builder" or "pheromone": how multi-mode tasks get their modes.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Build and reinforce until a stop criterion fires.

position_trails

position_trails(items: Items) -> Trails

Return fresh (item, position) trails for items.

mode_trails

mode_trails(problem: Problem) -> Trails | None

Return fresh (task, mode) trails, or None when modes come from the builder.

heuristic_rule

heuristic_rule(name: str, objective: str) -> str | None

Return the priority rule of HEURISTICS that name selects, or None.

"auto" picks a rule suited to the primary objective: the earliest due date for due-date objectives, the shortest duration for completion-time objectives, and the upward rank otherwise. "none" selects no rule.

desirability

desirability(items: Items, priority: Sequence[float]) -> list[float]

Return the heuristic desirability of each item from a task priority.

An item's priority is the largest priority of its tasks. The desirability is 1 - h / k for an item with h of the k items strictly ahead of it: 1 for the items of highest priority down to 1 / k. Using ranks rather than raw priorities keeps the desirability positive and independent of the time unit.

dispatchatlas.solvers.continuous

Continuous optimisers and their use on scheduling problems.

Each optimiser searches real vectors and needs only a box, a fitness it can compare, and a budget (see core). The same object minimises a plain function through minimize() and solves a scheduling problem as a registered solver, through the random-key encoding of encoded:

  • differential-evolution, DifferentialEvolution: DE/rand/1/bin (Storn and Price 1997);
  • particle-swarm-optimization, ParticleSwarmOptimization: global-best particle swarm with a decreasing inertia weight (Kennedy and Eberhart 1995; Shi and Eberhart 1998);
  • clpso, Clpso: comprehensive learning particle swarm (Liang et al. 2006);
  • lshade, LShade: success-history adaptive differential evolution with linear population size reduction (Tanabe and Fukunaga 2014);
  • cma-es, CmaEs: covariance matrix adaptation evolution strategy (Hansen and Ostermeier 2001).

register

register(registry: SolverRegistry) -> None

Add the continuous optimisers to registry.

dispatchatlas.solvers.continuous.core

Search boxes, optimisation runs, and the minimize entry point.

The optimisers of this package search real vectors. Each implements optimize(run, rng): it draws vectors, asks run.evaluate for their fitness, calls run.next_iteration at the top of every generation, and keeps going until the run raises Exhausted. A Run bundles the search box, the fitness, and the budget, so one optimiser serves two purposes:

  • minimize() runs it on a plain function of real vectors, which is how the methods are checked on analytic test functions;
  • ScheduleRun scores a vector by the schedule it decodes to, which is how they solve scheduling problems.

Fitness values only need an order. Functions return floats; schedules return a Score, compared by deadline overrun first and objective second. Every comparison uses that order. The one method that weighs how much a candidate improved, L-SHADE, asks Run.improvement().

Methods that adapt a parameter over the run, such as a decreasing inertia weight or a shrinking population, follow Run.progress: the fraction of the tightest time, evaluation, or iteration limit spent so far. A schedule therefore reaches its end whichever limit stops the run.

Ordered

Bases: Protocol

A fitness value: ordered by < and <=, smaller is better.

Box dataclass

Box(lower: tuple[float, ...], upper: tuple[float, ...], strict: bool = True)

An axis-aligned search box.

Attributes:

Name Type Description
lower tuple[float, ...]

Lower bound of each coordinate.

upper tuple[float, ...]

Upper bound of each coordinate, above the lower bound.

strict bool

Whether the fitness is defined only inside the box. When false, as for random keys, where every real vector decodes, the box only marks where the search starts, and methods designed for unbounded spaces may leave it.

dimension property

dimension: int

Number of coordinates.

widths property

widths: tuple[float, ...]

Upper minus lower bound of each coordinate.

cube classmethod

cube(dimension: int, lower: float, upper: float, *, strict: bool = True) -> Box

Return the box [lower, upper] in every one of dimension coordinates.

sample

sample(rng: Random) -> list[float]

Return a point drawn uniformly from the box.

contains

contains(vector: Sequence[float]) -> bool

Return whether every coordinate of vector lies within its bounds.

clip

clip(vector: Sequence[float]) -> list[float]

Return vector with each coordinate moved to its nearest bound when outside.

Run

Bases: Protocol

What an optimiser sees of the task it minimises.

Attributes:

Name Type Description
box Box

The search box.

seeds Sequence[tuple[Sequence[float], F]]

Starting points with a known fitness. Population methods place them in their initial population; CMA-ES centres its first distribution on the best one.

box property

box: Box

The search box.

seeds property

seeds: Sequence[tuple[Sequence[float], F]]

Starting points with their fitness.

progress property

progress: float

Fraction of the tightest time, evaluation, or iteration limit spent, in [0, 1].

evaluate

evaluate(vector: Sequence[float]) -> F

Return the fitness of vector, counting one evaluation.

Raises:

Type Description
Exhausted

When a stop criterion fires.

next_iteration

next_iteration() -> None

Start a generation.

Raises:

Type Description
Exhausted

When a stop criterion fires.

improvement

improvement(before: F, after: F) -> float

Return how much better after is than before, positive when it is better.

note

note(key: str, value: Scalar) -> None

Record a fact about the search, such as the final population size.

Optimizer

Bases: Protocol

A method that minimises the fitness of a Run.

optimize

optimize(run: Run[F], rng: Random) -> None

Search until run raises Exhausted.

Minimum dataclass

Minimum(vector: tuple[float, ...], value: float, evaluations: int, iterations: int, reason: StopReason, elapsed: float, extras: Mapping[str, Scalar] = dict())

The outcome of minimize().

Attributes:

Name Type Description
vector tuple[float, ...]

The best point evaluated.

value float

Its function value.

evaluations int

Function evaluations performed.

iterations int

Generations started.

reason StopReason

The stop criterion that ended the run.

elapsed float

Wall-clock seconds.

extras Mapping[str, Scalar]

Facts the method recorded, such as its final population size.

FunctionRun

FunctionRun(function: Callable[[Sequence[float]], float], box: Box, stop: StopCriteria)

A run over a plain function of real vectors.

Its budget behaves like that of Search: the evaluation and time limits are checked before each evaluation, the iteration limit and the patience at the start of each generation, and the target after each evaluation. A NaN function value counts as infinity.

Parameters:

Name Type Description Default
function Callable[[Sequence[float]], float]

The function to minimise.

required
box Box

The search box.

required
stop StopCriteria

Stop criteria. Must include a time, evaluation, or iteration limit.

required

Raises:

Type Description
SolverError

If stop is unbounded.

elapsed property

elapsed: float

Seconds since the run started, or since the origin clock_origin set.

progress property

progress: float

Fraction of the tightest limit spent, in [0, 1], by StopCriteria.progress.

A run that reads it records in the extras of its result which clock its schedule followed, see result().

check

check() -> None

Raise Exhausted once the time limit has passed.

next_iteration

next_iteration() -> None

Start a generation, or raise Exhausted when a limit is reached.

evaluate

evaluate(vector: Sequence[float]) -> float

Return the function value of vector, counting one evaluation.

improvement

improvement(before: float, after: float) -> float

Return before - after.

note

note(key: str, value: Scalar) -> None

Record a fact about the search.

result

result() -> Minimum

Return the best point found and the run's counts.

A run that read progress records in its extras which clock its parameter schedule followed: schedule_clock is "evaluations", "iterations", or "time", the limit that places the end of the run on the schedule, and schedule_progress is that place, in [0, 1].

Raises:

Type Description
SolverError

If nothing was evaluated.

initial_population

initial_population(run: Run[F], size: int, rng: Random) -> tuple[list[list[float]], list[F]]

Return a population of size members and their fitness.

The run's seeds come first, without a new evaluation; uniform samples of the box fill the remaining places, each evaluated.

midpoint_repair

midpoint_repair(value: float, parent: float, lower: float, upper: float) -> float

Move a coordinate that left [lower, upper] halfway back to its parent's value.

The repair of JADE (Zhang and Sanderson 2009) that L-SHADE adopts: a value below the box becomes (lower + parent) / 2, a value above it (upper + parent) / 2. It stays inside whenever the parent is inside.

minimize

minimize(optimizer: Optimizer, function: Callable[[Sequence[float]], float], box: Box, stop: StopCriteria, *, seed: int = 0, initial: Sequence[Sequence[float]] = ()) -> Minimum

Minimise a function of real vectors over a box.

Example:

from dispatchatlas.core import StopCriteria
from dispatchatlas.solvers.continuous import Box, CmaEs, minimize

def sphere(x):
    return sum(value * value for value in x)

box = Box.cube(10, -5.0, 5.0)
best = minimize(CmaEs(), sphere, box, StopCriteria(max_evaluations=5000))

Parameters:

Name Type Description Default
optimizer Optimizer

The method, for example CmaEs.

required
function Callable[[Sequence[float]], float]

The function to minimise.

required
box Box

The search box.

required
stop StopCriteria

Stop criteria. Must include a time, evaluation, or iteration limit.

required
seed int

Seed of the run's random generator.

0
initial Sequence[Sequence[float]]

Points evaluated first and handed to the method as seeds.

()

Returns:

Type Description
Minimum

The best point evaluated, its value, and the run's counts.

dispatchatlas.solvers.continuous.encoded

Solving scheduling problems with methods that search real vectors.

EncodedSolver is the base of every solver that searches a real vector space: the continuous methods of this package and the random-key population methods of dispatchatlas.solvers.population. A subclass implements optimize(run, rng) on any Run; the base class supplies EncodedSolver.solve(), which hands the method a ScheduleRun:

  • vectors decode through VectorEncoding with the random-key rule of Bean (1994): tasks run in ascending order of their keys, as far as precedence allows; each multi-mode task either has one more key that selects its mode or runs in the mode the schedule builder finds earliest-finishing (see EncodedSolver.modes);
  • every fitness call is one evaluation of the run's Search, so each method honours every stop criterion and reports exact counts;
  • the search box is the unit cube, marked non-strict because every real vector decodes: methods designed for unbounded spaces leave it freely.

ScheduleRun

ScheduleRun(search: Search, encoding: VectorEncoding, seeds: Sequence[tuple[Sequence[float], Score]] = ())

A run whose fitness is the score of the schedule a vector decodes to.

Parameters:

Name Type Description Default
search Search

The solver run that pays for every evaluation.

required
encoding VectorEncoding

The vector encoding of the problem.

required
seeds Sequence[tuple[Sequence[float], Score]]

Starting points with their scores.

()

progress property

progress: float

Fraction of the tightest limit spent, in [0, 1]: the search's progress.

evaluate

evaluate(vector: Sequence[float]) -> Score

Decode vector and return the score of its schedule.

next_iteration

next_iteration() -> None

Start a generation of the search.

improvement

improvement(before: Score, after: Score) -> float

Return score_improvement() of the two scores.

note

note(key: str, value: Scalar) -> None

Record a fact in the result's extras.

EncodedSolver dataclass

EncodedSolver(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys')

Base of the solvers that search real vectors decoded into schedules.

Subclasses define their parameters as dataclass fields, their SolverInfo, and optimize(), the method itself, which works on any run: a plain function through minimize(), or a scheduling problem through solve().

When every vector decodes to the same schedule (see single_schedule()), solve() evaluates that schedule and completes.

Attributes:

Name Type Description
seeded bool

Start from a heuristic schedule (see heuristic_seed()), which joins the initial population, or centres the first distribution of CMA-ES.

modes Literal['keys', 'builder']

Where the modes of multi-mode tasks come from. "keys": one more key per multi-mode task selects its mode, so the search covers every mode choice, including slower modes that save energy or cost. "builder": the vector holds task keys only and the schedule builder gives each task its earliest-finishing mode, which suits time-based objectives such as the makespan or tardiness and leaves a smaller space to search.

optimize

optimize(run: Run[F], rng: Random) -> None

Search run until it raises Exhausted.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Search the random-key space of problem until a stop criterion fires.

score_improvement

score_improvement(before: Score, after: Score) -> float

Return how much better after is than before, in the first component that differs.

Scores compare lexicographically, so the improvement is measured in the leading component where they differ: the reduction of the deadline overrun when the overruns differ, otherwise the reduction of the objective. It is positive exactly when after < before.

heuristic_seed

heuristic_seed(search: Search, encoding: VectorEncoding) -> tuple[list[float], Score]

Evaluate a heuristic schedule and return its vector and score.

The schedule decodes the tasks in decreasing upward rank, the priority of HEFT (Topcuoglu, Hariri and Wu 2002), with each task in its earliest-finishing mode. It costs one evaluation. The returned vector, from encode(), decodes to the same order and modes, hence to the same schedule.

single_schedule

single_schedule(encoding: VectorEncoding) -> bool

Return whether every vector decodes to the same schedule.

That is the case when precedence admits one task sequence, that of the jobs in permutation problems, and no key selects a mode.

dispatchatlas.solvers.continuous.de

Differential evolution: DE/rand/1/bin of Storn and Price (1997).

DifferentialEvolution dataclass

DifferentialEvolution(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys', population_size: int | None = None, scale_factor: float = 0.5, crossover_rate: float = 0.1)

Bases: EncodedSolver

DE/rand/1/bin, the differential evolution of Storn and Price (1997).

Each generation builds one trial vector per member, the target x_i, from the population at the start of the generation:

  1. mutation: v = x_a + F (x_b - x_c) for three distinct members a, b, c other than i, drawn uniformly;
  2. binomial crossover: the trial takes each coordinate from v with probability CR and from x_i otherwise; one coordinate drawn uniformly always comes from v;
  3. selection: the trial replaces x_i when it is no worse.

On a strict box a mutated coordinate that leaves the box is moved halfway back to the target's coordinate, the repair of JADE (Zhang and Sanderson 2009); random keys need no repair. The population starts uniform in the box, with the seed, if any, as one member.

Attributes:

Name Type Description
population_size int | None

Members NP, at least 4. None uses 5 D for a D-dimensional box, the lower end of the 5 D to 10 D that Storn and Price recommend, which leaves more generations in a budget.

scale_factor float

Difference weight F, in (0, 2]; they recommend 0.5.

crossover_rate float

Crossover probability CR, in [0, 1]; 0.1 is their first choice, and 0.9 or 1 may speed up convergence.

optimize

optimize(run: Run[F], rng: Random) -> None

Evolve the population until the run is exhausted.

dispatchatlas.solvers.continuous.pso

Particle swarm optimisation with a decreasing inertia weight.

ParticleSwarmOptimization dataclass

ParticleSwarmOptimization(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys', population_size: int = 30, inertia_start: float = 0.9, inertia_end: float = 0.4, cognitive: float = 2.0, social: float = 2.0, velocity_limit: float = 1.0)

Bases: EncodedSolver

Global-best particle swarm optimisation with a decreasing inertia weight.

Each particle has a position x, a velocity v, and the best position it has visited, p; g is the best position of the whole swarm. Every generation moves each particle in turn, coordinate by coordinate:

v = w v + c1 r1 (p - x) + c2 r2 (g - x) and then x = x + v,

with r1 and r2 uniform in [0, 1), drawn per coordinate (Kennedy and Eberhart 1995). The inertia weight w of Shi and Eberhart (1998) decreases linearly from inertia_start to inertia_end as the budget is spent (Shi and Eberhart 1999). Each velocity coordinate is limited to velocity_limit times the box width. After each move the particle is evaluated, updates p when strictly better, and g at once when better than the swarm's best. On a strict box positions are clipped to the box; random keys leave it free. Velocities start uniform within their limits.

Attributes:

Name Type Description
population_size int

Particles.

inertia_start float

Inertia weight at the start of the run.

inertia_end float

Inertia weight at the end of the run.

cognitive float

Acceleration c1 toward the particle's own best.

social float

Acceleration c2 toward the swarm's best.

velocity_limit float

Velocity limit as a fraction of the box width; 1 limits each step to the dynamic range of its coordinate.

inertia

inertia(progress: float) -> float

Return the inertia weight after progress of the budget, a fraction in [0, 1].

optimize

optimize(run: Run[F], rng: Random) -> None

Move the swarm until the run is exhausted.

dispatchatlas.solvers.continuous.clpso

Comprehensive learning particle swarm optimisation (Liang, Qin, Suganthan and Baskar 2006).

Clpso dataclass

Clpso(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys', population_size: int = 40, inertia_start: float = 0.9, inertia_end: float = 0.4, acceleration: float = 1.49445, refresh_gap: int = 7, velocity_limit: float = 0.2)

Bases: EncodedSolver

The comprehensive learning particle swarm optimiser of Liang et al. (2006).

Each coordinate of each particle learns from a possibly different particle's best position, its exemplar, so a particle follows a composite of the swarm's experience rather than one leader:

v_d = w v_d + c r_d (p_{f(d), d} - x_d) and then x_d = x_d + v_d,

with r_d uniform in [0, 1) and f(d) the exemplar of coordinate d (see select_exemplars()), chosen with the particle's learning probability (see learning_probabilities()). A particle whose best position has not improved for refresh_gap evaluations draws new exemplars. The inertia weight decreases linearly from inertia_start to inertia_end as the budget is spent, and each velocity coordinate is limited to velocity_limit times the box width, 20 % in the original. Velocities start uniform within their limits.

Positions are never clipped. On a strict box, the original bound handling applies: a particle outside the box is neither evaluated nor allowed to update its best position, and its exemplars, all inside the box, draw it back. Random keys decode anywhere, so there every particle is evaluated after every move.

The defaults are the published settings; Liang et al. use 10 particles for 10-dimensional problems and 40 for 30-dimensional ones.

Attributes:

Name Type Description
population_size int

Particles, at least 3.

inertia_start float

Inertia weight at the start of the run.

inertia_end float

Inertia weight at the end of the run.

acceleration float

The acceleration c.

refresh_gap int

Evaluations without improvement before new exemplars, m.

velocity_limit float

Velocity limit as a fraction of the box width.

optimize

optimize(run: Run[F], rng: Random) -> None

Move the swarm until the run is exhausted.

learning_probabilities

learning_probabilities(size: int) -> list[float]

Return the learning probability of each of size particles.

Particle i (from 0) learns from others with probability 0.05 + 0.45 (exp(10 i / (N - 1)) - 1) / (exp(10) - 1), rising from 0.05 for the first particle to 0.5 for the last, so the swarm mixes particles that mostly follow their own best with particles that mostly follow others.

select_exemplars

select_exemplars(particle: int, best_fitness: Sequence[F], probability: float, dimension: int, rng: Random) -> list[int]

Choose, for each coordinate, whose best position particle learns from.

With probability probability a coordinate follows the winner of a tournament between two other particles drawn uniformly, the one with the better best position (the first drawn on ties); otherwise it follows the particle's own best. When every coordinate chose the particle itself, one coordinate drawn uniformly follows a tournament winner instead. Needs at least three particles.

dispatchatlas.solvers.continuous.lshade

L-SHADE: success-history adaptive differential evolution with linear population reduction.

SuccessMemory

SuccessMemory(size: int)

The success-history memory of SHADE (Tanabe and Fukunaga 2013) as L-SHADE uses it.

H slots hold a crossover-rate mean M_CR and a scale-factor mean M_F, both 0.5 at first. A trial draws a slot uniformly, then CR ~ N(M_CR, 0.1) clipped to [0, 1], or exactly 0 when the slot holds the terminal value, and F ~ Cauchy(M_F, 0.1), drawn again while not positive and capped at 1. After a generation with successful trials, the slot under the cursor receives the weighted Lehmer means of the successful CR and F values, weighted by their fitness improvements, and the cursor advances. The slot's M_CR becomes terminal for good when it already was, or when every successful CR was 0.

Parameters:

Name Type Description Default
size int

Slots H.

required

Attributes:

Name Type Description
crossover

M_CR of each slot, meaningless for terminal slots.

scale

M_F of each slot.

terminal

Whether each slot's M_CR holds the terminal value.

cursor

The slot the next update writes.

sample

sample(rng: Random) -> tuple[float, float]

Draw the (CR, F) pair of one trial.

update

update(rates: Sequence[float], scales: Sequence[float], improvements: Sequence[float]) -> None

Fold a generation's successful trials into the slot under the cursor.

A generation without success changes nothing, not even the cursor. Improvements weigh the means; when they do not sum to a positive number, the successes weigh equally.

mean_crossover

mean_crossover() -> float

Return the mean M_CR over the slots, a terminal slot counting as 0.

LShade dataclass

LShade(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys', population_size: int | None = None, min_population: int = 4, memory_size: int = 6, best_fraction: float = 0.11, archive_rate: float = 2.6)

Bases: EncodedSolver

L-SHADE, the adaptive differential evolution of Tanabe and Fukunaga (2014).

Every generation builds one trial per member x_i from the population at the start of the generation, with its own CR and F drawn from a SuccessMemory:

  1. current-to-pbest/1 mutation (Zhang and Sanderson 2009): v = x_i + F (x_pbest - x_i) + F (x_r1 - x_r2), where x_pbest is drawn uniformly from the max(2, round(p N)) best members, x_r1 from the population and x_r2 from the population together with the archive, with i, r1, and r2 distinct positions;
  2. binomial crossover with rate CR, one uniformly drawn coordinate always taken from v;
  3. repair: a coordinate outside the box moves halfway back to that of x_i;
  4. selection: the trial replaces x_i when no worse. When strictly better, x_i enters the archive and (CR, F) counts as a success, weighted by the improvement (for schedules, see score_improvement()).

After the generation the memory absorbs the successes, the population shrinks to planned_population() by dropping its worst members, and random archive members are dropped until at most round(archive_rate N) remain. The population thus reaches min_population at the end of the run, whichever limit binds.

The defaults are the published settings: N_init = 18 D, N_min = 4, H = 6, p = 0.11, and an archive rate of 2.6. The final population size and the mean memories appear in the result's extras.

Attributes:

Name Type Description
population_size int | None

Initial population N_init. None uses 18 D for a D-dimensional box.

min_population int

Final population N_min, at least 4.

memory_size int

Memory slots H.

best_fraction float

Fraction p of the population x_pbest is drawn from.

archive_rate float

Archive capacity as a multiple of the population size.

optimize

optimize(run: Run[F], rng: Random) -> None

Evolve the population until the run is exhausted.

lehmer_mean

lehmer_mean(values: Sequence[float], weights: Sequence[float]) -> float

Return the weighted Lehmer mean sum(w s^2) / sum(w s).

Falls back to the arithmetic mean when the denominator is not positive.

planned_population

planned_population(initial: int, minimum: int, progress: float) -> int

Return the population size of linear population size reduction.

round(initial + (minimum - initial) * progress): the size falls on a straight line from initial to minimum as the budget is spent. Tanabe and Fukunaga (2014) key the line to the evaluations spent; progress follows whichever limit binds.

dispatchatlas.solvers.continuous.cmaes

The covariance matrix adaptation evolution strategy (CMA-ES).

Strategy dataclass

Strategy(dimension: int, offspring: int, parents: int, weights: NDArray[float64], mu_eff: float, c_sigma: float, d_sigma: float, c_c: float, c_1: float, c_mu: float, chi_n: float)

The strategy constants of CMA-ES for one dimension and population size.

The defaults of Hansen's tutorial (2016) for positive recombination weights, as in Hansen and Ostermeier (2001) with the rank-mu update of Hansen, Müller and Koumoutsakos (2003):

  • mu = floor(lambda / 2) parents with weights proportional to ln((lambda + 1) / 2) - ln i, summing to 1;
  • mu_eff = 1 / sum(w_i^2);
  • c_sigma = (mu_eff + 2) / (n + mu_eff + 5) and d_sigma = 1 + 2 max(0, sqrt((mu_eff - 1) / (n + 1)) - 1) + c_sigma;
  • c_c = (4 + mu_eff / n) / (n + 4 + 2 mu_eff / n);
  • c_1 = 2 / ((n + 1.3)^2 + mu_eff) and c_mu = min(1 - c_1, 2 (mu_eff - 2 + 1 / mu_eff) / ((n + 2)^2 + mu_eff));
  • chi_n = sqrt(n) (1 - 1 / (4 n) + 1 / (21 n^2)), the expected length of a standard normal vector.

Attributes:

Name Type Description
dimension int

n.

offspring int

lambda.

parents int

mu.

weights NDArray[float64]

Recombination weights of the mu best offspring.

mu_eff float

Variance-effective selection mass.

c_sigma float

Learning rate of the step-size path.

d_sigma float

Damping of the step-size update.

c_c float

Learning rate of the covariance path.

c_1 float

Learning rate of the rank-one update.

c_mu float

Learning rate of the rank-mu update.

chi_n float

Expected length of an n-dimensional standard normal vector.

default classmethod

default(dimension: int, offspring: int | None = None) -> Strategy

Return the constants for dimension; lambda defaults to 4 + floor(3 ln n).

CmaEs dataclass

CmaEs(seeded: bool = False, modes: Literal['keys', 'builder'] = 'keys', population_size: int | None = None, step_size: float = 0.3)

Bases: EncodedSolver

CMA-ES, the evolution strategy of Hansen and Ostermeier (2001).

Each generation samples lambda points x_k = m + sigma y_k with y_k ~ N(0, C) and ranks them by fitness. Then:

  1. the mean moves to the weighted mean of the mu best points, m' = m + sigma y_w with y_w = sum(w_i y_{i:lambda});
  2. the conjugate evolution path p_sigma accumulates C^{-1/2} y_w and the step size follows its length: sigma' = sigma exp((c_sigma / d_sigma) (|p_sigma| / chi_n - 1)) (cumulative step-size adaptation);
  3. the evolution path p_c accumulates y_w, except while |p_sigma| is too long, the h_sigma stall of the tutorial;
  4. the covariance combines a rank-one update with p_c and the rank-mu update of Hansen, Müller and Koumoutsakos (2003) with the selected steps: C' = (1 - c_1 - c_mu) C + c_1 (p_c p_c^T + delta C) + c_mu sum(w_i y_i y_i^T), where delta = (1 - h_sigma) c_c (2 - c_c).

The eigendecomposition C = B D^2 B^T that sampling needs is refreshed once the evaluations since the last one exceed lambda / (10 n (c_1 + c_mu)). The constants are those of Strategy.

The first distribution is centred on the box, or on the best seed, and has, along coordinate i, a standard deviation of step_size times the box width. On a strict box a sample's coordinates outside the box are set to the nearest bound, the boundary repair of Hansen (2016), and the repaired point is both evaluated and used in the updates, so the mean, a weighted mean of repaired points, stays inside the box. Random keys need no repair. The step size and the axis ratio max(D) / min(D) of the final distribution appear in the result's extras.

Attributes:

Name Type Description
population_size int | None

Offspring lambda per generation, at least 2. None uses 4 + floor(3 ln n).

step_size float

Initial step size as a fraction of the box width.

optimize

optimize(run: Run[F], rng: Random) -> None

Adapt the search distribution until the run is exhausted.

dispatchatlas.solvers.swarm

Population metaheuristics on priority vectors.

Every method here keeps a population of real vectors in the unit hypercube and moves it with the update rule of its paper. A vector holds one key per task, plus, by default, one per task with several modes, and decodes through VectorEncoding into a task order and mode choices, which the shared schedule builder turns into a schedule. The engine in _engine does everything the methods share: the uniformly random initial population, bounds, evaluation, the budget schedule, memories of the best vectors, and numerical helpers. Each method module implements one iteration of its rule, and its docstring states the rule with the paper's equation numbers and where the port has to choose between the paper and the authors' implementation.

Representation. The rule parameter of every method selects how keys become an order: "random-key", the default, sorts tasks by ascending key (Bean 1994), and "largest-value" by descending key, the largest-order-value rule of many swarm scheduling papers. Both reach every order, but they differ for update rules that are not symmetric under x -> 1 - x, such as rules drawn towards the origin. The modes parameter selects where the modes of tasks with several modes come from. With "keys", the default, one more key per such task selects its mode, so the search covers every mode choice, including slower modes that save energy or cost. With "builder" the vectors hold task keys only and the schedule builder gives each task its earliest-finishing mode. This suits time-based objectives such as the makespan or tardiness, where learning modes from keys can leave these methods behind random search, which lets the builder choose modes too.

Budget. Each decoded vector costs one evaluation of the run's budget, the initial population included, and one iteration applies the update rule to the whole population. Most methods evaluate one vector per member and iteration; teaching-learning-based optimization and the marine predators algorithm evaluate two, the artificial bee colony two plus one per restart, cuckoo search one plus one per replaced member, and Harris hawks optimization one or two. The rules that the papers schedule over an iteration budget use the fraction of the actual budget spent, so every method honours any single bounded stop criterion.

Methods. grey-wolf-optimizer, whale-optimization-algorithm, firefly-algorithm, moth-flame-optimization, sine-cosine-algorithm, arithmetic-optimization-algorithm, harris-hawks-optimization, teaching-learning-based-optimization, salp-swarm-algorithm, marine-predators-algorithm, cuckoo-search, artificial-bee-colony, gravitational-search-algorithm, and jaya.

Caveats. These methods are provided as reproducible baselines, not as recommendations. Sörensen (2015) argues that metaphor-based methods hide familiar mechanisms behind new vocabulary and are rarely validated with rigour. Camacho-Villalón et al. show that the grey wolf, firefly, moth-flame and whale algorithms reuse the concepts of particle swarm optimization under new names (2020, 2023) and that cuckoo search brings no new idea to optimization (2022). Kůdela (2022, 2023) shows that many recent methods contain operators biased towards the centre of the search space, which flatters them on benchmarks with the optimum there; nine of the methods here (grey wolf, whale, sine cosine, arithmetic, Harris hawks, teaching-learning, salp swarm, marine predators, and Jaya) are among those found biased. Niu, Niu, Liu and Chang (2019) show the defect for the grey wolf optimizer, Castelli, Manzoni, Mariot, Nobile and Tangherloni (2022) review the salp swarm algorithm, Črepinšek, Liu and Mernik (2012) correct the published account of teaching-learning-based optimization, and Gauci, Dodd and Groß (2012) show that the pull between two members in the gravitational search algorithm does not depend on their distance, unlike the law of gravity. These findings concern continuous benchmark functions; how the biases carry over to the rank-based decode used here has not been measured.

register

register(registry: SolverRegistry) -> None

Add the population metaheuristics on priority vectors to registry.

dispatchatlas.solvers.swarm.arithmetic

Arithmetic Optimization Algorithm (Abualigah, Diabat, Mirjalili, Abd Elaziz and Gandomi 2021).

Each iteration resamples every component of every vector around the matching component b of the best vector found so far; the member's own position plays no part. With w = (UB - LB) mu + LB, which is mu in the unit hypercube, a component becomes

  • when a uniform draw exceeds MOA (Eq. 3): b / (MOP + eps) * w or b * MOP * w, with equal probability;
  • otherwise (Eq. 5): b - MOP * w or b + MOP * w, with equal probability.

MOA = MOA_min + (t/T) (MOA_max - MOA_min) rises linearly (Eq. 2), so the wide multiplicative moves give way to additive ones, and MOP = 1 - (t/T)^(1/alpha) falls from 1 to 0 (Eq. 4), so the additive steps shrink. The constants are the paper's: alpha = 5 and mu = 0.5 (its Table 1) and MOA rising from 0.2 to 0.9 (its Section 2.5); eps is the machine epsilon. The new vectors replace the old ones whatever their scores.

ArithmeticOptimizationAlgorithm dataclass

ArithmeticOptimizationAlgorithm(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', moa_min: float = 0.2, moa_max: float = 0.9, alpha: float = 5.0, mu: float = 0.5)

Bases: SwarmMethod

Arithmetic Optimization Algorithm on priority vectors.

One evaluation per member and iteration.

Attributes:

Name Type Description
moa_min float

Value of MOA at the start (Eq. 2).

moa_max float

Value of MOA at the end of the budget (Eq. 2).

alpha float

Exponent alpha of the MOP schedule (Eq. 4).

mu float

Control parameter mu of the step width (Eqs. 3 and 5).

step

step(swarm: Swarm) -> None

Resample every vector around the best vector.

dispatchatlas.solvers.swarm.bee_colony

Artificial Bee Colony (Karaboga and Basturk 2007).

Each iteration has three phases:

  1. Every member x proposes a copy of itself with one uniformly drawn component k moved to x_k + phi (x_k - y_k), where y is another uniformly drawn member and phi is uniform in [-1, 1], and keeps it only if it is better.
  2. As many members as the population holds are drawn, with replacement and with probability p_i = f_i / sum_j f_j, and each makes the same kind of proposal. The quality is f = 1 / (1 + v) for a number v >= 0 and f = 1 + |v| otherwise, where v is the member's magnitudes() value, and the probabilities are fixed when the phase starts.
  3. The member whose proposals failed most often in a row, the lowest index on ties, is replaced by a uniformly random vector if that count has reached limit. At most one member is replaced per iteration.

An iteration therefore costs two evaluations per member, plus one when a member is replaced. limit defaults to the number of members times the vector length, the setting commonly recommended for the method.

ArtificialBeeColony dataclass

ArtificialBeeColony(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', limit: int | None = None)

Bases: SwarmMethod

Artificial Bee Colony on priority vectors.

Attributes:

Name Type Description
limit int | None

Failed proposals in a row after which a member is replaced by a random vector. None uses the population size times the vector length.

step

step(swarm: Swarm) -> None

Run the three phases: every member, members drawn by quality, restart.

Cuckoo Search (Yang and Deb 2009).

Each iteration has two phases:

  1. Every member x proposes x + alpha * l (Eq. 1), where l is a vector of Lévy steps of index beta = 1.5 drawn by Mantegna's algorithm, and keeps it unless it is worse.
  2. The worst fraction pa of the members, at least one, is replaced by uniformly random vectors whatever their scores, the simplified form of its replacement rule that the paper states. pa = 0.25 as in the paper.

The paper sets alpha = 1 and compares each proposal with a randomly chosen member. This port follows the authors' implementation on both points instead: alpha = 0.01 (x - b), with b the best vector found so far, is a hundredth of the offset from b and leaves the best member in place, and each proposal competes with the member it came from. That implementation also multiplies every step by a standard normal draw, which this port leaves out, and replaces the second phase by a random walk along differences of members, where this port follows the paper. An iteration costs one evaluation per member plus one per replaced member.

CuckooSearch dataclass

CuckooSearch(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', step_size: float = 0.01, replaced_fraction: float = 0.25)

Bases: SwarmMethod

Cuckoo Search on priority vectors.

Attributes:

Name Type Description
step_size float

Factor of the offset from the best vector in the step size.

replaced_fraction float

The fraction pa of worst members replaced every iteration.

step

step(swarm: Swarm) -> None

Take a Lévy step from every member, then replace the worst members.

dispatchatlas.solvers.swarm.firefly

Firefly Algorithm (Yang 2009).

Each iteration moves every vector x_i towards every member x_j that scored better at the start of the iteration, in member order:

x_i <- x_i + beta0 e^(-gamma r^2) (x_j - x_i) + alpha_t (u - 1/2)

where r is the current distance between the two vectors, u a fresh uniform vector, beta0 = 1 the attraction at zero distance and gamma how fast it decays with distance. A member that no other member beats takes the random term alone, the paper's rule for the best one. gamma = 1 and alpha_0 = 0.25 are the defaults of Yang's reference implementation, and the noise weight falls geometrically, alpha_t = alpha_0 theta^t at iteration t counted from 0 with theta = 0.97, within the range Yang (2014) gives for this reduction. Distances and noise are in units of the unit hypercube, the scale of the search space as the method prescribes.

Every vector is evaluated once per iteration, after all its moves, as in Yang's reference implementation: comparisons use the scores and positions of the previous iteration, and a moved vector replaces the old one whatever its score. The cost per iteration is therefore one evaluation per member plus a number of vector operations quadratic in the population size.

FireflyAlgorithm dataclass

FireflyAlgorithm(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', attraction: float = 1.0, attraction_decay: float = 1.0, noise: float = 0.25, noise_decay: float = 0.97)

Bases: SwarmMethod

Firefly Algorithm on priority vectors.

Attributes:

Name Type Description
attraction float

Attraction beta0 between two vectors at zero distance.

attraction_decay float

The coefficient gamma of the squared distance in the attraction's exponential decay.

noise float

Initial weight alpha_0 of the uniform random term.

noise_decay float

Factor theta applied to the noise weight every iteration.

step

step(swarm: Swarm) -> None

Move every vector towards the better vectors of the previous iteration.

Gravitational Search Algorithm (Rashedi, Nezamabadi-pour and Saryazdi 2009).

Each iteration gives every member a weight from its quality: with v the magnitudes() values, w_i = (v_worst - v_i) / (v_worst - v_best), normalised to sum to one, or equal weights when all values tie. Only the K heaviest members attract, where K falls linearly from the population size to 1 over the budget, the elitism the paper calls Kbest. Member i accelerates by

a_i = sum over attracting j != i of  rand_ij G w_j (x_j - x_i) / (R_ij + eps)

with R_ij the Euclidean distance, a fresh uniform scalar rand_ij per pair, and the gain G = G0 e^(-alpha t/T) with G0 = 100 and alpha = 20 as in the paper. The velocity and the position then follow v_i <- rand_i v_i + a_i and x_i <- x_i + v_i, with a uniform scalar rand_i per member, and the new vectors replace the old ones whatever their scores. All accelerations use the population as it stood when the iteration began. eps is the machine epsilon.

G0 = 100 is large for the unit hypercube: until the gain has decayed, steps overshoot the bounds many times over and the folding back into the hypercube scatters the vectors almost at random. Because x_j - x_i is not normalised, the division by R_ij cancels its length, so the pull of a member does not depend on its distance, as Gauci, Dodd and Groß (2012) point out; the physical law the method is named after would make it fall with the squared distance.

GravitationalSearchAlgorithm dataclass

GravitationalSearchAlgorithm(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', gain: float = 100.0, gain_decay: float = 20.0)

Bases: SwarmMethod

Gravitational Search Algorithm on priority vectors.

One evaluation per member and iteration.

Attributes:

Name Type Description
gain float

The initial gain G0.

gain_decay float

The rate alpha of the gain's exponential decay.

step

step(swarm: Swarm) -> None

Accelerate every vector towards the heaviest members and move it.

dispatchatlas.solvers.swarm.grey_wolf

Grey Wolf Optimizer (Mirjalili, Mirjalili and Lewis 2014).

Each iteration moves every vector to the mean of three points, one drawn around each of the three best vectors evaluated so far (Eqs. 3.5 to 3.7). The point drawn around such a leader L is L - A * |C * L - x| for the member x, with A = 2 a r1 - a and C = 2 r2 for fresh uniform vectors r1 and r2 (Eqs. 3.3 and 3.4), drawn anew for every leader. The coefficient a falls linearly from 2 to 0 over the budget, so the points spread beyond the leaders early and contract around them late. The new vectors replace the old ones whatever their scores.

GreyWolfOptimizer dataclass

GreyWolfOptimizer(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys')

Bases: SwarmMethod

Grey Wolf Optimizer on priority vectors.

One evaluation per member and iteration.

step

step(swarm: Swarm) -> None

Move every vector towards the three best vectors found so far.

dispatchatlas.solvers.swarm.harris_hawks

Harris Hawks Optimization (Heidari, Mirjalili, Faris, Aljarah, Mafarja and Chen 2019).

Each iteration draws, per member x, a coefficient E = 2 E0 (1 - t/T) with E0 uniform in [-1, 1] (Eq. 3), so its range shrinks from [-2, 2] to 0 over the budget, and a factor J = 2 (1 - u) for a uniform u. With b the best vector found so far, m the mean of the population and y a uniformly drawn member, all taken at the start of the iteration, and fresh uniform scalars q, r and r1 to r4:

  • |E| >= 1 (Eq. 1): y - r1 |y - 2 r2 x| when q >= 0.5, otherwise (b - m) - r3 (LB + r4 (UB - LB));
  • |E| < 1 and r >= 0.5: (b - x) - E |J b - x| when |E| >= 0.5 (Eqs. 4 and 5), otherwise b - E |b - x| (Eq. 6);
  • |E| < 1 and r < 0.5: two greedy trials. The first is Y = b - E |J b - c| with c = x when |E| >= 0.5 (Eq. 7) and c = m otherwise (Eq. 12); the second is Z = Y + s * LF, a uniform vector s times Lévy steps with beta = 1.5 scaled by 0.01 (Eqs. 8, 9, and 13). The member moves to Y if it beats the member, otherwise to Z if that does, otherwise it stays (Eqs. 10 and 11).

The first two cases replace the member whatever its new score. As E shrinks, the population passes from the first case to the others. Every trial vector is one evaluation, so an iteration costs between one and two evaluations per member, and a member that keeps its position is not evaluated again.

HarrisHawksOptimization dataclass

HarrisHawksOptimization(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys')

Bases: SwarmMethod

Harris Hawks Optimization on priority vectors.

step

step(swarm: Swarm) -> None

Move every vector by the rule its coefficient E selects.

dispatchatlas.solvers.swarm.jaya

Jaya (Rao 2016).

Each iteration moves every member x towards the best member b and away from the worst member w of the population, both taken when the iteration starts:

x' = x + r1 * (b - |x|) - r2 * (w - |x|)

with fresh uniform vectors r1 and r2 (Eq. 1). x' replaces x only if it is better, so each iteration costs one evaluation per member. The absolute values are the paper's; in the unit hypercube they change nothing.

Jaya dataclass

Jaya(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys')

Bases: SwarmMethod

Jaya on priority vectors.

step

step(swarm: Swarm) -> None

Move every vector towards the best and away from the worst member.

dispatchatlas.solvers.swarm.marine_predators

Marine Predators Algorithm (Faramarzi, Heidarinejad, Mirjalili and Gandomi 2020).

Each iteration moves every member x relative to the best vector e found so far with random vectors: g standard normal, l Lévy steps with beta = 1.5 scaled by 0.05 (the scale of the authors' implementation), and u uniform. With P = 0.5 and CF = (1 - t/T)^(2 t/T), the step that depends on the budget used:

  • first third (Eq. 12): x + P u * g * (e - g * x);
  • second third (Eqs. 13 and 14): x + P u * l * (e - l * x) for the first half of the population, e + P CF g * (g * e - x) for the second half;
  • last third (Eq. 15): e + P CF l * (l * e - x).

A second perturbation follows (Eq. 16). For each member a uniform r is drawn: if r <= FADs, the member moves by CF (LB + v (UB - LB)) * m, with v uniform and the mask m zero where its own uniform draw is below FADs and one elsewhere, as the paper defines it (the authors' code uses the opposite mask); otherwise it moves by (FADs (1 - r) + r) (x_1 - x_2), the difference of two random members, scaled with the same r. FADs = 0.2. The authors' code makes this choice once per iteration for the whole population and scales the differences with a second, independent draw; this port applies Eq. 16 to each member with a single r.

After each of the two moves a member keeps its new vector unless the vector is worse, which costs two evaluations per member and iteration.

MarinePredatorsAlgorithm dataclass

MarinePredatorsAlgorithm(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', step_scale: float = 0.5, jump_probability: float = 0.2)

Bases: SwarmMethod

Marine Predators Algorithm on priority vectors.

Attributes:

Name Type Description
step_scale float

The constant P that scales every step of Eqs. 12 to 15.

jump_probability float

The constant FADs of Eq. 16: the probability of a masked uniform jump instead of a scaled member difference.

step

step(swarm: Swarm) -> None

Apply the step of the current third of the budget, then the perturbation.

dispatchatlas.solvers.swarm.moth_flame

Moth-Flame Optimization (Mirjalili 2015).

The method keeps a sorted memory of the best vectors ever evaluated, as many as the population (the paper merges the moved population with the memory and keeps the best, which amounts to the same set). Each iteration uses the first F = round(N - t (N - 1) / T) entries of that memory, a count falling linearly from the population size N to 1 (Eq. 3.14). Member i moves along a logarithmic spiral around entry m, the one at position min(i, F - 1) (Eqs. 3.12 and 3.13),

x <- |m - x| e^(b s) cos(2 pi s) + m

with shape b and, per component, s = (r - 1) u + 1 for a fresh uniform u, so s lies in [r, 1] where r falls linearly from -1 to -2 over the budget. As F shrinks, more members share the best entries. The moved vectors replace the old ones whatever their scores.

MothFlameOptimization dataclass

MothFlameOptimization(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', spiral_shape: float = 1.0)

Bases: SwarmMethod

Moth-Flame Optimization on priority vectors.

One evaluation per member and iteration.

Attributes:

Name Type Description
spiral_shape float

The constant b of the logarithmic spiral (Eq. 3.12).

step

step(swarm: Swarm) -> None

Spiral every vector around its assigned entry of the memory of best vectors.

dispatchatlas.solvers.swarm.salp_swarm

Salp Swarm Algorithm (Mirjalili, Gandomi, Mirjalili, Saremi, Faris and Mirjalili 2017).

The population is a chain. Each iteration first resamples the head of the chain around the best vector b found so far, component by component,

x_0 <- b +/- c1 ((UB - LB) c2 + LB)

with c2 uniform and the sign drawn by a second uniform c3 (Eq. 3.1), and c1 = 2 e^(-(4 t/T)^2) falling from 2 to nearly 0 over the budget (Eq. 3.2). Every other member then moves halfway to the member ahead of it, x_i <- (x_i + x_(i-1)) / 2 (Eq. 3.4), in chain order, so each follows the already moved one. The new vectors replace the old ones whatever their scores.

The paper draws the minus sign when c3 < 0, which a uniform c3 never is; as in the authors' implementation, each sign has probability one half here. Unlike that implementation, which treats the first half of the chain as heads, this port follows the paper and has a single head. Castelli, Manzoni, Mariot, Nobile and Tangherloni (2022) review both discrepancies.

SalpSwarmAlgorithm dataclass

SalpSwarmAlgorithm(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys')

Bases: SwarmMethod

Salp Swarm Algorithm on priority vectors.

One evaluation per member and iteration.

step

step(swarm: Swarm) -> None

Resample the head of the chain, then pull every member to its predecessor.

dispatchatlas.solvers.swarm.sine_cosine

Sine Cosine Algorithm (Mirjalili 2016).

Each iteration moves every component of every vector by

x <- x + r1 * w(r2) * |r3 * p - x|

where p is the best vector found so far, w is the sine or, with equal probability, the cosine (Eq. 3.3), and fresh uniform draws per component give r2 in [0, 2 pi) and r3 in [0, 2). The amplitude r1 = a (1 - t/T) falls linearly from a to 0 over the budget (Eq. 3.4), so steps longer than the distance to p are common early and the vectors settle late. The moved vectors replace the old ones whatever their scores.

SineCosineAlgorithm dataclass

SineCosineAlgorithm(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', amplitude: float = 2.0)

Bases: SwarmMethod

Sine Cosine Algorithm on priority vectors.

One evaluation per member and iteration.

Attributes:

Name Type Description
amplitude float

The constant a, the amplitude at the start (Eq. 3.4).

step

step(swarm: Swarm) -> None

Move every vector by a sine or cosine step relative to the best vector.

dispatchatlas.solvers.swarm.teaching_learning

Teaching-Learning-Based Optimization (Rao, Savsani and Vakharia 2011).

Each iteration runs two greedy phases over the population:

  1. Every member x proposes x + r (b - F m), where b is the best member and m the mean of the population, both taken when the phase starts, r is a uniform scalar and F, 1 or 2 with equal probability, sets how much of the mean is subtracted.
  2. Every member x then draws another member y and proposes x + r (x - y) if x is better than y, otherwise x + r (y - x): a step away from worse members and towards better ones.

A proposal replaces the member only if it is better, so each iteration costs two evaluations per member. r and F are drawn once per proposal. Črepinšek, Liu and Mernik (2012) report that the published description omits a step of the authors' implementation, gives wrong formulae for the number of evaluations, and wrongly presents the method as free of parameters of its own. This port implements the two published phases and counts every evaluation.

TeachingLearningBasedOptimization dataclass

TeachingLearningBasedOptimization(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys')

Bases: SwarmMethod

Teaching-Learning-Based Optimization on priority vectors.

step

step(swarm: Swarm) -> None

Run the phase guided by the best member, then the pairwise phase.

dispatchatlas.solvers.swarm.whale

Whale Optimization Algorithm (Mirjalili and Lewis 2016).

Each iteration moves every vector x by one of two rules, chosen by a fair coin p:

  • p < 0.5: the point g - A * |C * g - x| (Eqs. 2.1, 2.2, 2.7, 2.8) with A = 2 a r1 - a and C = 2 r2. The guide g is the best vector found so far when |A| < 1 and a uniformly drawn member otherwise, so large coefficients explore around random members and small ones contract around the best vector;
  • p >= 0.5: the logarithmic spiral |x* - x| e^(b l) cos(2 pi l) + x* around the best vector x*, with l uniform in [-1, 1] and shape b (Eq. 2.5).

a falls linearly from 2 to 0 over the budget. A and C are scalars drawn once per member and iteration, and the same A both selects the guide and scales the move, as in the authors' implementation (the paper writes them as vectors but tests |A| < 1 as a single decision). That implementation also draws a random member per component, and draws l from [a2, 1] with a2 falling from -1 to -2 over the run; this port follows the paper on both points. The new vectors replace the old ones whatever their scores.

WhaleOptimizationAlgorithm dataclass

WhaleOptimizationAlgorithm(population_size: int = 20, rule: OrderRule = 'random-key', modes: ModeSource = 'keys', spiral_shape: float = 1.0)

Bases: SwarmMethod

Whale Optimization Algorithm on priority vectors.

One evaluation per member and iteration.

Attributes:

Name Type Description
spiral_shape float

The constant b of the logarithmic spiral (Eq. 2.5).

step

step(swarm: Swarm) -> None

Move every vector relative to the best vector or a random member, or along a spiral.