shark::LeastContributorApproximator< Rng, ExactHypervolume > Struct Template Reference

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

#include <shark/Algorithms/DirectSearch/Indicators/LeastContributorApproximator.h>

Classes

struct  IdentityFitnessExtractor
 Returns the supplied argument. More...
 
struct  Point
 Models a point and associated information for book-keeping purposes. More...
 

Public Types

enum  Strategy { ENSURE_UNION_BOUND, FAST }
 Models the sampling strategy. More...
 

Public Member Functions

 LeastContributorApproximator (double startDelta=this_type::DEFAULT_START_DELTA(), double multiplierDelta=this_type::DEFAULT_MULTIPLIER_DELTA(), double minimumDeltaMultiplier=this_type::DEFAULT_MINIMUM_MULTIPLIER_DELTA(), unsigned long long maxNumSamples=this_type::DEFAULT_MAX_NUM_SAMPLES(), double gamma=this_type::DEFAULT_GAMMA(), double delta=1.E-2, double eps=1.E-2)
 C'tor. More...
 
template<typename Set , typename VectorType >
void sample (const Set &s, typename Set::iterator point, unsigned int r, double delta, const VectorType &refPoint)
 Samples in the bounding box of the supplied point until a pre-defined threshold is reached. More...
 
template<typename iterator >
double deltaForPoint (iterator point, unsigned int R)
 
template<typename Extractor , typename Set , typename VectorType >
std::size_t leastContributor (Extractor e, const Set &s, const VectorType &refPoint)
 Determines the point contributing the least hypervolume to the overall set of points. More...
 
template<typename Extractor , typename ParetoFrontType >
std::size_t leastContributor (Extractor extractor, ParetoFrontType const &front)
 Determines the point contributing the least hypervolume to the overall front of points. More...
 
template<typename Extractor , typename PointSet >
void updateInternals (Extractor extractor, PointSet const &set)
 Updates the internal variables of the indicator using a whole population. More...
 

Static Public Member Functions

static registry_type & STRATEGY_REGISTRY ()
 
static Strategy DEFAULT_STRATEGY ()
 Default sampling strategy. More...
 
static boost::uint_fast64_t DEFAULT_SAMPLE_THRESHOLD ()
 Default sampling strategy. More...
 
static const double DEFAULT_START_DELTA ()
 Default delta value at start of algorithm. More...
 
static const double DEFAULT_MULTIPLIER_DELTA ()
 Default multiplier value for adjusting delta. More...
 
static const double DEFAULT_MINIMUM_MULTIPLIER_DELTA ()
 Default multiplier value for adjusting delta. More...
 
static const boost::uint_fast64_t DEFAULT_MAX_NUM_SAMPLES ()
 Default threshold for sample count. More...
 
static const double DEFAULT_GAMMA ()
 Default gamma value. More...
 

Public Attributes

double m_logFactor
 
double m_startDelta
 
double m_multiplierDelta
 
double m_minimumMultiplierDelta
 
unsigned long long m_maxNumSamples
 
double m_gamma
 
unsigned int m_round
 
double m_errorProbability
 The error probability. More...
 
double m_errorBound
 The error bound. More...
 
Strategy m_strategy
 
boost::uint_fast64_t m_sampleCounter
 
boost::uint_fast64_t m_sampleCountThreshold
 
RealVector m_reference
 the reference calculates by updateInternals More...
 

Friends

std::ostream & operator<< (std::ostream &stream, Strategy strategy)
 
std::istream & operator>> (std::istream &stream, Strategy &strategy)
 

Detailed Description

template<typename Rng, typename ExactHypervolume>
struct shark::LeastContributorApproximator< Rng, ExactHypervolume >

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.

Template Parameters
RngThe type of the Rng for sampling random points.
ExactHypervolumeExact hypervolume calculator that is used to speed up the approximation scheme.

Definition at line 193 of file LeastContributorApproximator.h.

Member Enumeration Documentation

§ Strategy

template<typename Rng , typename ExactHypervolume >
enum shark::LeastContributorApproximator::Strategy

Models the sampling strategy.

Enumerator
ENSURE_UNION_BOUND 

Ensures that the selected epsilon and delta are reached.

FAST 

Puts a threshold on the number of samples.

Definition at line 203 of file LeastContributorApproximator.h.

Constructor & Destructor Documentation

§ LeastContributorApproximator()

