Base hypervolume class. More...

#include <base.h>

Inheritance diagram for pagmo::util::hv_algorithm::base:

Public Member Functions
virtual double	compute (std::vector< fitness_vector > &points, const fitness_vector &r_point) const =0
	Compute method. More...

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 std::vector< double >	contributions (std::vector< fitness_vector > &, const fitness_vector &) const
	Contributions method. More...

virtual void	verify_before_compute (const std::vector< fitness_vector > &points, const fitness_vector &r_point) const =0
	Verification of input. More...

virtual base_ptr	clone () const =0
	Clone method. More...

virtual std::string	get_name () const
	Get algorithm's name. More...

virtual	~base ()
	Destructor required for pure virtual methods.

Static Public Member Functions
static double	volume_between (const fitness_vector &, const fitness_vector &, unsigned int=0)
	Compute volume between two points. More...

Protected Types
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
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
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...

Friends
class	boost::serialization::access

Detailed Description

Base hypervolume class.

This class represents the abstract hypervolume algorithm used for computing the hypervolume indicator (also known as Lebesgue measure, or S-metric), and other measures that can derive from it, e.g. exclusive contribution by given point

The are few public methods available:

'compute' - returns the total hypervolume of the set of points
'exclusive' - returns the exclusive volume contributed by given point
'least_contributor' - returns an index of the point contributing the least volume
'greatest_contributor' - returns an index of the point contributing the most volume
'contributions' - returns a vector of exclusive contributions by each of the points.

Additionally a private method 'base::extreme_contributor' can be overloaded:

'extreme_contributor' - returns an index of a single individual that contributes either the least or the greatest amount of the volume. The distinction between the extreme contributors is made using a comparator function. Purpose of this method is to avoid repeating a similar code for the least and the greatest contributor methods. In many cases it's just a matter of a single alteration in a comparison sign '<' to '>'. See concrete example here for more details.

The following base class provides an interface for any hv_algorithm that may be added. The crucial method to implement is the 'compute' method, as the remaining methods can be derived from it.

Base class assumes that the hv_algorithm implements the 'compute' method, and employs a naive approach to provide other functionalities:

'base::exclusive' method relies on 'compute' method, by computing the hypervolume twice (e.g. ExclusiveHV = HV(P) - HV(P/{p})) 'base::contributions' method relies on 'compute' method as well, by computing the exclusive volume for each point using approach above. 'base::extreme_contributor' (private method) relies on the 'base::contributions' method in order to elicit the correct extreme individual. 'base::least_contributor' and 'base::greatest_contributor' methods rely on 'base::extreme_contributor' method by providing the correct comparator.

Thanks to that, any newly implemented hypervolume algorithm that overloads the 'compute' method, gets the functionalities above as well. It is often the case that the algorithm may provide a better solution for each of the features above, e.g. overloading the 'base::extreme_contributor' method with an efficient solution, will automatically speed up the 'least_contributor' and the 'greatest_contributor' methods as well.

Additionally, any newly implemented hypervolume algorithm should overload the 'base::verify_before_compute' method in order to prevent the computation for the incompatible data.

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

Definition at line 90 of file util/hv_algorithm/base.h.

Member Function Documentation

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

protected

Assert that reference point dominates every other point from the set.

This is a method that can be referenced from verify_before_compute method. The method checks whether the provided reference point fits the minimisation assumption, e.g., reference point must be "no worse" and in at least one objective and "better" for each of the points from the set.

Parameters

[in]	points	- vector of fitness_vectors for which the hypervolume is computed
[in]	r_point	- distinguished "reference point".

Definition at line 41 of file util/hv_algorithm/base.cpp.

virtual base_ptr pagmo::util::hv_algorithm::base::clone ( ) const

pure virtual

Clone method.

Returns: pagmo::util::hv_algorithm::base_ptr to a copy of this.

Implemented in pagmo::util::hv_algorithm::hv4d, pagmo::util::hv_algorithm::fpl, pagmo::util::hv_algorithm::hoy, pagmo::util::hv_algorithm::bf_fpras, pagmo::util::hv_algorithm::hv3d, pagmo::util::hv_algorithm::bf_approx, pagmo::util::hv_algorithm::wfg, and pagmo::util::hv_algorithm::hv2d.

