Contributing Hypervolume Indicator

Preamble

In [1]:
import numpy as np                   # for multi-dimensional 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              # multi-objective optimisation framework
import pygmo as pg                   # multi-objective 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 two-dimensional space with a population of three solutions.

Contributing Hypervolume Indicator

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 two-objective 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.

CHV with three solutions

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.

CHV with four 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$.

In [2]:
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.

In [3]:
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.

In [4]:
print(f"Design variables:\n {solutions[0].variables}")
print(f"Objective values:\n {solutions[0].objectives}")
Design variables:
 [0.15075328 0.67733039 0.28828798 0.77994058 0.45665193 0.57820741
 0.56201372 0.97177937 0.27651144 0.71249518 0.84085362 0.4039491
 0.64843207 0.62018162 0.55052643 0.15276781 0.95331894 0.12605556
 0.33930358 0.66852502 0.8936662  0.58917854 0.23363381 0.14102791
 0.62399114 0.96264146 0.67394996 0.47540925 0.86808249 0.12328518]
Objective values:
 [0.15075328001905353, 5.072052879064982]

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$.

In [5]:
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.

In [6]:
HV = hyp.calculate(solutions)
print(f"Hypervolume indicator value: {HV}")
Hypervolume indicator value: 0.7598049263738476

We now have this single hypervolume indicator value that we will use to calculate the explicit hypervolume contribution of each solution in the population.

In [7]:
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]}")
CHV of solution 0:	0.0
CHV of solution 1:	0.0
CHV of solution 2:	1.1102230246251565e-16
CHV of solution 3:	0.0002092519790036773
CHV of solution 4:	0.0
CHV of solution 5:	0.0
CHV of solution 6:	0.0
CHV of solution 7:	0.0
CHV of solution 8:	0.0
CHV of solution 9:	0.0
CHV of solution 10:	0.0
CHV of solution 11:	0.0
CHV of solution 12:	0.0
CHV of solution 13:	0.0
CHV of solution 14:	0.0
CHV of solution 15:	0.0
CHV of solution 16:	0.0
CHV of solution 17:	0.0
CHV of solution 18:	5.576591804534736e-05
CHV of solution 19:	7.796603141430047e-06
CHV of solution 20:	0.0
CHV of solution 21:	-1.1102230246251565e-16
CHV of solution 22:	0.0
CHV of solution 23:	1.1102230246251565e-16
CHV of solution 24:	0.0
CHV of solution 25:	0.0
CHV of solution 26:	5.1443529762384976e-05
CHV of solution 27:	0.0
CHV of solution 28:	0.0
CHV of solution 29:	-1.1102230246251565e-16
CHV of solution 30:	0.0
CHV of solution 31:	0.0
CHV of solution 32:	0.0
CHV of solution 33:	0.00020671258311477647
CHV of solution 34:	0.0
CHV of solution 35:	0.0
CHV of solution 36:	1.1102230246251565e-16
CHV of solution 37:	0.0
CHV of solution 38:	0.0012109326868405823
CHV of solution 39:	0.0
CHV of solution 40:	0.0
CHV of solution 41:	0.0
CHV of solution 42:	0.0
CHV of solution 43:	0.0
CHV of solution 44:	0.0
CHV of solution 45:	0.0
CHV of solution 46:	0.0
CHV of solution 47:	0.0
CHV of solution 48:	-1.1102230246251565e-16
CHV of solution 49:	1.1102230246251565e-16
CHV of solution 50:	0.0
CHV of solution 51:	0.0
CHV of solution 52:	0.0
CHV of solution 53:	0.00016943666158597548
CHV of solution 54:	-1.1102230246251565e-16
CHV of solution 55:	0.0
CHV of solution 56:	1.1102230246251565e-16
CHV of solution 57:	0.0
CHV of solution 58:	-1.1102230246251565e-16
CHV of solution 59:	1.1102230246251565e-16
CHV of solution 60:	0.0
CHV of solution 61:	0.0
CHV of solution 62:	0.0
CHV of solution 63:	0.0
CHV of solution 64:	0.0
CHV of solution 65:	0.0
CHV of solution 66:	0.0
CHV of solution 67:	0.0
CHV of solution 68:	1.1102230246251565e-16
CHV of solution 69:	0.0
CHV of solution 70:	0.0
CHV of solution 71:	0.0
CHV of solution 72:	1.1102230246251565e-16
CHV of solution 73:	0.0
CHV of solution 74:	1.1102230246251565e-16
CHV of solution 75:	0.0
CHV of solution 76:	0.002428824169973476
CHV of solution 77:	0.0
CHV of solution 78:	0.0
CHV of solution 79:	0.0
CHV of solution 80:	-1.1102230246251565e-16
CHV of solution 81:	0.0
CHV of solution 82:	0.0
CHV of solution 83:	0.0
CHV of solution 84:	-1.1102230246251565e-16
CHV of solution 85:	1.1102230246251565e-16
CHV of solution 86:	-1.1102230246251565e-16
CHV of solution 87:	0.0
CHV of solution 88:	0.0
CHV of solution 89:	1.1102230246251565e-16
CHV of solution 90:	0.0
CHV of solution 91:	0.0
CHV of solution 92:	0.0
CHV of solution 93:	0.0
CHV of solution 94:	0.0
CHV of solution 95:	0.0
CHV of solution 96:	0.0
CHV of solution 97:	0.0
CHV of solution 98:	1.1102230246251565e-16
CHV of solution 99:	0.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 built-in function to calculate the CHV of each solution. PyGMO's hypervolume indicator function can work with a few different data-types, 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.

