@File : novelty_search.py @Time : 2023/10/24 11:23:08 @Author : Alejandro Marrero @Version : 1.0 @Contact : amarrerd@ull.edu.es @License : (C)Copyright 2023, Alejandro Marrero @Desc : None

NS

Source code in digneapy/_core/_novelty_search.py 
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
class NS:
    def __init__(
        self,
        archive: Optional[Archive] = None,
        k: int = 15,
    ):
        """Creates an instance of the Novelty Search Algorithm
        Args:
            archive (Archive): Archive to store the instances to guide the evolution. Defaults to Archive(threshold=0.001).
            k (int, optional): Number of neighbours to calculate the sparseness. Defaults to 15.
        """
        if k < 0:
            raise ValueError(
                f"{__name__} k must be a positive integer and less than the number of instances."
            )

        if archive is not None and not isinstance(archive, Archive):
            raise ValueError("You must provide a valid Archive object")
        self._k = k
        self._archive = archive if archive is not None else Archive(threshold=0.001)

    @property
    def archive(self):
        return self._archive

    @property
    def k(self):
        return self._k

    def __str__(self):
        return f"NS(k={self._k},A={self._archive})"

    def __repr__(self) -> str:
        return f"NS<k={self._k},A={self._archive}>"

    def __call__(self, instances_descriptors: np.ndarray) -> np.ndarray:
        """Computes the Novelty Search of the instance descriptors with respect to the archive.
           It uses the Euclidean distance to compute the sparseness.

        Args:
            instance_descriptors (np.ndarray): Numpy array with the descriptors of the instances
            archive (Archive): Archive which stores the novelty instances found so far
            k (int, optional): Number of neighbors to consider in the computation of the sparseness. Defaults to 15.

        Raises:
            ValueError: If len(instance_descriptors) <= k

        Returns:
            np.ndarray: novelty scores (s) of the instances descriptors
        """
        if len(instances_descriptors) == 0:
            raise ValueError(
                f"NS was given an empty population to compute the sparseness. Shape is: {instances_descriptors.shape}"
            )
        num_instances = len(instances_descriptors)
        num_archive = len(self.archive)
        result = np.zeros(num_instances, dtype=np.float64)
        if num_archive == 0 and num_instances <= self._k:
            # Initially, the archive is empty and we may not have enough instances to evaluate
            print(
                f"NS has an empty archive at this moment and the given population is not large enough to compute the sparseness. {num_instances} < k ({self._k}). Returning zeros.",
                file=sys.stderr,
            )
            return result

        if num_instances + num_archive <= self._k:
            msg = f"Trying to calculate novelty search with k({self._k}) >= {num_instances} (instances) + {num_archive} (archive)."
            raise ValueError(msg)

        combined = (
            instances_descriptors
            if num_archive == 0
            else np.vstack([instances_descriptors, self._archive.descriptors])
        )
        for i in range(num_instances):
            mask = np.ones(num_instances, bool)
            mask[i] = False
            differences = combined[i] - combined[np.nonzero(mask)]
            distances = np.linalg.norm(differences, axis=1)
            _neighbors = np.partition(distances, self._k + 1)[1 : self._k + 1]
            result[i] = np.sum(_neighbors) / self._k

        return result

__call__(instances_descriptors)

Computes the Novelty Search of the instance descriptors with respect to the archive. It uses the Euclidean distance to compute the sparseness.

Parameters:
  • instance_descriptors (ndarray) –

    Numpy array with the descriptors of the instances

  • archive (Archive) –

    Archive which stores the novelty instances found so far

  • k (int) –

    Number of neighbors to consider in the computation of the sparseness. Defaults to 15.
Raises:
  • ValueError –

    If len(instance_descriptors) <= k
Returns:
  • ndarray –

    np.ndarray: novelty scores (s) of the instances descriptors
