Hypervolumes
Hypervolumes#
The computation of hypervolumes plays an important role in solving multiobjective optimization problems. In pagmo we include a number of different methods and algorithms that allow hypervolumes to be computed efficiently at all dimensions. More information on the details of the algorithms implemented and their performance can be found in the publication:
 Title
“Empirical performance of the approximation of the least hypervolume contributor.”
 Authors
Krzysztof Nowak, Marcus Märtens, and Dario Izzo.
 Published in
International Conference on Parallel Problem Solving from Nature. Springer International Publishing, 2014.

class hypervolume#
Hypervolume.
This class encapsulate various utilities used to compute the hypervolume of a set of points or the various exclusive contributions.
The main API consists of the five methods:
hypervolume::compute  returns the total hypervolume of the set of points
hypervolume::exclusive  returns the exclusive volume contributed by a given point
hypervolume::least_contributor  returns the index of the point contributing the least volume
hypervolume::greatest_contributor  returns the index of the point contributing the most volume
hypervolume::contributions  returns the vector of exclusive contributions for each of the points.
Each of the methods can be called passing them a reference point (and an index where needed) and will, internally, select the most efficient exact Hypervolume algorithm able to compute the requested quantity. A pagmo::hv_algorithm can also be passed as optional argument, in which case it will be used to perform the computations.
Public Functions

hypervolume()#
Default constructor.
Initiates hypervolume with empty set of points. Used for serialization purposes.

hypervolume(const pagmo::population &pop, bool verify = false)#
Constructor from population.
Constructs a hypervolume object, where points are elicited from a pagmo::population object.
Example:
population pop(zdt{1u}, 20u); hypervolume hv(pop); hypervolume hv2(pop, false);
 Parameters
pop – a pagmo::population
verify – flag stating whether the points should be verified for consistency after the construction.
 Throws
std::invalid_argument – if the population contains a problem that is constrained or singleobjective

hypervolume(const std::vector<vector_double> &points, bool verify = true)#
Constructor from points.
Constructs a hypervolume object from a provided set of points.
Example:
hypervolume hv({{2,3},{3,4}}); hypervolume hv2({{2,3},{3,4}}, false);
 Parameters
points – vector of points for which the hypervolume is computed
verify – flag stating whether the points should be verified after the construction. This regulates validation for further computation as well, use ‘set_verify’ flag to alter it later.

hypervolume(const hypervolume&)#
Default copy constructor.
The copy constructor will deep copy the input problem
other
. Throws
unspecified – any exception thrown by:
memory allocation errors in standard containers,

hypervolume &operator=(const hypervolume&)#
Default copy assignment operator.
 Returns
a reference to
this
.

void set_copy_points(bool)#
Setter for ‘copy_points’ flag.
It is used in cases where we are certain that we can alter the original set of points from the hypervolume object. This is useful when we don’t want to make a copy of the points first, as most algorithms alter the original set, but may result in unexpected behaviour when used incorrectly (e.g. requesting the computation twice out of the same object)
Warning
When this flag is set to true the object can reliably be used only once to compute the hypervolume. Successive usages are undefined behaviour.
 Parameters
copy_points – boolean value stating whether the hypervolume computation may use original set

bool get_copy_points() const#
Getter for ‘copy_points’ flag.
Gets the copy_points flag
 Returns
the copy_points flag value

void set_verify(bool)#
Setter for the ‘verify’ flag.
Turns off the verification phase. By default, the hypervolume object verifies whether certain characteristics of the point set hold, such as valid dimension sizes or a reference point that suits the minimisation. In order to optimize the computation when the rules above are certain, we can turn off that phase.
This may result in unexpected behaviour when used incorrectly (e.g. requesting the computation of empty set of points)
 Parameters
verify – boolean value stating whether the hypervolume computation is to be executed without verification

bool get_verify() const#
Getter for the ‘verify’ flag.
Gets the verify flag
 Returns
the verify flag value

vector_double refpoint(double offset = 0.0) const#
Calculate a default reference point.
Calculates a mock refpoint by taking the maximum in each dimension over all points saved in the hypervolume object. The result is a point that is necessarily dominated by all other points, frequently used for hypervolume computations.
Note
This point is different from the one computed by
pagmo::nadir()
as only the non dominated front is considered in that method (also its complexity is thus higher) Parameters
offset – value that can be added to each objective to assure strict domination
 Returns
reference point

const std::vector<vector_double> &get_points() const#
Get points.
Will return a vector containing the points as they were set up during construction of the hypervolume object.
 Returns
