This package implements a multi-objective non-dominated archive for 2, 3 or 4 objectives, providing easy and fast access to multiple hypervolume indicators:
- the hypervolume of the entire archive,
- the contributing hypervolume of each element,
- the uncrowded hypervolume improvement (see also here) of any given point in the objective space, and
- the uncrowded hypervolume of the (unpruned) archive, here called hypervolume plus.
Additionally, the package provides a constrained version of the archive, which allows to store points with constraints.
The source code is available on GitHub.
On a system shell, either like
pip install moarchiving
or from GitHub, for example
pip install git+https://github.com/CMA-ES/moarchiving.git@development
installing from the development branch.
python -m moarchiving.test
on a system shell should output something like
doctest.testmod(<module 'moarchiving.moarchiving2obj' from '...\\moarchiving\\moarchiving2obj.py'>)
TestResults(failed=0, attempted=90)
...
OK
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromModule(<module 'moarchiving.tests.test_sorted_list' from '...\\moarchiving\\tests\\test_sorted_list.py'>))
.......
----------------------------------------------------------------------
Ran 7 tests in 0.001s
moarchiving with 2 objectives uses the fractions.Fraction type to avoid rounding errors when computing hypervolume differences, but its usage can also be easily switched off by assigning the respective class attributes hypervolume_computation_float_type and hypervolume_final_float_type. The Fraction type can become prohibitively computationally expensive with increasing precision.
The implementation of the two-objective archive is heavily based on the bisect module, while in three and four objectives it is based on the sortedcontainers module.
- 1.0.0 addition of MOArchive classes for 3 and 4 objectives, as well as a class for handling solutions to constrained problems
- 0.7.0 reimplementation of
BiobjectiveNondominatedSortedList.hypervolume_improvementby extracting a sublist first. - 0.6.0 the
infosattribute is alistwith corresponding (arbitrary) information, e.g. for keeping the respective solutions. - 0.5.3 fixed assertion error when not using
fractions.Fraction - 0.5.2 first published version
- Initialization
- Constrained MOArchive
- Accessing solution information
- Adding solutions
- Archive size
- Performance indicators
- Contributing hypervolumes
- Hypervolume improvement
- Distance to the Pareto front
- Enabling or disabling fractions
- Additional functions
- Visualization of indicator values
- Performance tests
The MOArchive object can be created using the get_mo_archive function by providing a list of objective values, a reference point, or at least the number of objectives.
Further solutions can be added using add or add_list methods, but the reference point cannot be changed once the instance is created. A list of information strings can be provided for each element, which will be stored as long as the corresponding element remains in the archive (e.g., the x values of the element). At any time, the list of non-dominated elements and their corresponding information can be accessed.
from moarchiving import get_mo_archive
moa2obj = get_mo_archive([[1, 5], [2, 3], [4, 5], [5, 0]], reference_point=[10, 10], infos=["a", "b", "c", "d"])
moa3obj = get_mo_archive([[1, 2, 3], [3, 2, 1], [3, 3, 0], [2, 2, 1]], [10, 10, 10], ["a", "b", "c", "d"])
moa4obj = get_mo_archive([[1, 2, 3, 4], [1, 3, 4, 5], [4, 3, 2, 1], [1, 3, 0, 1]], reference_point=[10, 10, 10, 10], infos=["a", "b", "c", "d"])
print("points in the 2 objective archive:", list(moa2obj))
print("points in the 3 objective archive:", list(moa3obj))
print("points in the 4 objective archive:", list(moa4obj))points in the 2 objective archive: [[1, 5], [2, 3], [5, 0]]
points in the 3 objective archive: [[3, 3, 0], [2, 2, 1], [1, 2, 3]]
points in the 4 objective archive: [[1, 3, 0, 1], [1, 2, 3, 4]]
MOArchive objects can also be initialized empty.
moa = get_mo_archive(reference_point=[4, 4, 4])
print("points in the empty archive:", list(moa))points in the empty archive: []
Constrained MOArchive supports all the functionalities of a non-constrained MOArchive, with the added capability of handling constraints when adding or initializing the archive. In addition to the objective values of a solution, constraint values must be provided in the form of a list or a number. A solution is deemed feasible when all its constraint values are less than or equal to zero.
from moarchiving import get_cmo_archive
cmoa = get_cmo_archive([[1, 2, 3], [1, 3, 4], [4, 3, 2], [1, 3, 0]], [[3, 0], [0, 0], [0, 0], [0, 1]],
reference_point=[5, 5, 5], infos=["a", "b", "c", "d"])
print("points in the archive:", list(cmoa))points in the archive: [[4, 3, 2], [1, 3, 4]]
archive.infos is used to get the information on solutions in the archive.
# infos of the previously defined empty archive
print("infos of the empty archive", moa.infos)
print("infos of the constrained archive", cmoa.infos)infos of the empty archive []
infos of the constrained archive ['c', 'b']
Solutions can be added to the MOArchive at any time using the add function (for a single solution) or the add_list function (for multiple solutions).
moa.add([1, 2, 3], "a")
print("points:", list(moa))
print("infos:", moa.infos)
moa.add_list([[3, 2, 1], [2, 3, 2], [2, 2, 2]], ["b", "c", "d"])
print("points:", list(moa))
print("infos:", moa.infos)points: [[1, 2, 3]]
infos: ['a']
points: [[3, 2, 1], [2, 2, 2], [1, 2, 3]]
infos: ['b', 'd', 'a']
When adding to the constrained archive, constraint values must be added as well.
cmoa.add_list([[3, 3, 3], [1, 1, 1]], [[0, 0], [42, 0]], ["e", "f"])
print("points:", list(cmoa))
print("infos:", cmoa.infos)points: [[4, 3, 2], [3, 3, 3], [1, 3, 4]]
infos: ['c', 'e', 'b']
The MOArchive implements some functionality of a list (in the 2 objective case, it actually extends the list class, though this is not the case in 3 and 4 objectives). In particular, it includes the len method to get the number of solutions in the archive as well as the in keyword to check if a point is in the archive.
print("Points in the archive:", list(moa))
print("Length of the archive:", len(moa))
print("[2, 2, 2] in moa:", [2, 2, 2] in moa)
print("[3, 2, 0] in moa:", [3, 2, 0] in moa)Points in the archive: [[3, 2, 1], [2, 2, 2], [1, 2, 3]]
Length of the archive: 3
[2, 2, 2] in moa: True
[3, 2, 0] in moa: False
An archive provides the following performance indicators:
hypervolumehypervolume_plus, providing additionally the closest distance to the reference area for an empty archive, see here and herehypervolume_plus_constr(for CMOArchive), based on, but not completely equal to the one defined here
Indicators are defined for maximization (the original hypervolume_plus_constr indicator is multiplied by -1). When the archive is not empty, all the indicators are positive and have the same value. As the archive does not (yet) support an ideal point, the values of indicators are not normalized.
print("Hypervolume of the archive:", moa.hypervolume)
print("Hypervolume plus of the archive:", moa.hypervolume_plus)Hypervolume of the archive: 12
Hypervolume plus of the archive: 12
In case of a constrained MOArchive, the hypervolume_plus_constr attribute can be accessed as well.
print("Hyperolume of the constrained archive:", cmoa.hypervolume)
print("Hypervolume plus of the constrained archive:", cmoa.hypervolume_plus)
print("Hypervolume plus constr of the constrained archive:", cmoa.hypervolume_plus_constr)Hyperolume of the constrained archive: 14
Hypervolume plus of the constrained archive: 14
Hypervolume plus constr of the constrained archive: 14
The contributing_hypervolumes attribute provides a list of hypervolume contributions for each point of the archive. Alternatively, the contribution for a single point can be computed using the contributing_hypervolume(point) method.
for i, objectives in enumerate(moa):
assert moa.contributing_hypervolume(objectives) == moa.contributing_hypervolumes[i]
print("contributing hv of point", objectives, "is", moa.contributing_hypervolume(objectives))
print("All contributing hypervolumes:", moa.contributing_hypervolumes)contributing hv of point [3, 2, 1] is 2
contributing hv of point [2, 2, 2] is 2
contributing hv of point [1, 2, 3] is 2
All contributing hypervolumes: [Fraction(2, 1), Fraction(2, 1), Fraction(2, 1)]
The hypervolume_improvement(point) method returns the improvement of the hypervolume if we would add the point to the archive.
point = [1, 3, 0]
print(f"hypervolume before adding {point}: {moa.hypervolume}")
print(f"hypervolume improvement of point {point}: {moa.hypervolume_improvement(point)}")
moa.add(point)
print(f"hypervolume after adding {point}: {moa.hypervolume}")hypervolume before adding [1, 3, 0]: 12
hypervolume improvement of point [1, 3, 0]: 6
hypervolume after adding [1, 3, 0]: 18
The distance_to_pareto_front(point) method returns the distance between the given point and the Pareto front.
print(f"Current archive: {list(moa)}")
print("Distance of [3, 2, 1] to pareto front:", moa.distance_to_pareto_front([3, 2, 1]))
print("Distance of [3, 2, 2] to pareto front:", moa.distance_to_pareto_front([3, 3, 3]))Current archive: [[1, 3, 0], [3, 2, 1], [2, 2, 2], [1, 2, 3]]
Distance of [3, 2, 1] to pareto front: 0.0
Distance of [3, 2, 2] to pareto front: 1.0
To avoid loss of precision, fractions are used by default. This can be changed to floats by setting the hypervolume_final_float_type and hypervolume_computation_float_type function attributes.
import fractions
get_mo_archive.hypervolume_computation_float_type = fractions.Fraction
get_mo_archive.hypervolume_final_float_type = fractions.Fraction
moa3_fr = get_mo_archive([[1, 2, 3], [2, 1, 3], [3, 3, 1.32], [1.3, 1.3, 3], [1.7, 1.1, 2]], reference_point=[4, 4, 4])
print(moa3_fr.hypervolume)
get_mo_archive.hypervolume_computation_float_type = float
get_mo_archive.hypervolume_final_float_type = float
moa3_nofr = get_mo_archive([[1, 2, 3], [2, 1, 3], [3, 3, 1.32], [1.3, 1.3, 3], [1.7, 1.1, 2]], reference_point=[4, 4, 4])
print(moa3_nofr.hypervolume)161245156349030777798724819133399/10141204801825835211973625643008
15.899999999999999