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

random The 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]	delta	the error probability of the least contributor
[in]	eps	the 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

Definition at line 117 of file HypervolumeContributionApproximator.h.

References m_errorProbability.

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

◆ 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

Definition at line 124 of file HypervolumeContributionApproximator.h.

References m_errorBound.

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

◆ 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