OpenEvolve Native

Overview

OpenEvolve Native is a faithful SkyDiscover port of the OpenEvolve algorithm, implementing MAP-Elites (a quality-diversity algorithm) with an island-based population model. It maintains a feature map that preserves diverse solutions across multiple behavioral dimensions.

MAP-Elites

Maintains archive of best programs in each region of feature space

Island Populations

Multiple independent populations with periodic migration

Quality-Diversity

Optimizes both fitness and behavioral diversity

Adaptive Sampling

Balances exploration, exploitation, and random search

Key Concepts

MAP-Elites Archive

MAP-Elites discretizes the behavior space into a grid and maintains the best solution in each cell:

Feature Space Grid (2D example: complexity × diversity)

   Diversity →
C  ┌─────┬─────┬─────┬─────┐
o  │ A   │     │ C   │     │  Each cell holds the best
m  │0.85 │     │0.78 │     │  program with that feature
p  ├─────┼─────┼─────┼─────┤  combination
l  │     │ B   │     │ D   │
e  │     │0.92 │     │0.81 │  Numbers = fitness scores
x  ├─────┼─────┼─────┼─────┤
i  │ E   │     │     │     │  Empty = no solution found
t  │0.73 │     │     │     │  for that behavior yet
y  └─────┴─────┴─────┴─────┘

This preserves diverse solutions instead of just the single best.

Feature Dimensions

OpenEvolve Native supports both built-in and custom feature dimensions: Built-in features:

complexity: Length of solution code
diversity: Average distance from reference set
score: Fitness value itself

Custom features: Any metric returned by your evaluator can be used as a feature dimension.

Island Architecture

Multiple independent populations (islands) evolve in parallel:

Each island has its own MAP-Elites grid
Islands evolve independently most of the time
Periodic migration exchanges top solutions between islands
Prevents premature convergence to single approach

Configuration

Basic Usage

skydiscover-run initial_program.py evaluator.py \
  --search openevolve_native \
  --iterations 200

Configuration File

search:
  type: openevolve_native
  database:
    # Island configuration
    num_islands: 5
    population_size: 40
    
    # MAP-Elites archive
    archive_size: 100
    feature_dimensions: ["complexity", "diversity"]
    feature_bins: 10  # 10x10 grid = 100 cells
    
    # Sampling strategy
    exploration_ratio: 0.2   # Random from island
    exploitation_ratio: 0.7  # Elite from archive
    # remainder (0.1) is random from entire population
    
    # Migration
    migration_interval: 10   # Migrate every 10 generations
    migration_rate: 0.1      # Migrate top 10% of each island
    
    # Diversity tracking
    diversity_reference_size: 20

Configuration Options

num_islands

int

default:"5"

Number of independent island populations

population_size

int

default:"40"

Maximum total programs across all islands

archive_size

int

default:"100"

Size of elite archive (best programs)

feature_dimensions

list

default:"['complexity', 'diversity']"

List of feature dimensions for MAP-Elites grid. Can be:

Built-in: "complexity", "diversity", "score"
Custom: Any metric name from your evaluator

Example with custom features:

feature_dimensions: ["accuracy", "latency"]

feature_bins

int | dict

default:"10"

Number of bins per feature dimension.Single value (same for all dimensions):

feature_bins: 10  # 10x10 grid for 2 features

Per-dimension (different resolution):

feature_bins:
  complexity: 20
  diversity: 5

exploration_ratio

float

default:"0.2"

Fraction of iterations to sample random parent from island (exploration)

exploitation_ratio

float

default:"0.7"

Fraction of iterations to sample elite parent from archive (exploitation)

migration_interval

int

default:"10"

Number of generations between island migrations

migration_rate

float

default:"0.1"

Fraction of island population to migrate (top programs)

elite_selection_ratio

float

default:"0.1"

Fraction of context programs to sample from island elite

diversity_reference_size

int

default:"20"

Number of programs in reference set for diversity calculation

How It Works

Sampling Strategy

On each iteration, OpenEvolve selects a parent using a probabilistic strategy:

rand = random()

if rand < exploration_ratio:
    # Exploration: random program from current island
    parent = random_choice(island_programs)
    
elif rand < exploration_ratio + exploitation_ratio:
    # Exploitation: elite program from archive
    parent = sample_from_archive(prefer_current_island=True)
    