Source code in digneapy/_core/_novelty_search.py 
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
def __call__(self, instances_descriptors: np.ndarray) -> np.ndarray:
    """Computes the Novelty Search of the instance descriptors with respect to the archive.
       It uses the Euclidean distance to compute the sparseness.

    Args:
        instance_descriptors (np.ndarray): Numpy array with the descriptors of the instances
        archive (Archive): Archive which stores the novelty instances found so far
        k (int, optional): Number of neighbors to consider in the computation of the sparseness. Defaults to 15.

    Raises:
        ValueError: If len(instance_descriptors) <= k

    Returns:
        np.ndarray: novelty scores (s) of the instances descriptors
    """
    if len(instances_descriptors) == 0:
        raise ValueError(
            f"NS was given an empty population to compute the sparseness. Shape is: {instances_descriptors.shape}"
        )
    num_instances = len(instances_descriptors)
    num_archive = len(self.archive)
    result = np.zeros(num_instances, dtype=np.float64)
    if num_archive == 0 and num_instances <= self._k:
        # Initially, the archive is empty and we may not have enough instances to evaluate
        print(
            f"NS has an empty archive at this moment and the given population is not large enough to compute the sparseness. {num_instances} < k ({self._k}). Returning zeros.",
            file=sys.stderr,
        )
        return result

    if num_instances + num_archive <= self._k:
        msg = f"Trying to calculate novelty search with k({self._k}) >= {num_instances} (instances) + {num_archive} (archive)."
        raise ValueError(msg)

    combined = (
        instances_descriptors
        if num_archive == 0
        else np.vstack([instances_descriptors, self._archive.descriptors])
    )
    for i in range(num_instances):
        mask = np.ones(num_instances, bool)
        mask[i] = False
        differences = combined[i] - combined[np.nonzero(mask)]
        distances = np.linalg.norm(differences, axis=1)
        _neighbors = np.partition(distances, self._k + 1)[1 : self._k + 1]
        result[i] = np.sum(_neighbors) / self._k

    return result

__init__(archive=None, k=15)

Creates an instance of the Novelty Search Algorithm Args: archive (Archive): Archive to store the instances to guide the evolution. Defaults to Archive(threshold=0.001). k (int, optional): Number of neighbours to calculate the sparseness. Defaults to 15.

Source code in digneapy/_core/_novelty_search.py 
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def __init__(
    self,
    archive: Optional[Archive] = None,
    k: int = 15,
):
    """Creates an instance of the Novelty Search Algorithm
    Args:
        archive (Archive): Archive to store the instances to guide the evolution. Defaults to Archive(threshold=0.001).
        k (int, optional): Number of neighbours to calculate the sparseness. Defaults to 15.
    """
    if k < 0:
        raise ValueError(
            f"{__name__} k must be a positive integer and less than the number of instances."
        )

    if archive is not None and not isinstance(archive, Archive):
        raise ValueError("You must provide a valid Archive object")
    self._k = k
    self._archive = archive if archive is not None else Archive(threshold=0.001)

dominated_novelty_search(descriptors, performances, k=15, force_feasible_only=True)

Dominated Novelty Search (DNS) Bahlous-Boldi, R., Faldor, M., Grillotti, L., Janmohamed, H., Coiffard, L., Spector, L., & Cully, A. (2025). Dominated Novelty Search: Rethinking Local Competition in Quality-Diversity. 1. https://arxiv.org/abs/2502.00593v1

Quality-Diversity algorithm that implements local competition through dynamic fitness transformations,
eliminating the need for predefined bounds or parameters. The competition fitness, also known as the dominated novelty score,
is calculated as the average distance to the k nearest neighbors with higher fitness.

The method returns a descending sorted list of instances by their competition fitness value. For each instance ``i'' in the sequence, we calculate all the other instances that dominate it. Then, we compute the distances between their descriptors using the norm of the difference for each dimension of the descriptors. Novel instances will get a competition fitness of np.inf (assuring they will survive). Less novel instances will be selected by their competition fitness value. This competition mechanism creates two complementary evolutionary pressures: individuals must either improve their fitness or discover distinct behaviors that differ from better-performing solutions. Solutions that have no fitter neighbors (D𝑖 = ∅) receive an infinite competition fitness, ensuring their preservation in the population.

Parameters:
  • descriptors (ndarray) –

    Numpy array with the descriptors of the instances

  • performances (ndarray) –

    Numpy array with the performance values of the instances

  • k (int, default: 15 ) –

    Number of nearest neighbours to calculate the competition fitness. Default to 15.

  • force_feasible_only (bool, default: True ) –

    Allow only instances with performance >= 0 to be considered. Default True.

