ribs.archives.SlidingBoundariesArchive¶
- class ribs.archives.SlidingBoundariesArchive(*, solution_dim, dims, ranges, epsilon=1e-06, qd_score_offset=0.0, seed=None, dtype=<class 'numpy.float64'>, extra_fields=None, remap_frequency=100, buffer_capacity=1000)[source]¶
An archive with a fixed number of sliding boundaries on each dimension.
This archive is the container described in Fontaine 2019. Just like the
GridArchive
, it can be visualized as an n-dimensional grid in the measure space that is divided into a certain number of cells in each dimension. Internally, this archive stores a buffer with thebuffer_capacity
most recent solutions and uses them to determine the boundaries of each dimension of the measure space. After everyremap_frequency
solutions are inserted, the archive remaps the boundaries based on the solutions in the buffer.Initially, the archive has no solutions, so it cannot automatically calculate the boundaries. Thus, until the first remap, this archive divides the measure space defined by
ranges
into equally sized cells.Overall, this archive attempts to make the distribution of the space illuminated by the archive more accurately match the true distribution of the measures when they are not uniformly distributed.
Note
Unlike other archives, this archive does not currently support thresholds or batched addition (see
add()
).- Parameters
solution_dim (int) – Dimension of the solution space.
dims (array-like) – Number of cells in each dimension of the measure space, e.g.
[20, 30, 40]
indicates there should be 3 dimensions with 20, 30, and 40 cells. (The number of dimensions is implicitly defined in the length of this argument).ranges (array-like of (float, float)) – Initial upper and lower bound of each dimension of the measure space, e.g.
[(-1, 1), (-2, 2)]
indicates the first dimension should have bounds \([-1,1]\) (inclusive), and the second dimension should have bounds \([-2,2]\) (inclusive).ranges
should be the same length asdims
.epsilon (float) – Due to floating point precision errors, we add a small epsilon when computing the archive indices in the
index_of()
method – refer to the implementation here. Pass this parameter to configure that epsilon.qd_score_offset (float) – Archives often contain negative objective values, and if the QD score were to be computed with these negative objectives, the algorithm would be penalized for adding new cells with negative objectives. Thus, a standard practice is to normalize all the objectives so that they are non-negative by introducing an offset. This QD score offset will be subtracted from all objectives in the archive, e.g., if your objectives go as low as -300, pass in -300 so that each objective will be transformed as
objective - (-300)
.seed (int) – Value to seed the random number generator. Set to None to avoid a fixed seed.
dtype (str or data-type or dict) – Data type of the solutions, objectives, and measures. We only support
"f"
/np.float32
and"d"
/np.float64
. Alternatively, this can be a dict specifying separate dtypes, of the form{"solution": <dtype>, "objective": <dtype>, "measures": <dtype>}
.extra_fields (dict) – Description of extra fields of data that is stored next to elite data like solutions and objectives. The description is a dict mapping from a field name (str) to a tuple of
(shape, dtype)
. For instance,{"foo": ((), np.float32), "bar": ((10,), np.float32)}
will create a “foo” field that contains scalar values and a “bar” field that contains 10D values. Note that field names must be valid Python identifiers, and names already used in the archive are not allowed.remap_frequency (int) – Frequency of remapping. Archive will remap once after
remap_frequency
number of solutions has been found.buffer_capacity (int) – Number of solutions to keep in the buffer. Solutions in the buffer will be reinserted into the archive after remapping.
Methods
__iter__
()Creates an iterator over the elites in the archive.
__len__
()Number of elites in the archive.
add
(solution, objective, measures, **fields)Inserts a batch of solutions into the archive.
add_single
(solution, objective, measures, ...)Inserts a single solution into the archive.
as_pandas
([include_solutions, include_metadata])DEPRECATED.
clear
()Removes all elites from the archive.
cqd_score
(iterations, target_points, ...[, ...])Computes the CQD score of the archive.
data
([fields, return_type])Retrieves data for all elites in the archive.
grid_to_int_index
(grid_indices)Converts a batch of grid indices into a batch of integer indices.
index_of
(measures)Returns archive indices for the given batch of measures.
index_of_single
(measures)Returns the index of the measures for one solution.
int_to_grid_index
(int_indices)Converts a batch of indices into indices in the archive's grid.
retrieve
(measures)Retrieves the elites with measures in the same cells as the measures specified.
retrieve_single
(measures)Retrieves the elite with measures in the same cell as the measures specified.
Randomly samples elites from the archive.
Attributes
The elite with the highest objective in the archive.
The dynamic boundaries of the cells in each dimension.
Maximum capacity of the buffer.
Total number of cells in the archive.
Number of cells in each dimension.
DEPRECATED.
Mapping from field name to dtype for all fields in the archive.
Whether the archive is empty.
Epsilon for computing archive indices.
List of data fields in the archive.
The size of each dim (upper_bounds - lower_bounds).
The learning rate for threshold updates.
Lower bound of each dimension.
Dimensionality of the measure space.
The offset which is subtracted from objective values when computing the QD score.
Frequency of remapping.
Dimensionality of the solutions in the archive.
Statistics about the archive.
The initial threshold value for all the cells.
Upper bound of each dimension.
- __iter__()¶
Creates an iterator over the elites in the archive.
Example
for elite in archive: elite["solution"] elite["objective"] ...
- __len__()¶
Number of elites in the archive.
- add(solution, objective, measures, **fields)[source]¶
Inserts a batch of solutions into the archive.
Note
Unlike in other archives, this method (currently) is not truly batched; rather, it is implemented by calling
add_single()
on the solutions in the batch, in the order that they are passed in. As such, this method is not invariant to the ordering of the solutions in the batch.See
ArchiveBase.add()
for arguments and return values.
- add_single(solution, objective, measures, **fields)[source]¶
Inserts a single solution into the archive.
This method remaps the archive after every
remap_frequency
solutions are added. Remapping involves changing the boundaries of the archive to the percentage marks of the measures stored in the buffer and re-adding all of the solutions stored in the buffer and the current archive.See
ArchiveBase.add_single()
for arguments and return values.
- as_pandas(include_solutions=True, include_metadata=False)¶
DEPRECATED.
- clear()¶
Removes all elites from the archive.
After this method is called, the archive will be
empty
.
- cqd_score(iterations, target_points, penalties, obj_min, obj_max, dist_max=None, dist_ord=None)¶
Computes the CQD score of the archive.
The Continuous Quality Diversity (CQD) score was introduced in Kent 2022.
Note
This method by default assumes that the archive has an
upper_bounds
andlower_bounds
property which delineate the bounds of the measure space, as is the case inGridArchive
,CVTArchive
, andSlidingBoundariesArchive
. If this is not the case,dist_max
must be passed in, andtarget_points
must be an array of custom points.- Parameters
iterations (int) – Number of times to compute the CQD score. We return the mean CQD score across these iterations.
target_points (int or array-like) – Number of target points to generate, or an (iterations, n, measure_dim) array which lists n target points to list on each iteration. When an int is passed, the points are sampled uniformly within the bounds of the measure space.
penalties (int or array-like) – Number of penalty values over which to compute the score (the values are distributed evenly over the range [0,1]). Alternatively, this may be a 1D array which explicitly lists the penalty values. Known as \(\theta\) in Kent 2022.
obj_min (float) – Minimum objective value, used when normalizing the objectives.
obj_max (float) – Maximum objective value, used when normalizing the objectives.
dist_max (float) – Maximum distance between points in measure space. Defaults to the distance between the extremes of the measure space bounds (the type of distance is computed with the order specified by
dist_ord
). Known as \(\delta_{max}\) in Kent 2022.dist_ord – Order of the norm to use for calculating measure space distance; this is passed to
numpy.linalg.norm()
as theord
argument. Seenumpy.linalg.norm()
for possible values. The default is to use Euclidean distance (L2 norm).
- Returns
The mean CQD score obtained with
iterations
rounds of calculations.- Raises
RuntimeError – The archive does not have the bounds properties mentioned above, and dist_max is not specified or the target points are not provided.
ValueError – target_points or penalties is an array with the wrong shape.
- data(fields=None, return_type='dict')¶
Retrieves data for all elites in the archive.
- Parameters
fields (str or array-like of str) – List of fields to include. By default, all fields will be included, with an additional “index” as the last field (“index” can also be placed anywhere in this list). This can also be a single str indicating a field name.
return_type (str) – Type of data to return. See below. Ignored if
fields
is a str.
- Returns
The data for all entries in the archive. If
fields
was a single str, this will just be an array holding data for the given field. Otherwise, this data can take the following forms, depending on thereturn_type
argument:return_type="dict"
: Dict mapping from the field name to the field data at the given indices. An example is:{ "solution": [[1.0, 1.0, ...], ...], "objective": [1.5, ...], "measures": [[1.0, 2.0], ...], "threshold": [0.8, ...], "index": [4, ...], }
Observe that we also return the indices as an
index
entry in the dict. The keys in this dict can be modified with thefields
arg; duplicate fields will be ignored since the dict stores unique keys.return_type="tuple"
: Tuple of arrays matching the field order given infields
. For instance, iffields
was["objective", "measures"]
, we would receive a tuple of(objective_arr, measures_arr)
. In this case, the results fromretrieve
could be unpacked as:objective, measures = archive.data(["objective", "measures"], return_type="tuple")
Unlike with the
dict
return type, duplicate fields will show up as duplicate entries in the tuple, e.g.,fields=["objective", "objective"]
will result in two objective arrays being returned.By default, (i.e., when
fields=None
), the fields in the tuple will be ordered according to thefield_list
along withindex
as the last field.return_type="pandas"
: AArchiveDataFrame
with the following columns:For fields that are scalars, a single column with the field name. For example,
objective
would have a single column calledobjective
.For fields that are 1D arrays, multiple columns with the name suffixed by its index. For instance, if we have a
measures
field of length 10, we create 10 columns with namesmeasures_0
,measures_1
, …,measures_9
. We do not currently support fields with >1D data.1 column of integers (
np.int32
) for the index, namedindex
.
In short, the dataframe might look like this by default:
solution_0
…
objective
measures_0
…
threshold
index
…
…
Like the other return types, the columns can be adjusted with the
fields
parameter.
All data returned by this method will be a copy, i.e., the data will not update as the archive changes.
- grid_to_int_index(grid_indices)¶
Converts a batch of grid indices into a batch of integer indices.
Refer to
index_of()
for more info.- Parameters
grid_indices (array-like) – (batch_size,
measure_dim
) array of indices in the archive grid.- Returns
(batch_size,) array of integer indices.
- Return type
- Raises
ValueError –
grid_indices
is not of shape (batch_size,measure_dim
)
- index_of(measures)[source]¶
Returns archive indices for the given batch of measures.
First, values are clipped to the bounds of the measure space. Then, the values are mapped to cells via a binary search along the boundaries in each dimension.
At this point, we have “grid indices” – indices of each measure in each dimension. Since indices returned by this method must be single integers (as opposed to a tuple of grid indices), we convert these grid indices into integer indices with
numpy.ravel_multi_index()
and return the result.It may be useful to have the original grid indices. Thus, we provide the
grid_to_int_index()
andint_to_grid_index()
methods for converting between grid and integer indices.As an example, the grid indices can be used to access boundaries of a measure value’s cell. For example, the following retrieves the lower and upper bounds of the cell along dimension 0:
# Access only element 0 since this method operates in batch. idx = archive.int_to_grid_index(archive.index_of(...))[0] lower = archive.boundaries[0][idx[0]] upper = archive.boundaries[0][idx[0] + 1]
See
boundaries
for more info.- Parameters
measures (array-like) – (batch_size,
measure_dim
) array of coordinates in measure space.- Returns
(batch_size,) array of integer indices representing the flattened grid coordinates.
- Return type
- Raises
ValueError –
measures
is not of shape (batch_size,measure_dim
).
- index_of_single(measures)¶
Returns the index of the measures for one solution.
While
index_of()
takes in a batch of measures, this method takes in the measures for only one solution. Ifindex_of()
is implemented correctly, this method should work immediately (i.e. “out of the box”).- Parameters
measures (array-like) – (
measure_dim
,) array of measures for a single solution.- Returns
Integer index of the measures in the archive’s storage arrays.
- Return type
int or numpy.integer
- Raises
ValueError –
measures
is not of shape (measure_dim
,).ValueError –
measures
has non-finite values (inf or NaN).
- int_to_grid_index(int_indices)¶
Converts a batch of indices into indices in the archive’s grid.
Refer to
index_of()
for more info.- Parameters
int_indices (array-like) – (batch_size,) array of integer indices such as those output by
index_of()
.- Returns
(batch_size,
measure_dim
) array of indices in the archive grid.- Return type
- Raises
ValueError –
int_indices
is not of shape (batch_size,).
- retrieve(measures)¶
Retrieves the elites with measures in the same cells as the measures specified.
This method operates in batch, i.e., it takes in a batch of measures and outputs the batched data for the elites:
occupied, elites = archive.retrieve(...) elites["solution"] # Shape: (batch_size, solution_dim) elites["objective"] elites["measures"] elites["threshold"] elites["index"]
If the cell associated with
elites["measures"][i]
has an elite in it, thenoccupied[i]
will be True. Furthermore,elites["solution"][i]
,elites["objective"][i]
,elites["measures"][i]
,elites["threshold"][i]
, andelites["index"][i]
will be set to the properties of the elite. Note thatelites["measures"][i]
may not be equal to themeasures[i]
passed as an argument, since the measures only need to be in the same archive cell.If the cell associated with
measures[i]
does not have any elite in it, thenoccupied[i]
will be set to False. Furthermore, the corresponding outputs will be set to empty values – namely:NaN for floating-point fields
-1 for the “index” field
0 for integer fields
None for object fields
If you need to retrieve a single elite associated with some measures, consider using
retrieve_single()
.- Parameters
measures (array-like) – (batch_size,
measure_dim
) array of coordinates in measure space.- Returns
2-element tuple of (occupied array, dict). The occupied array indicates whether each of the cells indicated by the coordinates in
measures
has an elite, while the dict contains the data of those elites. The dict maps from field name to the corresponding array.- Return type
- Raises
ValueError –
measures
is not of shape (batch_size,measure_dim
).ValueError –
measures
has non-finite values (inf or NaN).
- retrieve_single(measures)¶
Retrieves the elite with measures in the same cell as the measures specified.
While
retrieve()
takes in a batch of measures, this method takes in the measures for only one solution and returns a single bool and a dict with single entries.- Parameters
measures (array-like) – (
measure_dim
,) array of measures.- Returns
If there is an elite with measures in the same cell as the measures specified, then this method returns a True value and a dict where all the fields hold the info of the elite. Otherwise, this method returns a False value and a dict filled with the same “empty” values described in
retrieve()
.- Return type
- Raises
ValueError –
measures
is not of shape (measure_dim
,).ValueError –
measures
has non-finite values (inf or NaN).
- sample_elites(n)¶
Randomly samples elites from the archive.
Currently, this sampling is done uniformly at random. Furthermore, each sample is done independently, so elites may be repeated in the sample. Additional sampling methods may be supported in the future.
Example
elites = archive.sample_elites(16) elites["solution"] # Shape: (16, solution_dim) elites["objective"] ...
- Parameters
n (int) – Number of elites to sample.
- Returns
Holds a batch of elites randomly selected from the archive.
- Return type
- Raises
IndexError – The archive is empty.
- property best_elite¶
The elite with the highest objective in the archive.
None if there are no elites in the archive.
Note
If the archive is non-elitist (this occurs when using the archive with a learning rate which is not 1.0, as in CMA-MAE), then this best elite may no longer exist in the archive because it was replaced with an elite with a lower objective value. This can happen because in non-elitist archives, new solutions only need to exceed the threshold of the cell they are being inserted into, not the objective of the elite currently in the cell. See #314 for more info.
Note
The best elite will contain a “threshold” key. This threshold is the threshold of the best elite’s cell after the best elite was inserted into the archive.
- Type
- property boundaries¶
The dynamic boundaries of the cells in each dimension.
Entry
i
in this list is an array that contains the boundaries of the cells in dimensioni
. The array containsself.dims[i] + 1
entries laid out like this:Archive cells: | 0 | 1 | ... | self.dims[i] | boundaries[i]: 0 1 2 self.dims[i] - 1 self.dims[i]
Thus,
boundaries[i][j]
andboundaries[i][j + 1]
are the lower and upper bounds of cellj
in dimensioni
. To access the lower bounds of all the cells in dimensioni
, useboundaries[i][:-1]
, and to access all the upper bounds, useboundaries[i][1:]
.- Type
list of numpy.ndarray
- property dims¶
Number of cells in each dimension.
- Type
(measure_dim,) numpy.ndarray
- property dtype¶
DEPRECATED.
- property epsilon¶
Epsilon for computing archive indices. Refer to the documentation for this class.
- Type
dtypes[“measures”]
- property interval_size¶
The size of each dim (upper_bounds - lower_bounds).
- Type
(measure_dim,) numpy.ndarray
- property lower_bounds¶
Lower bound of each dimension.
- Type
(measure_dim,) numpy.ndarray
- property qd_score_offset¶
The offset which is subtracted from objective values when computing the QD score.
- Type
- property remap_frequency¶
Frequency of remapping. Archive will remap once after
remap_frequency
number of solutions has been found.- Type
- property stats¶
Statistics about the archive.
See
ArchiveStats
for more info.- Type
- property upper_bounds¶
Upper bound of each dimension.
- Type
(measure_dim,) numpy.ndarray