template<typename Rng , typename ExactHypervolume >
shark::LeastContributorApproximator< Rng, ExactHypervolume >::LeastContributorApproximator ( double  startDelta = this_type::DEFAULT_START_DELTA(),
double  multiplierDelta = this_type::DEFAULT_MULTIPLIER_DELTA(),
double  minimumDeltaMultiplier = this_type::DEFAULT_MINIMUM_MULTIPLIER_DELTA(),
unsigned long long  maxNumSamples = this_type::DEFAULT_MAX_NUM_SAMPLES(),
double  gamma = this_type::DEFAULT_GAMMA(),
double  delta = 1.E-2,
double  eps = 1.E-2 
)
inline

C'tor.

Parameters
[in]startDeltaInitial delta value.
[in]multiplierDeltaMultiplier for adjusting the delta value.
[in]minimumDeltaMultiplierMultiplier for adjusting the delta value.
[in]maxNumSamplesThe maximum number of samples. If reached, the algorithm aborts.
[in]gamma
[in]deltathe error probability of the least contributor
[in]epsthe error bound of the least contributor

Definition at line 374 of file LeastContributorApproximator.h.

Member Function Documentation

§ DEFAULT_GAMMA()

template<typename Rng , typename ExactHypervolume >
static const double shark::LeastContributorApproximator< Rng, ExactHypervolume >::DEFAULT_GAMMA ( )
inlinestatic

Default gamma value.

Definition at line 280 of file LeastContributorApproximator.h.

§ DEFAULT_MAX_NUM_SAMPLES()

template<typename Rng , typename ExactHypervolume >
static const boost::uint_fast64_t shark::LeastContributorApproximator< Rng, ExactHypervolume >::DEFAULT_MAX_NUM_SAMPLES ( )
inlinestatic

Default threshold for sample count.

Definition at line 272 of file LeastContributorApproximator.h.

References shark::blas::max().

§ DEFAULT_MINIMUM_MULTIPLIER_DELTA()

template<typename Rng , typename ExactHypervolume >
static const double shark::LeastContributorApproximator< Rng, ExactHypervolume >::DEFAULT_MINIMUM_MULTIPLIER_DELTA ( )
inlinestatic

Default multiplier value for adjusting delta.

Definition at line 264 of file LeastContributorApproximator.h.

§ DEFAULT_MULTIPLIER_DELTA()

template<typename Rng , typename ExactHypervolume >
static const double shark::LeastContributorApproximator< Rng, ExactHypervolume >::DEFAULT_MULTIPLIER_DELTA ( )
inlinestatic

Default multiplier value for adjusting delta.

Definition at line 256 of file LeastContributorApproximator.h.

§ DEFAULT_SAMPLE_THRESHOLD()

template<typename Rng , typename ExactHypervolume >
static boost::uint_fast64_t shark::LeastContributorApproximator< Rng, ExactHypervolume >::DEFAULT_SAMPLE_THRESHOLD ( )
inlinestatic

Default sampling strategy.

Definition at line 240 of file LeastContributorApproximator.h.

§ DEFAULT_START_DELTA()

template<typename Rng , typename ExactHypervolume >
static const double shark::LeastContributorApproximator< Rng, ExactHypervolume >::DEFAULT_START_DELTA ( )
inlinestatic

Default delta value at start of algorithm.

Definition at line 248 of file LeastContributorApproximator.h.

§ DEFAULT_STRATEGY()

template<typename Rng , typename ExactHypervolume >
static Strategy shark::LeastContributorApproximator< Rng, ExactHypervolume >::DEFAULT_STRATEGY ( )
inlinestatic

Default sampling strategy.

Definition at line 232 of file LeastContributorApproximator.h.

§ deltaForPoint()

template<typename Rng , typename ExactHypervolume >
template<typename iterator >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::deltaForPoint ( iterator  point,
unsigned int  R 
)
inline

Definition at line 446 of file LeastContributorApproximator.h.

§ leastContributor() [1/2]

template<typename Rng , typename ExactHypervolume >
template<typename Extractor , typename Set , typename VectorType >
std::size_t shark::LeastContributorApproximator< Rng, ExactHypervolume >::leastContributor ( Extractor  e,
const Set &  s,
const VectorType refPoint 
)
inline

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

Parameters
[in]eExtracts point information from set elements.
[in]sSet of points.
[in]refPointThe reference point to consider for calculating individual points' contributions.

Definition at line 460 of file LeastContributorApproximator.h.

References shark::blas::distance(), and shark::blas::max().

§ leastContributor() [2/2]

template<typename Rng , typename ExactHypervolume >
template<typename Extractor , typename ParetoFrontType >
std::size_t shark::LeastContributorApproximator< Rng, ExactHypervolume >::leastContributor ( Extractor  extractor,
ParetoFrontType const &  front 
)
inline

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

