Hypervolume¶
A Quick Look¶
Many multiple objective optimization problems often require a good method for comparison of solutions. The question of how to do it is neither trivial, nor definite. Hypervolume indicator (also known as Lebesgue measure or S-metric) found its application in that domain. PyGMO allows for computing the hypervolume for the population objects (in that case, each individual fitness vector is treated as d-dimensional point), or for the fixed set of points.
Main class for that purpose is the PyGMO.util.hypervolume class. It is a main interface for computation of the hypervolume. In order to compute a hypervolume from a population object, you can do the following:
from PyGMO import *
from PyGMO.util import *
prob = problem.dtlz(1)
pop = population(prob,20)
hv = hypervolume(pop)
print hv.compute(r = [1000.0]*3)
Additionally, you can use the same module for the computation of a fixed hypervolume problem:
from PyGMO.util import *
hv = hypervolume([[3,1],[2,1], [3,1]])
print hv.compute(r = [4.0]*2)
You can also explicitly request an particular algorithm for the computation:
from PyGMO.util import *
hv = hypervolume([[2,1,1] , [1,2,1], [1,1,2]])
print hv.compute(r = [3.5]*3, algorithm = hv_algorithm.hv3d())
Besides the computation of the hypervolume of given pareto front (which may serve as a quality indicator), other methods are available as well:
from PyGMO.util import *
hv = hypervolume([[2,1,1] , [1,2,1], [1,1,2]])
print hv.exclusive(p_idx = 0, r = [3.5]*3) # returns the exclusive volume by point 0
print hv.least_contributor(r = [3.5]*3) # returns the index of the least contributor
Method ‘exlusive’ computes the hypervolume of the point at given index. Method ‘least_contributors’ returns the index of the individual (point) contributing the least to the hypervolume.
Available Hypervolume algorithms¶
| Common Name | Name in PyGMO | Comments |
|---|---|---|
| hv2d | PyGMO.util.hv_algorithm.hv2d | Algorithm for quick computation of 2d hypervolumes. |
| hv3d | PyGMO.util.hv_algorithm.hv3d | Algorithm for quick computation of 3d hypervolumes. |
| hv4d | PyGMO.util.hv_algorithm.hv4d | Algorithm for quick computation of 4d hypervolumes. |
| WFG | PyGMO.util.hv_algorithm.wfg | General algorithm for any dimension. |
| HOY | PyGMO.util.hv_algorithm.hoy | General algorithm for any dimension. |
| Bringmann-Friedrich approximation | PyGMO.util.hv_algorithm.bf_approx | Algorithm for computation of the approximated least contributor. |
| FPRAS | PyGMO.util.hv_algorithm.bf_fpras | Algorithm for computation of the approximated hypervolume. |
Detailed Documentation¶
- class PyGMO.util.hypervolume¶
This class allows for setting up hypervolume computation problems. Given hypervolume problem can be set up using population object, or by a list object.
- __init__((PyGMO.population)pop)¶
Constructs a hypervolume problem from a population object. In that case, each individual’s fitness vector is pulled from the population, and treated as a point in hyperspace.
- USAGE:
from PyGMO import * from PyGMO.util import *
prob = problem.dtlz(1)
pop = population(prob,20)
hv = hypervolume(pop)
- __init__((list)L)
Constructs a custom hypervolume problem from a list. List object must contain other list objects that represent points in hyperspace. List object cannot be empty, and the dimension of each point must be no lesser than 2.
- USAGE:
from PyGMO.util import *
hv = hypervolume([[2,1,1], [1,1,2], [1,2,1]])
- compute(r, algorithm = None)¶
Computes the hypervolume for given problem, using the provided reference point r. Keyword algorithm must be an instance of algorithms that can be found inside PyGMO.util.hv_algorithm module. If the keyword is not provided, PyGMO chooses one automatically using the information about the reference point. In case of 2, 3 and 4 dimensions, algorithms hv2d, hv3d and hv4d are used. For larger dimensions the default method is the WFG. As of yet, it is required that reference point is numerically no lesser by each dimension than any point from the previously constructed set of points.
- r - reference point used for computation
- algorithm (optional) - hypervolume algorithm used for the computation, uses the best performing algorithm for given dimension by default
- USAGE:
print hv.compute([3,3,3])
print hv.compute([3,3,3], algorithm = hv_algorithm.hv3d())
print hv.compute([3,3,3], algorithm = hv_algorithm.wfg())
- exclusive(p_idx, r, algorithm = None)¶
Computes the exlusive hypervolume for point at given index ‘p_idx’, using the provided reference point ‘r’ and the hypervolume algorithm (optional). Keyword algorithm must be an instance of algorithms that can be found inside PyGMO.util.hv_algorithm module. If the keyword is not provided, PyGMO chooses one automatically using the information about the reference point.
- p_idx - index of the point for which we compute the exclusive hypervolume
- r - reference point used for computation
- algorithm (optional) - hypervolume algorithm used for the computation, uses the best performing algorithm for given dimension by default
- USAGE:
hv.exclusive(p_idx=5, r=[5.0]*3)
hv.exclusive(p_idx=5, r=[5.0]*3, algorithm=hv_algorithm.hv3d())
- least_contributor(r, algorithm = None)¶
Computes the least contributor to the hypervolume using provided reference point ‘r’ and the hypervolume algorithm (optional). Keyword algorithm must be an instance of algorithms that can be found inside PyGMO.util.hv_algorithm module. If the keyword is not provided, PyGMO chooses one automatically using the information about the reference point.
- r - reference point used for computation
- algorithm (optional) - hypervolume algorithm used for the computation, uses the best performing algorithm for given dimension by default
- USAGE:
hv.least_contributor(r=[5.0]*3)
hv.least_contributor(r=[5.0]*3, algorithm=hv_algorithm.bf_approx())
- class PyGMO.util.hv_algorithm.hv2d¶
- This is the quick algorithm the 2 dimensional problems.
- __init__()¶
Creates an instance of PyGMO.util.hv_algorithm.hv2d class that serves as a parameter to the hypervolume object.
- class PyGMO.util.hv_algorithm.hv3d¶
- This is the quick algorithm for the 3 dimensional problems.
- __init__()¶
Creates an instance of PyGMO.util.hv_algorithm.hv3d class that serves as a parameter to the hypervolume object.
- class PyGMO.util.hv_algorithm.hv4d¶
- This is the quick algorithm for the 4 dimensional problems.
- __init__()¶
Creates an instance of PyGMO.util.hv_algorithm.hv4d class that serves as a parameter to the hypervolume object.
- class PyGMO.util.hv_algorithm.wfg¶
- This is the implementation of the WFG algorithm. Its main purpose is handling hypervolume computation for any dimension.
- __init__()¶
Creates an instance of PyGMO.util.hv_algorithm.wfg class that serves as a parameter to the hypervolume object.
- class PyGMO.util.hv_algorithm.hoy¶
- This is the implementation of the HOY algorithm. Its main purpose is handling hypervolume computation for any dimension.
- __init__()¶
Creates an instance of PyGMO.util.hv_algorithm.hoy class that serves as a parameter to the hypervolume object.
- class PyGMO.util.hv_algorithm.bf_approx¶
- This is the implementation of the Bringmann-Friedrich approximation algorithm. Its main purpose is handling least contributor computation for any dimension. Algorithm’s output is an approximation of the exact one to a certain degree of accuracy and certain confidence.
- __init__(use_exact = True, trivial_subcase_size = 1, eps = 1e-1, delta = 1e-4, gamma = 0.25, delta_multiplier = 0.775, initial_delta_coeff = 1e-1, alpha = 0.2)¶
Creates an instance of PyGMO.util.hv_algorithm.bf_approx class that serves as a parameter to the hypervolume object. Default values for the parameters of the algorithm were obtained from the shark implementation of the algorithm: http://image.diku.dk/shark/doxygen_pages/html/_least_contributor_approximator_8hpp_source.html
- Parameters:
- use_exact - should bf_approx use exact methods for computation
- trivial_subcase_size - when the number of points overlapping the bounding box is smaller or equal to that argument, we compute the exlusive hypervolume exactly
- eps - accuracy of approximation
- delta - confidence of approximation
- gamma - constant used for computation of delta for each of the points during the sampling
- delta_multiplier - factor with which delta diminishes each round
- initial_delta_coeff - initial coefficient multiplied by the delta at round 0
- alpha - coefficicient stating how accurately current lowest contributor should be sampled
- class PyGMO.util.hv_algorithm.bf_fpras¶
- This is the implementation of the Bringmann-Friedrich FPRAS algorithm, applied to the hypervolume computation problem. Its main purpose is handling hypervolume computation for any dimension. Algorithm’s output is an approximation of the exact one to a certain degree of accuracy and certain confidence.
- __init__(eps = 1e-2, delta = 1e-2)¶
Creates an instance of PyGMO.util.hv_algorithm.bf_fpras class that serves as a parameter to the hypervolume object.
- Parameters:
- eps - accuracy of approximation
- delta - probability of error of the approximation