saealib.HypervolumeComparator

class saealib.HypervolumeComparator(direction=None, *, eps_cv=1e-06, eps_obj=1e-06, reference_point=None, margin=0.1, last_front_only=False, sorter=<function non_dominated_sort>, dominator=None)

Bases: ParetoComparator

Comparator using front rank and exclusive HV contribution (SMS-EMOA style).

Ordering rules:

• Feasibility first (Deb 2000): infeasible individuals (cv > eps_cv) are placed after all feasible ones, ordered by ascending constraint violation.

• Primary key: non-dominated front rank (ascending, lower = better).

• Secondary key (within a front): exclusive hypervolume contribution (descending, higher = better).

Note

Generalization from SMS-EMOA. The original SMS-EMOA (Beume et al., 2007) computes HV contributions only on the last (worst) front to determine the single removal candidate at each generation. By default this comparator applies HV-contribution ordering within every front to produce a full ranking over the entire population, a deliberate generalization that enables use in standard survivor-selection and tournament-selection contexts. Set last_front_only=True for the paper’s scope instead: contributions are then computed on the last front alone and better fronts are ordered by rank only.

Warning

Computing hypervolume is exponential in the number of objectives, and hypervolume_contributions() performs O(N) hypervolume evaluations per front (leave-one-out). For large populations or many objectives this becomes expensive.

Note

compare() raises NotImplementedError because the hypervolume contribution of a point depends on the other points in the population (it is population-relative). Components that require pairwise comparison (e.g. PSO pbest update, PairwiseComparisonSet) should use a ParetoComparator instead. Tournament selection should call compare_population(), which IS defined and safe to use.

Note

Deferred gap. Beume et al. (2007) explicitly special-cases two-objective problems: the reference point is skipped entirely and the two extremal (best-per-objective) solutions are unconditionally kept. This comparator always computes a reference point and HV contributions for every point, including the two-objective case; the paper’s special case is not implemented here.

Parameters:

• direction (np.ndarray or None) – Per-objective optimization directions (+1 = maximize, -1 = minimize). None defaults to minimization for all objectives.

• eps_cv (float) – Feasibility threshold for constraint violation.

• eps_obj (float) – Epsilon for objective-value equality (stored for interface compatibility).

• reference_point (np.ndarray or None) – Reference point in the original objective space, shape (n_obj,). If None (default), it is recomputed fresh on every call as the front’s worst objective values plus 1.0 (Beume et al. 2007, boundary-solution handling) – see _hv_default_reference_point().

• margin (float) – Unused by the default (reference_point=None) computation, which now follows the paper’s fixed +1.0 offset instead of a fractional one. Retained only so existing constructor calls do not break; kept as a stored, inert attribute (see margin). Pass an explicit reference_point if a margin-scaled reference point is needed.

• last_front_only (bool) – Restrict HV-contribution ordering to the last (worst) front, as in Beume et al. (2007). Individuals in better fronts then share one contribution value and keep their relative order. Defaults to False, which ranks within every front. Setting it also removes the per-front hypervolume cost for all but the last front.

• sorter (NonDominatedSorter) – Non-dominated sorting callable.

• dominator (Dominator or None) – Dominance predicate. None defaults to ParetoDominator.

References

[5]: Beume, N., Naujoks, B., & Emmerich, M. (2007). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653-1669.

[10]: Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2-4), 311-338.

Methods

__init__
compare	Raise NotImplementedError — HV contribution is population-relative.
compare_population	Compare two individuals using constraint-domination then HV ranking.
get_required_attrs	Return population attributes this comparator needs to persist.
prepare_population	Freshly recompute and materialize population-relative ranking state.
rank_population	Prepare population-relative ranking state, then sort.
sort_population	Sort by front rank then HV contribution; infeasible individuals last.

Method Details

HypervolumeComparator.__init__(direction=None, *, eps_cv=1e-06, eps_obj=1e-06, reference_point=None, margin=0.1, last_front_only=False, sorter=<function non_dominated_sort>, dominator=None)

Parameters:

• direction (ndarray | None)

• eps_cv (float)

• eps_obj (float)

• reference_point (ndarray | None)

• margin (float)

• last_front_only (bool)

• sorter (NonDominatedSorter)

• dominator (Dominator | None)

HypervolumeComparator.compare(fa, cv_a, fb, cv_b)

Raise NotImplementedError — HV contribution is population-relative.

Parameters:

• fa (ndarray)

• cv_a (float)

• fb (ndarray)

• cv_b (float)

Return type:

int

HypervolumeComparator.compare_population(population, idx_a, idx_b)

Compare two individuals using constraint-domination then HV ranking.

Returns -1 if a is better, 1 if b is better, 0 if equal. The feasibility rule (Deb 2000) is applied first. Among both-feasible pairs, lower front rank wins; within the same front, higher HV contribution wins.

Parameters:

• population (Population) – The population containing both individuals.

• idx_a (int) – Index of the first individual.

• idx_b (int) – Index of the second individual.

Returns:

-1, 0, or 1.

Return type:

int

HypervolumeComparator.get_required_attrs(problem)

Return population attributes this comparator needs to persist.

Population-relative ranking state (e.g. SPEA2 fitness) that must survive across selections belongs here as a named, typed attribute rather than in the population’s transient cache. Default: no additional attributes.

Parameters:

problem (Problem) – The optimization problem.

Returns:

Empty by default.

Return type:

list[PopulationAttribute]

HypervolumeComparator.prepare_population(population)

Freshly recompute and materialize population-relative ranking state.

Default is a no-op — comparators whose ranking depends only on per-individual values already stored in f/cv do not need this. Comparators that declare attributes via get_required_attrs() should override this to recompute and write those attributes for the given population, unconditionally (not reusing any prior cached value).

Parameters:

population (Population) – The population to prepare ranking state for.

Return type:

None

HypervolumeComparator.rank_population(population)

Prepare population-relative ranking state, then sort.

Equivalent to calling prepare_population() followed by sort_population(). Callers performing environmental selection on a freshly assembled pool (e.g. survivor selection merging population and offspring) should call this instead of sort_population() directly, so any population-relative state declared via get_required_attrs() is recomputed for the new set before ranking.

Parameters:

population (Population) – The population to rank.

Returns:

Sorted population indices, as returned by sort_population().

Return type:

np.ndarray

HypervolumeComparator.sort_population(population)

Sort by front rank then HV contribution; infeasible individuals last.

Within the feasible block the primary sort key is non-dominated front rank (ascending) and the secondary key is exclusive hypervolume contribution (descending). Infeasible individuals follow, sorted by ascending constraint violation.

Parameters:

population (Population) – The population to sort.

Returns:

Sorted population indices (int).

Return type:

np.ndarray