Practical Evolutionary Algorithms
A practical book on Evolutionary Algorithms that teaches you the concepts and how they’re implemented in practice.
Get the bookContributing Hypervolume Indicator
Contents Chat Share Follow Download Source
Get access to this section and more
Below is a featured selection from this section. You can access this notebook and more by getting the ebook on Practical Evolutionary Algorithms.
Preamble¶
import numpy as np # for multidimensional containers
import pandas as pd # for DataFrames
import platypus as plat # multiobjective optimisation framework
import pygmo as pg # multiobjective optimisation framework
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 hypervolume 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 in 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 decisionmaker.
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 the number of design variables $\mathrm{D}=30$ throughout this example, and with the 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}")
Design variables: [0.388372 0.16503775 0.32763606 0.80250695 0.27260434 0.09171043 0.28853992 0.2869231 0.55675102 0.01486664 0.40790584 0.31637772 0.6012928 0.90728331 0.75130006 0.87632648 0.03419778 0.39863985 0.55448981 0.31577517 0.72176196 0.54713074 0.7239315 0.95006824 0.38856727 0.60305019 0.27776695 0.41258289 0.65094839 0.02544009] Objective values: [0.38837200082254586, 3.7087621950846414]
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}")
Hypervolume indicator value: 0.7988496734751387
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]}")
CHV of solution 0: 0.0 CHV of solution 1: 0.0 CHV of solution 2: 0.0 CHV of solution 3: 0.0 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: 2.1016782758342956e05 CHV of solution 9: 1.1102230246251565e16 CHV of solution 10: 1.1102230246251565e16 CHV of solution 11: 0.0 CHV of solution 12: 1.1102230246251565e16 CHV of solution 13: 0.0 CHV of solution 14: 0.0 CHV of solution 15: 0.0 CHV of solution 16: 1.1102230246251565e16 CHV of solution 17: 0.0 CHV of solution 18: 0.0 CHV of solution 19: 0.0 CHV of solution 20: 1.1102230246251565e16 CHV of solution 21: 0.0 CHV of solution 22: 0.0 CHV of solution 23: 1.1102230246251565e16 CHV of solution 24: 0.0005987393592888912 CHV of solution 25: 1.1102230246251565e16 CHV of solution 26: 0.0 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.0 CHV of solution 34: 1.1102230246251565e16 CHV of solution 35: 0.0 CHV of solution 36: 0.0 CHV of solution 37: 0.0 CHV of solution 38: 0.0 CHV of solution 39: 4.5810210042018795e06 CHV of solution 40: 1.1102230246251565e16 CHV of solution 41: 0.0 CHV of solution 42: 0.0 CHV of solution 43: 1.1102230246251565e16 CHV of solution 44: 0.0 CHV of solution 45: 0.0 CHV of solution 46: 0.0001693656124199805 CHV of solution 47: 0.0 CHV of solution 48: 1.1102230246251565e16 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.0 CHV of solution 54: 0.0 CHV of solution 55: 6.056482614091863e06 CHV of solution 56: 1.1102230246251565e16 CHV of solution 57: 1.1102230246251565e16 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: 1.1102230246251565e16 CHV of solution 64: 1.1102230246251565e16 CHV of solution 65: 0.0 CHV of solution 66: 1.1102230246251565e16 CHV of solution 67: 0.0 CHV of solution 68: 3.6880928190763385e05 CHV of solution 69: 0.05976250426304486 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.0 CHV of solution 77: 0.0 CHV of solution 78: 0.0 CHV of solution 79: 5.772156118832861e05 CHV of solution 80: 0.0 CHV of solution 81: 1.1102230246251565e16 CHV of solution 82: 9.727938862358343e05 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: 1.1102230246251565e16 CHV of solution 89: 1.1102230246251565e16 CHV of solution 90: 1.1102230246251565e16 CHV of solution 91: 0.0 CHV of solution 92: 0.0006112409913804351 CHV of solution 93: 4.781326621960957e06 CHV of solution 94: 0.0 CHV of solution 95: 1.1102230246251565e16 CHV of solution 96: 0.0 CHV of solution 97: 0.0 CHV of solution 98: 3.6825691780317804e05 CHV of solution 99: 1.1102230246251565e16
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 learn 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()
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 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()
f1  f2  

0  0.388372  3.708762 
1  0.682821  3.925579 
2  0.451501  3.956080 
3  0.482829  4.662264 
4  0.481288  4.249790 
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])}")
CHV of solution 0: 0.0 CHV of solution 1: 0.0 CHV of solution 2: 0.0 CHV of solution 3: 0.0 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: 2.1016782758638404e05 CHV of solution 9: 0.0 CHV of solution 10: 1.1744508029092565e16 CHV of solution 11: 0.0 CHV of solution 12: 0.0 CHV of solution 13: 1.1744508029092565e16 CHV of solution 14: 0.0 CHV of solution 15: 1.1744508029092565e16 CHV of solution 16: 0.0 CHV of solution 17: 0.0 CHV of solution 18: 1.1744508029092565e16 CHV of solution 19: 0.0 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.0005987393592886903 CHV of solution 25: 1.1744508029092565e16 CHV of solution 26: 0.0 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.0 CHV of solution 34: 0.0 CHV of solution 35: 1.1744508029092565e16 CHV of solution 36: 0.0 CHV of solution 37: 0.0 CHV of solution 38: 0.0 CHV of solution 39: 4.581021004415666e06 CHV of solution 40: 1.1744508029092565e16 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.00016936561242023008 CHV of solution 47: 0.0 CHV of solution 48: 0.0 CHV of solution 49: 0.0 CHV of solution 50: 1.1744508029092565e16 CHV of solution 51: 0.0 CHV of solution 52: 0.0 CHV of solution 53: 0.0 CHV of solution 54: 0.0 CHV of solution 55: 6.0564826140698415e06 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: 1.1744508029092565e16 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: 3.688092819079091e05 CHV of solution 69: 0.05976250426304513 CHV of solution 70: 0.0 CHV of solution 71: 0.0 CHV of solution 72: 1.1744508029092565e16 CHV of solution 73: 0.0 CHV of solution 74: 0.0 CHV of solution 75: 0.0 CHV of solution 76: 0.0 CHV of solution 77: 0.0 CHV of solution 78: 0.0 CHV of solution 79: 5.7721561188396505e05 CHV of solution 80: 0.0 CHV of solution 81: 0.0 CHV of solution 82: 9.727938862354673e05 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: 1.1744508029092565e16 CHV of solution 92: 0.0006112409913808416 CHV of solution 93: 4.781326621988483e06 CHV of solution 94: 0.0 CHV of solution 95: 1.1744508029092565e16 CHV of solution 96: 1.1744508029092565e16 CHV of solution 97: 0.0 CHV of solution 98: 3.6825691780362765e05 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 value, although PyGMO has handled 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 ↩
Get access to this section and more
You can access this notebook and more by getting the ebook on Practical Evolutionary Algorithms.