This version uses the reference point estimated by the last call to updateInternals.

Parameters
[in]extractorExtracts point information from front elements.
[in]frontpareto front of points

Definition at line 574 of file LeastContributorApproximator.h.

§ sample()

template<typename Rng , typename ExactHypervolume >
template<typename Set , typename VectorType >
void shark::LeastContributorApproximator< Rng, ExactHypervolume >::sample ( const Set &  s,
typename Set::iterator  point,
unsigned int  r,
double  delta,
const VectorType refPoint 
)
inline

Samples in the bounding box of the supplied point until a pre-defined threshold is reached.

Parameters
[in]sSet of points.
[in]pointIterator to the point that should be sampled.
[in]rThe current round.
[in]deltaThe delta that should be reached.
[in]refPointReference point for hypervolume calculation/approximation.

Definition at line 405 of file LeastContributorApproximator.h.

References shark::blas::max(), SHARKEXCEPTION, and shark::sqr().

§ STRATEGY_REGISTRY()

template<typename Rng , typename ExactHypervolume >
static registry_type& shark::LeastContributorApproximator< Rng, ExactHypervolume >::STRATEGY_REGISTRY ( )
inlinestatic

Definition at line 209 of file LeastContributorApproximator.h.

§ updateInternals()

template<typename Rng , typename ExactHypervolume >
template<typename Extractor , typename PointSet >
void shark::LeastContributorApproximator< Rng, ExactHypervolume >::updateInternals ( Extractor  extractor,
PointSet const &  set 
)
inline

Updates the internal variables of the indicator using a whole population.

Calculates the reference point of the volume from the population using the maximum value in every dimension+1

Parameters
extractorExtracts point information from set.
setThe set of points.

Definition at line 586 of file LeastContributorApproximator.h.

References shark::blas::max(), and shark::blas::noalias().

Friends And Related Function Documentation

§ operator<<

template<typename Rng , typename ExactHypervolume >
std::ostream& operator<< ( std::ostream &  stream,
Strategy  strategy 
)
friend

Definition at line 215 of file LeastContributorApproximator.h.

§ operator>>

template<typename Rng , typename ExactHypervolume >
std::istream& operator>> ( std::istream &  stream,
Strategy strategy 
)
friend

Definition at line 221 of file LeastContributorApproximator.h.

Member Data Documentation

§ m_errorBound

template<typename Rng , typename ExactHypervolume >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_errorBound

The error bound.

Definition at line 356 of file LeastContributorApproximator.h.

§ m_errorProbability

template<typename Rng , typename ExactHypervolume >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_errorProbability

The error probability.

Definition at line 355 of file LeastContributorApproximator.h.

§ m_gamma

template<typename Rng , typename ExactHypervolume >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_gamma

Definition at line 351 of file LeastContributorApproximator.h.

§ m_logFactor

template<typename Rng , typename ExactHypervolume >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_logFactor

Definition at line 346 of file LeastContributorApproximator.h.

§ m_maxNumSamples

template<typename Rng , typename ExactHypervolume >
unsigned long long shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_maxNumSamples

Definition at line 350 of file LeastContributorApproximator.h.

§ m_minimumMultiplierDelta

template<typename Rng , typename ExactHypervolume >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_minimumMultiplierDelta

Definition at line 349 of file LeastContributorApproximator.h.

§ m_multiplierDelta

template<typename Rng , typename ExactHypervolume >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_multiplierDelta

Definition at line 348 of file LeastContributorApproximator.h.

§ m_reference

template<typename Rng , typename ExactHypervolume >
RealVector shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_reference

the reference calculates by updateInternals

Definition at line 362 of file LeastContributorApproximator.h.

§ m_round

template<typename Rng , typename ExactHypervolume >
unsigned int shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_round

Definition at line 353 of file LeastContributorApproximator.h.

§ m_sampleCounter

template<typename Rng , typename ExactHypervolume >
boost::uint_fast64_t shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_sampleCounter

Definition at line 359 of file LeastContributorApproximator.h.

§ m_sampleCountThreshold

template<typename Rng , typename ExactHypervolume >
boost::uint_fast64_t shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_sampleCountThreshold

Definition at line 360 of file LeastContributorApproximator.h.

§ m_startDelta

template<typename Rng , typename ExactHypervolume >
double shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_startDelta

Definition at line 347 of file LeastContributorApproximator.h.

§ m_strategy

template<typename Rng , typename ExactHypervolume >
Strategy shark::LeastContributorApproximator< Rng, ExactHypervolume >::m_strategy

Definition at line 358 of file LeastContributorApproximator.h.


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