### Install project dependencies

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/README.md

Use pip to install all necessary packages listed in the requirements file.

```bash
$ pip install -r requirements.txt
```

--------------------------------

### Execute the genetic algorithm

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/README.md

Run the main script to start the genetic algorithm process.

```bash
$ python ga.py
```

--------------------------------

### String Matching Output Example

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Displays the generation count and the found solution for string matching tasks. Indicates when a perfect match is achieved.

```text
generation 50
Attention is all you need (inf)  ← Solution found (fitness = infinity)
```

--------------------------------

### Example Execution of Fast GA

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/fast_ga.md

Demonstrates how to run the Fast GA from the command line and provides an overview of its typical convergence behavior. The output highlights the rapid initial progress and occasional breakthroughs characteristic of the power law mutation.

```bash
# Running with Python
python fast_ga.py
```

```text
# Output shows faster convergence than canonical GA:
# generation 1-40: most progress happens here due to many 1-2 position mutations
# generation 41-60: rare large mutations push final corrections
# generation ~62: solution typically found
```

--------------------------------

### Symbolic Regression Output Example

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Shows the generation progress and best Mean Squared Error (MSE) for symbolic regression. Highlights when an exact match is found and the discovered expression.

```text
generation 250 | best mse: 0.000123
generation 287 | best mse: 0.000001

exact match found at gen 287! stopping early.
global best mse: 0.000000
discovered expression: eml(x, eml(1, x))  ← Found correct formula
```

--------------------------------

### Example Output of Genetic Algorithm

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/ga.md

Illustrates the typical output progression of the genetic algorithm across generations, showing convergence.

```text
generation 1

Attention is !ll you need (inf)

generation 2

Attention is all you need (inf)
```

--------------------------------

### Fitness Function Examples

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Examples of fitness functions for string matching, symbolic regression, and clustering. The symbolic regression example uses a population of islands and calculates Mean Squared Error.

```python
# String matching
fitness = 1. / (genes - target).pow(2).sum(dim=-1)
```

```python
# Symbolic regression
def fitness_fn(pop_islands):
    y_pred = evaluate_population(pop_islands, tree_depth, x_vals)
    mse = (y_pred - y_target).pow(2).mean(dim=-1)
    return 1. / (mse + 1e-8)
```

```python
# Clustering
silhouette_score(clusters: Tensor, points: Tensor) -> Tensor
```

--------------------------------

### Sort by Fitness (Ascending)

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Sorts individuals by their fitness in descending order, placing the best at the start. Requires fitnesses to be calculated first.

```python
# Standard ascending sort (best at start)
fitnesses = 1. / mse                           # Inverse error
indices = fitnesses.sort(descending=True).indices
pool = pool[indices]
fitnesses = fitnesses[indices]
```

--------------------------------

### Generation Termination Codes

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/types.md

Provides examples of conditions used to terminate the genetic algorithm generation process. These include finding a perfect solution, a near-perfect solution, or convergence in clustering.

```python
# Implicit convergence detection
if (fitnesses == float('inf')).any():
    break                             # Solution found (matching)
```

```python
if best_mse < 1e-7:
    break                             # Near-perfect solution (symreg)
```

```python
if torch.allclose(centers, next_centers, atol=1e-6):
    break                             # Converged (kmeans)
```

--------------------------------

### Run Fast GA

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/overview.md

Execute the fast genetic algorithm implementation with power law mutation.

```bash
python fast_ga.py
```

--------------------------------

### Queen-Bee v1 GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Queen-Bee v1 (BEGA) Genetic Algorithm.

```python
bega.py                       # Queen-Bee v1 (126 lines)
```

--------------------------------

### Run Canonical GA

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/overview.md

Execute the canonical genetic algorithm implementation.

```bash
python ga.py
```

--------------------------------

### Fast GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Fast Genetic Algorithm.

```python
fast_ga.py                    # Fast GA (108 lines)
```

--------------------------------

### Initialize Population and Ages Tensors

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/symbolic_regression.md

Sets up the initial population of symbolic regression trees and their corresponding ages. Ensures internal nodes can be any token, while leaf nodes are restricted to constants or variables.

```python
islands = torch.randint(0, 3, (num_islands, pop_size, num_nodes), device = device)
islands[..., num_internal:] = islands[..., num_internal:].clamp(0, 1)

ages = torch.zeros((num_islands, pop_size), dtype=torch.long, device=device)
```

--------------------------------

### Clustering Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for K-Means clustering.

```python
kmeans.py                     # Clustering (177 lines)
```

--------------------------------

### N-Parent GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the N-Parent crossover Genetic Algorithm.

```python
ga_multi_crossover.py         # N-Parent (123 lines)
```

--------------------------------

### Symbolic Regression GA Configuration

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Command-line arguments for configuring the symbolic regression genetic algorithm. Includes parameters for target expression, tree depth, population size, and island/migration settings.