else:
    # Global random: any program from any island
    parent = random_choice(all_programs)

This balances:

Exploration (0.2): Try diverse approaches
Exploitation (0.7): Refine known good solutions
Global search (0.1): Avoid island isolation

MAP-Elites Insertion

When a new program is generated:

Calculate features: Determine feature coordinates (e.g., complexity=5, diversity=3)
Find cell: Locate corresponding grid cell
Compare: Is new program better than current cell occupant?
Update: If yes, replace cell occupant

def add(program):
    coords = calculate_feature_coords(program)  # e.g., [5, 3]
    cell_key = "5-3"
    
    if cell_key not in feature_map or is_better(program, feature_map[cell_key]):
        feature_map[cell_key] = program.id
        if cell_key in feature_map:  # Replace old occupant
            remove_from_island(feature_map[cell_key])

Migration Process

Every migration_interval generations:

Select migrants: Top migration_rate fraction from each island
Ring topology: Island i sends to islands i+1 and i-1
Copy programs: Migrants are copied (not moved)
Prevent duplicates: Skip if target island already has identical solution

When to Use OpenEvolve Native

Best For

Problems with multiple complementary solutions
Need for behavioral diversity (not just fitness)
Multi-objective optimization with trade-offs
Long runs (150+ iterations) where quality-diversity pays off
Problems with custom feature dimensions

Avoid When

Single optimal solution exists
Short runs (< 50 iterations) - not enough time for MAP-Elites to fill
No meaningful behavioral dimensions
Need for maximum simplicity

Example: Algorithm Design

Custom Feature Dimensions

Optimize sorting algorithms with custom features:

# evaluator.py
def evaluate(program_path):
    import importlib.util
    spec = importlib.util.spec_from_file_location("solution", program_path)
    module = importlib.util.module_from_spec(spec)
    spec.loader.exec_module(module)
    
    # Test on different input types
    random_time = benchmark(module.sort, random_data(1000))
    sorted_time = benchmark(module.sort, sorted_data(1000))
    reverse_time = benchmark(module.sort, reverse_sorted_data(1000))
    
    # Custom feature dimensions
    return {
        "combined_score": 1.0 / random_time,  # Fitness
        "sorted_advantage": sorted_time / random_time,  # Feature 1
        "reverse_advantage": reverse_time / random_time,  # Feature 2
    }

# config.yaml
search:
  type: openevolve_native
  database:
    num_islands: 5
    feature_dimensions: ["sorted_advantage", "reverse_advantage"]
    feature_bins: 10
    archive_size: 100

Result: Discovers diverse sorting algorithms optimized for different input patterns.

Monitoring OpenEvolve Native

Island Status

for i in range(database.num_islands):
    island_programs = database.islands[i]
    print(f"Island {i}: {len(island_programs)} programs")
    
    if database.island_best_programs[i]:
        best = database.programs[database.island_best_programs[i]]
        print(f"  Best score: {best.metrics['combined_score']:.4f}")

MAP-Elites Coverage

# How many cells are occupied?
for i, feature_map in enumerate(database.island_feature_maps):
    total_cells = database.feature_bins ** len(database.feature_dimensions)
    coverage = len(feature_map) / total_cells
    print(f"Island {i} coverage: {coverage:.1%} ({len(feature_map)}/{total_cells} cells)")

Archive Quality

archive_programs = [database.programs[pid] for pid in database.archive 
                    if pid in database.programs]
archive_scores = [p.metrics['combined_score'] for p in archive_programs]

print(f"Archive size: {len(archive_programs)}")
print(f"Archive quality: {sum(archive_scores) / len(archive_scores):.4f} avg")

Feature Space Visualization

Visualize the MAP-Elites grid (2D example):

import numpy as np
import matplotlib.pyplot as plt

# Extract grid data
grid = np.zeros((database.feature_bins, database.feature_bins))
for key, pid in database.island_feature_maps[0].items():
    i, j = map(int, key.split('-'))
    prog = database.programs[pid]
    grid[i, j] = prog.metrics['combined_score']

# Plot
plt.imshow(grid, origin='lower', cmap='viridis')
plt.colorbar(label='Fitness')
plt.xlabel(database.feature_dimensions[0])
plt.ylabel(database.feature_dimensions[1])
plt.title('MAP-Elites Feature Grid')
plt.show()

