Skip to content

Selection

Selection operators for evolutionary algorithms.

Selection

Bases: ABC, Generic[G]

Abstract base class for selection operators.

Source code in src/rotalabs_redqueen/core/selection.py 
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Selection(ABC, Generic[G]):
    """Abstract base class for selection operators."""

    @abstractmethod
    def select(
        self,
        population: Population[G],
        n: int,
        rng: np.random.Generator | None = None,
    ) -> list[Individual[G]]:
        """Select N individuals from the population.

        Args:
            population: Population to select from
            n: Number of individuals to select
            rng: Random number generator

        Returns:
            List of selected individuals
        """
        pass

select(population: Population[G], n: int, rng: np.random.Generator | None = None) -> list[Individual[G]] abstractmethod

Select N individuals from the population.

Parameters:

Name Type Description Default
population Population[G]

Population to select from

 required
n int

Number of individuals to select

 required
rng Generator | None

Random number generator

 None

Returns:

Type Description
list[Individual[G]]

List of selected individuals
Source code in src/rotalabs_redqueen/core/selection.py 
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
@abstractmethod
def select(
    self,
    population: Population[G],
    n: int,
    rng: np.random.Generator | None = None,
) -> list[Individual[G]]:
    """Select N individuals from the population.

    Args:
        population: Population to select from
        n: Number of individuals to select
        rng: Random number generator

    Returns:
        List of selected individuals
    """
    pass

TournamentSelection

Bases: Selection[G], Generic[G]

Tournament selection operator.

Selects individuals by running tournaments where the best of a random subset wins.

Source code in src/rotalabs_redqueen/core/selection.py 
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class TournamentSelection(Selection[G], Generic[G]):
    """Tournament selection operator.

    Selects individuals by running tournaments where the best
    of a random subset wins.
    """

    def __init__(self, tournament_size: int = 3):
        """Initialize tournament selection.

        Args:
            tournament_size: Number of individuals per tournament
        """
        self.tournament_size = tournament_size

    def select(
        self,
        population: Population[G],
        n: int,
        rng: np.random.Generator | None = None,
    ) -> list[Individual[G]]:
        """Select N individuals via tournament."""
        return population.select_parents(n, self.tournament_size, rng)

__init__(tournament_size: int = 3)

Initialize tournament selection.

Parameters:

Name Type Description Default
tournament_size int

Number of individuals per tournament

 3
Source code in src/rotalabs_redqueen/core/selection.py 
51
52
53
54
55
56
57
def __init__(self, tournament_size: int = 3):
    """Initialize tournament selection.

    Args:
        tournament_size: Number of individuals per tournament
    """
    self.tournament_size = tournament_size

select(population: Population[G], n: int, rng: np.random.Generator | None = None) -> list[Individual[G]]

Select N individuals via tournament.

Source code in src/rotalabs_redqueen/core/selection.py 
59
60
61
62
63
64
65
66
def select(
    self,
    population: Population[G],
    n: int,
    rng: np.random.Generator | None = None,
) -> list[Individual[G]]:
    """Select N individuals via tournament."""
    return population.select_parents(n, self.tournament_size, rng)

NoveltySelection

Bases: Selection[G], Generic[G]

Selection based purely on novelty.

Selects individuals with the most novel behaviors.

Source code in src/rotalabs_redqueen/core/selection.py 
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
class NoveltySelection(Selection[G], Generic[G]):
    """Selection based purely on novelty.

    Selects individuals with the most novel behaviors.
    """

    def __init__(self, archive: NoveltyArchive[G] | None = None, k_nearest: int = 15):
        """Initialize novelty selection.

        Args:
            archive: Shared novelty archive (or creates new one)
            k_nearest: Number of neighbors for novelty computation
        """
        self.archive = archive or NoveltyArchive(k_nearest=k_nearest)
        self.k_nearest = k_nearest

    def select(
        self,
        population: Population[G],
        n: int,
        rng: np.random.Generator | None = None,
    ) -> list[Individual[G]]:
        """Select N most novel individuals."""
        # Score all individuals by novelty
        scored = []
        for ind in population:
            novelty = self.archive.compute_novelty(ind.behavior)
            scored.append((ind, novelty))

        # Sort by novelty (highest first)
        scored.sort(key=lambda x: x[1], reverse=True)

        # Update archive with selected behaviors
        selected = [ind for ind, _ in scored[:n]]
        for ind in selected:
            self.archive.add(ind.behavior)

        return selected

__init__(archive: NoveltyArchive[G] | None = None, k_nearest: int = 15)

Initialize novelty selection.

Parameters:

