Contributing Hypervolume Indicator
Contents
Preamble¶
import numpy as np # for multidimensional containers
import pandas as pd # for DataFrames
import plotly.graph_objects as go # for data visualisation
import plotly.io as pio # to set shahin plot layout
import platypus as plat # multiobjective optimisation framework
import pygmo as pg # multiobjective optimisation framework
import plotly.express as px
pio.templates['shahin'] = pio.to_templated(go.Figure().update_layout(legend=dict(orientation="h",y=1.1, x=.5, xanchor='center'),margin=dict(t=0,r=0,b=40,l=40))).layout.template
pio.templates.default = 'shahin'
Introduction¶
In this section we're going to take a look at how to calculate the contributing hypervolume indicator values for a population of solutions.
The Contributing Hypervolume (CHV) indicator is a population sorting mechanism based on an adaptation of the hypervolume indicator. The hypervoume indicator works by calculating the size of the objective space that has been dominated by an entire approximation set with respect to a specified reference point, whereas the CHV indicator assigns each solution in an approximation set with the size of the space that has been dominated by each solution exclusively. With this information the population can be sorted by the most dominant and diverse solutions. This has been illustrated below in twodimensional space with a population of three solutions.
Calculating the exact CHV indicator is attractively simple. The method begins by first calculating the hypervolume indicator quality of a population $\mathrm{X}$, and then for each solution in the population, the solution is removed and the hypervolume indicator quality is again calculated for the new population. The new hypervolume indicator value is then subtracted from the hypervolume indicator value of the whole population, which results in the CHV indicator value of the solution which was removed. It is then possible to calculate the CHV indicator values of all the solutions in the population, order them by descending value so that they are ordered by the greatest explicit hypervolume indicator contribution, and select the better solutions to form the next parent population. This approach has been listed in Algorithm below.
$$ \begin{aligned} &\textbf{CHVIndicator}(f^{ref}, X)\\ &\;\;\;\;X_{HV} \leftarrow HV(f^{ref},X)\\ &\;\;\;\;for\;\;{n = 1 : \lambda}\;\;do\\ &\;\;\;\;X_t \leftarrow X \backslash {X_n}\\ &HV_n \leftarrow HV(f^{ref},X_t)\\ &CHV_n \leftarrow X_{HV}  HV_n\\ &\textbf{return}\;\;CHV \end{aligned} $$Although many optimisation algorithms use the CHV as a sorting criterion for selection, its calculation becomes computationally infeasible as the number of objectives being considered increase. Monte Carlo approximations have been used to speed up the calculation of the CHV in which through empirical experiments has shown that the method does not impair the quality of the approximation set. However, the speed increase provided by the Monte Carlo approximation method still results into an infeasibility of the CHV indicator on problems consisting of five objectives or more.
This particular measure of diversity preservation can also be used to reduce the size of a final approximation set produced by an optimiser, to a size that will not overwhelm and confuse a decision maker.
CHV Dependence¶
It is important to note the dependence of the CHV indicator on the population on which it is being calculated. To demonstrate this a population initially consisting of three solutions in twoobjective space has been created, these solutions are $A:(1,10)$, $B:(5,3)$, $C:(6,2)$. The figure below illustrates the explicit HV which is contributed by each solution in the population, and it can be observed that in this population solution B contributes the most to the overall HV indicator value. This can be seen clearly by the number of squares shaded by the corresponding colour, and in this case solution B covers seven squares.
In order to properly demonstrate this dependence, a solution has been inserted into the population used in the previous example. The solutions for the following example are now $A:(1,10)$, $B:(5,3)$, $C:(6,2)$, $D:(4,4)$. The figure below illustrates the explicit HV which is contributed by each solution in this updated population, and it can be observed that in this population solution B now contributes the least to the overall HV indicator value. This can again be seen clearly by the number of squares shaded by the corresponding colour, and in this case solution B now covers a single square. This is because the new solution, D, offers dominance over new areas of the objective space as well as objective space which is mutually dominated by solution B. As such, the objective which is mutually dominated by both of these solutions is no longer considered an explicit contribution by any one of these solutions.
Calculating the Contributing Hypervolume Indicator with Platypus¶
Let's define some necessary variables before invoking the Platypus implementation of the hypervolume indicator algorithm to calculate the CHV of each solution. We will use the ZDT1 test function with design variables $\mathrm{D}=30$ throughout this example, with population size $\mathrm{N}=100$.
problem = plat.ZDT1()
D = 30
N = 100
With these variables defined, we will now move onto generating our initial population. We will be using Platypus Solution
objects for this, which we will initialise with random problem variables, evaluate, and then append to a list named solutions
.
solutions = []
for i in range(N):
solution = plat.Solution(problem)
solution.variables = np.random.rand(D)
solution.evaluate()
solutions.append(solution)
Let's print out the variables
and objectives
for the first solution in this list to see what they look like.
print(f"Design variables:\n {solutions[0].variables}")
print(f"Objective values:\n {solutions[0].objectives}")
Now that we have a population of solutions stored in the solutions
variable, we can prepare an instance of the Platypus.indicators.Hypervolume()
object with the desired reference point for the hypervolume indicator calculation. For ZDT1, the reference point is typically $\langle11,11\rangle$.
hyp = plat.indicators.Hypervolume(minimum=[0, 0], maximum=[11, 11])
We can now use this hyp
object to calculate the hypervolume indicator for any population.
Note
The Platypus implementation of the hypervolume indicator requires either a minimum
and a maximum
point, or a reference_set
(not the same as the hypervolume reference point). Normally, a hypervolume indicator algorithm would only require a single vector that defines the reference point $f ^{ref}$. In the case of Platypus, $f ^{ref}$ actually corresponds to maximum
, but Platypus also forces us to provide a vector for minimum
, which we have set to $\langle0, 0\rangle$
Let's calculate the hypervolume indicator value for the population of solutions we created above and named solution
. We'll store this in HV
.
HV = hyp.calculate(solutions)
print(f"Hypervolume indicator value: {HV}")
We now have this single hypervolume indicator value that we will use to calculate the explicit hypervolume contribution of each solution in the population.
CHV = np.empty((0, 1))
for i in range(N):
solutions_subset = solutions[:i] + solutions[i+1:]
CHV = np.vstack([CHV, HV  hyp.calculate(solutions_subset)])
print(f"CHV of solution {i}:\t{CHV[i][0]}")
With the above list, we can consider anything with a CHV of $0$ or around the precision of $16$ positions behind the decimal as a solution that does not contribute to the hypervolume quality of the population.
Calculating the Contributing Hypervolume Indicator with PyGMO¶
We can also use a different framework's implementation of the hypervolume indicator on our population. We should be expecting the same values, but this is a good exercise to larn how to use a different framework, and perhaps to check that they do indeed arrive at the same value.
This time we will use the PyGMO framework. With PyGMO, we are lucky enough to have a builtin function to calculate the CHV of each solution. PyGMO's hypervolume indicator function can work with a few different datatypes, including numpy.array()
. We have previously moved our Platypus solutions to a pandas.DataFrame
(which can easily be output as a numpy.array()
). Let's begin by creating a new DataFrame with the columns f1
and f2
which will be used to store our objective values for each solution.
solutions_df = pd.DataFrame(index=range(N),columns=['f1','f2']).astype(float)
solutions_df.head()
We can see that we've also defined an index range that covers the number of solutions in our population, $\mathrm{N}=100$. This means we have $100$ rows ready, but they their values are initialised to NaN
(Not A Number), which in this case simply indicates missing data.
Let's use a loop to iterate through our solutions
list of $100$ solutions and assign the desired values to the corresponding row in our solutions_df
DataFrame
for i in range(N):
solutions_df.loc[i].f1 = solutions[i].objectives[0]
solutions_df.loc[i].f2 = solutions[i].objectives[1]
solutions_df.head()
We can see our DataFrame now contains the desired values. We can now easily get this data as a numpy.array()
to feed into PyGMO's hypervolume indicator object constructor.
hyp = pg.hypervolume(solutions_df[['f1','f2']].values)
Now we can invoke the exclusive()
method on our hypervolume object and pass in the reference point to calculate the CHV values.
for i in range(N):
print(f"CHV of solution {i}:\t{hyp.exclusive(i, [11, 11]) / np.prod([11, 11])}")
With the knowledge that Platypus normalises the HV values, we have already normalised PyGMO's results by dividing by the product of the reference point. Now we can see that both frameworks have arrived at the same hypervolume indicator, although PyGMO has handled our the precision issue differently.
Conclusion¶
In this section we have introduced the contributing hypervolume indicator as a criterion that can be used in the selection of solutions from a population. With CHV values assigned to solutions in a population, we can, for example, sort them by descending order and select the top 10 solutions to get the 10 solutions that contribute most to the population. We also demonstrated the application of two implementations of the contributing hypervolume indicator, one in Platypus, and one in PyGMO.
Exercise
Try updating the code for the Platypus CHV calculation to address the precision issue.
Exercise
Try using the CHV values for each solution to create a visualisation which highlights the top $T$ (e.g. $T=5$) solutions in a nondominated front.

E. Zitzler, S. K ̈unzli, Indicatorbased selection in multiobjective search, in: Parallel Problem Solving from NaturePPSNVIII, Springer, 2004, pp. 832–842 ↩