moarchiving.moarchiving.BiobjectiveNondominatedSortedList

list_of_f_pairs does not need to be sorted.

f-pairs beyond the reference_point are pruned away. The reference_point is also used to compute the hypervolume.

sort is a sorting function and sort=None will prevent a sort, which can be useful if the list_of_f_pairs is already sorted.

CAVEAT: the interface, in particular the positional interface may change in future versions.

insert f_pair in self if it is not (weakly) dominated.

Return index at which the insertion took place or None. The list remains sorted in the process.

The list remains non-dominated with unique elements, which means that some or many or even all of its present elements may be removed.

info is added to the infos list. It can be an arbitrary object, e.g. a list or dictionary. It can in particular contain (or be) the solution x such that f_pair == fun(info['x']).

Implementation detail: For performance reasons, insert is avoided in favor of __setitem__, if possible.

>>> from moarchiving import BiobjectiveNondominatedSortedList
>>> arch = BiobjectiveNondominatedSortedList()
>>> len(arch.infos) == len(arch) == 0
True
>>> len(arch), arch.add([2, 2]), len(arch), arch.infos
(0, 0, 1, [None])
>>> arch.add([3, 1], info={'x': [-1, 2, 3], 'note': 'rocks'})
1
>>> len(arch.infos) == len(arch) == 2
True
>>> arch.infos[0], sorted(arch.infos[1].items())
(None, [('note', 'rocks'), ('x', [-1, 2, 3])])
>>> arch.infos[arch.index([3, 1])]['x']
[-1, 2, 3]

insert a list of f-pairs which doesn't need to be sorted.

This is just a shortcut for looping over add, but discarded now contains the discarded elements from all add operations.

>>> from moarchiving import BiobjectiveNondominatedSortedList
>>> arch = BiobjectiveNondominatedSortedList()
>>> list_of_f_pairs = [[1, 2], [0, 3]]
>>> for f_pair in list_of_f_pairs:
...     arch.add(f_pair)  # return insert index or None
0
0
>>> arch == sorted(list_of_f_pairs)  # both entries are nondominated
True
>>> arch.compute_hypervolume([3, 4]) == 5.0
True
>>> arch.infos  # to have infos use `add` instead
[None, None]

Return None.

Details: discarded does not contain elements of list_of_f_pairs. When list_of_pairs is already sorted, merge may have a small performance benefit.

return index where f_pair may need to be inserted.

Smaller indices have a strictly better f1 value or they have equal f1 and better f2 value.

lowest_index restricts the search from below.

Details: This method does a binary search in self using bisect.bisect_left.

return hypervolume w.r.t. reference_point

depricated, subject to removal, see compute_hypervolume and contributing_hypervolumes.

Never implemented: return list of contributing hypervolumes w.r.t. reference_point

return contributing hypervolume of element idx.

If idx is an f_pair, return contributing hypervolume of element with value f_pair. If f_pair is not in self, return hypervolume_improvement(f_pair), i.e., its uncrowded contributing hypervolume (which can be negative).

