Discovering General Methods (DGM)

# Standard DGM solution interface
def solve(problem_instance: ProblemInstance) -> Solution:
    """
    A general-purpose algorithm that takes a problem instance
    and returns a solution.

    The 'generality' of this function is measured by how well
    it performs across diverse problem instances.
    """
    # Algorithm implementation here
    ...
    return solution

TRADITIONAL EVOLUTION              LLM-GUIDED EVOLUTION (DGM)
====================              =========================

Parent Program                    Parent Program(s)
     |                                  |
     v                                  v
Random Mutation                   LLM Mutation Operator
(bit flip, swap,                  (semantic understanding,
 insert, delete)                   algorithmic reasoning,
     |                             cross-pollination)
     v                                  |
Child Program                          v
(often broken,                    Child Program
 usually small delta)             (syntactically valid,
                                   potentially novel algorithm)

# DGM mutation prompt template
MUTATION_PROMPT = """
You are an expert algorithm designer. You are given one or more
parent algorithms that solve a class of problems. Your task is to
create an improved or novel variant.

## Parent Algorithm(s):
{parent_code_blocks}

## Performance of Parents:
{parent_fitness_scores}

## Problem Description:
{problem_description}

## Evaluation Criteria:
The algorithm will be evaluated on DIVERSE problem instances.
It must generalize well, not just work on specific cases.

## Mutation Instructions:
{mutation_type_instruction}

Generate ONLY the Python function. The function must be self-contained
and follow this signature:
def solve(problem_instance) -> solution:
"""

# Conceptual reproduction setup
# 1. Define problem and fitness function
from dgm import EvolutionarySearch, BinPackingProblem

problem = BinPackingProblem(
    train_distributions=["uniform", "normal", "bimodal"],
    test_distributions=["heavy_tail", "sparse"],
    instances_per_dist=50
)

# 2. Configure evolutionary search
search = EvolutionarySearch(
    llm_model="gpt-4o",
    population_size=50,
    n_generations=100,
    mutation_types=["refine", "crossover", "radical"],
    diversity_weight=0.2,
    generality_weight=0.8
)

# 3. Run evolution
results = search.run(problem)
best_general_algorithm = results.best_by_generality()

def estimate_cost(n_generations, mutations_per_gen,
                   avg_input_tokens=2000, avg_output_tokens=500,
                   model="gpt-4o"):
    """Estimate total API cost for a DGM run."""
    pricing = {
        "gpt-4o": {"input": 2.50 / 1e6, "output": 10.00 / 1e6},
        "gpt-4-turbo": {"input": 10.00 / 1e6, "output": 30.00 / 1e6},
        "claude-3-5-sonnet": {"input": 3.00 / 1e6, "output": 15.00 / 1e6},
    }
    p = pricing[model]
    total_calls = n_generations * mutations_per_gen
    cost = total_calls * (avg_input_tokens * p["input"] +
                          avg_output_tokens * p["output"])
    return cost

# Example: Medium run with GPT-4o
cost = estimate_cost(100, 50, model="gpt-4o")
# ~$87.50 for mutations alone, plus evaluation overhead

+==============================================================================+
|                         DGM SYSTEM ARCHITECTURE                              |
+==============================================================================+
|                                                                              |
|  +-----------------------+        +------------------------+                 |
|  |   PROBLEM DEFINITION  |        |   POPULATION STORE     |                 |
|  |                       |        |                        |                 |
|  | - Problem class       |        | - Candidate programs   |                 |
|  | - Instance generators |        | - Fitness scores       |                 |
|  | - Fitness function    |        | - Diversity metrics    |                 |
|  | - Evaluation suite    |        | - Genealogy/lineage    |                 |
|  +-----------+-----------+        +----------+-------------+                 |
|              |                               |                               |
|              v                               v                               |
|  +-----------------------------------------------------------+              |
|  |              EVOLUTIONARY SEARCH ENGINE                    |              |
|  |                                                           |              |
|  |  +--------------+  +----------------+  +---------------+  |              |
|  |  | Parent       |  | LLM Mutation   |  | Fitness       |  |              |
|  |  | Selection    |->| Operator       |->| Evaluation    |  |              |
|  |  | Module       |  | Module         |  | Module        |  |              |
|  |  +--------------+  +----------------+  +---------------+  |              |
|  |         ^                  |                   |          |              |
|  |         |                  v                   v          |              |
|  |  +--------------+  +----------------+  +---------------+  |              |
|  |  | Population   |  | LLM API        |  | Sandboxed     |  |              |
|  |  | Management   |<-| (GPT-4, Claude,|  | Code Executor |  |              |
|  |  | & Diversity  |  |  Gemini, etc.) |  | (Docker/subprocess)|            |
|  |  +--------------+  +----------------+  +---------------+  |              |
|  +-----------------------------------------------------------+              |
|              |                                                               |
|              v                                                               |
|  +-----------------------------------------------------------+              |
|  |              OUTPUT / ANALYSIS                             |              |
|  |  - Best general algorithm                                 |              |
|  |  - Pareto front (generality vs. specialization)           |              |
|  |  - Evolution history and genealogy                        |              |
|  |  - Diversity analysis                                     |              |
|  +-----------------------------------------------------------+              |
+==============================================================================+