```bash
python ga_eml_symreg.py \
    --target="x - ln(x)"         # Target expression or None
    --depth=2                    # Auto-generate target; override if target set
    --tree_depth=5               # Tree depth for population
    --num_points=100             # X-values for evaluation
    --pop_size=1000              # Per island
    --num_islands=10
    --generations=500
    --power_law_beta=1.1         # Fast GA mutation
    --strong_mutation_rate=0.25  # Drone mutation (25%)
    --frac_fittest_survive=0.25  # Elite size (25%)
    --elite_frac=0.05            # Elite protection (5%)
    --migrate_every=250
    --frac_migrate=0.1
    --max_elite_age=5            # Generations before elite can mutate
    --seed=42
```

--------------------------------

### Fitness Uniform GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Fitness Uniform (FUSS) Genetic Algorithm.

```python
fuss.py                       # Fitness Uniform (115 lines)
```

--------------------------------

### Run K-means Comparison

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Executes a comparison script that evaluates the performance of k-means clustering against genetic algorithm approaches, including a hybrid GA+k-means method. The output provides silhouette scores for comparison.

```bash
python kmeans.py
# Output: Silhouette scores comparing k-means, GA, and GA+k-means hybrid
```

--------------------------------

### Run K-Means Comparison

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/overview.md

Execute the k-means clustering algorithm optimized with a genetic algorithm.

```bash
python kmeans.py
```

--------------------------------

### Queen-Bee v2 GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Queen-Bee v2 Genetic Algorithm.

```python
qbmb.py                       # Queen-Bee v2 (128 lines)
```

--------------------------------

### Canonical GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Canonical Genetic Algorithm.

```python
genetic-algorithm-pytorch/
├── ga.py                         # Canonical GA (92 lines)
```

--------------------------------

### Bee Colonies GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Bee Colonies Genetic Algorithm.

```python
bcga.py                       # Bee Colonies (149 lines)
```

--------------------------------

### Running Comparisons of Clustering Methods

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/kmeans_and_inbreed.md

Compares the performance of standard k-means, a pure genetic clustering algorithm, and a hybrid genetic algorithm with k-means refinement. The comparison is run over multiple trials on randomly generated datasets.

```python
import torch
from sklearn.datasets import make_blobs

# Assuming kmeans and genetic_clustering are defined elsewhere or imported
# For demonstration, let's assume they are available in the scope

def kmeans(points, num_clusters, initial_centers=None, max_iterations=10):
    # Placeholder for kmeans implementation
    if initial_centers is not None:
        centers = initial_centers
    else:
        centers = torch.randn(num_clusters, points.shape[1])
    
    for _ in range(max_iterations):
        distances = torch.cdist(points, centers)
        labels = distances.argmin(dim=-1)
        new_centers = torch.zeros_like(centers)
        counts = torch.zeros(num_clusters)
        for i in range(points.shape[0]):
            new_centers[labels[i]] += points[i]
            counts[labels[i]] += 1
        centers = new_centers / counts.unsqueeze(1).clamp(min=1e-6)
    return centers

def silhouette_score(centers, points):
    # Placeholder for silhouette_score implementation
    distances = torch.cdist(points, centers)
    labels = distances.argmin(dim=-1)
    
    # Simplified silhouette score calculation for demonstration
    score = torch.zeros(centers.shape[0])
    for k in range(centers.shape[0]):
        cluster_points = points[labels == k]
        if cluster_points.shape[0] > 1:
            other_centers = torch.cat([centers[:k], centers[k+1:]])
            if other_centers.shape[0] > 0:
                avg_dist_to_others = torch.cdist(centers[k].unsqueeze(0), other_centers).mean()
                avg_dist_within = torch.cdist(cluster_points, centers[k].unsqueeze(0)).mean()
                score[k] = avg_dist_to_others / avg_dist_within.clamp(min=1e-6)
            else:
                score[k] = 1.0 
        else:
            score[k] = 0.0 
    return score

@torch.inference_mode()
def genetic_clustering(
    points,
    num_clusters,
    pop_size = 250,
    num_generations = 100,
    frac_fittest_selected = 0.25,
    frac_elites = 0.1,
    mutation_strength = 0.1,
    kmeans_each_generation = False
):
    num_points, dim = points.shape
    keep_fittest = int(frac_fittest_selected * pop_size)

    num_elites = int(frac_elites * pop_size)
    has_elites = num_elites > 0

    pop_centers = torch.randn(pop_size, num_clusters, dim)

    for _ in range(num_generations):

        if kmeans_each_generation:
            pass # Placeholder for kmeans_each_generation logic

        fitness = silhouette_score(pop_centers, points)

        fitness, sel_indices = fitness.topk(keep_fittest, dim = -1)

        pop_centers = pop_centers[sel_indices]

        tourn_ids = torch.randn((pop_size - keep_fittest, keep_fittest)).argsort(dim = -1)

        competitor_fitness = fitness[tourn_ids]

        tourn_winner_indices = competitor_fitness.topk(2, dim = -1).indices

        parent1, parent2 = pop_centers[tourn_winner_indices].unbind(dim = 1)

        crossover_mix = torch.randn_like(parent1).sigmoid()

        child = parent1.lerp(parent2, crossover_mix)

        pop_centers = torch.cat((pop_centers, child))

        if has_elites:
            elites, pop_centers = pop_centers[:num_elites], pop_centers[num_elites:]

        pop_centers += torch.randn_like(pop_centers) * points.std() * mutation_strength

        if has_elites:
            pop_centers = torch.cat((elites, pop_centers))

    fitness = silhouette_score(pop_centers, points)

    best_index = fitness.argmax(dim = -1).item()

    return pop_centers[best_index]


num_trials = 10

avg_kmeans = 0.
avg_genetic = 0.
avg_genetic_kmeans = 0.

for _ in range(num_trials):

    points, _ = make_blobs(
        n_samples = 500,
        n_features = 16,
        centers = 10,
        cluster_std = 1.0
    )

    points = torch.from_numpy(points).float()

    clusters = kmeans(points, 6)
    kmeans_score = silhouette_score(clusters, points)

    clusters = genetic_clustering(points, 6)
    genetic_score = silhouette_score(clusters, points)

    clusters = genetic_clustering(points, 6, kmeans_each_generation = True)
    genetic_kmeans_score = silhouette_score(clusters, points)

    avg_kmeans += kmeans_score / num_trials
    avg_genetic += genetic_score / num_trials
    avg_genetic_kmeans += genetic_kmeans_score / num_trials

print(f'kmeans: {avg_kmeans:.4f}')
print(f'genetic clustering: {avg_genetic:.4f}')
print(f'genetic kmeans hybrid: {avg_genetic_kmeans:.4f}')

```

