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.

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.

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.

Public Attributes
double	m_startDeltaMultiplier

double	m_multiplierDelta

double	m_minimumMultiplierDelta

double	m_gamma

double	m_errorProbability
	The error probability.

double	m_errorBound
	The error bound.

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.

Definition at line 106 of file HypervolumeContributionApproximator.h.

Member Function Documentation

◆ delta() [1/2]

double & shark::HypervolumeContributionApproximator::delta ( )

inline

Definition at line 118 of file HypervolumeContributionApproximator.h.

References m_errorProbability.

◆ delta() [2/2]

double shark::HypervolumeContributionApproximator::delta ( ) const

inline

Definition at line 115 of file HypervolumeContributionApproximator.h.

References m_errorProbability.

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

◆ epsilon() [1/2]

double & shark::HypervolumeContributionApproximator::epsilon ( )

inline

Definition at line 125 of file HypervolumeContributionApproximator.h.

References m_errorBound.

◆ epsilon() [2/2]

double shark::HypervolumeContributionApproximator::epsilon ( ) const

inline

Definition at line 122 of file HypervolumeContributionApproximator.h.

References m_errorBound.

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

◆ serialize()

template<typename Archive >

void shark::HypervolumeContributionApproximator::serialize	(	Archive &	archive,
		const unsigned int	version
	)

inline

Definition at line 130 of file HypervolumeContributionApproximator.h.

References m_errorBound, m_errorProbability, m_gamma, m_minimumMultiplierDelta, m_multiplierDelta, and m_startDeltaMultiplier.

◆ smallest() [1/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]	points	The set \(S\) of points from which to select the smallest contributor.
[in]	k	The number of points to select.

Definition at line 176 of file HypervolumeContributionApproximator.h.

References SHARK_RUNTIME_CHECK, and smallest().

◆ smallest() [2/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]	points	pareto front of points
[in]	k	The number of points to select.
[in]	reference	The reference point to consider for calculating individual points' contributions.

Definition at line 145 of file HypervolumeContributionApproximator.h.

References SHARK_RUNTIME_CHECK, and smallest().

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