Empirical Attainment Function (EAF)

EAF Computation

eaf(data, /, sets, *[, percentiles])	Exact computation of the Empirical Attainment Function (EAF).
eafdiff(x, y, /, *[, intervals, maximise, ...])	Compute empirical attainment function (EAF) differences.
largest_eafdiff(x, /, ref, *[, maximise, ...])	Identify largest EAF differences.

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 [1][2] 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) [3]. 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\) [4]. 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.

Vorob’ev Expectation and Deviation

vorob_t(data, /, sets, *, ref)	Compute Vorob'ev threshold and expectation.
vorob_dev(data, /, sets, *, ref[, ve])	Compute Vorob'ev deviation.

Let \(\mathcal{A} = \{A_1, \dots, A_n\}\) be a multi-set of \(n\) sets \(A_i \subset \mathbb{R}^d\) of mutually nondominated vectors, with finite (but not necessarily equal) cardinality. If bounded by a reference point \(\vec{r}\) that is strictly dominated by any point in any set, then these sets can be seen a samples from a random closed set [5].

Let the \(\beta\)-quantile be the subset of the empirical attainment function \(\mathcal{Q}_\beta = \{\vec{z}\in \mathbb{R}^d : \hat{\alpha}_{\mathcal{A}}(\vec{z}) \geq \beta\}\).

The Vorob’ev expectation is the \(\beta^{*}\)-quantile set \(\mathcal{Q}_{\beta^{*}}\) such that the mean value hypervolume of the sets is equal (or as close as possible) to the hypervolume of \(\mathcal{Q}_{\beta^{*}}\), that is, \(\text{hyp}(\mathcal{Q}_\beta) \leq \mathbb{E}[\text{hyp}(\mathcal{A})] \leq \text{hyp}(\mathcal{Q}_{\beta^{*}})\), \(\forall \beta > \beta^{*}\). Thus, the Vorob’ev expectation provides a definition of the notion of mean nondominated set.

The value \(\beta^{*} \in [0,1]\) is called the Vorob’ev threshold. Large differences from the median quantile (0.5) indicate a skewed distribution of \(\mathcal{A}\).

The Vorob’ev deviation is the mean hypervolume of the symmetric difference between the Vorob’ev expectation and any set in \(\mathcal{A}\), that is, \(\mathbb{E}[\text{hyp}(\mathcal{Q}_{\beta^{*}} \ominus \mathcal{A})]\), where the symmetric difference is defined as \(A \ominus B = (A \setminus B) \cup (B \setminus A)\). Low deviation values indicate that the sets are very similar, in terms of the location of the weakly dominated space, to the Vorob’ev expectation.

For more background, see Binois et al.[6], Molchanov[5], Chevalier et al.[7].

Bibliography

[1]

Viviane Grunert da Fonseca, Carlos M. Fonseca, and Andreia O. Hall. Inferential performance assessment of stochastic optimisers and the attainment function. In Eckart Zitzler, Kalyanmoy Deb, Lothar Thiele, Carlos A. Coello Coello, and David Corne, editors, Evolutionary Multi-criterion Optimization, EMO 2001, volume 1993 of Lecture Notes in Computer Science, pages 213–225. Springer, Berlin / Heidelberg, 2001. doi:10.1007/3-540-44719-9_15, [BibTeX].

[2]

Viviane Grunert da Fonseca and Carlos M. Fonseca. The attainment-function approach to stochastic multiobjective optimizer assessment and comparison. In Thomas Bartz-Beielstein, Marco Chiarandini, Luís Paquete, and Mike Preuss, editors, Experimental Methods for the Analysis of Optimization Algorithms, pages 103–130. Springer, Berlin / Heidelberg, 2010. doi:10.1007/978-3-642-02538-9_5, [BibTeX].

[3]

Manuel López-Ibáñez, Diederick Vermetten, Johann Dreo, and Carola Doerr. Using the empirical attainment function for analyzing single-objective black-box optimization algorithms. IEEE Transactions on Evolutionary Computation, 2025. doi:10.1109/TEVC.2024.3462758, [BibTeX].

[4]

Carlos M. Fonseca, Andreia P. Guerreiro, Manuel López-Ibáñez, and Luís Paquete. On the computation of the empirical attainment function. In R. H. C. Takahashi, Kalyanmoy Deb, Elizabeth F. Wanner, and Salvatore Greco, editors, Evolutionary Multi-criterion Optimization, EMO 2011, volume 6576 of Lecture Notes in Computer Science, pages 106–120. Springer, Berlin / Heidelberg, 2011. doi:10.1007/978-3-642-19893-9_8, [BibTeX].

[5] (1,2)

Ilya Molchanov. Theory of Random Sets. Springer, 2005. [BibTeX].

[6]

Mickaël Binois, David Ginsbourger, and Olivier Roustant. Quantifying uncertainty on Pareto fronts with Gaussian process conditional simulations. European Journal of Operational Research, 243(2):386–394, 2015. doi:10.1016/j.ejor.2014.07.032, [BibTeX].

[7]

Clément Chevalier, David Ginsbourger, Julien Bect, and Ilya Molchanov. Estimating and quantifying uncertainties on level sets using the Vorob’ev expectation and deviation with Gaussian process models. In Dariusz Ucinski, Anthony C. Atkinson, and Maciej Patan, editors, mODa 10–Advances in Model-Oriented Design and Analysis, pages 35–43. Springer International Publishing, Heidelberg, Germany, 2013. doi:10.1007/978-3-319-00218-7_5, [BibTeX].