bool pagmo::util::hv_algorithm::base::cmp_greatest	(	const double	a,
		const double	b
	)

staticprotected

Comparison method for the least contributor.

This method is used as a comparison function for the extreme contributor method which may be overloaded by hv algorithms. In such case, this method can determine, given two contributions of points, which one is the "greater" contributor.

Parameters

[in]	a	first contribution of a point
[in]	b	second contribution of a point

Returns: true if contribution 'a' is greater than contribution 'b'

Definition at line 150 of file util/hv_algorithm/base.cpp.

bool pagmo::util::hv_algorithm::base::cmp_least	(	const double	a,
		const double	b
	)

staticprotected

Comparison method for the least contributor.

This method is used as a comparison function for the extreme contributor method which may be overloaded by hv algorithms. In such case, this method can determine, given two contributions of points, which one is the "smaller" contributor.

Parameters

[in]	a	first contribution of a point
[in]	b	second contribution of a point

Returns: true if contribution 'a' is lesser than contribution 'b'

Definition at line 134 of file util/hv_algorithm/base.cpp.

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

pure virtual

Compute method.

This method computes the hypervolume. It accepts a list of points as an input, and the distinguished "reference point". Hypervolume is then computed as a joint hypervolume of hypercubes, generated pairwise with the reference point and each point from the set.

Parameters

[in]	points	- vector of fitness_vectors for which the hypervolume is computed
[in]	r_point	- distinguished "reference point".

Implemented in pagmo::util::hv_algorithm::hv4d, pagmo::util::hv_algorithm::hoy, pagmo::util::hv_algorithm::fpl, pagmo::util::hv_algorithm::hv3d, pagmo::util::hv_algorithm::bf_approx, pagmo::util::hv_algorithm::bf_fpras, pagmo::util::hv_algorithm::wfg, and pagmo::util::hv_algorithm::hv2d.

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

virtual

Contributions method.

This methods return the exclusive contribution to the hypervolume for each point. Main reason for this method is the fact that in most cases the explicit request for all contributions can be done more efficiently (may vary depending on the provided hv_algorithm) than executing "exclusive" method in a loop.

This base method uses a very naive approach, which in fact is only slightly more efficient than calling "exclusive" method successively.

Parameters

[in]	points	vector of fitness_vectors for which the contributions are computed
[in]	r_point	distinguished "reference point".

Returns: vector of exclusive contributions by every point

Reimplemented in pagmo::util::hv_algorithm::bf_fpras, pagmo::util::hv_algorithm::hv3d, pagmo::util::hv_algorithm::wfg, and pagmo::util::hv_algorithm::hv2d.

Definition at line 199 of file util/hv_algorithm/base.cpp.

int pagmo::util::hv_algorithm::base::dom_cmp	(	double *	a,
		double *	b,
		unsigned int	size
	)

staticprotected

Dominance comparison method.

Establishes the domination relationship between two points (overloaded for double*);

returns DOM_CMP_B_DOMINATES_A if point 'b' DOMINATES point 'a' returns DOM_CMP_A_DOMINATES_B if point 'a' DOMINATES point 'b' returns DOM_CMP_A_B_EQUAL if point 'a' IS EQUAL TO 'b' returns DOM_CMP_INCOMPARABLE otherwise

Definition at line 320 of file util/hv_algorithm/base.cpp.

int pagmo::util::hv_algorithm::base::dom_cmp	(	const fitness_vector &	a,
		const fitness_vector &	b,
		unsigned int	dim_bound = `0`
	)

staticprotected

Dominance comparison method.

Establishes the domination relationship between two points.

returns DOM_CMP_B_DOMINATES_A if point 'b' DOMINATES point 'a' returns DOM_CMP_A_DOMINATES_B if point 'a' DOMINATES point 'b' returns DOM_CMP_A_B_EQUAL if point 'a' IS EQUAL TO 'b' returns DOM_CMP_INCOMPARABLE otherwise

Definition at line 285 of file util/hv_algorithm/base.cpp.

double pagmo::util::hv_algorithm::base::exclusive	(	const unsigned int	p_idx,
		std::vector< fitness_vector > &	points,
		const fitness_vector &	r_point
	)		const

virtual

Exclusive hypervolume method.

This method computes the exclusive hypervolume for given individual. It accepts a list of points as an input, and the distinguished "reference point". Hypervolume is then computed as a joint hypervolume of hypercubes, generated pairwise with the reference point and each point from the set.

