Hypervolumes#

The computation of hypervolumes plays an important role in solving multi-objective 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 single-objective

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.

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