--------------------------------

### Island Model GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Island Model Genetic Algorithm.

```python
islands.py                    # Island Model (181 lines)
```

--------------------------------

### Project Module Dependency Map

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Illustrates the module dependencies within the project, showing base PyTorch modules and advanced modules like symbolic regression and k-means implementations.

```text
All modules:
├── torch                (base tensor operations)
├── einx                 (batch-aware indexing)
└── einops              (tensor rearrangement)

Advanced modules:
├── ga_eml_symreg.py
│   ├── fire             (CLI generation)
│   └── accelerate       (GPU/multi-device)
└── kmeans.py
    └── sklearn.datasets (test data generation)

No module imports from other modules in the project (all standalone).
```

--------------------------------

### Fast GA Configuration

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Configuration for a faster genetic algorithm, introducing a power law exponent for mutation length sampling. Favors smaller mutations with higher beta values.

```python
GOAL = 'Attention is all you need'
POP_SIZE = 100
FRAC_FITTEST_SURVIVE = 0.25
FRAC_TOURNAMENT = 0.25
POWER_LAW_BETA = 1.1           # Power law exponent (higher = favor small mutations)
```

--------------------------------

### Symbolic Regression GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Symbolic Regression Genetic Algorithm.

```python
ga_eml_symreg.py              # Symbolic Regression (338 lines)
```

--------------------------------

### Provide Default Value

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

Returns a value if it exists, otherwise returns a specified default. Useful for setting fallback configurations.

```python
default(v, d) -> Any               # v if exists, else d
```

--------------------------------

### K-means Clustering Output Comparison

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Compares the performance of standard k-means, genetic clustering, and a hybrid approach, indicating the best performing method.

```text
kmeans: 0.5234
genetic clustering: 0.5847
genetic kmeans hybrid: 0.6123  ← Best approach
```

--------------------------------

### einx.less() - Comparison for Mask Creation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Employ einx.less for creating boolean masks based on ranked data. This is useful for selecting elements below a certain rank or threshold, such as for mutation.

```python
# Create mutation mask from ranked random positions
ranks = torch.randn(100, 51).argsort(dim=-1)  # (100, 51) ranks
num_mutate = torch.tensor([5, 3, 8, ...])     # (100,) per-individual budgets
mutate_mask = less('i j, i -> i j', ranks, num_mutate)
# Result: (100, 51) bool - True where rank < threshold
```

--------------------------------

### Outbreeding GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Outbreeding Genetic Algorithm.

```python
inbreed.py                    # Outbreeding GA (142 lines)
```

--------------------------------

### Ring Topology Migration (PyTorch)

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Implements migration in a ring topology where individuals move from one island to the next in a circular fashion. Uses `torch.roll` for efficient rotation.

```python
# Extract migrants
migrants = islands[:, :num_migrants]
remaining = islands[:, num_migrants:]

# Ring rotation: island[i] -> island[(i+1) % n]
migrants = torch.roll(migrants, 1, dims=0)

# Reattach to receiving islands
islands = torch.cat((migrants, remaining), dim=1)
```

--------------------------------

### Standard K-means Algorithm Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/kmeans_and_inbreed.md

Implements the standard Lloyd's k-means algorithm for clustering data points. It handles initialization, point assignment, center updates, empty clusters, and convergence.

