Skip to content

README.md

Latest commit

 

History

History
202 lines (155 loc) · 7.48 KB

README.md

File metadata and controls

202 lines (155 loc) · 7.48 KB

Function Minimization Example

This example demonstrates how OpenEvolve can discover sophisticated optimization algorithms starting from a simple implementation.

Problem Description

The task is to minimize a complex non-convex function with multiple local minima:

f(x, y) = sin(x) * cos(y) + sin(x*y) + (x^2 + y^2)/20

The global minimum is approximately at (-1.704, 0.678) with a value of -1.519.

Getting Started

To run this example:

cd examples/function_minimization
python ../../openevolve-run.py initial_program.py evaluator.py --config config.yaml

Algorithm Evolution

Initial Algorithm (Random Search)

The initial implementation was a simple random search that had no memory between iterations:

def search_algorithm(iterations=1000, bounds=(-5, 5)):
    """
    A simple random search algorithm that often gets stuck in local minima.
    
    Args:
        iterations: Number of iterations to run
        bounds: Bounds for the search space (min, max)
        
    Returns:
        Tuple of (best_x, best_y, best_value)
    """
    # Initialize with a random point
    best_x = np.random.uniform(bounds[0], bounds[1])
    best_y = np.random.uniform(bounds[0], bounds[1])
    best_value = evaluate_function(best_x, best_y)
    
    for _ in range(iterations):
        # Simple random search
        x = np.random.uniform(bounds[0], bounds[1])
        y = np.random.uniform(bounds[0], bounds[1])
        value = evaluate_function(x, y)
        
        if value < best_value:
            best_value = value
            best_x, best_y = x, y
    
    return best_x, best_y, best_value

Evolved Algorithm (Simulated Annealing)

After running OpenEvolve, it discovered a simulated annealing algorithm with a completely different approach:

def search_algorithm(bounds=(-5, 5), iterations=2000, initial_temperature=100, cooling_rate=0.97, step_size_factor=0.2, step_size_increase_threshold=20):
    """
    Simulated Annealing algorithm for function minimization.
    
    Args:
        bounds: Bounds for the search space (min, max)
        iterations: Number of iterations to run
        initial_temperature: Initial temperature for the simulated annealing process
        cooling_rate: Cooling rate for the simulated annealing process
        step_size_factor: Factor to scale the initial step size by the range
        step_size_increase_threshold: Number of iterations without improvement before increasing step size

    Returns:
        Tuple of (best_x, best_y, best_value)
    """
    # Initialize
    best_x = np.random.uniform(bounds[0], bounds[1])
    best_y = np.random.uniform(bounds[0], bounds[1])
    best_value = evaluate_function(best_x, best_y)

    current_x, current_y = best_x, best_y
    current_value = best_value
    temperature = initial_temperature
    step_size = (bounds[1] - bounds[0]) * step_size_factor  # Initial step size
    min_temperature = 1e-6 # Avoid premature convergence
    no_improvement_count = 0 # Counter for tracking stagnation

    for i in range(iterations):
        # Adaptive step size and temperature control
        if i > iterations * 0.75:  # Reduce step size towards the end
            step_size *= 0.5
        if no_improvement_count > step_size_increase_threshold: # Increase step size if stuck
            step_size *= 1.1
            no_improvement_count = 0 # Reset the counter

        step_size = min(step_size, (bounds[1] - bounds[0]) * 0.5) # Limit step size

        new_x = current_x + np.random.uniform(-step_size, step_size)
        new_y = current_y + np.random.uniform(-step_size, step_size)

        # Keep the new points within the bounds
        new_x = max(bounds[0], min(new_x, bounds[1]))
        new_y = max(bounds[0], min(new_y, bounds[1]))

        new_value = evaluate_function(new_x, new_y)

        if new_value < current_value:
            # Accept the move if it's better
            current_x, current_y = new_x, new_y
            current_value = new_value
            no_improvement_count = 0  # Reset counter

            if new_value < best_value:
                # Update the best found solution
                best_x, best_y = new_x, new_y
                best_value = new_value
        else:
            # Accept with a certain probability (Simulated Annealing)
            probability = np.exp((current_value - new_value) / temperature)
            if np.random.rand() < probability:
                current_x, current_y = new_x, new_y
                current_value = new_value
                no_improvement_count = 0  # Reset counter
            else:
                no_improvement_count += 1 # Increment counter if not improving

        temperature = max(temperature * cooling_rate, min_temperature) #Cool down

    return best_x, best_y, best_value

Key Improvements

Through evolutionary iterations, OpenEvolve discovered several key algorithmic concepts:

  1. Exploration via Temperature: Simulated annealing uses a temperature parameter to allow uphill moves early in the search, helping escape local minima that would trap simpler methods.

    probability = np.exp((current_value - new_value) / temperature)

  2. Adaptive Step Size: The step size is adjusted dynamically—shrinking as the search converges and expanding if progress stalls—leading to better coverage and faster convergence.

    if i > iterations * 0.75:  # Reduce step size towards the end
    step_size *= 0.5
if no_improvement_count > step_size_increase_threshold: # Increase step size if stuck
    step_size *= 1.1
    no_improvement_count = 0 # Reset the counter

  3. Bounded Moves: The algorithm ensures all candidate solutions remain within the feasible domain, avoiding wasted evaluations.

    # Keep the new points within the bounds
new_x = max(bounds[0], min(new_x, bounds[1]))
new_y = max(bounds[0], min(new_y, bounds[1]))

  4. Stagnation Handling: By counting iterations without improvement, the algorithm responds by boosting exploration when progress stalls.

    if no_improvement_count > step_size_increase_threshold: # Increase step size if stuck
    step_size *= 1.1
    no_improvement_count = 0 # Reset the counter

Results

The evolved algorithm shows substantial improvement in finding better solutions:

Metric Value
Value Score 0.990
Distance Score 0.921
Standard Deviation Score 0.900
Speed Score 0.466
Reliability Score 1.000
Overall Score 0.984
Combined Score 0.922

The simulated annealing algorithm:

  • Achieves higher quality solutions (closer to the global minimum)
  • Has perfect reliability (100% success rate in completing runs)
  • Maintains a good balance between performance and reliability

How It Works

This example demonstrates key features of OpenEvolve:

  • Code Evolution: Only the code inside the evolve blocks is modified
  • Complete Algorithm Redesign: The system transformed a random search into a completely different algorithm
  • Automatic Discovery: The system discovered simulated annealing without being explicitly programmed with knowledge of optimization algorithms
  • Function Renaming: The system even recognized that the algorithm should have a more descriptive name

Next Steps

Try modifying the config.yaml file to:

  • Increase the number of iterations
  • Change the LLM model configuration
  • Adjust the evaluator settings to prioritize different metrics
  • Try a different objective function by modifying evaluate_function()