Initialize Population (seed programs or LLM-generated)
                |
                v
        +-----------------+
        |  GENERATION g   |<-----------------------------------------+
        +-----------------+                                           |
                |                                                     |
    +-----------+-----------+                                         |
    |                       |                                         |
    v                       v                                         |
+--------+           +----------+                                     |
| SELECT |           | SELECT   |                                     |
| Parent |           | Parents  |                                     |
| (single|           | (pair for|                                     |
|  mut.) |           | crossovr)|                                     |
+---+----+           +----+-----+                                     |
    |                      |                                          |
    v                      v                                          |
+---+----------------------+-----+                                    |
|   LLM MUTATION OPERATOR        |                                    |
|                                |                                    |
|  Choose mutation type:         |                                    |
|  - Refinement (p=0.4)         |                                    |
|  - Crossover  (p=0.25)        |                                    |
|  - Radical    (p=0.15)        |                                    |
|  - Simplify   (p=0.1)         |                                    |
|  - Generalize (p=0.1)         |                                    |
+---------------+----------------+                                    |
                |                                                     |
                v                                                     |
    +------------------------+                                        |
    | VALIDATE & COMPILE     |--- Invalid ---> Discard               |
    +------------------------+                                        |
                |                                                     |
                v (valid)                                              |
    +------------------------+                                        |
    | EVALUATE FITNESS       |                                        |
    |                        |                                        |
    | For each distribution: |                                        |
    |   For each instance:   |                                        |
    |     Run solve(instance)|                                        |
    |     Score result       |                                        |
    +------------------------+                                        |
                |                                                     |
                v                                                     |
    +------------------------+                                        |
    | COMPUTE GENERALITY     |                                        |
    | & DIVERSITY SCORES     |                                        |
    +------------------------+                                        |
                |                                                     |
                v                                                     |
    +------------------------+                                        |
    | UPDATE POPULATION      |                                        |
    | (survival selection,   |--------> g < max_gen? ----Yes----------+
    |  archive management)   |
    +------------------------+
                |
                v (g == max_gen)
    +------------------------+
    | RETURN BEST GENERAL    |
    | ALGORITHM + ARCHIVE    |
    +------------------------+

+----------------------------------+
| SANDBOX (Docker / subprocess)    |
|                                  |
| - Resource limits (CPU, memory)  |
| - Timeout enforcement (e.g. 30s) |
| - No network access              |
| - No filesystem access           |
| - Restricted imports              |
| - Output capture (stdout/stderr) |
+----------------------------------+