```python
@torch.inference_mode()
def kmeans(points, num_clusters, centers = None, max_iterations = float('inf')):
    num_points, dim = points.shape

    iterations = 0

    if not exists(centers):
        centers = torch.randn(num_clusters, dim)

    while iterations < max_iterations:
        # assign points to a center

        dist = torch.cdist(points, centers)

        center_ids = dist.argmin(dim = -1)
        expanded_center_ids = repeat(center_ids, '... n -> ... n d', d = dim)

        expanded_points = repeat(points, 'n d -> p n d', p = center_ids.shape[0]) if expanded_center_ids.ndim == 3 else points

        # average intra cluster distance

        next_centers = torch.zeros_like(centers).scatter_reduce_(-2, expanded_center_ids, expanded_points, 'mean')

        # account for empty clusters by not changing

        is_empty_cluster = einx.not_equal('c, ... n -> ... c n', torch.arange(num_clusters), center_ids).all(dim = -1)

        next_centers = einx.where('... c, ... c d, ... c d', is_empty_cluster, centers, next_centers)

        # stop if no changes between iterations

        if torch.allclose(centers, next_centers, atol = 1e-6):
            break

        centers.copy_(next_centers)

        iterations += 1

    return centers
```

--------------------------------

### Symbolic Regression Output Monitoring

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/symbolic_regression.md

This snippet shows the typical output format during the symbolic regression process, including target expression, depth, population details, and generation-wise MSE. It also indicates when an exact match is found and the final discovered expression.

```text
using device: cuda
target: x - ln(x - ln(x))
target depth: 3
tree depth: 5
population: 10 islands x 1000 individuals

generation 10 | best mse: 0.123456
generation 20 | best mse: 0.045678
...
generation 287 | best mse: 0.000001

exact match found at gen 287! stopping early.

--- training complete ---
global best mse: 0.000000
discovered expression: eml(x, eml(1, eml(x, 1)))

```

--------------------------------

### Selective Mutation GA Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

This file contains the implementation for the Selective Mutation Genetic Algorithm.

```python
ga_select_beneficial_changes.py # Selective Mutation (116 lines)
```

--------------------------------

### GA Function Signature with Optional Types

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/types.md

Illustrates the function signature for running the genetic algorithm, highlighting the use of optional type annotations like `str | None` and `int | None` for parameters that can be absent.

```python
def run_ga(
    target: str | None = None,
    depth: int | None = None,
    tree_depth: int | None = None,
    num_points = 100,
    pop_size = 1000,
    num_islands = 10,
    generations = 500,
    power_law_beta = 1.1,
    strong_mutation_rate = 0.25,
    frac_fittest_survive = 0.25,
    frac_tournament = 0.10,
    elite_frac = 0.05,
    migrate_every = 250,
    frac_migrate = 0.1,
    max_elite_age = 5,
    cpu = False,
    seed = 42
) -> None
```

--------------------------------

### Run Queen-Bee Evolution

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Executes the Queen-Bee evolution variant, which is generally faster, converging in 30-50 generations. This method incorporates strong mutation rates.

```bash
python bega.py
# Output: Convergence in ~30-50 generations (faster)
```

--------------------------------

### Uniform Fitness Sampling with PyTorch

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/selection_and_crossover_variants.md

Implements uniform fitness sampling for parent selection. This method normalizes fitness values and uses a cumulative distribution function (CDF) to select parents randomly across fitness levels, promoting population diversity. Requires PyTorch.

```python
sorted_fitness, sorted_gene_indices = fitnesses.sort(dim = -1)

sorted_fitness = sorted_fitness - sorted_fitness[0]
sorted_fitness_cdf = sorted_fitness.cumsum(dim = -1)
sorted_fitness_cdf = sorted_fitness_cdf / sorted_fitness_cdf[-1]

rand = torch.rand((2, num_children))
rand_parent_sorted_gene_ids = torch.searchsorted(sorted_fitness_cdf, rand) - 1
```

--------------------------------

### Initialize Queen State

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/queen_bee_ga.md

Initialize queen and queen_fitness to None. The queen is maintained separately from the population across generations.

```python
queen = queen_fitness = None  # Initially no queen
```

--------------------------------

### Run Symbolic Regression GA

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/symbolic_regression.md

Command-line interface for running the genetic algorithm for symbolic regression. Specify target expressions, tree depth, population size, and other GA parameters.

```bash
python ga_eml_symreg.py --target="x" --depth=2 --num_points=100 --seed=42
```

```bash
python ga_eml_symreg.py \
    --target="x - ln(x - ln(x))" \
    --tree_depth=5 \
    --pop_size=1000 \
    --num_islands=10 \
    --generations=500
```

--------------------------------

### Fitness-Uniform Selection

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/README.md

Implements fitness-uniform selection using cumulative distribution functions. Ensures selection probability is proportional to fitness.

```python
torch.searchsorted(sorted_fitness_cdf, torch.rand(...))
```

--------------------------------

### Tournament Selection

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Implements tournament selection by selecting contender IDs and then retrieving the corresponding parents based on their rankings.

