Operators
This section documents the available genetic algorithm operators in MetaZoo.
Evolutionary operators are essential components of genetic algorithms that mimic the process of natural selection and evolution.
They are used to generate new candidate solutions (offspring) from existing ones (parents) in order to explore the solution space and optimize a given objective function.
The main types of evolutionary operators include crossover, mutation, and selection.
Crossover
Crossover operators combine the genetic information of two parent solutions to produce one or more offspring.
This process is inspired by biological reproduction and is crucial for introducing diversity into the population.
Common crossover techniques include:
For parametric problems:
One-point crossover between two parents.
A crossover point is selected at random, and the segments after this point are swapped
between the two parents to create two children.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/crossover.py
7
8
9
10
11
12
13
14
15
16
17 | def onepoint(parent1, parent2):
"""
One-point crossover between two parents.
A crossover point is selected at random, and the segments after this point are swapped
between the two parents to create two children.
"""
point = np.random.randint(1, parent1.shape[0])
child1 = np.concatenate([parent1[:point], parent2[point:]])
child2 = np.concatenate([parent2[:point], parent1[point:]])
return child1, child2
|
Two-point crossover between two parents.
Two crossover points are selected at random, and the segments between these points are swapped
between the two parents to create two children.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/crossover.py
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | def two_point_crossover(parent1, parent2):
"""
Two-point crossover between two parents.
Two crossover points are selected at random, and the segments between these points are swapped
between the two parents to create two children.
"""
point1 = np.random.randint(1, parent1.shape[0])
point2 = np.random.randint(1, parent1.shape[0])
if point1 > point2:
point1, point2 = point2, point1
child1 = np.concatenate([parent1[:point1], parent2[point1:point2], parent1[point2:]])
child2 = np.concatenate([parent2[:point1], parent1[point1:point2], parent2[point2:]])
return child1, child2
|
K-point crossover between two parents.
K crossover points are selected at random, and the segments between these points are swapped
between the two parents to create two children.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/crossover.py
34
35
36
37
38
39
40
41
42
43
44
45
46 | def k_points_crossover(parent1, parent2, k=3):
"""
K-point crossover between two parents.
K crossover points are selected at random, and the segments between these points are swapped
between the two parents to create two children.
"""
points = np.random.choice(range(1, parent1.shape[0]), size=k, replace=False)
points.sort()
child1 = np.concatenate([parent1[:points[0]], parent2[points[0]:points[1]], parent1[points[1]:]])
child2 = np.concatenate([parent2[:points[0]], parent1[points[0]:points[1]], parent2[points[1]:]])
return child1, child2
|
For permutation-based representations:
Partially Mapped Crossover (PMX) for permutation encoding.
It consists of choosing a subsegment from one of the parents and crossing
them while preserving the order and position of as many genes as possible
from the other parent, maintaining consistency.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/crossover.py
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 | def PMX(parent1, parent2):
"""
Partially Mapped Crossover (PMX) for permutation encoding.
It consists of choosing a subsegment from one of the parents and crossing
them while preserving the order and position of as many genes as possible
from the other parent, maintaining consistency.
"""
size = len(parent1) # Length of the permutation
# Position mapping is used to keep track of the positions of elements in the parents
p1, p2 = np.zeros(size, dtype=int), np.zeros(size, dtype=int)
# Initialize the position of each index in the individuals
for i in range(size):
p1[parent1[i]] = i
p2[parent2[i]] = i
# Choose crossover points
cxpoint1 = np.random.randint(0, size) # First crossover point
cxpoint2 = np.random.randint(0, size - 1) # Second crossover point
if cxpoint2 >= cxpoint1:
cxpoint2 += 1
else: # Swap the two cx points
cxpoint1, cxpoint2 = cxpoint2, cxpoint1
# Apply crossover between cx points
for i in range(cxpoint1, cxpoint2):
# Keep track of the values to be swapped
temp1 = parent1[i]
temp2 = parent2[i]
# Swap the matched value
parent1[i], parent1[p1[temp2]] = temp2, temp1
parent2[i], parent2[p2[temp1]] = temp1, temp2
# Update the position of the swapped values
p1[temp1], p1[temp2] = p1[temp2], p1[temp1]
p2[temp1], p2[temp2] = p2[temp2], p2[temp1]
return parent1, parent2
|
Mutation
Mutation operators introduce random changes to individual solutions, helping to maintain genetic diversity within the population and preventing premature convergence to suboptimal solutions.
Common mutation techniques include:
For parametric problems:
Gaussian mutation for real-valued encoding.
Each gene in the individual has a certain probability of being mutated by adding Gaussian noise.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/mutation.py
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | def gaussian(individual, mutation_rate=0.01, mutation_strength=0.1):
"""
Gaussian mutation for real-valued encoding.
Each gene in the individual has a certain probability of being mutated by adding Gaussian noise.
"""
# Apply Gaussian noise to each gene with a certain probability
if np.random.rand() < mutation_rate:
# Gaussian Noise with mean 0 and standard deviation mutation_strength
noise = np.random.normal(0, mutation_strength, size=individual.shape)
# Create the mutated individual (Individual + Noise)
individual += noise
# Clip to keep within bounds [0, 1]
individual = np.clip(individual, 0, 1)
return individual
|
Bit-flip mutation for binary encoding.
Each bit in the individual has a certain probability of being flipped (0 -> 1 or 1 -> 0).
Source code in metazoo/src/metazoo/bio/evolutionary/operators/mutation.py
24
25
26
27
28
29
30
31
32
33
34
35 | def flip_bit(individual, mutation_rate=0.01):
"""
Bit-flip mutation for binary encoding.
Each bit in the individual has a certain probability of being flipped (0 -> 1 or 1 -> 0).
"""
# Flip each bit with a certain probability
if np.random.rand() < mutation_rate:
# Create a mask for the bits to flip
mask = np.random.rand(individual.shape[0]) < mutation_rate
# Flip the bits
individual[mask] = 1 - individual[mask]
return individual
|
For permutation-based representations:
Swap mutation for permutation encoding.
Two positions in the permutation are selected at random and their values are swapped.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/mutation.py
39
40
41
42
43
44
45
46
47
48
49 | def swap(individual, mutation_rate=0.01):
"""
Swap mutation for permutation encoding.
Two positions in the permutation are selected at random and their values are swapped.
"""
if np.random.rand() < mutation_rate:
# Swap two random positions in the permutation
idx1, idx2 = np.random.choice(range(individual.shape[0]), size=2, replace=False)
# Swap the elements at idx1 and idx2
individual[idx1], individual[idx2] = individual[idx2], individual[idx1]
return individual
|
Selection
Selection operators determine which individuals from the current population are chosen to contribute to the next generation.
This process is inspired by the concept of "survival of the fittest" in natural selection
Uniform Random Selection
Info: In uniform random selection, individuals are selected randomly from the population with equal probability,
regardless of their fitness values. This method does not consider the fitness of individuals and treats all individuals equally.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/selection.py
138
139
140
141
142
143
144
145
146 | def uniform(population: np.ndarray, fitness: np.ndarray) -> np.ndarray:
"""
Uniform Random Selection
Info: In uniform random selection, individuals are selected randomly from the population with equal probability,
regardless of their fitness values. This method does not consider the fitness of individuals and treats all individuals equally.
"""
selected_indices = np.random.choice(len(population), size=len(population), replace=True)
assert len(selected_indices) == len(population)
return selected_indices
|
Calculate expected values for a given fitness array.
The expected value for each individual is calculated as
expected_value = (fitness / average_fitness) * number_of_individuals
This function normalizes the fitness values to ensure that they sum up to the population size.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/selection.py
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | def expected_values(fitness: np.array) -> np.array:
"""
Calculate expected values for a given fitness array.
The expected value for each individual is calculated as:
expected_value = (fitness / average_fitness) * number_of_individuals
This function normalizes the fitness values to ensure that they sum up to the population size.
"""
average_fitness = np.sum(fitness)
number_of_individuals = len(fitness)
if np.isclose(average_fitness, 0):
# If the average fitness is close to zero, assign uniform expected values
return np.ones_like(fitness)
return fitness / average_fitness * number_of_individuals
|
Roulette Wheel Selection
Info: In the roulette wheel selection method, a.k.a fitness proportionate selection (FPS),
the probability for selecting an individual is directly proportionate to its fitness value.
Think of this as a roulette wheel where each individual has a slice of the wheel sized according to its fitness.
The wheel is spun, and the individual on which the wheel stops is selected.
This process is repeated until the desired number of individuals is selected.
shift: If True, shifts fitness values to be non-negative.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/selection.py
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | def roulette(population: np.ndarray, fitness: np.ndarray, shift: bool = True) -> np.ndarray:
"""
Roulette Wheel Selection
Info: In the roulette wheel selection method, a.k.a fitness proportionate selection (FPS),
the probability for selecting an individual is directly proportionate to its fitness value.
Think of this as a roulette wheel where each individual has a slice of the wheel sized according to its fitness.
The wheel is spun, and the individual on which the wheel stops is selected.
This process is repeated until the desired number of individuals is selected.
shift: If True, shifts fitness values to be non-negative.
"""
expected = expected_values(fitness) # This normalizes fitness values to sum to population size
if shift:
# Shift expected values to be non-negative
# Shift works by subtracting the minimum expected value from all expected values
# and adding a small constant (1e-6) to avoid zero probabilities
expected = expected - np.min(expected) + 1e-6
probabilities = expected / np.sum(expected)
selected_indices = np.random.choice(len(population), size=len(population), p=probabilities)
assert len(selected_indices) == len(population)
return selected_indices
|
Stochastic Universal Sampling (SUS)
Info: The Stochastic Universal Sampling (SUS) ensures a more uniform selection of individuals
based on their fitness values. It is an improvement over the traditional roulette wheel selection method.
Think of SUS as a roulette wheel where multiple equally spaced pointers are used to select individuals from the population.
This method helps to reduce the stochastic noise associated with single-pointer methods like roulette wheel selection.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/selection.py
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 | def stochastic_universal_sampling(population: np.ndarray, fitness: np.ndarray, shift: bool = True) -> np.ndarray:
"""
Stochastic Universal Sampling (SUS)
Info: The Stochastic Universal Sampling (SUS) ensures a more uniform selection of individuals
based on their fitness values. It is an improvement over the traditional roulette wheel selection method.
Think of SUS as a roulette wheel where multiple equally spaced pointers are used to select individuals from the population.
This method helps to reduce the stochastic noise associated with single-pointer methods like roulette wheel selection.
"""
expected = expected_values(fitness)
if shift:
expected = expected - np.min(expected) + 1e-6
total_fitness = np.sum(expected)
point_distance = total_fitness / len(population)
start_point = np.random.uniform(0, point_distance)
# Generate pointers for selection
# These pointers are equally spaced around the roulette wheel,
# in other words, they are spaced by point_distance and are evenly distributed.
pointers = [start_point + i * point_distance for i in range(len(population))]
selected_indices = []
cumulative_fitness = np.cumsum(expected)
for pointer in pointers:
for idx, cum_fit in enumerate(cumulative_fitness):
if cum_fit >= pointer:
selected_indices.append(idx)
break
assert len(selected_indices) == len(population)
return np.array(selected_indices)
|
Rank Selection
Info: The rank-based selection method is similar to the roulette wheel selection,
but instead of directly using the fitness values to calculate the probabilities
for selecting each individual, we use the fitness values to order the individuals and assign selection probabilities based on their positions.
The actual selection probabilities are then assigned based on the rank of each individual.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/selection.py
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93 | def rank(population: np.ndarray, fitness: np.ndarray) -> np.ndarray:
"""
Rank Selection
Info: The rank-based selection method is similar to the roulette wheel selection,
but instead of directly using the fitness values to calculate the probabilities
for selecting each individual, we use the fitness values to order the individuals and assign selection probabilities based on their positions.
The actual selection probabilities are then assigned based on the rank of each individual.
"""
ranks = np.argsort(np.argsort(fitness)) # Get ranks
# Convert ranks to probabilities
total_rank = np.sum(ranks) # Sum of ranks
probabilities = ranks / total_rank if total_rank > 0 else np.ones_like(ranks) / len(ranks) # Avoid division by zero
selected_indices = np.random.choice(len(population), size=len(population), p=probabilities) # Select individuals based on probabilities
assert len(selected_indices) == len(population)
return selected_indices
|
Tournament Selection
Info: In tournament selection, a subset of individuals is randomly chosen from the population,
and the individual with the highest fitness in this subset is selected.
This process is repeated until the desired number of individuals is selected.
K is the tournament size, which determines how many individuals are randomly chosen for each tournament.
Source code in metazoo/src/metazoo/bio/evolutionary/operators/selection.py
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136 | def tournament(population: np.ndarray, fitness: np.ndarray, K: int = 3, type: str = "standard", replace: bool = True) -> np.ndarray:
"""
Tournament Selection
Info: In tournament selection, a subset of individuals is randomly chosen from the population,
and the individual with the highest fitness in this subset is selected.
This process is repeated until the desired number of individuals is selected.
K is the tournament size, which determines how many individuals are randomly chosen for each tournament.
"""
if not replace and K > len(population):
raise ValueError(f"K={K} is larger than population size={len(population)}")
selected_indices = []
if type == "standard":
for _ in range(len(population)):
# Randomly select K individuals for the tournament
# IF replace is True, individuals can be selected multiple times
tournament_indices = np.random.choice(len(population), size=K, replace=replace)
# Select the individual with the highest fitness from the tournament
# Tie-breaking is handled by np.argmax which returns the first occurrence
best_idx = tournament_indices[np.argmax(fitness[tournament_indices])]
selected_indices.append(best_idx)
elif type == "proportional":
for _ in range(len(population)):
# Randomly select K individuals for the tournament
# IF replace is True, individuals can be selected multiple times
tournament_indices = np.random.choice(len(population), size=K, replace=replace)
# Select an individual based on fitness-proportionate probabilities
tournament_fitness = fitness[tournament_indices]
# Here, ties are handled by the probability distribution.
# If multiple individuals have the same fitness, they will have the same probability of being selected.
total = np.sum(tournament_fitness)
probabilities = tournament_fitness / total if not np.isnan(total) and not total == 0 else np.full_like(tournament_fitness, 1.0 / len(tournament_fitness)) # Avoid division by zero
selected_idx = np.random.choice(tournament_indices, p=probabilities)
selected_indices.append(selected_idx)
else:
raise ValueError("Invalid tournament type. Choose 'standard' or 'proportional'.")
assert len(selected_indices) == len(population)
return np.array(selected_indices)
|