Parameters

[in]	p_idx	index of the individual
[in]	points	vector of fitness_vectors for which the hypervolume is computed
[in]	r_point	distinguished "reference point".

Returns: exlusive hypervolume contributed by the individual at index p_idx

Reimplemented in pagmo::util::hv_algorithm::bf_fpras.

Definition at line 86 of file util/hv_algorithm/base.cpp.

unsigned int pagmo::util::hv_algorithm::base::extreme_contributor	(	std::vector< fitness_vector > &	points,
		const fitness_vector &	r_point,
		bool(*)(double, double)	cmp_func
	)		const

protectedvirtual

compute the extreme contributor

Computes the index of the individual that contributes the most or the least to the hypervolume (depending on the prodivded comparison function)

Definition at line 103 of file util/hv_algorithm/base.cpp.

std::string pagmo::util::hv_algorithm::base::get_name ( ) const

virtual

Get algorithm's name.

Default implementation will return the algorithm's mangled C++ name.

Returns: name of the algorithm.

Reimplemented in pagmo::util::hv_algorithm::hv4d, pagmo::util::hv_algorithm::fpl, pagmo::util::hv_algorithm::hoy, pagmo::util::hv_algorithm::bf_fpras, pagmo::util::hv_algorithm::hv3d, pagmo::util::hv_algorithm::bf_approx, pagmo::util::hv_algorithm::wfg, and pagmo::util::hv_algorithm::hv2d.

Definition at line 366 of file util/hv_algorithm/base.cpp.

unsigned int pagmo::util::hv_algorithm::base::greatest_contributor	(	std::vector< fitness_vector > &	points,
		const fitness_vector &	r_point
	)		const

virtual

Greatest contributor method.

This method establishes the individual that contributes the most to the hypervolume. By default it computes each individual contribution, and chooses the one with the highest contribution. Other algorithms may overload this method for a more efficient solution.

Parameters

[in]	points	vector of fitness_vectors for which the hypervolume is computed
[in]	r_point	distinguished "reference point".

Returns: index of the greatest contributor

Reimplemented in pagmo::util::hv_algorithm::bf_fpras, and pagmo::util::hv_algorithm::bf_approx.

Definition at line 182 of file util/hv_algorithm/base.cpp.

unsigned int pagmo::util::hv_algorithm::base::least_contributor	(	std::vector< fitness_vector > &	points,
		const fitness_vector &	r_point
	)		const

virtual

Least contributor method.

This method establishes the individual that contributes the least to the hypervolume. By default it computes each individual contribution, and chooses the one with the lowest contribution. Other algorithms may overload this method for a more efficient solution.

Parameters

[in]	points	vector of fitness_vectors for which the hypervolume is computed
[in]	r_point	distinguished "reference point".

Returns: index of the least contributor

Reimplemented in pagmo::util::hv_algorithm::bf_fpras, and pagmo::util::hv_algorithm::bf_approx.

Definition at line 166 of file util/hv_algorithm/base.cpp.

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

pure virtual

Verification of input.

This method serves as a verification method. Not every algorithm is suited of every type of problem.

Parameters

[in]	points	- vector of fitness_vectors for which the hypervolume is computed
[in]	r_point	- distinguished "reference point".

Implemented in pagmo::util::hv_algorithm::hv4d, pagmo::util::hv_algorithm::fpl, pagmo::util::hv_algorithm::hoy, pagmo::util::hv_algorithm::bf_fpras, pagmo::util::hv_algorithm::hv3d, pagmo::util::hv_algorithm::bf_approx, pagmo::util::hv_algorithm::wfg, and pagmo::util::hv_algorithm::hv2d.

double pagmo::util::hv_algorithm::base::volume_between	(	const fitness_vector &	a,
		const fitness_vector &	b,
		unsigned int	dim_bound = `0`
	)

static

Compute volume between two points.

Calculates the volume between points a and b (as defined for n-dimensional Euclidean spaces).

Parameters

[in]	a	first point defining the hypercube
[in]	b	second point defining the hypercube
[in]	dim_bound	dimension boundary for the volume. If equal to 0 (default value), then compute the volume of whole vector. Any positive number limits the computation from dimension 1 to dim_bound INCLUSIVE.