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 ofdispatchatlas.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:
- elitism: the
elitesbest members pass unchanged, without a new evaluation; - selection: each further child has two parents, each the best of
tournament_sizemembers drawn uniformly with replacement; - crossover: with probability
crossover_rate, the order crossover of Davis (1985) and a uniform crossover of the mode settings (seerecombine()); otherwise a copy of the first parent; - 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
|
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:
- the elite, the
elite_fractionbest members, copied unchanged and never evaluated again; - mutants,
mutant_fractionof new uniform random chromosomes; - 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
inheritanceand 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. |
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. |
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:
- selection: the
selection_fractionbest members are selected (truncation selection); - estimation: each coordinate's normal distribution gets the maximum likelihood mean and standard deviation of the selected members;
- sampling: the next population holds the
elitesbest 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
|
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:
- diversification: new sequences are built position by position, each
next item drawn among the eligible ones with probability proportional
to
1 / (1 + f), wherefcounts how often the item has held that position in the sequences built so far; - improvement: the first-improvement climb of
climb(), which stops aftermax_failuresconsecutive random neighbours fail to improve; - reference set:
reference_sizesolutions, thequality_sizebest of the improved population and then, one at a time, the solution whose smallestdistance()to those already chosen is largest; - subset generation: every pair of reference solutions of which at least one entered the set since the last round;
- 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 |
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.
distance
¶
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 |
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
¶
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 |
beta |
float
|
Weight |
heuristic |
str
|
The priority rule of the desirability: |
evaporation |
float
|
Fraction of pheromone lost per iteration. |
best_probability |
float
|
The |
deposit |
Literal['iteration-best', 'best-so-far']
|
|
modes |
Literal['builder', 'pheromone']
|
|
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Build and reinforce until a stop criterion fires.
position_trails
¶
Return fresh (item, position) trails for items.
heuristic_rule
¶
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).
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;ScheduleRunscores 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
¶
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. |
cube
classmethod
¶
cube(dimension: int, lower: float, upper: float, *, strict: bool = True) -> Box
Return the box [lower, upper] in every one of dimension coordinates.
contains
¶
Return whether every coordinate of vector lies within its bounds.
clip
¶
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. |
progress
property
¶
Fraction of the tightest time, evaluation, or iteration limit spent, in [0, 1].
evaluate
¶
Return the fitness of vector, counting one evaluation.
Raises:
| Type | Description |
|---|---|
Exhausted
|
When a stop criterion fires. |
next_iteration
¶
improvement
¶
Return how much better after is than before, positive when it is better.
note
¶
Record a fact about the search, such as the final population size.
Optimizer
¶
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 |
elapsed
property
¶
Seconds since the run started, or since the origin clock_origin set.
progress
property
¶
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().
evaluate
¶
Return the function value of vector, counting one evaluation.
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
¶
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 |
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
VectorEncodingwith 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 (seeEncodedSolver.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
¶
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.
improvement
¶
Return score_improvement() of the two scores.
EncodedSolver
dataclass
¶
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 |
modes |
Literal['keys', 'builder']
|
Where the modes of multi-mode tasks come from. |
solve
¶
solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult
Search the random-key space of problem until a stop criterion fires.
score_improvement
¶
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:
- mutation:
v = x_a + F (x_b - x_c)for three distinct membersa,b,cother thani, drawn uniformly; - binomial crossover: the trial takes each coordinate from
vwith probabilityCRand fromx_iotherwise; one coordinate drawn uniformly always comes fromv; - selection: the trial replaces
x_iwhen 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 |
scale_factor |
float
|
Difference weight |
crossover_rate |
float
|
Crossover probability |
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 |
social |
float
|
Acceleration |
velocity_limit |
float
|
Velocity limit as a fraction of the box width; 1 limits each step to the dynamic range of its coordinate. |
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 |
refresh_gap |
int
|
Evaluations without improvement before new exemplars, |
velocity_limit |
float
|
Velocity limit as a fraction of the box width. |
learning_probabilities
¶
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
¶
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 |
required |
Attributes:
| Name | Type | Description |
|---|---|---|
crossover |
|
|
scale |
|
|
terminal |
Whether each slot's |
|
cursor |
The slot the next update writes. |
update
¶
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
¶
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:
- current-to-pbest/1 mutation (Zhang and Sanderson 2009):
v = x_i + F (x_pbest - x_i) + F (x_r1 - x_r2), wherex_pbestis drawn uniformly from themax(2, round(p N))best members,x_r1from the population andx_r2from the population together with the archive, withi,r1, andr2distinct positions; - binomial crossover with rate
CR, one uniformly drawn coordinate always taken fromv; - repair: a coordinate outside the box moves halfway back to that of
x_i; - selection: the trial replaces
x_iwhen no worse. When strictly better,x_ienters the archive and(CR, F)counts as a success, weighted by the improvement (for schedules, seescore_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 |
min_population |
int
|
Final population |
memory_size |
int
|
Memory slots |
best_fraction |
float
|
Fraction |
archive_rate |
float
|
Archive capacity as a multiple of the population size. |
lehmer_mean
¶
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
¶
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 toln((lambda + 1) / 2) - ln i, summing to 1;mu_eff = 1 / sum(w_i^2);c_sigma = (mu_eff + 2) / (n + mu_eff + 5)andd_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)andc_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
|
|
offspring |
int
|
|
parents |
int
|
|
weights |
NDArray[float64]
|
Recombination weights of the |
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 |
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:
- the mean moves to the weighted mean of the
mubest points,m' = m + sigma y_wwithy_w = sum(w_i y_{i:lambda}); - the conjugate evolution path
p_sigmaaccumulatesC^{-1/2} y_wand the step size follows its length:sigma' = sigma exp((c_sigma / d_sigma) (|p_sigma| / chi_n - 1))(cumulative step-size adaptation); - the evolution path
p_caccumulatesy_w, except while|p_sigma|is too long, theh_sigmastall of the tutorial; - the covariance combines a rank-one update with
p_cand 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), wheredelta = (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 |
step_size |
float
|
Initial step size as a fraction of the box width. |
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.
METHODS
module-attribute
¶
METHODS: tuple[type[SwarmMethod], ...] = (GreyWolfOptimizer, WhaleOptimizationAlgorithm, FireflyAlgorithm, MothFlameOptimization, SineCosineAlgorithm, ArithmeticOptimizationAlgorithm, HarrisHawksOptimization, TeachingLearningBasedOptimization, SalpSwarmAlgorithm, MarinePredatorsAlgorithm, CuckooSearch, ArtificialBeeColony, GravitationalSearchAlgorithm, Jaya)
Every method of the package, in the order of the list above.
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) * worb * MOP * w, with equal probability; - otherwise (Eq. 5):
b - MOP * worb + 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_max |
float
|
Value of |
alpha |
float
|
Exponent |
mu |
float
|
Control parameter |
dispatchatlas.solvers.swarm.bee_colony
¶
Artificial Bee Colony (Karaboga and Basturk 2007).
Each iteration has three phases:
- Every member
xproposes a copy of itself with one uniformly drawn componentkmoved tox_k + phi (x_k - y_k), whereyis another uniformly drawn member andphiis uniform in[-1, 1], and keeps it only if it is better. - 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 isf = 1 / (1 + v)for a numberv >= 0andf = 1 + |v|otherwise, wherevis the member'smagnitudes()value, and the probabilities are fixed when the phase starts. - 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. |
step
¶
Run the three phases: every member, members drawn by quality, restart.
dispatchatlas.solvers.swarm.cuckoo_search
¶
Cuckoo Search (Yang and Deb 2009).
Each iteration has two phases:
- Every member
xproposesx + alpha * l(Eq. 1), wherelis a vector of Lévy steps of indexbeta = 1.5drawn by Mantegna's algorithm, and keeps it unless it is worse. - The worst fraction
paof 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.25as 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 |
step
¶
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 |
attraction_decay |
float
|
The coefficient |
noise |
float
|
Initial weight |
noise_decay |
float
|
Factor |
step
¶
Move every vector towards the better vectors of the previous iteration.
dispatchatlas.solvers.swarm.gravitational_search
¶
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 |
gain_decay |
float
|
The rate |
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.
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|whenq >= 0.5, otherwise(b - m) - r3 (LB + r4 (UB - LB));|E| < 1andr >= 0.5:(b - x) - E |J b - x|when|E| >= 0.5(Eqs. 4 and 5), otherwiseb - E |b - x|(Eq. 6);|E| < 1andr < 0.5: two greedy trials. The first isY = b - E |J b - c|withc = xwhen|E| >= 0.5(Eq. 7) andc = motherwise (Eq. 12); the second isZ = Y + s * LF, a uniform vectorstimes Lévy steps withbeta = 1.5scaled by 0.01 (Eqs. 8, 9, and 13). The member moves toYif it beats the member, otherwise toZif 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.
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.
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 |
jump_probability |
float
|
The constant |
step
¶
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 |
step
¶
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
¶
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 |
step
¶
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:
- Every member
xproposesx + r (b - F m), wherebis the best member andmthe mean of the population, both taken when the phase starts,ris a uniform scalar andF, 1 or 2 with equal probability, sets how much of the mean is subtracted. - Every member
xthen draws another memberyand proposesx + r (x - y)ifxis better thany, otherwisex + 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.
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 pointg - A * |C * g - x|(Eqs. 2.1, 2.2, 2.7, 2.8) withA = 2 a r1 - aandC = 2 r2. The guidegis the best vector found so far when|A| < 1and 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 vectorx*, withluniform in[-1, 1]and shapeb(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 |
step
¶
Move every vector relative to the best vector or a random member, or along a spiral.