Raises: ValueError: If len(d) where d is the descriptor of each instance i differs from another ValueError: If k >= len(instances)

Returns:
  • Tuple[ndarray, ndarray, ndarray, ndarray] –

    Tuple[np.ndarray]: Tuple with the descriptors, performances and competition fitness values sorted, plus the sorted indexing (descending order).
Source code in digneapy/_core/_novelty_search.py 
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
def dominated_novelty_search(
    descriptors: np.ndarray,
    performances: np.ndarray,
    k: int = 15,
    force_feasible_only: bool = True,
) -> Tuple[np.ndarray, np.ndarray, np.ndarray, np.ndarray]:
    """
    Dominated Novelty Search (DNS)
        Bahlous-Boldi, R., Faldor, M., Grillotti, L., Janmohamed, H., Coiffard, L., Spector, L., & Cully, A. (2025).
        Dominated Novelty Search: Rethinking Local Competition in Quality-Diversity. 1.
        https://arxiv.org/abs/2502.00593v1

        Quality-Diversity algorithm that implements local competition through dynamic fitness transformations,
        eliminating the need for predefined bounds or parameters. The competition fitness, also known as the dominated novelty score,
        is calculated as the average distance to the k nearest neighbors with higher fitness.

    The method returns a descending sorted list of instances by their competition fitness value.
    For each instance ``i'' in the sequence, we calculate all the other instances that dominate it.
    Then, we compute the distances between their descriptors using the norm of the difference for each dimension of the descriptors.
    Novel instances will get a competition fitness of np.inf (assuring they will survive).
    Less novel instances will be selected by their competition fitness value. This competition mechanism creates two complementary evolutionary
    pressures: individuals must either improve their fitness or discover distinct behaviors that differ from better-performing
    solutions. Solutions that have no fitter neighbors (D𝑖 = ∅) receive an infinite competition fitness, ensuring their preservation in the
    population.

    Args:
        descriptors (np.ndarray): Numpy array with the descriptors of the instances
        performances (np.ndarray): Numpy array with the performance values of the instances
        k (int): Number of nearest neighbours to calculate the competition fitness. Default to 15.
        force_feasible_only (bool): Allow only instances with performance >= 0 to be considered. Default True.
    Raises:
        ValueError: If len(d) where d is the descriptor of each instance i differs from another
        ValueError: If k >= len(instances)

    Returns:
        Tuple[np.ndarray]: Tuple with the descriptors, performances and competition fitness values sorted, plus the sorted indexing (descending order).
    """
    num_instances = len(descriptors)
    if num_instances <= k:
        msg = f"Trying to calculate the dominated novelty search with k({k}) > len(instances) = {num_instances}"
        raise ValueError(msg)

    if len(performances) != len(descriptors):
        raise ValueError(
            f"Array mismatch between peformances and descriptors. len(performance) = {len(performances)} != {len(descriptors)} len(descriptors)"
        )
    # Try to force only feasible performances to get proper biased instances
    is_unfeasible = (
        performances < 0.0 if force_feasible_only else (performances == -np.inf)
    )
    fitter = performances[:, None] <= performances[None, :]
    fitter = np.where(is_unfeasible[None, :], False, fitter)
    np.fill_diagonal(fitter, False)
    distance = np.linalg.norm(
        descriptors[:, None, :] - descriptors[None, :, :], axis=-1
    )
    distance = np.where(fitter, distance, np.inf)
    neg_dist = -distance
    indices = np.argpartition(neg_dist, -k, axis=-1)[..., -k:]
    values = np.take_along_axis(neg_dist, indices, axis=-1)
    indices = np.argsort(values, axis=-1)[..., ::-1]
    values = np.take_along_axis(values, indices, axis=-1)
    indices = np.take_along_axis(indices, indices, axis=-1)
    distance = np.mean(
        -values, where=np.take_along_axis(fitter, indices, axis=1), axis=-1
    )
    distance = np.where(np.isnan(distance), np.inf, distance)
    distance = np.where(is_unfeasible, -np.inf, distance)
    sorted_indices = np.argsort(-distance)
    return (
        descriptors[sorted_indices],
        performances[sorted_indices],
        distance[sorted_indices],
        sorted_indices,
    )