```python
# Tournament
contender_ids = torch.randn((num_children, keep_fittest_len)).argsort(dim=-1)[..., :num_tournament_contenders]
parents = get_at('p [t] g, p w -> p w g', participants, top_indices)
```

--------------------------------

### einx.get_at() - Advanced Indexing

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Use einx.get_at for advanced indexing into tensors based on dimension specifications. It allows for flexible selection and rearrangement of data across specified dimensions.

```python
# Get top 2 winners from tournament
participants = torch.randn(75, 6, 51)  # (num_children, tournament_size, gene_length)
top2_indices = torch.randn(75, 2)      # (num_children, 2) - indices into tournament_size

parents = get_at('p [t] g, p w -> p w g', participants, top2_indices)
# Result: (75, 2, 51) - selected parent pairs
```

```python
# Gather from population
genes = pool[contender_ids]                    # Standard PyTorch indexing
genes = get_at('[p] g, c -> c g', pool, ids)  # einx notation
```

```python
# Gather parents by index
parents = get_at('p [t] g, p w -> p w g', participants, top_indices)
```

```python
# Gather from 3D island populations
genes = get_at('i [p] g, i c -> i c g', islands, contender_ids)
```

```python
# Get best per population in batch
best = get_at('[p1] d, p2 -> p2 d', pop, best_indices)
```

--------------------------------

### GPU/CPU Compatibility with Accelerate

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Ensures tensors are on the correct device (CPU or GPU) using the Accelerate library for seamless multi-device compatibility. Automatically selects the appropriate device.

```python
# Using accelerate for automatic device selection
from accelerate import Accelerator

accelerator = Accelerator(cpu=cpu)
device = accelerator.device

# Ensure tensors on same device
tensor = tensor.to(device)
tensor = torch.randn(..., device=device)
```

--------------------------------

### Exact Match Convergence Detection (Python)

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Detects convergence when any individual achieves an inverse error of infinity. Useful for problems where an exact solution is sought.

```python
if (fitnesses == float('inf')).any():
    break  # Exact match found (inverse error = infinity)
```

--------------------------------

### Island GA Configuration

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Configuration for the Island genetic algorithm, employing an island model with migration and island reset strategies. Sets the number of islands, population per island, and migration/reset intervals.

```python
ISLANDS = 5
POP_SIZE = 100                 # Per island
MIGRATE_EVERY = 50
FRAC_MIGRATE = 0.1
ISLAND_RESET_EVERY = 100       # Reset worst island every 100 gen
NUM_ISLANDS_RESET = 1
```

--------------------------------

### Queen Promotion Logic

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/queen_bee_ga.md

If a new individual is fitter than the current queen, it replaces the queen, and the old queen is returned to the population. This ensures the best individual is always tracked.

```python
if queen is not None and queen_fitness < fitnesses[0]:
    pool = torch.cat((pool, queen[None, :]), dim = 0)
    fitnesses = torch.cat((fitnesses, queen_fitness[None]), dim = 0)
    queen = queen_fitness = None
```

--------------------------------

### Vectorized Population Evaluation in PyTorch

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/symbolic_regression.md

Evaluates an entire population of symbolic regression trees in parallel using PyTorch. Processes trees bottom-up from leaves to root for efficient computation.

```python
def evaluate_population(islands, tree_depth, x_vals):
    device = islands.device

    node_values = where('i p g, , n -> i p g n', islands == 0, 1., x_vals)

    for d in reversed(range(tree_depth)):
        start_idx = 2 ** d - 1
        end_idx = 2 ** (d + 1) - 1

        parent_indices = torch.arange(start_idx, end_idx, device = device)
        left_indices = 2 * parent_indices + 1
        right_indices = 2 * parent_indices + 2

        left_vals = node_values[:, :, left_indices, :]
        right_vals = node_values[:, :, right_indices, :]

        eml_vals = eml(left_vals, right_vals)

        node_values[:, :, parent_indices, :] = where(
            'i p k, i p k n, i p k n -> i p k n',
            islands[:, :, parent_indices] == 2,
            eml_vals,
            node_values[:, :, parent_indices, :]
        )

    return node_values[:, :, 0, :]
```

--------------------------------

### Global Population Communication (PyTorch)

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Facilitates communication across a global population by flattening all individuals and performing a tournament selection from the combined pool. Useful for island model resets.

```python
# Flatten all remaining islands
all_individuals = rearrange(islands, 'i p g -> (i p) g')
all_fitnesses = rearrange(island_fitnesses, 'i f -> (i f)')

# Tournament from global pool
tournament_ids = torch.randn((num_reset, pop_size, pop_size)).argsort(dim=-1)[..., :tournament_size]
participants = get_at('[global_pop] g, i p t -> t i p g', all_individuals, tournament_ids)

# Select best globally
best_globally = participants[best_indices]  # From global tournament
```

--------------------------------

### Batching for Multiple Islands in Parallel

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Efficiently handles operations across multiple independent 'islands' in a parallel genetic algorithm. Supports indexing, gathering, and scattering data per island.

