shark::HypervolumeContributionApproximator Struct Reference

Approximately determines the point of a set contributing the least hypervolume. More...

#include <shark/Algorithms/DirectSearch/Operators/Hypervolume/HypervolumeContributionApproximator.h>

Classes

struct  Point
 Models a point and associated information for book-keeping purposes. More...
 

Public Member Functions

 HypervolumeContributionApproximator ()
 C'tor. More...
 
double delta () const
 
double & delta ()
 
double epsilon () const
 
double & epsilon ()
 
template<typename Archive >
void serialize (Archive &archive, const unsigned int version)
 
template<class Set , class VectorType >
std::vector< KeyValuePair< double, std::size_t > > smallest (Set const &points, std::size_t k, VectorType const &reference) const
 Determines the point contributing the least hypervolume to the overall set of points. More...
 
template<class Set >
std::vector< KeyValuePair< double, std::size_t > > smallest (Set const &points, std::size_t k) const
 Returns the index of the points with smallest contribution. More...
 

Public Attributes

double m_startDeltaMultiplier
 
double m_multiplierDelta
 
double m_minimumMultiplierDelta
 
double m_gamma
 
double m_errorProbability
 The error probability. More...
 
double m_errorBound
 The error bound. More...
 

Detailed Description

Approximately determines the point of a set contributing the least hypervolume.

See K. Bringmann, T. Friedrich. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. Proc. of the 5th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2009), Vol. 5467 of LNCS, pages 6-20, Springer-Verlag, 2009.

The algorithm works by estimating a bounding box for every point that includes all its contribution volume and then draw sample inside the box to estimate which fraction of the box is covered by other points in the set.

The algorithm only implements the k=1 version of the smallest contribution. For the element A it returns holds the following guarantue: with probability of 1-delta, Con(A) < (1+epsilon)Con(LC) where LC is true least contributor. Note that there are no error guarantuees regarding the returned value of the contribution: the algorithm stops when it is sure that the bound above holds, but depending on the setup, this might be very early.

Note that, while on average the algorithm performs reasonable well, the upper run-time is not bounded by the number of elements or dimensionality. When two points have nearly the same(or exactly the same) contribution the algorithm will run for many iterations, until the bound above holds. The same holds if the point with the smallest contribution has a very large potential contribution as many samples are required to establish that allmost all of the box is covered.

Template Parameters
randomThe type of the random for sampling random points.

Definition at line 65 of file HypervolumeContributionApproximator.h.

Constructor & Destructor Documentation

◆ HypervolumeContributionApproximator()

shark::HypervolumeContributionApproximator::HypervolumeContributionApproximator ( )
inline

C'tor.

Parameters
[in]deltathe error probability of the least contributor
[in]epsthe error bound of the least contributor

Definition at line 108 of file HypervolumeContributionApproximator.h.

Member Function Documentation

◆ delta() [1/2]

double shark::HypervolumeContributionApproximator::delta ( ) const
inline

◆ delta() [2/2]

double& shark::HypervolumeContributionApproximator::delta ( )
inline

Definition at line 120 of file HypervolumeContributionApproximator.h.

References m_errorProbability.

◆ epsilon() [1/2]

double shark::HypervolumeContributionApproximator::epsilon ( ) const
inline

◆ epsilon() [2/2]

double& shark::HypervolumeContributionApproximator::epsilon ( )
inline

Definition at line 127 of file HypervolumeContributionApproximator.h.

References m_errorBound.

◆ serialize()

template<typename Archive >
void shark::HypervolumeContributionApproximator::serialize ( Archive &  archive,
const unsigned int  version 
)
inline

Definition at line 132 of file HypervolumeContributionApproximator.h.

◆ smallest() [1/2]

template<class Set , class VectorType >
std::vector<KeyValuePair<double,std::size_t> > shark::HypervolumeContributionApproximator::smallest ( Set const &  points,
std::size_t  k,
VectorType const &  reference 
) const
inline

Determines the point contributing the least hypervolume to the overall set of points.

Parameters
[in]spareto front of points
[in]referenceThe reference point to consider for calculating individual points' contributions.

Definition at line 146 of file HypervolumeContributionApproximator.h.

References shark::HypervolumeContributionApproximator::Point< VectorType >::point, and SHARK_RUNTIME_CHECK.

Referenced by shark::HypervolumeContribution::smallest().

◆ smallest() [2/2]

template<class Set >
std::vector<KeyValuePair<double,std::size_t> > shark::HypervolumeContributionApproximator::smallest ( Set const &  points,
std::size_t  k 
) const
inline

Returns the index of the points with smallest contribution.

As no reference point is given, the extremum points can not be computed and are never selected.

Parameters
[in]pointsThe set \(S\) of points from which to select the smallest contributor.
[in]kThe number of points to select.

Definition at line 177 of file HypervolumeContributionApproximator.h.

References SHARK_RUNTIME_CHECK.

Member Data Documentation

◆ m_errorBound

double shark::HypervolumeContributionApproximator::m_errorBound

The error bound.

Definition at line 103 of file HypervolumeContributionApproximator.h.

Referenced by epsilon().

◆ m_errorProbability

double shark::HypervolumeContributionApproximator::m_errorProbability

The error probability.

Definition at line 102 of file HypervolumeContributionApproximator.h.

Referenced by delta().

◆ m_gamma

double shark::HypervolumeContributionApproximator::m_gamma

Definition at line 101 of file HypervolumeContributionApproximator.h.

◆ m_minimumMultiplierDelta

double shark::HypervolumeContributionApproximator::m_minimumMultiplierDelta

Definition at line 99 of file HypervolumeContributionApproximator.h.

◆ m_multiplierDelta

double shark::HypervolumeContributionApproximator::m_multiplierDelta

Definition at line 98 of file HypervolumeContributionApproximator.h.

◆ m_startDeltaMultiplier

double shark::HypervolumeContributionApproximator::m_startDeltaMultiplier

Definition at line 97 of file HypervolumeContributionApproximator.h.


The documentation for this struct was generated from the following file: