Utilities#

Layer 2: Compose
saealib.hypervolume(f, reference_point)[source]#

Compute hypervolume indicator (minimization convention).

The hypervolume (S-metric) indicator was introduced by Zitzler & Thiele (1998) as a way to measure the quality of a Pareto front approximation without a priori knowledge of the true front.

Uses a recursive slicing algorithm. Complexity: O(n^(m-1) * n log n), where n is the number of points and m is the number of objectives.

Parameters:

  • f (np.ndarray) – Objective matrix, shape (n, n_obj).

  • reference_point (np.ndarray) – Reference (nadir) point, shape (n_obj,). Each component must be strictly greater than the corresponding component of at least one point in f for a non-zero hypervolume to be returned.

Returns:

Hypervolume value.

Return type:

float

saealib.hypervolume_contributions(f, reference_point=None, direction=None, margin=0.1)[source]#

Compute exclusive hypervolume contributions for each point.

The exclusive contribution of point i is defined as:

Delta_HV(i) = HV(S) - HV(S \ {i})

i.e. the volume exclusively dominated by point i relative to the reference point. Higher is better, consistent with the library-wide convention. Dominated points and points not strictly better than the reference point contribute 0.

This function reuses hypervolume() and therefore inherits the minimisation convention internally. Use the direction parameter to handle maximisation objectives.

Warning

Computing hypervolume is exponential in the number of objectives, and the leave-one-out loop adds a factor of N. For many objectives or large N this becomes prohibitively expensive. The hypervolume kernel this function calls already processes objectives rather than points, the slicing structure of While, Hingston, Barone & Huband (2006), so the remaining cost is the repetition itself: a faster contribution algorithm has to avoid recomputing the whole volume once per point. That work is not to be confused with the WFG benchmark-problem paper by Huband et al. (2006), a different paper despite the overlapping author list.

Parameters:

  • f (np.ndarray) – Objective matrix, shape (N, n_obj).

  • reference_point (np.ndarray or None, optional) – Reference point in the original objective space, shape (n_obj,). If None, it is auto-computed from the data with a fractional padding controlled by margin.

  • direction (np.ndarray or None, optional) – Per-objective optimisation direction: +1 to maximise, -1 to minimise. None defaults to all-minimise (equivalent to np.full(n_obj, -1.0)). Same convention as saealib.comparators.spea2_fitness().

  • margin (float, optional) – Fractional padding used when auto-computing the reference point. For each objective axis the auto reference is placed at nadir + margin * span. Ignored when reference_point is provided.

Returns:

Exclusive hypervolume contribution per point, shape (N,). All values are >= 0 (dominated / out-of-reference points get 0).

Return type:

np.ndarray

References

Beume, N., Naujoks, B., & Emmerich, M. (2007).

SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653-1669. https://doi.org/10.1016/j.ejor.2006.08.008

Zitzler, E., & Thiele, L. (1998).

Multiobjective optimization using evolutionary algorithms - a comparative case study. PPSN V, LNCS 1498, pp. 292-301.

saealib.uniform_weight_vectors(n_obj, n_divisions)[source]#

Generate weight vectors uniformly distributed on the unit simplex.

Uses the simplex lattice design described in Das & Dennis (1998), widely applied in MOEA/D (Zhang & Li, 2007) and NSGA-III (Deb & Jain, 2014).

Each weight vector w satisfies sum(w) == 1 and w_i >= 0. The granularity is 1 / n_divisions; each component takes a value in {0, 1/H, 2/H, ..., 1} where H = n_divisions.

The number of vectors returned is math.comb(n_obj + H - 1, H).

Parameters:

  • n_obj (int) – Number of objectives. Must be >= 2.

  • n_divisions (int) – Number of divisions H along each axis. Must be >= 1. Larger values produce more weight vectors and finer coverage.

Returns:

Weight matrix, shape (N, n_obj). Each row sums to 1.0 and all entries are non-negative.

Return type:

np.ndarray

Raises:

ValueError – If n_obj < 2 or n_divisions < 1.

References

[9]: Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712-731. (Appendix A describes the simplex lattice design originally due to Das & Dennis, 1998.)

Examples

>>> uniform_weight_vectors(2, 4)
array([[0.  , 1.  ],
       [0.25, 0.75],
       [0.5 , 0.5 ],
       [0.75, 0.25],
       [1.  , 0.  ]])