```python
# Index along island dimension
islands_arange = torch.arange(ISLANDS)[..., None]

# Gather per-island
selected = islands[islands_arange, indices]  # Batch gather

# Scatter per-island
islands[islands_arange, indices] = new_values
```

--------------------------------

### Stable Centers Convergence Detection (PyTorch)

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Checks for convergence in K-means clustering by comparing current cluster centers with newly computed ones. Stops if centers are within a specified absolute tolerance.

```python
if torch.allclose(centers, next_centers, atol=1e-6):
    break  # Centers converged within tolerance
```

--------------------------------

### Migration Strategy Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/bcga_and_islands.md

Implements a migration strategy every few generations to maintain diversity. It extracts individuals from the end of each colony, rotates them, and reattaches them to different colonies, facilitating information exchange.

```python
if not (generation % MIGRATE_EVERY) and num_bees_migrate > 0:
    colonies, migrant_colonies = colonies[:, :-num_bees_migrate], colonies[:, -num_bees_migrate:]
    migrant_colonies = torch.roll(migrant_colonies, 1, dims = 0)
    colonies = torch.cat((colonies, migrant_colonies), dim = 1)
```

--------------------------------

### Queen-Bee GA Configuration

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Configuration for the Queen-Bee genetic algorithm, which separates a 'queen' individual from the main population. Includes standard and strong mutation probabilities.

```python
POP_SIZE = 100
MUTATION_PROB = 0.04           # Standard mutation (4%)
STRONG_MUTATION_PROB = 0.25    # Strong mutation rate (25%)
STRONG_MUTATION_RATE = 0.1     # (BEGA) Fraction with strong mutation (10%)
NUM_TOURNAMENT_PARTICIPANTS = 25
```

--------------------------------

### String and Tensor Conversion

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Convert strings to tensors and vice versa for genetic algorithm operations. Also includes functions for decoding tree structures into string expressions.

```python
# String ↔ Tensor conversion
encode(s: str) -> Tensor              # "Hello" → tensor([72, 101, ...])
decode(t: Tensor) -> str              # tensor([72, 101, ...]) → "Hello"

# Tree ↔ Expression conversion (symreg only)
decode_tree(tree_array: list) -> str  # [1, 0, 2] → "eml(x, 1)"
evaluate_target_string(expr: str, x: Tensor) -> Tensor
```

--------------------------------

### Tournament Selection

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Implements the core tournament selection pattern for genetic algorithms. Gathers participants, selects the best k, and returns the winners.

```python
# Step 1: Create tournament participant indices
contender_ids = torch.randn((num_tournaments, tournament_size)).argsort(dim=-1)
# Step 2: Gather participants
participants = pool[contender_ids]            # (tournaments, tournament_size, genes)
tournaments = fitnesses[contender_ids]        # (tournaments, tournament_size)
# Step 3: Select best k
top_k = tournaments.topk(k, dim=-1, largest=True, sorted=False).indices
# Step 4: Gather winners
winners = get_at('t [f] g, t w -> t w g', participants, top_k)
```

--------------------------------

### Initialize BCGA Data Structures

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/bcga_and_islands.md

Initializes the data structures for the Bee Colony GA, including worker populations for each colony, individual queens, and their fitness scores. It also prepares a helper tensor for batch indexing.

```python
colonies = torch.randint(0, 255, (COLONIES, POP_SIZE - 1, gene_length))
colonies_arange = torch.arange(COLONIES)[..., None]

queens = torch.randint(0, 255, (COLONIES, gene_length))
queen_fitnesses = calc_fitness(queens, target_gene)

```

--------------------------------

### Canonical GA Configuration

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Standard configuration for the canonical genetic algorithm. Sets population size, mutation rate, and survival/tournament fractions.

```python
GOAL = 'Attention is all you need'
POP_SIZE = 100
MUTATION_RATE = 0.05           # Mutations per gene (5%)
FRAC_FITTEST_SURVIVE = 0.25    # Elite size (25 individuals)
FRAC_TOURNAMENT = 0.25         # Tournament size (6 individuals)
```

--------------------------------

### Safe Optional Handling with exists()

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/types.md

Demonstrates a common pattern for safely handling optional values using a custom `exists()` function, which checks for non-None values before use. This avoids runtime errors when a variable might be unassigned.

```python
def exists(v):
    return v is not None

if exists(queen):
    # Use queen safely
    print(f"Queen fitness: {queen_fitness.item():.3f}")
```

--------------------------------

### Elite with Age Tracking and Mutation Protection (PyTorch)

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Manages elites by tracking their age and protecting younger elites from mutation. Resets the age of an individual to zero upon mutation. This prevents promising young individuals from being prematurely altered.

```python
ages = torch.zeros((pop_size,), dtype=torch.long)

for gen in range(num_generations):
    # ... fitness evaluation ...
    
    ages += 1  # Age all individuals
    
    # ... selection and crossover ...
    
    # Protect young elites from mutation
    is_elite = torch.arange(pop_size) < num_elite
    is_too_old = ages >= max_elite_age
    protect_mask = is_elite & ~is_too_old
    
    # Apply mutation with protection
    mutate_mask = mutate_mask & ~protect_mask
    pool = torch.where(mutate_mask, pool + noise, pool)
    
    # Reset age on mutation
    has_mutated = mutate_mask.any(dim=-1)
    ages = torch.where(has_mutated, 0, ages)
```