In [8]:
solutions_df = pd.DataFrame(index=range(N),columns=['f1','f2']).astype(float)
solutions_df.head()
Out[8]:
f1 f2
0 NaN NaN
1 NaN NaN
2 NaN NaN
3 NaN NaN
4 NaN NaN

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

In [9]:
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()
Out[9]:
f1 f2
0 0.150753 5.072053
1 0.197567 5.161087
2 0.291905 3.832387
3 0.002193 6.197517
4 0.577217 3.750645

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.

In [10]:
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.

In [11]:
for i in range(N):
    print(f"CHV of solution {i}:\t{hyp.exclusive(i, [11, 11]) / np.prod([11, 11])}")
CHV of solution 0:	0.0
CHV of solution 1:	0.0
CHV of solution 2:	0.0
CHV of solution 3:	0.00020925197900382504
CHV of solution 4:	0.0
CHV of solution 5:	0.0
CHV of solution 6:	0.0
CHV of solution 7:	0.0
CHV of solution 8:	0.0
CHV of solution 9:	0.0
CHV of solution 10:	0.0
CHV of solution 11:	0.0
CHV of solution 12:	0.0
CHV of solution 13:	0.0
CHV of solution 14:	0.0
CHV of solution 15:	0.0
CHV of solution 16:	0.0
CHV of solution 17:	0.0
CHV of solution 18:	5.576591804538957e-05
CHV of solution 19:	7.796603141359396e-06
CHV of solution 20:	0.0
CHV of solution 21:	0.0
CHV of solution 22:	0.0
CHV of solution 23:	0.0
CHV of solution 24:	0.0
CHV of solution 25:	0.0
CHV of solution 26:	5.1443529762516185e-05
CHV of solution 27:	0.0
CHV of solution 28:	0.0
CHV of solution 29:	0.0
CHV of solution 30:	0.0
CHV of solution 31:	0.0
CHV of solution 32:	0.0
CHV of solution 33:	0.0002067125831148416
CHV of solution 34:	0.0
CHV of solution 35:	0.0
CHV of solution 36:	0.0
CHV of solution 37:	0.0
CHV of solution 38:	0.0012109326868405346
CHV of solution 39:	0.0
CHV of solution 40:	0.0
CHV of solution 41:	0.0
CHV of solution 42:	0.0
CHV of solution 43:	0.0
CHV of solution 44:	0.0
CHV of solution 45:	0.0
CHV of solution 46:	0.0
CHV of solution 47:	0.0
CHV of solution 48:	0.0
CHV of solution 49:	0.0
CHV of solution 50:	0.0
CHV of solution 51:	0.0
CHV of solution 52:	0.0
CHV of solution 53:	0.00016943666158564976
CHV of solution 54:	0.0
CHV of solution 55:	0.0
CHV of solution 56:	0.0
CHV of solution 57:	0.0
CHV of solution 58:	0.0
CHV of solution 59:	0.0
CHV of solution 60:	0.0
CHV of solution 61:	0.0
CHV of solution 62:	0.0
CHV of solution 63:	0.0
CHV of solution 64:	0.0
CHV of solution 65:	0.0
CHV of solution 66:	0.0
CHV of solution 67:	0.0
CHV of solution 68:	0.0
CHV of solution 69:	0.0
CHV of solution 70:	0.0
CHV of solution 71:	0.0
CHV of solution 72:	0.0
CHV of solution 73:	0.0
CHV of solution 74:	0.0
CHV of solution 75:	0.0
CHV of solution 76:	0.0024288241699734446
CHV of solution 77:	0.0
CHV of solution 78:	0.0
CHV of solution 79:	0.0
CHV of solution 80:	0.0
CHV of solution 81:	0.0
CHV of solution 82:	0.0
CHV of solution 83:	0.0
CHV of solution 84:	0.0
CHV of solution 85:	0.0
CHV of solution 86:	0.0
CHV of solution 87:	0.0
CHV of solution 88:	0.0
CHV of solution 89:	0.0
CHV of solution 90:	0.0
CHV of solution 91:	0.0
CHV of solution 92:	0.0
CHV of solution 93:	0.0
CHV of solution 94:	0.0
CHV of solution 95:	0.0
CHV of solution 96:	0.0
CHV of solution 97:	0.0
CHV of solution 98:	0.0
CHV of solution 99:	0.0

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 non-dominated front.


  1. E. Zitzler, S. K ̈unzli, Indicator-based selection in multiobjective search, in: Parallel Problem Solving from Nature-PPSNVIII, Springer, 2004, pp. 832–842