Name Type Description Default
archive NoveltyArchive[G] | None

Shared novelty archive (or creates new one)

 None
k_nearest int

Number of neighbors for novelty computation

 15
Source code in src/rotalabs_redqueen/core/selection.py 
128
129
130
131
132
133
134
135
136
def __init__(self, archive: NoveltyArchive[G] | None = None, k_nearest: int = 15):
    """Initialize novelty selection.

    Args:
        archive: Shared novelty archive (or creates new one)
        k_nearest: Number of neighbors for novelty computation
    """
    self.archive = archive or NoveltyArchive(k_nearest=k_nearest)
    self.k_nearest = k_nearest

select(population: Population[G], n: int, rng: np.random.Generator | None = None) -> list[Individual[G]]

Select N most novel individuals.

Source code in src/rotalabs_redqueen/core/selection.py 
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
def select(
    self,
    population: Population[G],
    n: int,
    rng: np.random.Generator | None = None,
) -> list[Individual[G]]:
    """Select N most novel individuals."""
    # Score all individuals by novelty
    scored = []
    for ind in population:
        novelty = self.archive.compute_novelty(ind.behavior)
        scored.append((ind, novelty))

    # Sort by novelty (highest first)
    scored.sort(key=lambda x: x[1], reverse=True)

    # Update archive with selected behaviors
    selected = [ind for ind, _ in scored[:n]]
    for ind in selected:
        self.archive.add(ind.behavior)

    return selected

NoveltyFitnessSelection

Bases: Selection[G], Generic[G]

Combined novelty and fitness selection.

Balances exploration (novelty) and exploitation (fitness).

Source code in src/rotalabs_redqueen/core/selection.py 
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
class NoveltyFitnessSelection(Selection[G], Generic[G]):
    """Combined novelty and fitness selection.

    Balances exploration (novelty) and exploitation (fitness).
    """

    def __init__(
        self,
        archive: NoveltyArchive[G] | None = None,
        novelty_weight: float = 0.5,
        k_nearest: int = 15,
    ):
        """Initialize combined selection.

        Args:
            archive: Shared novelty archive
            novelty_weight: Weight for novelty (0-1, rest goes to fitness)
            k_nearest: Number of neighbors for novelty
        """
        self.archive = archive or NoveltyArchive(k_nearest=k_nearest)
        self.novelty_weight = novelty_weight
        self.fitness_weight = 1.0 - novelty_weight

    def select(
        self,
        population: Population[G],
        n: int,
        rng: np.random.Generator | None = None,
    ) -> list[Individual[G]]:
        """Select based on combined novelty and fitness score."""
        # Score all individuals
        scored = []
        max_fitness = max(ind.fitness.value for ind in population) or 1.0
        max_novelty = 1.0  # Will normalize

        novelty_scores = []
        for ind in population:
            novelty = self.archive.compute_novelty(ind.behavior)
            novelty_scores.append(novelty)

        max_novelty = max(novelty_scores) or 1.0

        for ind, novelty in zip(population, novelty_scores):
            norm_fitness = ind.fitness.value / max_fitness
            norm_novelty = novelty / max_novelty
            combined = (
                self.fitness_weight * norm_fitness + self.novelty_weight * norm_novelty
            )
            scored.append((ind, combined))

        # Sort by combined score
        scored.sort(key=lambda x: x[1], reverse=True)

        # Update archive
        selected = [ind for ind, _ in scored[:n]]
        for ind in selected:
            self.archive.add(ind.behavior)

        return selected

__init__(archive: NoveltyArchive[G] | None = None, novelty_weight: float = 0.5, k_nearest: int = 15)

Initialize combined selection.

Parameters:

Name Type Description Default
archive NoveltyArchive[G] | None

Shared novelty archive

 None
novelty_weight float

Weight for novelty (0-1, rest goes to fitness)

 0.5
k_nearest int

Number of neighbors for novelty

 15
Source code in src/rotalabs_redqueen/core/selection.py 
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
def __init__(
    self,
    archive: NoveltyArchive[G] | None = None,
    novelty_weight: float = 0.5,
    k_nearest: int = 15,
):
    """Initialize combined selection.

    Args:
        archive: Shared novelty archive
        novelty_weight: Weight for novelty (0-1, rest goes to fitness)
        k_nearest: Number of neighbors for novelty
    """
    self.archive = archive or NoveltyArchive(k_nearest=k_nearest)
    self.novelty_weight = novelty_weight
    self.fitness_weight = 1.0 - novelty_weight

select(population: Population[G], n: int, rng: np.random.Generator | None = None) -> list[Individual[G]]