class MutationOperator:
    """LLM-based mutation operator for code evolution."""

    MUTATION_TYPES = {
        "refine": {
            "weight": 0.40,
            "n_parents": 1,
            "instruction": (
                "Improve this algorithm. Fix bugs, optimize performance, "
                "or enhance its handling of edge cases. Make small, "
                "targeted improvements."
            )
        },
        "crossover": {
            "weight": 0.25,
            "n_parents": 2,
            "instruction": (
                "You are given two algorithms that solve the same problem. "
                "Create a new algorithm that combines the best ideas from "
                "both. The result should be better than either parent."
            )
        },
        "radical": {
            "weight": 0.15,
            "n_parents": 1,
            "instruction": (
                "Completely redesign this algorithm using a fundamentally "
                "different approach. Think outside the box. The new "
                "algorithm should use a different strategy entirely."
            )
        },
        "simplify": {
            "weight": 0.10,
            "n_parents": 1,
            "instruction": (
                "Simplify this algorithm. Remove unnecessary complexity "
                "while preserving or improving performance."
            )
        },
        "generalize": {
            "weight": 0.10,
            "n_parents": 1,
            "instruction": (
                "Make this algorithm more general. It should handle "
                "a wider variety of input distributions and edge cases."
            )
        }
    }

    def mutate(self, parents, problem_desc, mutation_type=None):
        """Apply LLM-based mutation to produce a child program."""
        if mutation_type is None:
            mutation_type = self._sample_mutation_type()

        config = self.MUTATION_TYPES[mutation_type]
        selected_parents = parents[:config["n_parents"]]

        prompt = self._build_prompt(
            selected_parents, problem_desc, config["instruction"]
        )

        response = self.llm_client.generate(
            prompt=prompt,
            temperature=0.8,  # Higher temp for diversity
            max_tokens=2048
        )

        child_code = self._extract_function(response)
        return child_code

    def _sample_mutation_type(self):
        """Sample mutation type according to weights."""
        types = list(self.MUTATION_TYPES.keys())
        weights = [self.MUTATION_TYPES[t]["weight"] for t in types]
        return random.choices(types, weights=weights, k=1)[0]

class ParentSelector:
    """Multi-objective parent selection."""

    def __init__(self, alpha=0.7, beta=0.3, tournament_size=5):
        self.alpha = alpha   # fitness weight
        self.beta = beta     # diversity weight
        self.tournament_size = tournament_size

    def select(self, population, n_parents=1):
        """Select parents using fitness-diversity tournament."""
        selected = []
        for _ in range(n_parents):
            # Tournament selection
            candidates = random.sample(population, self.tournament_size)

            # Score each candidate
            scores = []
            for c in candidates:
                fitness_rank = c.generality_score  # [0, 1]
                diversity = self._compute_diversity(c, population)
                combined = (fitness_rank ** self.alpha) * (diversity ** self.beta)
                scores.append(combined)

            # Select best in tournament
            best_idx = max(range(len(candidates)), key=lambda i: scores[i])
            selected.append(candidates[best_idx])

        return selected

    def _compute_diversity(self, individual, population):
        """Compute diversity contribution of an individual."""
        # Average code distance to all other individuals
        distances = [
            self._code_distance(individual.code, other.code)
            for other in population if other != individual
        ]
        return sum(distances) / len(distances) if distances else 1.0

    def _code_distance(self, code_a, code_b):
        """Normalized edit distance between code strings."""
        from difflib import SequenceMatcher
        ratio = SequenceMatcher(None, code_a, code_b).ratio()
        return 1.0 - ratio  # distance = 1 - similarity

class PopulationManager:
    """Manage the evolving population of candidate algorithms."""

    def __init__(self, max_size=50, elite_fraction=0.2,
                 diversity_threshold=0.1):
        self.max_size = max_size
        self.elite_fraction = elite_fraction
        self.diversity_threshold = diversity_threshold
        self.population = []
        self.archive = []  # Hall of fame

    def update(self, children):
        """Add children and trim population."""
        # Add valid children
        for child in children:
            if self._is_sufficiently_novel(child):
                self.population.append(child)

        # Sort by generality score
        self.population.sort(
            key=lambda x: x.generality_score, reverse=True
        )

        # Preserve elites
        n_elite = int(self.max_size * self.elite_fraction)
        elites = self.population[:n_elite]

        # Fill remaining slots with diversity-aware selection
        remaining = self.population[n_elite:]
        diverse_fill = self._diversity_fill(
            remaining, self.max_size - n_elite
        )

        self.population = elites + diverse_fill

        # Update archive with best-ever individuals
        self._update_archive()

    def _is_sufficiently_novel(self, candidate):
        """Check if candidate is sufficiently different from population."""
        for existing in self.population:
            similarity = SequenceMatcher(
                None, candidate.code, existing.code
            ).ratio()
            if similarity > (1.0 - self.diversity_threshold):
                return False  # Too similar to existing
        return True

    def _diversity_fill(self, candidates, n_slots):
        """Select diverse individuals to fill remaining slots."""
        selected = []
        for _ in range(min(n_slots, len(candidates))):
            # Greedily select most diverse candidate
            best_div, best_idx = -1, 0
            for i, c in enumerate(candidates):
                div = min(
                    [self._code_dist(c, s) for s in selected]
                    or [1.0]
                )
                if div > best_div:
                    best_div, best_idx = div, i
            selected.append(candidates.pop(best_idx))
        return selected

