moocore.

UnboundedArchive

moocore.UnboundedArchive(dim, *, maximise=False, max_children=0, max_bucket_size=0, allow_duplicates=True)

Create an empty unbounded-size nondominated archive. The type of archive built depends on dim.

A nondominated archive is a data structure that stores only nondominated points and allows efficient updates with new points. When a new point is added, if the new point is (weakly)-dominated by an existing point in the archive, the point would be rejected. If the new point is not (weakly)-dominated, it will be accepted. Points in the archive (weakly)-dominated by the new one will be removed. If the archive allows duplicates, then duplicated points, i.e., weakly-dominated but not dominated, are allowed in the archive.

These archives are unbounded, that is, there is no limit in the number of nondominated points that can be stored in the archive.

The archive can optionally store an arbitrary Python object associated to each point. When the archive allows duplicates, duplicated points may be associated to different Python objects.

When dim = 2, the archive is based on a treap data structure [1]. When dim > 2, the archive is based on a ND-Tree [2].

Parameters:

• dim (int) – Dimension (number of criteria/objectives) of the input points stored in the archive.

• maximise (bool | Sequence[bool]) – Whether the objectives must be maximised instead of minimised. Either a single boolean value that applies to all objectives or a list of boolean values, with one value per objective. Also accepts a 1D array with values 0 or 1 for each objective. (default: False)

• max_children (int) – Maximum number of children used in the ND-Tree (only when dim > 2). (default: 0)

• max_bucket_size (int) – Maximum number of solutions stored in each leaf of the ND-Tree (only when dim > 2). (default: 0)

• allow_duplicates (bool) – Whether to allow or reject duplicated input points (i.e., objective vectors). (default: True)

Returns:

BaseUnboundedArchive – Abstract base class that documents the methods available.

References

[1]

C. R. Aragon and R. G. Seidel. Randomized search trees. In 30th Annual Symposium on Foundations of Computer Science, 540–545. 1989. doi:10.1109/SFCS.1989.63531, [BibTeX].

[2]

Andrzej Jaszkiewicz and Thibaut Lust. ND-tree-based update: a fast algorithm for the dynamic nondominance problem. IEEE Transactions on Evolutionary Computation, 22(5):778–791, 2018. doi:10.1109/TEVC.2018.2799684, [BibTeX].

Examples

>>> arch = UnboundedArchive(dim=2)
>>> arch.add_many([[10, 10], [5, 20], [20, 5]])
[True, True, True]
>>> arch.add([11, 11])
False

The len() function applied to the archive returns the number of points:

>>> len(arch)
3
>>> arch.add([5, 5])
True
>>> len(arch)
1
>>> arch.add_many([[6, 4], [4, 6]])
[True, True]

We can also iterate over the contents:

>>> for z, _ in arch:
...     print(z)
[4. 6.]
[5. 5.]
[6. 4.]

It is possible to associate x-values to each point.

>>> arch = UnboundedArchive(3)
>>> arch.add_many([[10, 10, 10], [5, 5, 20], [20, 5, 5]], x=["a", "b", "c"])
[True, True, True]
>>> len(arch)
3
>>> arch.add([9, 9, 9], x="d")
True
>>> arch
[[20.  5.  5.]
 [ 5.  5. 20.]
 [ 9.  9.  9.]]
x = ['c', 'b', 'd']

The default is to allow duplicates:

>>> arch.add([9, 9, 9], x="e")
True
>>> arch
[[20.  5.  5.]
 [ 5.  5. 20.]
 [ 9.  9.  9.]
 [ 9.  9.  9.]]
x = ['c', 'b', 'd', 'e']

The in keyword can be used to test if a point is in the archive:

>>> [9, 9, 9] in arch
True
>>> [10, 10, 10] in arch
False

And we can retrieve the object associated to a particular point:

>>> arch.get_x_values_of_vector([9, 9, 9])
['d', 'e']
>>> arch.get_x_values_of_vector([10, 10, 10])
[]

The contents of the archive can be obtained in different ways:

>>> arch.get_contents()
(array([[20.,  5.,  5.],
       [ 5.,  5., 20.],
       [ 9.,  9.,  9.],
       [ 9.,  9.,  9.]]), ['c', 'b', 'd', 'e'])
>>> arch.get_unique_vectors()
array([[20.,  5.,  5.],
       [ 5.,  5., 20.],
       [ 9.,  9.,  9.]])
>>> arch.get_x_values()
['c', 'b', 'd', 'e']
>>> for z, x in arch:
...     print(f"{x} -> {z}")
c -> [20.  5.  5.]
b -> [ 5.  5. 20.]
d -> [9. 9. 9.]
e -> [9. 9. 9.]

The vectors returned by iterating are read-only:

>>> for z, x in arch:
...     z[0] = 1
Traceback (most recent call last):
ValueError: assignment destination is read-only

We can also mix maximisation and minimisation objectives:

>>> arch = UnboundedArchive(dim=2, maximise=[False, True])
>>> arch.add_many([[10, 10], [9, 9], [0, 0]])
[True, True, True]
>>> arch.add([10, 9])
False
>>> arch.dominated_by([0, 11])
True
>>> arch.dominates([10, 11])
False
>>> arch
[[ 0.  0.]
 [ 9.  9.]
 [10. 10.]]
x = []