Multi-objective methods¶
Evolutionary algorithms that approximate the Pareto front of several objectives, and their selection operators.
dispatchatlas.solvers.multiobjective
¶
Multi-objective evolutionary algorithms.
Eight published methods share one evolutionary loop and differ only in their selection:
nsga-ii,Nsga2: non-dominated fronts and crowding distance (Deb, Pratap, Agarwal and Meyarivan 2002);nsga-iii,Nsga3: non-dominated fronts and niching around reference points (Deb and Jain 2014);moea-d,MoeaD: Tchebycheff subproblems with neighbourhood replacement (Zhang and Li 2007);spea2,Spea2: strength fitness, density, and archive truncation (Zitzler, Laumanns and Thiele 2001);ibea,Ibea: additive epsilon indicator fitness (Zitzler and Künzli 2004);sms-emoa,SmsEmoa: steady-state removal of the smallest hypervolume contributor (Beume, Naujoks and Emmerich 2007);rvea,Rvea: reference vectors and the angle-penalised distance (Cheng, Jin, Olhofer and Sendhoff 2016);age-moea-ii,AgeMoea2: survival by the estimated geometry of the first front (Panichella 2022).
Genomes and variation. A genome is a precedence-feasible item sequence (tasks, or whole jobs in permutation problems) and an explicit mode for every task. Children come from the order crossover of Davis (1985) and a uniform crossover of the modes, followed by an insert or swap move and a redraw of some modes; sequences are repaired to respect precedence. Every child is decoded by the shared schedule builder, counts against the budget, and is scored on every objective the problem declares.
Deadlines. Hard deadlines are handled by the constrained domination of Deb, Pratap, Agarwal and Meyarivan (2002): a schedule that meets every deadline is better than one that does not, and of two that do not, the one with the smaller total overrun is better. Each method applies its own rule to the feasible members and fills the rest of the population with the members of smallest overrun.
Result. The front of a result is the run's archive: the non-dominated
feasible schedules among all evaluated ones, over the problem's objectives,
with values equal to those evaluate()
computes. The result's schedule is the best one for the primary objective.
The pure selection rules live in
selection.
register
¶
register(registry: SolverRegistry) -> None
Add the multi-objective evolutionary algorithms to registry.
dispatchatlas.solvers.multiobjective.nsga2
¶
NSGA-II: non-dominated sorting with crowding distance.
Nsga2
dataclass
¶
Nsga2(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0)
Bases: MultiObjectiveEvolution
The non-dominated sorting genetic algorithm II (Deb, Pratap, Agarwal and Meyarivan 2002).
Each generation breeds population_size children from parents chosen
by binary tournaments under the crowded comparison: the lower
non-dominated rank wins, and on equal ranks the larger crowding distance.
Parents and children are then sorted into non-dominated fronts, whole
fronts survive in rank order, and the front that does not fit keeps its
members of largest crowding distance, the boundary points of every
objective first. Deadline overruns are handled by the constrained
domination of the same paper (see dispatchatlas.solvers.multiobjective).
With one objective the fronts are groups of equal values, and the method is a (mu + mu) evolutionary algorithm that keeps the best members.
selection
¶
Return the crowding-distance selection for one run.
dispatchatlas.solvers.multiobjective.nsga3
¶
NSGA-III: non-dominated sorting with niching around reference points.
Nsga3
dataclass
¶
Nsga3(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0)
Bases: MultiObjectiveEvolution
The reference-point-based NSGA-III of Deb and Jain (2014).
The reference points are the Das and Dennis (1998) lattice of the unit
simplex with the most divisions that give at most population_size
points. Each generation breeds population_size children from pairs of
parents drawn at random, as the paper prescribes. Parents and children are
sorted into non-dominated fronts, whole fronts survive in rank order, and
the front that does not fit is filled by niching: objectives are
normalised by the ideal point and the intercepts of the hyperplane through
the extreme points, every member joins its nearest reference line, and the
least represented reference points receive members first. Deadline
overruns are handled by constrained domination.
With one objective the lattice is a single reference point and the method keeps the best members, breaking ties among equal values at random.
selection
¶
Return the niching selection for one run.
dispatchatlas.solvers.multiobjective.moead
¶
MOEA/D: decomposition into Tchebycheff subproblems.
MoeaD
dataclass
¶
MoeaD(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0, neighbourhood_size: int = 20)
Bases: MultiObjectiveEvolution
The multi-objective evolutionary algorithm based on decomposition (Zhang and Li 2007).
The weight vectors are the Das and Dennis (1998) lattice with the most
divisions that give at most population_size points, and each defines
a Tchebycheff subproblem with one incumbent schedule. Objectives are
normalised by the ideal point and the largest value in the population, the
normalisation the paper applies to disparately scaled objectives, and
zero weights count as WEIGHT_FLOOR.
In every generation each subproblem in turn breeds one child from two
distinct incumbents of its neighbourhood, the neighbourhood_size
nearest weight vectors; the child updates the ideal point and replaces
every neighbourhood incumbent whose scalarised value is no better than its
own. With deadlines, a child replaces an incumbent when it overruns them by
less, or by as much with a no larger scalarised value. The run's archive
of non-dominated schedules plays the role of the paper's external
population.
With one objective the lattice holds a single weight vector, and the method is a (1 + 1) evolutionary algorithm in which a child replaces its parent when it is no worse.
Attributes:
| Name | Type | Description |
|---|---|---|
neighbourhood_size |
int
|
Weight vectors in each neighbourhood, the vector itself included; 20 in the paper's experiments. |
selection
¶
Return the decomposition selection for one run.
dispatchatlas.solvers.multiobjective.spea2
¶
SPEA2: strength fitness, nearest-neighbour density, and archive truncation.
Spea2
dataclass
¶
Spea2(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0)
Bases: MultiObjectiveEvolution
The improved strength Pareto evolutionary algorithm of Zitzler, Laumanns and Thiele (2001).
The population is the archive, of population_size members, and each
generation breeds as many children from parents chosen by binary
tournaments on fitness. Every member of the archive and the children
receives the SPEA2 fitness: the summed strengths of the members that
dominate it, the strength being the number of members a member dominates,
plus a density 1 / (sigma + 2) from the distance to the k-th nearest
member, k the square root of their number. All non-dominated members
enter the next archive; a shortfall is filled with the dominated members of
best fitness, and a surplus is removed one member at a time, always the one
closest to its nearest remaining neighbour, ties by the next nearest.
Distances are measured after scaling each objective to the range of the
members, so that they do not depend on the objectives' units; the paper
uses raw objective values. Deadline overruns are handled by constrained
domination.
With one objective the fitness orders members by value, and the method keeps the best members.
selection
¶
Return the strength-fitness selection for one run.
dispatchatlas.solvers.multiobjective.ibea
¶
IBEA: fitness from the additive epsilon indicator.
Ibea
dataclass
¶
Ibea(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0, kappa: float = IBEA_KAPPA)
Bases: MultiObjectiveEvolution
The indicator-based evolutionary algorithm of Zitzler and Künzli (2004).
Each generation breeds population_size children from parents chosen by
binary tournaments on fitness. Objectives of parents and children are
scaled to their range, and each member x receives the fitness
sum over y != x of -exp(-I(y, x) / (c * kappa)), where I is the
additive epsilon indicator and c its largest absolute value, the
adaptive variant of the paper. The least fit member is removed and the
others' fitness is updated to exclude it, until population_size
members remain. Deadline overruns are handled by constrained domination.
With one objective the indicator is the difference of values, and the method removes the worst members.
Attributes:
| Name | Type | Description |
|---|---|---|
kappa |
float
|
Scaling factor of the fitness; 0.05 in the paper. |
selection
¶
Return the indicator selection for one run.
dispatchatlas.solvers.multiobjective.sms_emoa
¶
SMS-EMOA: steady-state selection by hypervolume contribution.
SmsEmoa
dataclass
¶
SmsEmoa(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0)
Bases: MultiObjectiveEvolution
The S-metric selection EMOA of Beume, Naujoks and Emmerich (2007).
A steady-state (mu + 1) algorithm: each step breeds one child from two
parents drawn at random, sorts the parents and the child into
non-dominated fronts, and removes from the last front the member whose
exclusive hypervolume is smallest. The contributions are exact. The best
member of the last front in each objective is always kept, which Emmerich,
Beume and Naujoks (2005) note makes a reference point unnecessary with
two objectives; with more, the reference point lies beyond the front's
worst values by a tenth of its range. When a member misses a deadline, the
member with the largest overrun is removed instead, the last front under
constrained domination. population_size steps make one iteration.
With one objective the last front holds the members of worst value, and the method is a steady-state evolutionary algorithm that removes one of them per step.
selection
¶
Return the hypervolume selection for one run.
dispatchatlas.solvers.multiobjective.rvea
¶
RVEA: reference vectors and the angle-penalised distance.
Rvea
dataclass
¶
Rvea(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0, alpha: float = 2.0, adaptation_frequency: float = 0.1)
Bases: MultiObjectiveEvolution
The reference vector guided evolutionary algorithm, RVEA.
The method of Cheng, Jin, Olhofer and Sendhoff (2016). The reference
vectors are the Das and Dennis (1998) lattice with the most
divisions that give at most population_size points, scaled to unit
length. Each generation breeds one child per vector from pairs of parents
drawn at random. Parents and children are translated by their ideal point
and grouped by the vector at the smallest angle, and each group keeps the
member of smallest angle-penalised distance
(1 + M * (t / t_max) ** alpha * theta / gamma) * |f'|, where theta
is the member's angle to its vector and gamma the vector's smallest
angle to another vector. The fraction t / t_max is the fraction of the
budget used, so the selection moves from convergence to spread along the
vectors as the run proceeds. Each time a further adaptation_frequency
of the budget is used, the vectors are rescaled to the ranges of the
objectives in the population. The population therefore holds at most one
member per vector. Deadlines are handled by constrained domination within
each group: a group keeps its feasible member of smallest distance or,
without one, its member of smallest deadline overrun.
With one objective there is one vector and the method is a (1 + 1) evolutionary algorithm that keeps the better of parent and child.
Attributes:
| Name | Type | Description |
|---|---|---|
alpha |
float
|
Rate at which the angle penalty grows with the budget used; 2 in the paper. |
adaptation_frequency |
float
|
Fraction of the budget between vector adaptations; 0.1 in the paper. |
selection
¶
Return the reference-vector selection for one run.
dispatchatlas.solvers.multiobjective.age_moea2
¶
AGE-MOEA-II: survival by the estimated geometry of the first front.
AgeMoea2
dataclass
¶
AgeMoea2(population_size: int = 40, crossover_rate: float = 0.9, mutation_rate: float = 0.2, mode_mutation: float = 1.0)
Bases: MultiObjectiveEvolution
The adaptive geometry estimation MOEA of Panichella (2022), AGE-MOEA-II.
Each generation breeds population_size children from parents chosen by
binary tournaments on non-dominated rank, then on survival score. Parents
and children are sorted into non-dominated fronts and whole fronts survive
in rank order. The first front is normalised by its ideal point and the
intercepts of its extreme points, and Newton's method fits the exponent
p of the surface sum f_i ** p = 1 through its central point, which
tells a linear front from a convex or a concave one. Its extreme points
score infinity, and the others are scored greedily by the geodesic
distance, on the fitted surface, to their two nearest already scored
points (Panichella 2019; 2022). Later fronts score their proximity to the
ideal point in the p-norm. The front that does not fit keeps its best
scores. Deadline overruns are handled by constrained domination.
With one objective the first front holds the members of best value and later fronts are ordered by value, so the method keeps the best members.
selection
¶
Return the geometry-based selection for one run.
dispatchatlas.solvers.multiobjective.selection
¶
Environmental and mating selection of the multi-objective evolutionary algorithms.
Every function here is pure and works on objective vectors in minimisation
form, as vector() returns them.
Functions that break ties at random take the run's generator. The solvers in
this package call them on the feasible members of a population; infeasible
members are ranked by deadline overrun before any of these rules applies.
Contents, by method:
- shared: ideal and nadir points, range normalisation, and the Das and Dennis (1998) points of the unit simplex;
- NSGA-II: survival by non-dominated fronts and crowding distance;
- NSGA-III: hyperplane normalisation and niching around reference points;
- SPEA2: strength fitness with nearest-neighbour density, and archive truncation;
- IBEA: additive epsilon indicator fitness and its update on removal;
- SMS-EMOA: exact hypervolume contributions and the choice of the member to discard;
- MOEA/D: the Tchebycheff scalarisation and weight neighbourhoods;
- RVEA: angle-penalised distance and reference-vector adaptation;
- AGE-MOEA-II: estimation of the front's curvature, geodesic distances, and survival scores.
ASF_WEIGHT
module-attribute
¶
Weight of the other objectives in the achievement function that finds extreme points.
WEIGHT_FLOOR
module-attribute
¶
Smallest weight the Tchebycheff scalarisation gives an objective.
IBEA_KAPPA
module-attribute
¶
Fitness scaling factor of IBEA used by Zitzler and Künzli (2004).
Survivors
dataclass
¶
The members an environmental selection keeps, with their mating keys.
Attributes:
| Name | Type | Description |
|---|---|---|
indices |
tuple[int, ...]
|
Positions of the kept members in the pool, in selection order. |
keys |
tuple[tuple[float, ...], ...]
|
One key per kept member, aligned with |
ideal_point
¶
Return the smallest value of every objective over points.
nadir_point
¶
Return the largest value of every objective over points.
normalize
¶
normalize(points: Sequence[Vector], lower: Vector | None = None, upper: Vector | None = None) -> list[Point]
Map every objective linearly so that lower becomes 0 and upper becomes 1.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
points
|
Sequence[Vector]
|
Objective vectors. |
required |
lower
|
Vector | None
|
Values mapped to 0. Defaults to the ideal point of |
None
|
upper
|
Vector | None
|
Values mapped to 1. Defaults to the nadir point of |
None
|
Returns:
| Type | Description |
|---|---|
list[Point]
|
The mapped vectors. An objective whose bounds coincide is only |
list[Point]
|
translated, so its values stay finite. |
das_dennis
¶
Return the Das and Dennis (1998) lattice of the unit simplex.
Every point has non-negative coordinates that are multiples of
1 / divisions and sum to one. There are
comb(divisions + objectives - 1, objectives - 1) of them, listed in
increasing lexicographic order of their leading coordinates, the last
coordinate taking what remains: (0, 1), (0.5, 0.5), (1, 0) for two
objectives and two divisions. With one objective the lattice is the single
point (1,).
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
divisions
|
int
|
Steps along each objective, at least 1. |
required |
objectives
|
int
|
Number of objectives, at least 1. |
required |
Raises:
| Type | Description |
|---|---|
ValueError
|
If either count is smaller than 1. |
simplex_divisions
¶
Return the most divisions whose Das and Dennis lattice has at most size points.
This sizes the reference sets of NSGA-III, MOEA/D, and RVEA from a
population size. The result is at least 1, so with more objectives than
size the lattice has one point per objective.
perpendicular_distance
¶
Return the distance from point to the line through the origin along direction.
extreme_points
¶
Return, for every objective, the point that best approximates its axis.
The extreme point of objective j minimises the achievement function
max_i f_i / w_i with w_j = 1 and every other weight
ASF_WEIGHT, as in Deb and Jain (2014). Points should be translated
so that the ideal point is the origin. Ties go to the lowest index, and a
point may be extreme for several objectives.
intercepts
¶
Return where the hyperplane through the extreme points meets each objective axis.
Points should be translated so that the ideal point is the origin. When the extreme points do not span a hyperplane with positive intercepts, because two of them coincide or they are linearly dependent, the largest value of each objective is used instead, and an objective whose largest value is zero keeps the scale 1.
hyperplane_normalize
¶
Normalise points by the ideal point and the intercepts of their extreme points.
The adaptive normalisation of Deb and Jain (2014): translate so that the
ideal point is the origin, find one extreme point per objective with
extreme_points(), and divide each objective by the intercept of the
hyperplane through them (intercepts()). AGE-MOEA-II uses the same
procedure.
Returns:
| Type | Description |
|---|---|
tuple[list[Point], list[int]]
|
The normalised points and the indices of the extreme points. |
crowding_survival
¶
crowding_survival(points: Sequence[Vector], size: int) -> Survivors
Select size points by non-dominated fronts, then crowding distance.
The environmental selection of NSGA-II (Deb, Pratap, Agarwal and
Meyarivan 2002): whole fronts are kept in rank order, and the front that
does not fit is cut by decreasing crowding distance, boundary points
first, ties in front order. Each survivor's key is (rank, -crowding),
the crowded-comparison order of the binary tournament.
niching_survival
¶
niching_survival(points: Sequence[Vector], size: int, references: Sequence[Vector], rng: Random) -> list[int]
Select size points by non-dominated fronts, then niching around reference points.
The environmental selection of NSGA-III (Deb and Jain 2014). Whole fronts
are kept while they fit. The kept points and the front that does not fit
are normalised together (hyperplane_normalize()), and each is
associated with the reference line, through the origin and a reference
point, at the smallest perpendicular distance. The niche count of a
reference point is the number of kept points associated with it. Points
of the last front are then added one at a time: a reference point with
the smallest niche count is drawn at random; if no remaining point of the
last front is associated with it, it leaves the competition; otherwise it
receives the associated point nearest its line when its count is zero,
and a random associated point otherwise.
Returns:
| Type | Description |
|---|---|
list[int]
|
Indices of the selected points: the kept fronts in rank order, then |
list[int]
|
the niched points in the order they were chosen. |
spea2_fitness
¶
Return the SPEA2 fitness of every point: raw fitness plus density.
Zitzler, Laumanns and Thiele (2001). The strength of a point is the number
of points it dominates; its raw fitness is the sum of the strengths of the
points that dominate it, zero for a non-dominated point; its density is
1 / (sigma + 2), where sigma is the Euclidean distance to its k-th
nearest neighbour. Smaller is better, and exactly the non-dominated points
score below 1.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
points
|
Sequence[Vector]
|
Objective vectors. |
required |
k
|
int | None
|
Neighbour rank of the density. Defaults to the integer square root of the number of points, the square root of the sample size of the paper. |
None
|
spea2_truncation
¶
Return the indices left after SPEA2's archive truncation.
Points are removed one at a time until size remain. The removed point
has the smallest distance to its nearest remaining neighbour; ties are
decided by the second-nearest distance, then the third, and so on, which
is the lexicographic order of the sorted distance lists
(Zitzler, Laumanns and Thiele 2001). Complete ties go to the lowest index.
Returns:
| Type | Description |
|---|---|
list[int]
|
The remaining indices, in increasing order. |
spea2_survival
¶
spea2_survival(points: Sequence[Vector], size: int) -> Survivors
Select size points by the SPEA2 environmental selection.
Every non-dominated point is kept. A shortfall is filled with the
dominated points of smallest fitness; a surplus is removed by
spea2_truncation(). Objectives are first scaled to the range of the
pool, so that distances, and with them the density and the truncation, do
not depend on the objectives' units. Each survivor's key is its fitness.
additive_epsilon
¶
Return the additive epsilon indicator max_i (first_i - second_i).
It is the smallest amount by which first must be translated in every
objective to weakly dominate second, negative when first
dominates second.
ibea_fitness
¶
ibea_fitness(points: Sequence[Vector], kappa: float = IBEA_KAPPA) -> list[float]
Return the IBEA fitness of every point, larger being better.
The adaptive fitness of Zitzler and Künzli (2004): objectives are scaled to
the range of the points, I is the additive epsilon indicator
(additive_epsilon()), c the largest absolute indicator value,
and F(x) = sum over y != x of -exp(-I(y, x) / (c * kappa)).
ibea_survival
¶
ibea_survival(points: Sequence[Vector], size: int, kappa: float = IBEA_KAPPA) -> Survivors
Select size points by IBEA's environmental selection.
The point of smallest fitness (ibea_fitness()) is removed, and every
remaining point x gains exp(-I(removed, x) / (c * kappa)), which
is exactly its fitness without the removed point; this repeats until
size points remain (Zitzler and Künzli 2004). Ties go to the lowest
index. Each survivor's key is its negated final fitness.
Returns:
| Type | Description |
|---|---|
Survivors
|
The survivors in increasing index order. |
hypervolume_contributions
¶
Return the exclusive hypervolume of every point.
The contribution of a point is the volume that it alone dominates within
the box bounded by reference: the hypervolume of the set minus the
hypervolume of the set without it. Points outside the box, dominated
points, and repeated points contribute nothing. Two and three objectives
use exact sweeps; more objectives take differences of
dispatchatlas.core.pareto.hypervolume().
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
points
|
Sequence[Vector]
|
Objective vectors in minimisation form. |
required |
reference
|
Vector
|
The corner of the box, worse than the points in every objective. |
required |
Returns:
| Type | Description |
|---|---|
list[float]
|
One contribution per point. |
last_front
¶
Return, in increasing order, the indices of the last non-dominated front.
It equals the last front of
fast_non_dominated_sort() at a lower
cost: a point's front is one more than the highest front among the
points that dominate it, and every dominating point precedes the point
in lexicographic order, so one pass in that order ranks every point.
hypervolume_discard
¶
Return the index of the point SMS-EMOA removes from a pool.
The point comes from the last non-dominated front of the pool
(Beume, Naujoks and Emmerich 2007). A last front of one point loses it.
Otherwise the front is scaled to its own range, the best point in each
objective is kept, as Emmerich, Beume and Naujoks (2005) allow, and the
point of smallest exact hypervolume contribution
(hypervolume_contributions()) is removed, ties at random. The
reference point lies beyond the front's worst values by
HYPERVOLUME_MARGIN of its range, so the choice does not depend on
the objectives' units.
tchebycheff
¶
Return the weighted Tchebycheff distance of vector from ideal.
max_i w_i * |f_i - z_i| / s_i (Zhang and Li 2007), where each weight
is at least WEIGHT_FLOOR, so that the subproblems on the edge of
the simplex still prefer Pareto-optimal points, and s is the
normalising span of each objective, 1 by default.
weight_neighbourhoods
¶
Return, for every weight vector, the size nearest weight vectors.
Distances are Euclidean, so a vector is its own nearest neighbour and comes first. Ties go to the lower index.
unit_vectors
¶
Return each point scaled to unit Euclidean length. A zero point is kept as it is.
smallest_angles
¶
Return the angle between each unit vector and its nearest other vector.
This is the gamma that normalises the angle penalty of RVEA. A vector
without a distinct neighbour, as with one objective, gets 1.
adapt_vectors
¶
Rescale reference vectors to the ranges of the objectives.
RVEA's adaptation (Cheng, Jin, Olhofer and Sendhoff 2016): each initial
vector is multiplied objective by objective by nadir - ideal and
scaled back to unit length. An objective whose range is zero keeps the
factor 1.
rvea_survival
¶
rvea_survival(points: Sequence[Vector], vectors: Sequence[Vector], gammas: Sequence[float], progress: float, alpha: float = 2.0, violations: Sequence[float] | None = None) -> list[int]
Keep at most one point per reference vector by angle-penalised distance.
RVEA's elitism selection (Cheng, Jin, Olhofer and Sendhoff 2016). Points
are translated by their ideal point and each joins the unit reference
vector at the smallest angle theta. Within each group the point of
smallest angle-penalised distance
(1 + M * progress ** alpha * theta / gamma) * |f'| survives, where
M is the number of objectives and gamma the vector's
smallest_angles() entry. Early in a run the penalty is small and the
point closest to the ideal point wins, which favours convergence; late in
the run the angle dominates, which spreads the points along the vectors.
With violations, a group keeps its feasible point of smallest distance
or, if it has none, its point of smallest violation.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
points
|
Sequence[Vector]
|
Objective vectors. |
required |
vectors
|
Sequence[Vector]
|
Unit reference vectors. |
required |
gammas
|
Sequence[float]
|
Smallest angle between each vector and the others. |
required |
progress
|
float
|
Fraction of the budget used, in |
required |
alpha
|
float
|
Rate at which the penalty grows with |
2.0
|
violations
|
Sequence[float] | None
|
Constraint violation of each point, zero when feasible. |
None
|
Returns:
| Type | Description |
|---|---|
list[int]
|
One index per reference vector that attracted a point, in vector order. |
minkowski_norm
¶
Return (sum |v_i| ** p) ** (1 / p), computed without overflow.
newton_curvature
¶
newton_curvature(point: Vector, precision: float = NEWTON_PRECISION, steps: int = NEWTON_STEPS) -> float
Solve sum point_i ** p = 1 for p by Newton's method.
The root finder of AGE-MOEA-II (Panichella 2022), as in the author's
implementation: starting from p = 1, it iterates on
f(p) = log(sum point_i ** p), whose derivative is
sum point_i ** p * log(point_i) / sum point_i ** p over the positive
coordinates, until a step moves p by at most precision or
steps steps are made.
Returns:
| Type | Description |
|---|---|
float
|
The estimate, or |
float
|
coordinate, a zero derivative, or overflow. |
corner_points
¶
Return, for each objective axis, the point nearest to it.
A front with no more points than objectives is all corners. Otherwise the point at the smallest perpendicular distance from each axis is a corner, ties to the lowest index, as in the reference implementation of AGE-MOEA-II.
front_curvature
¶
Estimate the exponent p of the surface sum f_i ** p = 1 through a normalised front.
AGE-MOEA-II takes the point nearest the origin among those that are not
corners (corner_points()) and solves for the p whose surface
passes through it (newton_curvature()): 1 for a linear front, 2 for
a spherical one, below 1 for a convex one. A failed estimate, a
non-positive one, or a front without such a point gives 1.
project_to_front
¶
Scale point onto the surface sum f_i ** p = 1. A zero point stays as it is.
geodesic_distance
¶
Return the AGE-MOEA-II distance between two points of the surface sum f_i ** p = 1.
The midpoint of the two points is projected onto the surface
(project_to_front()), and the distance is the sum of the Euclidean
distances from each point to that projection (Panichella 2022), a
two-segment approximation of the geodesic that grows with the curvature.
age_scores
¶
Return the AGE-MOEA-II survival score of every point of a first front, and p.
As in the author's implementation: the front is normalised
(hyperplane_normalize()), its curvature p is estimated
(front_curvature()), and every point is projected onto the surface
of that curvature. The extreme points score infinity. The other points
are ranked greedily: the next one is the point whose two nearest already
ranked points are farthest in geodesic distance divided by the point's own
p-norm, and it scores that sum. Every non-extreme point is scored.
Returns:
| Type | Description |
|---|---|
tuple[list[float], float]
|
The scores, larger being better, and the curvature |
age_survival
¶
age_survival(points: Sequence[Vector], size: int) -> Survivors
Select size points by the environmental selection of AGE-MOEA-II.
Whole non-dominated fronts are kept in rank order. The first front is
scored by age_scores(); every later front by its proximity
1 / |f - z|_p, the inverse p-norm distance to the ideal point of
the pool in the objectives' own units, as in the author's implementation.
The front that does not fit is cut by decreasing score, ties in front
order (Panichella 2022). Each survivor's key is (rank, -score).