Select based on combined novelty and fitness score.

Source code in src/rotalabs_redqueen/core/selection.py 
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
def select(
    self,
    population: Population[G],
    n: int,
    rng: np.random.Generator | None = None,
) -> list[Individual[G]]:
    """Select based on combined novelty and fitness score."""
    # Score all individuals
    scored = []
    max_fitness = max(ind.fitness.value for ind in population) or 1.0
    max_novelty = 1.0  # Will normalize

    novelty_scores = []
    for ind in population:
        novelty = self.archive.compute_novelty(ind.behavior)
        novelty_scores.append(novelty)

    max_novelty = max(novelty_scores) or 1.0

    for ind, novelty in zip(population, novelty_scores):
        norm_fitness = ind.fitness.value / max_fitness
        norm_novelty = novelty / max_novelty
        combined = (
            self.fitness_weight * norm_fitness + self.novelty_weight * norm_novelty
        )
        scored.append((ind, combined))

    # Sort by combined score
    scored.sort(key=lambda x: x[1], reverse=True)

    # Update archive
    selected = [ind for ind, _ in scored[:n]]
    for ind in selected:
        self.archive.add(ind.behavior)

    return selected

NoveltyArchive

Bases: Generic[G]

Archive for novelty search.

Tracks explored behaviors to compute novelty scores.

Source code in src/rotalabs_redqueen/core/selection.py 
 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
@dataclass
class NoveltyArchive(Generic[G]):
    """Archive for novelty search.

    Tracks explored behaviors to compute novelty scores.
    """

    behaviors: list[BehaviorDescriptor] = field(default_factory=list)
    novelty_threshold: float = 0.1
    max_size: int = 1000
    k_nearest: int = 15

    def add(self, behavior: BehaviorDescriptor) -> None:
        """Add a behavior to the archive.

        Only adds if sufficiently novel.

        Args:
            behavior: Behavior descriptor to potentially add
        """
        if len(self.behaviors) == 0:
            self.behaviors.append(behavior)
            return

        novelty = self.compute_novelty(behavior)
        if novelty > self.novelty_threshold:
            self.behaviors.append(behavior)
            # Trim if too large
            if len(self.behaviors) > self.max_size:
                self.behaviors = self.behaviors[-self.max_size:]

    def compute_novelty(self, behavior: BehaviorDescriptor) -> float:
        """Compute novelty score for a behavior.

        Novelty is the average distance to k-nearest neighbors.

        Args:
            behavior: Behavior to score

        Returns:
            Novelty score (higher = more novel)
        """
        if len(self.behaviors) == 0:
            return float("inf")

        # Compute distances to all archived behaviors
        distances = sorted([behavior.distance(b) for b in self.behaviors])

        # Average of k-nearest
        k = min(self.k_nearest, len(distances))
        return sum(distances[:k]) / k

add(behavior: BehaviorDescriptor) -> None

Add a behavior to the archive.

Only adds if sufficiently novel.

Parameters:

Name Type Description Default
behavior BehaviorDescriptor

Behavior descriptor to potentially add

 required
Source code in src/rotalabs_redqueen/core/selection.py 
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
def add(self, behavior: BehaviorDescriptor) -> None:
    """Add a behavior to the archive.

    Only adds if sufficiently novel.

    Args:
        behavior: Behavior descriptor to potentially add
    """
    if len(self.behaviors) == 0:
        self.behaviors.append(behavior)
        return

    novelty = self.compute_novelty(behavior)
    if novelty > self.novelty_threshold:
        self.behaviors.append(behavior)
        # Trim if too large
        if len(self.behaviors) > self.max_size:
            self.behaviors = self.behaviors[-self.max_size:]

compute_novelty(behavior: BehaviorDescriptor) -> float

Compute novelty score for a behavior.

Novelty is the average distance to k-nearest neighbors.

Parameters:

Name Type Description Default
behavior BehaviorDescriptor

Behavior to score

 required

Returns:

Type Description
float

Novelty score (higher = more novel)
Source code in src/rotalabs_redqueen/core/selection.py 
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
def compute_novelty(self, behavior: BehaviorDescriptor) -> float:
    """Compute novelty score for a behavior.

    Novelty is the average distance to k-nearest neighbors.

    Args:
        behavior: Behavior to score

    Returns:
        Novelty score (higher = more novel)
    """
    if len(self.behaviors) == 0:
        return float("inf")

    # Compute distances to all archived behaviors
    distances = sorted([behavior.distance(b) for b in self.behaviors])

    # Average of k-nearest
    k = min(self.k_nearest, len(distances))
    return sum(distances[:k]) / k