Skip to content

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

selection(evolution: Evolution) -> GenerationalSelection

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

selection(evolution: Evolution) -> GenerationalSelection

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

selection(evolution: Evolution) -> SteadyStateSelection

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

selection(evolution: Evolution) -> GenerationalSelection

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

selection(evolution: Evolution) -> GenerationalSelection

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

selection(evolution: Evolution) -> SteadyStateSelection

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

selection(evolution: Evolution) -> GenerationalSelection

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

selection(evolution: Evolution) -> GenerationalSelection

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

ASF_WEIGHT = 1e-06

Weight of the other objectives in the achievement function that finds extreme points.

WEIGHT_FLOOR module-attribute

WEIGHT_FLOOR = 1e-06

Smallest weight the Tchebycheff scalarisation gives an objective.

IBEA_KAPPA module-attribute

IBEA_KAPPA = 0.05

Fitness scaling factor of IBEA used by Zitzler and Künzli (2004).

Survivors dataclass

Survivors(indices: tuple[int, ...], keys: tuple[tuple[float, ...], ...])

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 indices. A binary tournament prefers the member with the smaller key.

ideal_point

ideal_point(points: Sequence[Vector]) -> Point

Return the smallest value of every objective over points.

nadir_point

nadir_point(points: Sequence[Vector]) -> 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 points.

None
upper Vector | None

Values mapped to 1. Defaults to the nadir point of points.

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

das_dennis(divisions: int, objectives: int) -> list[Point]

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

simplex_divisions(objectives: int, size: int) -> int

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

perpendicular_distance(point: Vector, direction: Vector) -> float

Return the distance from point to the line through the origin along direction.

extreme_points

extreme_points(points: Sequence[Vector]) -> list[int]

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

intercepts(points: Sequence[Vector], extremes: Sequence[int]) -> list[float]

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

hyperplane_normalize(points: Sequence[Vector]) -> tuple[list[Point], list[int]]

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

spea2_fitness(points: Sequence[Vector], k: int | None = None) -> list[float]

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

spea2_truncation(points: Sequence[Vector], size: int) -> list[int]

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

additive_epsilon(first: Vector, second: Vector) -> float

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

hypervolume_contributions(points: Sequence[Vector], reference: Vector) -> list[float]

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

last_front(points: Sequence[Vector]) -> list[int]

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

hypervolume_discard(points: Sequence[Vector], rng: Random) -> int

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

tchebycheff(vector: Vector, weight: Vector, ideal: Vector, span: Vector | None = None) -> float

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

weight_neighbourhoods(weights: Sequence[Vector], size: int) -> list[list[int]]

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

unit_vectors(points: Sequence[Vector]) -> list[Point]

Return each point scaled to unit Euclidean length. A zero point is kept as it is.

smallest_angles

smallest_angles(vectors: Sequence[Vector]) -> list[float]

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

adapt_vectors(initial: Sequence[Vector], ideal: Vector, nadir: Vector) -> list[Point]

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 [0, 1].

required
alpha float

Rate at which the penalty grows with progress.

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

minkowski_norm(vector: Vector, p: float) -> float

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 nan when the iteration breaks down: no positive

float

coordinate, a zero derivative, or overflow.

corner_points

corner_points(front: Sequence[Vector]) -> list[int]

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

front_curvature(front: Sequence[Vector]) -> float

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

project_to_front(point: Vector, p: float) -> Point

Scale point onto the surface sum f_i ** p = 1. A zero point stays as it is.

geodesic_distance

geodesic_distance(first: Vector, second: Vector, p: float) -> float

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

age_scores(front: Sequence[Vector]) -> tuple[list[float], float]

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 p.

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).