pagmo::util::hv_algorithm::hv3d Class Reference

hv3d hypervolume algorithm class More...

#include <hv3d.h>

Inheritance diagram for pagmo::util::hv_algorithm::hv3d:

Public Member Functions
	hv3d (bool initial_sorting=true)
	Constructor. More...
double	compute (std::vector< fitness_vector > &, const fitness_vector &) const
	Compute hypervolume. More...
std::vector< double >	contributions (std::vector< fitness_vector > &, const fitness_vector &) const
	Contributions method.
void	verify_before_compute (const std::vector< fitness_vector > &, const fitness_vector &) const
	Verify before compute. More...
base_ptr	clone () const
	Clone method.
std::string	get_name () const
	Algorithm name.
Public Member Functions inherited from pagmo::util::hv_algorithm::base
virtual double	exclusive (const unsigned int, std::vector< fitness_vector > &, const fitness_vector &) const
	Exclusive hypervolume method. More...
virtual unsigned int	least_contributor (std::vector< fitness_vector > &, const fitness_vector &) const
	Least contributor method. More...
virtual unsigned int	greatest_contributor (std::vector< fitness_vector > &, const fitness_vector &) const
	Greatest contributor method. More...
virtual	~base ()
	Destructor required for pure virtual methods.

Friends
class	boost::serialization::access

Additional Inherited Members
Static Public Member Functions inherited from pagmo::util::hv_algorithm::base
static double	volume_between (const fitness_vector &, const fitness_vector &, unsigned int=0)
	Compute volume between two points. More...
Protected Types inherited from pagmo::util::hv_algorithm::base
enum	{ DOM_CMP_B_DOMINATES_A = 1, DOM_CMP_A_DOMINATES_B = 2, DOM_CMP_A_B_EQUAL = 3, DOM_CMP_INCOMPARABLE = 4 }
Protected Member Functions inherited from pagmo::util::hv_algorithm::base
void	assert_minimisation (const std::vector< fitness_vector > &, const fitness_vector &) const
	Assert that reference point dominates every other point from the set. More...
virtual unsigned int	extreme_contributor (std::vector< fitness_vector > &, const fitness_vector &, bool(*)(double, double)) const
	compute the extreme contributor More...
Static Protected Member Functions inherited from pagmo::util::hv_algorithm::base
static bool	cmp_least (const double, const double)
	Comparison method for the least contributor. More...
static bool	cmp_greatest (const double, const double)
	Comparison method for the least contributor. More...
static double	volume_between (double *, double *, unsigned int)
	Compute volume between two points. More...
static int	dom_cmp (double *, double *, unsigned int)
	Dominance comparison method. More...
static int	dom_cmp (const fitness_vector &, const fitness_vector &, unsigned int=0)
	Dominance comparison method. More...

Detailed Description

hv3d hypervolume algorithm class

This class contains the implementation of efficient algorithms for the hypervolume computation in 3-dimensions.

'compute' method relies on the efficient algorithm as it was presented by Nicola Beume et al. 'least[greatest]_contributor' methods rely on the HyCon3D algorithm by Emmerich and Fonseca.

See also

"On the Complexity of Computing the Hypervolume Indicator", Nicola Beume, Carlos M. Fonseca, Manuel Lopez-Ibanez, Luis Paquete, Jan Vahrenhold. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 13, NO. 5, OCTOBER 2009

"Computing hypervolume contribution in low dimensions: asymptotically optimal algorithm and complexity results", Michael T. M. Emmerich, Carlos M. Fonseca

Author

Krzysztof Nowak (kn@ki.nosp@m.ryx..nosp@m.net)

Definition at line 52 of file hv3d.h.

Constructor & Destructor Documentation

pagmo::util::hv_algorithm::hv3d::hv3d

(

bool

initial_sorting = true

)

Constructor.

Constructor of the algorithm object. In the very first step, algorithm requires the inital set of points to be sorted ASCENDING in the third dimension. If the input is already sorted, user can skip this step using "initial_sorting = false" option, saving some extra time.

Parameters

[in]

initial_sorting

when set to true (default), algorithm will sort the points ascending by third dimension

Definition at line 39 of file hv3d.cpp.

Member Function Documentation

double pagmo::util::hv_algorithm::hv3d::compute ( std::vector< fitness_vector > &  points, const fitness_vector &  r_point  ) const

virtual

Compute hypervolume.

This method should be used both as a solution to 3D cases, and as a general termination method for algorithms that reduce D-dimensional problem to 3-dimensional one.

This is the implementation of the algorithm for computing hypervolume as it was presented by Nicola Beume et al. The implementation uses std::multiset (which is based on red-black tree data structure) as a container for the sweeping front. Original implementation by Beume et. al uses AVL-tree. The difference is insiginificant as the important characteristics (maintaining order when traversing, self-balancing) of both structures and the asymptotic times (O(log n) updates) are guaranteed. Computational complexity: O(n*log(n))

Parameters

[in]	points	vector of points containing the 3-dimensional points for which we compute the hypervolume
[in]	r_point	reference point for the points

Returns

hypervolume.

Implements pagmo::util::hv_algorithm::base.

Definition at line 56 of file hv3d.cpp.

void pagmo::util::hv_algorithm::hv3d::verify_before_compute ( const std::vector< fitness_vector > &  points, const fitness_vector &  r_point  ) const

virtual

Verify before compute.

Verifies whether given algorithm suits the requested data.

Parameters

[in]	points	vector of points containing the d dimensional points for which we compute the hypervolume
[in]	r_point	reference point for the vector of points

Exceptions

value_error

when trying to compute the hypervolume for the dimension other than 3 or non-maximal reference point

Implements pagmo::util::hv_algorithm::base.

Definition at line 284 of file hv3d.cpp.

---

The documentation for this class was generated from the following files:

• hv3d.h
• hv3d.cpp