--------------------------------

### Inverse Transform Sampling for Power Law Distribution

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/common_patterns.md

Generates samples from a power law distribution using the inverse transform sampling method. Requires pre-calculated and normalized CDF.

```python
# For power law distribution P(k) ~ k^(-beta)
power_law_cdf = torch.linspace(1, max_val, max_val).pow(-beta).cumsum()
power_law_cdf = power_law_cdf / power_law_cdf[-1]  # Normalize to [0,1]

# Sample using inverse transform
uniform_samples = torch.rand(num_samples)
sampled_values = torch.searchsorted(power_law_cdf, uniform_samples)
```

--------------------------------

### Generate Mutation Mask with Einx

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/fast_ga.md

Generates a mutation mask for each individual using `einx.less()`. It ranks gene positions and selects positions where the rank is less than the individual's mutation budget.

```python
mutate_mask = less('i j, i', torch.randn(pool.shape).argsort(dim = -1), num_mutate)
```

--------------------------------

### EML Operator Implementation

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/symbolic_regression.md

Implements the Elementary Mathematical Logarithmic (EML) operator using PyTorch. This operator can represent various elementary functions through composition and safe logarithmic computation.

```python
def eml(x, y, ln_min = 1e-20):
    return torch.exp(x) - torch.log(y.clamp(min = ln_min))
```

--------------------------------

### Tournament Selection for Drones

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/queen_bee_ga.md

Selects parent drones for mating by randomly sampling contenders from the population and choosing the fittest among them. This process is repeated for each drone to be generated.

```python
contender_ids = torch.randn((POP_SIZE - 1, POP_SIZE - 1)).argsort(dim = -1)[..., :NUM_TOURNAMENT_PARTICIPANTS]
participants, tournaments = pool[contender_ids], fitnesses[contender_ids]
top_winner = tournaments.topk(1, dim = -1, largest = True, sorted = False).indices
parents = get_at('p [t] g, p 1 -> p g', participants, top_winner)
```

--------------------------------

### Power-Law Mutation (Fast GA)

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Implements power-law mutation using a pre-calculated cumulative distribution function (CDF) to determine the number of mutations.

```python
# Power-law mutation (Fast GA)
num_mutate = torch.searchsorted(power_law_cdf, torch.rand(pop_size))
mutate_mask = less('i j, i', torch.randn(pool.shape).argsort(dim=-1), num_mutate)
```

--------------------------------

### Run Symbolic Regression with Fire CLI

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/overview.md

Execute symbolic regression using the EML operator via the Fire command-line interface. Specify the target expression and number of data points.

```bash
python ga_eml_symreg.py --target="x" --num_points=100
```

--------------------------------

### Bee Colony GA Configuration

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Configuration for the Bee Colony genetic algorithm, designed for large-scale optimization. Specifies colony count, population size per colony, and migration parameters.

```python
COLONIES = 10
POP_SIZE = 250                 # Per colony
MUTATION_PROB = 0.05
STRONG_MUTATION_PROB = 0.15
NUM_TOURNAMENT_PARTICIPANTS = 25
MIGRATE_EVERY = 5              # Migration interval
FRAC_BEES_MIGRANTS = 0.1       # Migrants per migration (10%)
```

--------------------------------

### Queen Initialization

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/queen_bee_ga.md

Designates the top-performing individual from the current population as the queen for the generation. This is done when no queen has been selected yet.

```python
if queen is None:
    queen, pool = pool[0], pool[1:]
    queen_fitness, fitnesses = fitnesses[0], fitnesses[1:]
```

--------------------------------

### Drone Selection via Tournament

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/bcga_and_islands.md

Selects parent drones for reproduction using a tournament selection method. For each colony, it randomly picks a subset of contenders, identifies the top winner based on fitness, and extracts their genes to form the parents.

```python
colonies_arange_ = colonies_arange[..., None]
contender_ids = torch.randn((COLONIES, POP_SIZE - 1, POP_SIZE - 1)).argsort(dim = -1)[..., :NUM_TOURNAMENT_PARTICIPANTS]
participants, tournaments = colonies[colonies_arange_, contender_ids], colony_fitnesses[colonies_arange_, contender_ids]
top_winner = tournaments.topk(1, dim = -1, largest = True, sorted = False).indices
parents = einx.get_at('... [t] g, ... 1 -> ... g', participants, top_winner)
```

--------------------------------

### Run Symbolic Regression

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/quick_reference.md

Executes the genetic algorithm for symbolic regression, targeting a specific mathematical expression. The `--target` and `--generations` arguments control the expression to find and the search duration. The output includes the discovered expression as a decoded tree.

```bash
python ga_eml_symreg.py --target="x - ln(x)" --generations=500
# Output: Discovers expression, prints decoded tree
```