class LLMOrchestrator:
    """Orchestrate multiple LLMs for different mutation types."""

    def __init__(self):
        self.model_configs = {
            "high_quality": {
                "model": "gpt-4o",
                "temperature": 0.7,
                "use_for": ["crossover", "radical"]
            },
            "cost_effective": {
                "model": "deepseek-coder",
                "temperature": 0.8,
                "use_for": ["refine", "simplify"]
            },
            "diverse": {
                "model": "claude-3-5-sonnet",
                "temperature": 0.9,
                "use_for": ["generalize"]
            }
        }

    def select_model(self, mutation_type):
        """Select the best model for a given mutation type."""
        for config in self.model_configs.values():
            if mutation_type in config["use_for"]:
                return config["model"], config["temperature"]
        return "gpt-4o", 0.7  # default

class AdaptiveMutationScheduler:
    """Dynamically adjust mutation type probabilities."""

    def __init__(self):
        self.base_weights = {
            "refine": 0.4, "crossover": 0.25,
            "radical": 0.15, "simplify": 0.1,
            "generalize": 0.1
        }
        self.stagnation_counter = 0

    def get_weights(self, pop_diversity, fitness_improving):
        """Adapt mutation weights based on search state."""
        weights = dict(self.base_weights)

        # Low diversity -> more radical mutations
        if pop_diversity < 0.3:
            weights["radical"] *= 2.0
            weights["generalize"] *= 1.5

        # Fitness stagnating -> more crossover
        if not fitness_improving:
            self.stagnation_counter += 1
            if self.stagnation_counter > 5:
                weights["crossover"] *= 2.0
                weights["radical"] *= 1.5
        else:
            self.stagnation_counter = 0

        # Normalize
        total = sum(weights.values())
        return {k: v / total for k, v in weights.items()}

class GeneralityFitness:
    """Evaluate fitness with emphasis on generality."""

    def __init__(self, distributions, instances_per_dist=50,
                 alpha=0.6, beta=0.2, gamma=0.2):
        self.distributions = distributions
        self.instances_per_dist = instances_per_dist
        self.alpha = alpha  # generality weight
        self.beta = beta    # best-case weight
        self.gamma = gamma  # robustness weight

    def evaluate(self, candidate_code, timeout=30):
        """Evaluate a candidate algorithm on all distributions."""
        per_dist_scores = {}

        for dist_name, dist in self.distributions.items():
            instances = dist.generate(self.instances_per_dist)
            scores = []

            for instance in instances:
                try:
                    result = sandbox_execute(
                        candidate_code, instance, timeout=timeout
                    )
                    score = self._score_result(result, instance)
                    scores.append(score)
                except (TimeoutError, RuntimeError):
                    scores.append(0.0)

            per_dist_scores[dist_name] = np.mean(scores)

        # Compute composite fitness
        all_scores = list(per_dist_scores.values())
        generality = np.mean(all_scores)
        best_case = np.max(all_scores)
        robustness = 1.0 - (np.std(all_scores) /
                     (np.mean(all_scores) + 1e-8))

        fitness = (self.alpha * generality +
                   self.beta * best_case +
                   self.gamma * robustness)

        return {
            "fitness": fitness,
            "generality": generality,
            "best_case": best_case,
            "robustness": robustness,
            "per_distribution": per_dist_scores
        }

def build_mutation_prompt(parent, mutation_type, problem_desc, failures=None):
    """Build a context-rich mutation prompt."""
    prompt = f"""You are an expert algorithm designer.

## Problem
{problem_desc}

## Current Algorithm (Parent)
```python
{parent.code}

def solve(problem_instance):
    ...
```"""
    return prompt

class CostController:
    """Control API and compute costs across the search."""

    def __init__(self, total_budget_usd=200.0,
                 per_generation_budget=5.0):
        self.total_budget = total_budget_usd
        self.per_gen_budget = per_generation_budget
        self.spent = 0.0
        self.gen_spent = 0.0

    def can_mutate(self):
        return (self.spent < self.total_budget and
                self.gen_spent < self.per_gen_budget)

    def log_cost(self, cost):
        self.spent += cost
        self.gen_spent += cost

    def new_generation(self):
        self.gen_spent = 0.0

    def adaptive_eval_depth(self, candidate_fitness_estimate):
        """More instances for promising candidates."""
        if candidate_fitness_estimate > 0.8:
            return 100  # full evaluation
        elif candidate_fitness_estimate > 0.5:
            return 30   # moderate evaluation
        else:
            return 10   # quick screening

