Advanced hypervolume computation and analysis#
In this tutorial we cover more advanced topics on the hypervolume indicator and comment on the expected performance of its computation in pygmo.
Computing hypervolume using a specific algorithm#
pygmo uses different algorithms for computing the hypervolume indicator and the hypervolume contributions. By default, it picks the algorithm which is expected to yield the fastest computation with respect to the dimensionality of the given pointset. This selection can be bypassed by passing explicitly the algorithm as parameter of the corresponding method:
>>> import pygmo as pg
>>> hv = pg.hypervolume([[1,0,1],[1,1,0],[1,2,2]])
>>> hv.compute([5,5,5], hv_algo=pg.hvwfg())
114.0
The code above will compute the hypervolume indicator using the Walking Fish Group algorithm, whereas
>>> hv.compute([5,5,5])
114.0
would use (by default) the hv3d algorithm, since it is expected by pygmo to be faster for three dimensions. The following algorithms are available in pygmo:
Note
Some algorithms may not provide certain functionalities, e.g.: bf_fpras algorithm is designed for efficient approxmation of high dimensional hypervolumes, supports only the “compute” method.
We will discuss the details on the approximated hypervolume in the tutorial Approximating the hypervolume. In this tutorial, instead, we focus only on the exact methods.
Runtime analysis of pygmo hypervolume computation#
We have implemented a range of algorithms to choose from when in need to compute hypervolumes.
We utilize this fact to provide users with an efficient computation engine that will most likely pick the
fastest algorithm on default. During the course of some experiments we have measured the capabilities
of our engine for fronts with varying Front size
(number of points) and Dimension
.
Note
The obtained results are specific to the hardware and the architecture of the computer on which these experiments
were executed. Main idea of the plots in this and the following tutorials is to present the relative scaling of the
execution time for various settings of Front size
and Dimension
.
The results are shown in the plots reported on the right.
The first plot above shows the running time (average of 10 fronts per given combination of Front size
and Dimension
)
of computing the front of a DTLZ2 problem. Plot below, the worst case scenario (maximal time of 10 runs for given Front size
and Dimension
). The Z axis as well as the color indicate the execution time in seconds.
As you can see, computation of the hypervolume of 100 points and below is pretty fast, even when facing a 10dimensional problem.
When you’re designing your own experiment, be wary that the worst case complexity of hypervolume algorithms is exponential.
Although the hypervolume indicator is a very common quality indicator for pareto fronts, many multipleobjective optimizers
require a slightly different figure that evaluates the quality of a given individual within the population.
This is resolved by computing the exclusive contribution of a given individual to the population, and in most cases
boils down to eliminating the individual that contributes the least. For that reason, we would also report the timings for
the least_contributor
method.
The increase in the execution time is progressing in a similar fashion, yet the Z axis is now scaled by a factor of 10.
Algorithm comparison#
In this section discuss a quick comparison of the available algorithms, in support to our choice for the default set of algorithms. Since in many cases, multiple objective problems are either 2 or 3dimensional, it was important to have a dedicated algorithm for each of these scenarios. At the moment, there are three exact algorithms in PyGMO, two of which are dedicated for certain dimensions:
Even though WFG is regarded one of the state of the art algorithms for hypervolume computation, dedicated algorithms for 2 and 3 dimensions perform better than general purpose ones in terms of running time as shown by the plot reported below, where the hv3d algorithm shows to have a much lower complexity with respect to WFG.
Short summary of algorithms#
The default algorithm used by pygmo, if not specified otherwise, will be:
hypervolume method 
2D 
3D 
4D and up 




The methods supported by the specific algorithms are listed below:
hv_algorithm 
compute 
exclusive 
least_contributor 
greatest_contributor 
contributions 

Yes 
Yes 
Yes 
Yes 
Yes 

Yes 
Yes 
Yes 
Yes 
Yes 

Yes 
Yes 
Yes 
Yes 
Yes 

No 
No 
Yes 
Yes 
No 

Yes 
No 
No 
No 
No 