--------------------------------

### Standard K-means Algorithm

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/kmeans_and_inbreed.md

Implements the standard Lloyd's k-means algorithm for clustering data points. It iteratively refines cluster centers based on point assignments and recalculates means until convergence or maximum iterations are reached.

```APIDOC
## kmeans(points, num_clusters, centers = None, max_iterations = float('inf'))

### Description
Standard Lloyd's k-means algorithm.

1. **Initialize:** Random cluster centers (or provided)
2. **Assignment:** Assign points to nearest cluster
3. **Update:** Recompute centers as mean of assigned points
4. **Empty cluster handling:** Keep previous center if no points assigned
5. **Convergence:** Stop if centers don't change (within tolerance)

### Parameters
#### Path Parameters
- `points` (Tensor) - Required - Data points shape `(num_points, dim)`
- `num_clusters` (int) - Required - Number of clusters k
- `centers` (Tensor) - Optional - Initial centers; default random
- `max_iterations` (float) - Optional - Maximum iterations before stopping

### Returns
Tensor of shape `(num_clusters, dim)` - final cluster centers
```

--------------------------------

### Initialize Parent IDs - Python

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/kmeans_and_inbreed.md

Initializes a tensor to store parent IDs for each individual in the population. It is used to track lineage and prevent inbreeding.

```python
parent_ids = torch.full((POP_SIZE, 2), -1, dtype = torch.long)
```

--------------------------------

### Provide Default Value

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/overview.md

Utility function to return a value if it exists, otherwise return a specified default.

```python
default(v, d) -> Any              # Return v if exists, else d
```

--------------------------------

### Tournament Selection

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/types.md

Implements tournament selection where a subset of individuals (`participants`) compete, and the fittest are chosen. `top_indices` specifies the indices of the winners within each tournament.

```python
# Tournament selection
contender_ids: Tensor                 # (num_children, tournament_size)
participants: Tensor                  # (num_children, tournament_size, gene_length)
tournaments: Tensor                   # (num_children, tournament_size) - fitness scores
top_indices: Tensor                   # (num_children, k) - k best per tournament
parents = participants[..., top_indices]
```

--------------------------------

### Calculate Colony Fitness and Sort

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/bcga_and_islands.md

Calculates the fitness of each colony and sorts them in descending order. It then reorders the colonies and their fitnesses based on the sorted indices, utilizing batch indexing.

```python
colony_fitnesses = calc_fitness(colonies, target_gene)

indices = colony_fitnesses.sort(descending = True).indices
colonies, colony_fitnesses = colonies[colonies_arange, indices], colony_fitnesses[colonies_arange, indices]
```

--------------------------------

### Apply Mutation and Clamp Values

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/fast_ga.md

Applies mutations to the population by adding noise to selected positions and then clamping the values to the valid ASCII range (0-255).

```python
noise = torch.randint(0, 2, pool.shape) * 2 - 1
pool = torch.where(mutate_mask, pool + noise, pool)
pool.clamp_(0, 255)
```

--------------------------------

### Tournament Selection with Inbreeding Avoidance - Python

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/kmeans_and_inbreed.md

Implements a two-stage tournament selection process to avoid inbreeding. The first stage selects a parent, and the second stage penalizes siblings to favor distantly related individuals.

```python
first_winner = tournaments.topk(1, dim = -1, largest = True, sorted = False).indices
first_winner = rearrange('p 1 -> p', first_winner)

first_parent_ids = get_at('p [t] i, p -> p i', participants_parent_ids, first_winner)

# second tournament, masking out any siblings to first winners

contender_scores = torch.randn((num_children, num_repro_and_mutate))
self_mask = rearrange('i -> i 1', first_winner) == torch.arange(num_repro_and_mutate)
contender_scores = torch.where(self_mask, 1e6, contender_scores)

sibling_mask = (rearrange('p i -> p 1 i 1', first_parent_ids) == rearrange('c j -> 1 c 1 j', parent_ids))
valid_parent_mask = (rearrange('p i -> p 1 i 1', first_parent_ids) != -1) & (rearrange('c j -> 1 c 1 j', parent_ids) != -1)
num_shared_parents = (sibling_mask & valid_parent_mask).float().sum(dim = (-1, -2))
contender_scores += num_shared_parents * 1e3

second_contender_ids = contender_scores.argsort(dim = -1)[..., :num_tournament_contenders]
```

--------------------------------

### Standard One-Point Crossover with PyTorch

Source: https://github.com/lucidrains/genetic-algorithm-pytorch/blob/main/_autodocs/selection_and_crossover_variants.md

Performs standard one-point crossover on selected parents. It concatenates the first half of parent1's genes with the second half of parent2's genes to create the child. Assumes parents are retrieved using a helper function `get_at`.

```python
parents = get_at('[p] d, ... -> ... d', pool, parent_ids)

parent1, parent2 = parents
children = torch.cat((parent1[:, :gene_midpoint], parent2[:, gene_midpoint:]), dim = -1)
```