const reference to the vector containing the fitness_vectors representing the points in the hyperspace.

std::shared_ptr<hv_algorithm> get_best_compute(const vector_double&) const#
Chooses the best algorithm to compute the hypervolume.
Returns the best method for given hypervolume computation problem. As of yet, only the dimension size is taken into account.
 Parameters
r_point – reference point for the vector of points
 Returns
an std::shared_ptr to the selected algorithm

std::shared_ptr<hv_algorithm> get_best_exclusive(const unsigned, const vector_double&) const#
Chooses the best algorithm to compute the hypervolume.
Returns the best method for given hypervolume computation problem. As of yet, only the dimension size is taken into account.
 Parameters
p_idx – index of the point for which the exclusive contribution is to be computed
r_point – reference point for the vector of points
 Returns
an std::shared_ptr to the selected algorithm

std::shared_ptr<hv_algorithm> get_best_contributions(const vector_double&) const#
Chooses the best algorithm to compute the hypervolume.
Returns the best method for given hypervolume computation problem. As of yet, only the dimension size is taken into account.
 Parameters
r_point – reference point for the vector of points
 Returns
an std::shared_ptr to the selected algorithm

double compute(const vector_double&) const#
Compute hypervolume.
Computes hypervolume for given reference point. This method chooses the hv_algorithm dynamically.
 Parameters
r_point – vector describing the reference point
 Returns
value representing the hypervolume

double compute(const vector_double&, hv_algorithm&) const#
Compute hypervolume.
Computes hypervolume for given reference point, using given pagmo::hv_algorithm object.
 Parameters
r_point – fitness vector describing the reference point
hv_algo – instance of the algorithm object used for the computation
 Returns
the hypervolume

double exclusive(unsigned, const vector_double&, hv_algorithm&) const#
Compute exclusive contribution.
Computes exclusive hypervolume for given individual.
 Parameters
p_idx – index of the individual for whom we compute the exclusive contribution to the hypervolume
r_point – fitness vector describing the reference point
hv_algo – instance of the algorithm object used for the computation
 Returns
the exclusive contribution to the hypervolume

double exclusive(unsigned, const vector_double&) const#
Compute exclusive contribution.
Computes exclusive hypervolume for given individual. This methods chooses the hv_algorithm dynamically.
 Parameters
p_idx – index of the individual for whom we compute the exclusive contribution to the hypervolume
r_point – fitness vector describing the reference point
 Returns
the exclusive contribution to the hypervolume

std::vector<double> contributions(const vector_double&, hv_algorithm&) const#
Contributions method.
This method returns the exclusive contribution to the hypervolume by every point. The concrete algorithm can implement this feature optimally (as opposed to calling for the exclusive contributor in a loop).
 Parameters
r_point – fitness vector describing the reference point
hv_algo – instance of the algorithm object used for the computation
 Returns
vector of exclusive contributions by every point

std::vector<double> contributions(const vector_double&) const#
Contributions method.
This method returns the exclusive contribution to the hypervolume by every point. The concrete algorithm can implement this feature optimally (as opposed to calling for the exclusive contributor in a loop). The hv_algorithm itself is chosen dynamically, so the best performing method is employed for given task.
 Parameters
r_point – fitness vector describing the reference point
 Returns
vector of exclusive contributions by every point

unsigned long long least_contributor(const vector_double&, hv_algorithm&) const#
Find the least contributing individual.
Establishes the individual contributing the least to the total hypervolume.
 Parameters
r_point – fitness vector describing the reference point
hv_algo – instance of the algorithm object used for the computation
 Returns
index of the least contributing point

unsigned long long least_contributor(const vector_double&) const#
Find the least contributing individual.
Establishes the individual contributing the least to the total hypervolume. This method chooses the best performing hv_algorithm dynamically
 Parameters
r_point – fitness vector describing the reference point
 Returns
index of the least contributing point

unsigned long long greatest_contributor(const vector_double&, hv_algorithm&) const#
Find the most contributing individual.
Establish the individual contributing the most to the total hypervolume.
 Parameters
r_point – fitness vector describing the reference point
hv_algo – instance of the algorithm object used for the computation
 Returns
index of the most contributing point

unsigned long long greatest_contributor(const vector_double&) const#
Find the most contributing individual.
Establish the individual contributing the most to the total hypervolume. This method chooses the best performing hv_algorithm dynamically
 Parameters
r_point – fitness vector describing the reference point
 Returns
index of the most contributing point