Advanced Usage

Custom Feature Bins per Dimension

search:
  type: openevolve_native
  database:
    feature_dimensions: ["accuracy", "latency", "memory"]
    feature_bins:
      accuracy: 20     # Fine-grained
      latency: 10      # Medium
      memory: 5        # Coarse

Total cells = 20 × 10 × 5 = 1,000

Asymmetric Migration

Customize migration topology:

from skydiscover.search.openevolve_native import OpenEvolveNativeDatabase

class CustomMigrationDatabase(OpenEvolveNativeDatabase):
    def _migrate_programs(self):
        # Custom topology: star (all islands → island 0 → all islands)
        hub = 0
        
        # Collect migrants to hub
        for i in range(1, self.num_islands):
            # ... migration logic
        
        # Distribute from hub
        # ... distribution logic

Comparison with Other Algorithms

Algorithm	Diversity Mechanism	Archive	Best For
OpenEvolve Native	MAP-Elites grid	Yes	Quality-diversity
AdaEvolve	Island isolation	Per-island	Adaptive search
Beam Search	Beam pruning	No	Discrete choices
Top-K	None	No	Simple refinement

Tips for Best Results

Choose Meaningful Features

Feature dimensions should capture behavioral differences that matter for your problem. Don’t just use complexity and diversity by default.

Balance Feature Bins

Too few bins (< 5): Insufficient diversity
Too many bins (> 20): Sparse coverage, slow fill
Sweet spot: 8-12 bins per dimension

Tune Exploration/Exploitation

Adjust based on problem:

Unknown landscape: Higher exploration (0.3-0.4)
Refinement needed: Higher exploitation (0.7-0.8)

Monitor Coverage

Track MAP-Elites coverage over time. If coverage plateaus early, features may be too correlated.

AdaEvolve - Island-based with adaptive intensity
GEPA Native - Pareto frontier instead of MAP-Elites
EvoX - Can evolve the OpenEvolve strategy itself

Python API

CLI Reference

Configuration

Search Algorithms

Overview

MAP-Elites

Island Populations

Quality-Diversity

Adaptive Sampling

Key Concepts

MAP-Elites Archive

Feature Dimensions

Island Architecture

Configuration

Basic Usage

Configuration File

Configuration Options

How It Works

Sampling Strategy

MAP-Elites Insertion

Migration Process

When to Use OpenEvolve Native

Example: Algorithm Design

Custom Feature Dimensions

Monitoring OpenEvolve Native

Island Status

MAP-Elites Coverage

Archive Quality

Feature Space Visualization

Advanced Usage

Custom Feature Bins per Dimension

Asymmetric Migration

Comparison with Other Algorithms

Tips for Best Results

Build docs developers (and LLMs) love

Python API

CLI Reference

Configuration

Search Algorithms

Documentation Index

​Overview

MAP-Elites

Island Populations

Quality-Diversity

Adaptive Sampling

​Key Concepts

​MAP-Elites Archive

​Feature Dimensions

​Island Architecture

​Configuration

​Basic Usage

​Configuration File

​Configuration Options

​How It Works

​Sampling Strategy

​MAP-Elites Insertion

​Migration Process

​When to Use OpenEvolve Native

​Example: Algorithm Design

​Custom Feature Dimensions

​Monitoring OpenEvolve Native

​Island Status

​MAP-Elites Coverage

​Archive Quality

​Feature Space Visualization

​Advanced Usage

​Custom Feature Bins per Dimension

​Asymmetric Migration

​Comparison with Other Algorithms

​Tips for Best Results

​Related Algorithms

Build docs developers (and LLMs) love

Overview

Key Concepts

MAP-Elites Archive

Feature Dimensions

Island Architecture

Configuration

Basic Usage

Configuration File

Configuration Options

How It Works

Sampling Strategy

MAP-Elites Insertion

Migration Process

When to Use OpenEvolve Native

Example: Algorithm Design

Custom Feature Dimensions

Monitoring OpenEvolve Native

Island Status

MAP-Elites Coverage

Archive Quality

Feature Space Visualization

Advanced Usage

Custom Feature Bins per Dimension

Asymmetric Migration

Comparison with Other Algorithms

Tips for Best Results

Related Algorithms