class MetaLearner:
    """Track and adapt search hyperparameters."""

    def __init__(self):
        self.mutation_success_rates = {
            "refine": [], "crossover": [],
            "radical": [], "simplify": [],
            "generalize": []
        }

    def record_outcome(self, mutation_type, parent_fitness, child_fitness):
        improved = child_fitness > parent_fitness
        self.mutation_success_rates[mutation_type].append(improved)

    def get_adapted_weights(self, window=50):
        """Get mutation weights adapted by recent success rates."""
        weights = {}
        for mt, outcomes in self.mutation_success_rates.items():
            recent = outcomes[-window:]
            if recent:
                # Success rate + small baseline to never fully disable
                weights[mt] = sum(recent) / len(recent) + 0.05
            else:
                weights[mt] = 0.2  # default
        # Normalize
        total = sum(weights.values())
        return {k: v / total for k, v in weights.items()}

import numpy as np

def track_convergence(evolution_history):
    """Analyze convergence of the evolutionary search."""
    generations = []
    best_fitness = []
    mean_fitness = []
    diversity = []

    for gen, population in enumerate(evolution_history):
        fitnesses = [ind.fitness for ind in population]
        generations.append(gen)
        best_fitness.append(max(fitnesses))
        mean_fitness.append(np.mean(fitnesses))

        # Pairwise diversity
        codes = [ind.code for ind in population]
        pair_dists = []
        for i in range(len(codes)):
            for j in range(i + 1, len(codes)):
                pair_dists.append(code_distance(codes[i], codes[j]))
        diversity.append(np.mean(pair_dists) if pair_dists else 0)

    # Compute convergence rate (slope of best fitness)
    from numpy.polynomial import polynomial as P
    coeffs = np.polyfit(generations[-20:], best_fitness[-20:], 1)
    convergence_rate = coeffs[0]

    return {
        "generations": generations,
        "best_fitness": best_fitness,
        "mean_fitness": mean_fitness,
        "diversity": diversity,
        "convergence_rate": convergence_rate,
        "converged": abs(convergence_rate) < 1e-4
    }

def compute_pareto_front(population):
    """Compute the Pareto front of generality vs. specialization."""
    # Each individual has (generality, best_case) scores
    points = [(ind.generality_score, ind.best_case_score, ind)
              for ind in population]

    # Sort by generality descending
    points.sort(key=lambda x: -x[0])

    pareto = []
    max_special = -1

    for gen, spec, ind in points:
        if spec > max_special:
            pareto.append(ind)
            max_special = spec

    return pareto

class EvaluationCache:
    """Cache fitness evaluations to avoid redundant computation."""

    def __init__(self, max_cache_size=10000):
        self.cache = {}
        self.max_size = max_cache_size

    def get_or_evaluate(self, code, evaluator):
        code_hash = hashlib.sha256(code.encode()).hexdigest()
        if code_hash in self.cache:
            return self.cache[code_hash]

        result = evaluator.evaluate(code)
        self.cache[code_hash] = result

        # Evict oldest entries if cache is full
        if len(self.cache) > self.max_size:
            oldest_key = next(iter(self.cache))
            del self.cache[oldest_key]

        return result

class TransferLearning:
    """Transfer evolved algorithms across problem domains."""

    def extract_primitives(self, elite_population):
        """Extract reusable algorithmic primitives from elites."""
        primitives = []
        for individual in elite_population:
            # Parse AST to find reusable sub-functions
            tree = ast.parse(individual.code)
            for node in ast.walk(tree):
                if isinstance(node, ast.FunctionDef):
                    if node.name != "solve":  # helper functions
                        primitives.append({
                            "name": node.name,
                            "code": ast.unparse(node),
                            "source_fitness": individual.fitness
                        })
        return primitives

    def seed_new_problem(self, primitives, new_problem):
        """Create seed population for new problem using primitives."""
        seeds = []
        for prim in primitives:
            # Use LLM to adapt primitive to new problem
            prompt = f"""Adapt this algorithmic primitive for a new problem.

Primitive:
```python
{prim['code']}