eaf: Exact computation of the Empirical Attainment Function (EAF)

In moocore: Core Mathematical Functions for Multi-Objective Optimization

Exact computation of the Empirical Attainment Function (EAF)

Description

This function computes the EAF given a set of 2D or 3D points and a vector set that indicates to which set each point belongs.

Usage

eaf(x, sets, percentiles = NULL, maximise = FALSE, groups = NULL)

Arguments

x	matrix()|data.frame() Matrix or data frame of numerical values that represents multiple sets of points, where each row represents a point. If sets is missing, the last column of x gives the sets.
sets	integer() Vector that indicates the set of each point in x. If missing, the last column of x is used instead.
percentiles	numeric() Vector indicating which percentiles are computed. NULL computes all.
maximise	logical() Whether the objectives must be maximised instead of minimised. Either a single logical value that applies to all objectives or a vector of logical values, with one value per objective.
groups	factor() Indicates that the EAF must be computed separately for data belonging to different groups.

Details

Given a set A \subset \mathbb{R}^d, the attainment function of A, denoted by \alpha_{A}\colon \mathbb{R}^d\to \{0,1\}, specifies which points in the objective space are weakly dominated by A, where \alpha_A(\vec{z}) = 1 if \exists \vec{a} \in A, \vec{a} \leq \vec{z}, and \alpha_A(\vec{z}) = 0, otherwise.

Let \mathcal{A} = \{A_1, \dots, A_n\} be a multi-set of n sets A_i \subset \mathbb{R}^d, the EAF \citepGrunert01,GruFon2009:emaa is the function \hat{\alpha}_{\mathcal{A}}\colon \mathbb{R}^d\to [0,1], such that:

\hat{\alpha}_{\mathcal{A}}(\vec{z}) = \frac{1}{n}\sum_{i=1}^n \alpha_{A_i}(\vec{z})

The EAF is a coordinate-wise non-decreasing step function, similar to the empirical cumulative distribution function (ECDF) \citepLopVerDreDoe2025. Thus, a finite representation of the EAF can be computed as the set of minima, in terms of Pareto optimality, with a value of the EAF not smaller than a given t/n, where t=1,\dots,n \citepFonGueLopPaq2011emo. Formally, the EAF can be represented by the sequence (L_1, L_2, \dots, L_n), where:

L_t = \min \{\vec{z} \in \mathbb{R}^d : \hat{\alpha}_{\mathcal{A}}(\vec{z}) \geq t/n\}

It is also common to refer to the k\% \in [0,100] percentile. For example, the median (or 50%) attainment surface corresponds to L_{\lceil n/2 \rceil} and it is the lower boundary of the vector space attained by at least 50% of the input sets A_i. Similarly, L_1 is called the best attainment surface (\frac{1}{n}%) and represents the lower boundary of the space attained by at least one input set, whereas L_{100} is called the worst attainment surface (100%) and represents the lower boundary of the space attained by all input sets.

In the current implementation, the EAF is computed using the algorithms proposed by \citetFonGueLopPaq2011emo, which have complexity O(m\log m + nm) in 2D and O(n^2 m \log m) in 3D, where n is the number of input sets and m is the total number of input points.

Value

data.frame()
A data frame containing the exact representation of EAF. The last column gives the percentile that corresponds to each point. If groups is not NULL, then an additional column indicates to which group the point belongs.

Note

There are several examples of data sets in system.file(package="moocore","extdata"). The current implementation only supports two and three dimensional points.

Author(s)

Manuel López-Ibáñez

References

\insertAllCited

See Also

read_datasets()

Examples

extdata_path <- system.file(package="moocore", "extdata")

x <- read_datasets(file.path(extdata_path, "example1_dat"))
# Compute full EAF (sets is the last column)
str(eaf(x))

# Compute only best, median and worst
str(eaf(x[,1:2], sets = x[,3], percentiles = c(0, 50, 100)))

x <- read_datasets(file.path(extdata_path, "spherical-250-10-3d.txt"))
y <- read_datasets(file.path(extdata_path, "uniform-250-10-3d.txt"))
x <- rbind(data.frame(x, groups = "spherical"),
           data.frame(y, groups = "uniform"))
# Compute only median separately for each group
z <- eaf(x[,1:3], sets = x[,4], groups = x[,5], percentiles = 50)
str(z)

moocore documentation built on Aug. 8, 2025, 6:12 p.m.