eaf#

Namespaces#

stat

Classes#

Levels#

class Levels#

Computes attainment levels of the Empirical Attainment Function.

This computes the levelsets of the 2D (quality/time) function of the data logged by the EAF logger. Calling it returns a (sub)set of Pareto fronts which can be interpreted as a 2D generalization of quantiles. Each levelset is a set a points defined by a quality and a number of calls to the objective function (the “time”).

There is as much levelsets as there are runs that have been monitored by the logger. Several of those levelsets are expected to be identical, as several runs may have attained the same level.

You can ask for only a subset of the levels at construction. All levels are computed by default.

Example:

suite::BBOB suite({1, 2}, {1, 2}, {10, 30});
logger::EAF logger;
suite.attach_logger(logger);
// [call the problem... the logger will store the quality/time Pareto fronts for each run.
logger::eaf::stat::Levels levels_at(common::OptimizationType::MIN, {0, nb_runs/2, nb_runs-1}); // Will computes 3 level sets.
auto levels = levels_at(logger); // Actually compute the levels.

From code: https://eden.dei.uc.pt/~cmfonsec/aft.html Related publication:

@InProceedings{inp_Fonseca2011,
  author     = {Fonseca, Carlos M. and Guerreiro, Andreia P. and López-Ibáñez, Manuel and Paquete, Luís},
  booktitle  = {{I}nternational {C}onference on {E}volutionary {Multi}-{Criterion} {Optimization} ({EMO'11}},
  title      = {On the {Computation} of the {Empirical} {Attainment} {Function}},
  year       = {2011},
  address    = {Berlin, Heidelberg},
  editor     = {Takahashi, Ricardo H. C. and Deb, Kalyanmoy and Wanner, Elizabeth F. and Greco, Salvatore},
  pages      = {106--120},
  publisher  = {Springer},
  series     = {Lecture {Notes} in {Computer} {Science}},
  abstract   = {The attainment function provides a description of the location of the distribution of a random non-dominated point set. This function can be estimated from experimental data via its empirical counterpart, the empirical attainment function (EAF). However, computation of the EAF in more than two dimensions is a non-trivial task. In this article, the problem of computing the empirical attainment function is formalised, and upper and lower bounds on the corresponding number of output points are presented. In addition, efficient algorithms for the two and three-dimensional cases are proposed, and their time complexities are related to lower bounds derived for each case.},
  doi        = {10.1007/978-3-642-19893-9_8},
  isbn       = {9783642198939},
  language   = {en},
}

From code: https://github.com/MLopez-Ibanez/eaf Related publication:

@incollection{LopPaqStu09emaa,
  editor = { Thomas Bartz-Beielstein  and  Marco Chiarandini  and  Lu{\'\i}s Paquete  and  Mike Preuss },
  year = 2010,
  address = {Berlin, Germany},
  publisher = {Springer},
  booktitle = {Experimental Methods for the Analysis of Optimization Algorithms},
  author = { Manuel L{\'o}pez-Ib{\'a}{\~n}ez  and  Lu{\'\i}s Paquete  and  Thomas St{\"u}tzle },
  title = {Exploratory Analysis of Stochastic Local Search Algorithms in Biobjective Optimization},
  pages = {209--222},
  doi = {10.1007/978-3-642-02538-9_9},
  abstract = {This chapter introduces two Perl programs that
              implement graphical tools for exploring the performance of stochastic local search algorithms
              for biobjective optimization problems. These tools are based on the concept of the empirical attainment
              function (EAF), which describes the probabilistic distribution of the outcomes obtained by a
              stochastic algorithm in the objective space. In particular, we consider the visualization of
              attainment surfaces and differences between the first-order EAFs of the outcomes of two
              algorithms. This visualization allows us to identify certain algorithmic behaviors in a graphical way.
              We explain the use of these visualization tools and illustrate them with examples arising from
              practice.}
}

Public Types

using Type = std::map<size_t, eaf::Front>#: The type returned by the call interface.

Public Functions

inline Levels(const common::OptimizationType optim_type, std::vector<size_t> attainment_levels = {})#

Constructor.

Take the levelsets indices that you want to compute. There is as much attainment levelsets as there is runs in the logger, probably with duplicates. Indices should be in [0,nb_runs[.

If you pass an empty vector {} (the default), it will compute all the levelsets.

Parameters:

optim_type – whether the problem is minimizing or maximizing.
attainment_levels – Levelsets to be computed (empty=all, the default).

inline Type operator()(const EAF &logger)#: Extract the runs from the logger and computes the attainment levelsets.

Protected Functions

inline bool is_better(const double q1, const double q2)#

Compare two objective function values.

Handle maximization or minimizaton problems transparently.

Parameters:

q1 – the considered objective value.
q2 – the objective function value checked against.

Returns:

true if q1 is better than q2.

inline bool is_better_or_eq(const double q1, const double q2)#

Compare two objective function values.

Handle maximization or minimizaton problems transparently.

Parameters:

q1 – the considered objective value.
q2 – the objective function value checked against.

Returns:

true if q1 is better than or equal to q2.

Protected Attributes

std::vector<size_t> _attlevels#: Asked attainment levels indices.

const common::FOptimizationType _f_optim#: Whether we minimize or maximize.

Stat#

template<class T> class Stat#

Interface for classes that computes statistics over an eaf::Levels’ data.

Subclassed by ioh::eaf::NadirStat< double >, ioh::eaf::NadirStat< std::map< size_t, double > >, ioh::eaf::NadirStat< T >

Public Types

using Type = T #: Type of the statistic.

Public Functions

virtual T operator()(const eaf::Levels::Type &levels) = 0#: Main call interface.

NadirStat#

template<class T> class NadirStat : public ioh::eaf::Stat<T>#

Interface for statistics over an EAF, which depend on a nadir reference point.

Either the desired nadir point is given, either it is automatically computed as the extremum of all the levels, at the beginning of the call.

Note

Letting the class computes its nadir point will be more expensive than using an extremum that you would know from bounds.

Warning

This should always compute a metric that should be maximized in order to improve the performance. (i.e. under the curve for maximization problems, above the curve for minimization problems)

Public Types

using Type = typename Stat<T>::Type#: The type returned by the call interface.

Public Functions

inline NadirStat(const common::OptimizationType optim_type, const double shift_qual = 1e-6)#: Constructor without a nadir reference point.

inline NadirStat(const common::OptimizationType optim_type, eaf::Point nadir)#: Constructor with a nadir reference point.

Warning

Using this constructor, you are responsible of passing the correct nadir point.

Warning

Note that you must shift it to ensure that the statistic is always non-zero.

inline virtual T operator()(const eaf::Levels::Type &levels) override#: Update the nadir point (if not previously indicated) and then calls NadirStat::call.

Protected Functions

inline eaf::Point extremum(const eaf::Front &front) const#: Computes the extremum point as the worst coordinates on both quality and time axis for all front points.

virtual T call(const eaf::Levels::Type &levels) = 0#

Main interface.

This is called by the upper Stat::operator() interface, after having updated the nadir point.

Protected Attributes

bool _has_nadir#: Initialization check flag.

eaf::Point _nadir#: The worst reference point.

const common::FOptimizationType _is_better#: The problem type (i.e. min or max).

const double _shift_qual#: The shift quality.

Protected Static Attributes

static const size_t _shift_time = 1#: Shift of the nadir point regarding the extremum of data.

Functions#

levels#

inline Levels::Type ioh::eaf::levels(const EAF &logger, std::vector<size_t> levels = {})#

Computes attainment levels of the Empirical Attainment Function.