The return type is self.hypervolume_computation_float_type` and by default `fractions.Fraction`, which can be converted to `float` like ``float(....contributing_hypervolume(idx)).

return a "deep" copy of self

Undocumented

of a dominated f_pair also considering the reference domain.

Non-dominated points have (by definition) a distance of zero, unless the archive is empty and the point does not dominate the reference point.

The implementation assumes that all points of the archive are in the reference domain (and more extreme points have been pruned, as it is the default behavior).

Details: the distance for dominated points is computed by iterating over the relevant kink points (self[i+1][0], self[i][1]). In case of minimization, the boundary with two non-dominated points can be depicted like:

...______.      . <- reference point
         |
         x__. <- kink point
            |
            x___. <- kink point
                |
                |
                :
                :

The three kink points which are possibly used for the computations are denoted by a dot. The outer kink points use one coordinate of the reference point.

return True if any element of self dominates or is equal to f_pair.

Otherwise return False.

>>> from moarchiving import BiobjectiveNondominatedSortedList as NDA
>>> a = NDA([[0.39, 0.075], [0.0087, 0.14]])
>>> a.dominates(a[0])  # is always True if `a` is not empty
True
>>> a.dominates([-1, 33]) or a.dominates([33, -1])
False
>>> a._asserts()

See also bisect_left to find the closest index.

return True if self[idx] dominates or is equal to f_pair.

Otherwise return False or None if idx is out-of-range.

>>> from moarchiving import BiobjectiveNondominatedSortedList as NDA
>>> NDA().dominates_with(0, [1, 2]) is None  # empty NDA
True

return the list of all f_pair-dominating elements in self,

including an equal element. len(....dominators(...)) is hence the number of dominating elements which can also be obtained without creating the list with number_only=True.

>>> from moarchiving import BiobjectiveNondominatedSortedList as NDA
>>> a = NDA([[1.2, 0.1], [0.5, 1]])
>>> len(a)
2
>>> a.dominators([2, 3]) == a
True
>>> a.dominators([0.5, 1])
[[0.5, 1]]
>>> len(a.dominators([0.6, 3])), a.dominators([0.6, 3], number_only=True)
(1, 1)
>>> a.dominators([0.5, 0.9])
[]

return how much f_pair would improve the hypervolume.

If dominated, return the distance to the empirical pareto front multiplied by -1. Else if not in domain, return distance to the reference point dominating area times -1.

Overall this amounts to the uncrowded hypervolume improvement, see https://arxiv.org/abs/1904.08823

Details: when self.reference_point is None and f_pair is a new extreme point, the returned hypervolume improvement is float('inf').

This method extracts a sublist first and thereby tries to circumentvent to compute small differences between large hypervolumes.

return True if f_pair is dominating the reference point,

False otherwise. True means that f_pair contributes to the hypervolume if not dominated by other elements.

f_pair may also be an index in self in which case self[f_pair] is tested to be in-domain.

>>> from moarchiving import BiobjectiveNondominatedSortedList as NDA
>>> a = NDA([[2.2, 0.1], [0.5, 1]], reference_point=[2, 2])
>>> assert len(a) == 1
>>> a.in_domain([0, 0])
True
>>> a.in_domain([2, 1])
False
>>> all(a.in_domain(ai) for ai in a)
True
>>> a.in_domain(0)
True

TODO: improve name?

obsolete and replaced by add_list. merge in a sorted list of f-pairs.

The list can contain dominated pairs, which are discarded during the merge.

Return None.

Details: merging 200 into 100_000 takes 3e-4s vs 4e-4s with add_list. The discarded property is not consistent with the overall merge.

remove dominated or equal entries assuming that the list is sorted.

Return number of dropped elements.

Implementation details: pruning from right to left may be preferable, because list.insert(0) is O(n) while list.append is O(1), however it is not possible with the given sorting: in principle, the first element may dominate all others, which can only be discovered in the last step when traversing from right to left. This suggests that reverse sort may be better for pruning or we should inherit from collections.deque instead from list, but deque seems not to support deletion of slices.

remove element f_pair.

Raises a ValueError (like list) if f_pair is not in self. To avoid the error, checking if f_pair is in self first is a possible coding solution, like

>>> from moarchiving import BiobjectiveNondominatedSortedList
>>> nda = BiobjectiveNondominatedSortedList([[2, 3]])
>>> f_pair = [1, 2]
>>> assert [2, 3] in nda and f_pair not in nda
>>> if f_pair in nda:
...     nda.remove(f_pair)
>>> nda = BiobjectiveNondominatedSortedList()
>>> nda.add_list([[6, 6], [5, 7], [4, 8], [3, 9]])
>>> nda.remove(nda[-1])
>>> _ = nda.add([2, 10])
>>> nda = BiobjectiveNondominatedSortedList._random_archive(p_ref_point=1)
>>> for t in [None, float]:
...     if t:
...         nda.hypervolume_final_float_type = t
...         nda.hypervolume_computation_float_type = t
...     for pair in list(nda):
...         len_ = len(nda)
...         state = nda._state()
...         nda.remove(pair)
...         assert len(nda) == len_ - 1
...         if 100 * pair[0] - int(100 * pair[0]) < 0.7:
...             res = nda.add(pair)
...             assert all(state[i] == nda._state()[i] for i in (
...                [0, 3] if nda.hypervolume_final_float_type is float else [0, 2, 3]))

Return None (like list.remove).