# RefineEvo

**Repository Path**: simon1239/RefineEvo

## Basic Information

- **Project Name**: RefineEvo
- **Description**: LLM-driven evolutionary algorithm framework
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-09-23
- **Last Updated**: 2026-09-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience

This repository contains the implementation for **RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience**, a Large Language Model (LLM) driven evolutionary algorithm framework for automatically generating and optimizing heuristic algorithms for combinatorial optimization problems. The paper was accepted to the **Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)**.

## Introduction

RefineEvo combines evolutionary computation, reinforcement learning concepts, and the generative capabilities of large language models to enable automatic design and iterative optimization of heuristic algorithms. Through an intelligent planner that dynamically decides exploration/exploitation strategies and a bidirectional experience pool that stores and retrieves both positive insights and negative pitfalls, RefineEvo can automatically discover high-quality combinatorial optimization solving algorithms.

## Key Features

- **Algorithm Design**: Leverage LLM to automatically generate heuristic algorithms for solving combinatorial optimization problems
- **Evolutionary Optimization**: Iteratively improve algorithm performance through genetic algorithm-style evolutionary process
- **Strategy Planning & Operator Improvement**: LLM-based planner dynamically decides exploration/exploitation strategies and automatically triggers improvement processes when operator performance stagnates
- **Bidirectional Experience Pool Mechanism**: Store positive insights and negative pitfalls, then retrieve relevant experiences when generating new algorithms
- **Multi-Problem Support**: Support for various classic combinatorial optimization problems including TSP, CVRP, Knapsack, Bin Packing, and more
- **Modular Design**: Clear hierarchical structure, easy to extend with new problems and evolutionary operators
- **Complete Traceability**: Record strategy decision history, operator improvement history, and population evolution process

## Quick Start

### Prerequisites

- Python 3.8+
- Valid OpenAI API Key (or compatible API service)

### Basic Usage

Run TSP constructive heuristic optimization:

```bash
python main.py --config cfg/config.yaml --pool_config cfg/pool.yaml
```

## Configuration

### Main Configuration File (cfg/config.yaml)

```yaml
problem: tsp_constructive  # Problem to solve
algorithm: refineevo        # Algorithm to use

n_pop: 30                  # Number of iterations
pop_size: 10               # Population size
init_pop_size: 30          # Number of candidates during initialization
timeout: 60                # Single evaluation timeout (seconds)
diversify_init_pop: true   # Whether to diversify initial population

exp:
  output_root: Results     # Output directory
  run_name: auto           # Run name
  summary_name: summary.json
```

### LLM Client Configuration (cfg/llm_client/)

Configure LLM models for different roles:

- `generator_llm.yaml` - Generator model configuration
- `reflector_llm.yaml` - Reflector model configuration
- `planner_llm.yaml` - Planner model configuration

## Supported Problems

RefineEvo currently supports the following combinatorial optimization problems:

### Traveling Salesman Problem (TSP)
- `tsp_constructive` - Constructive heuristics
- `tsp_aco` - Ant Colony Optimization
- `tsp_gls` - Guided Local Search

### Capacitated Vehicle Routing Problem (CVRP)
- `cvrp_aco` - Ant Colony Optimization

### Other Problems
- `bpp_offline_aco` / `bpp_online` - Bin Packing Problem
- `mkp_aco` - Multi-dimensional Knapsack Problem


## Evolution Process

The RefineEvo evolution process includes the following steps:

1. **Initialize Population**: Generate initial set of candidate algorithms
2. **Evaluate Fitness**: Evaluate each algorithm's performance on test instances
3. **Strategy Planning**: Planner decides exploration/exploitation strategy
4. **Select Parents**: Select excellent individuals based on selection strategy
5. **Apply Operators**: Execute innovation or improvement operators to generate new individuals
6. **Population Management**: Maintain population size and diversity
7. **Iterative Optimization**: Repeat steps 2-6 until reaching iteration limit
8. **Validate Best Solution**: Perform final validation on the best algorithm

## Evolution Operators

RefineEvo provides multiple evolution operators:

- **op1**: Experience-based innovation operator (retrieve from experience pool)
- **op2**: Crossover-based innovation operator
- **op3**: Mutation-based improvement operator
- **op4**: Reflection-based improvement operator (single individual)
- **op5**: Reflection-based improvement operator (multi-individual comparison)

## Selection Strategies

- `prob_rank` - Probability ranking selection
- `equal` - Equal probability selection
- `roulette_wheel` - Roulette wheel selection
- `tournament` - Tournament selection

## Advanced Features

### Operator Self-Improvement

When operator performance stagnation is detected, the system automatically triggers an improvement process:

1. Analyze operator's historical performance
2. Identify failure patterns and improvement opportunities
3. Use LLM to generate improved operator prompts
4. Update operator configuration and continue evolution

### Bidirectional Experience Pool Retrieval

The experience pool uses vector similarity to retrieve relevant positive and negative experiences:

1. Convert problem description to vector embeddings
2. Retrieve top-k most similar cases from experience pool
3. Inject relevant experiences into LLM prompts
4. Generate new algorithms inspired by experiences


## Output Results

Run results are saved in `Results/{problem_name}/{timestamp}/` directory:

- `best/` - Best algorithm code and validation results
- `summary.json` - Evolution process summary
- `planner_stats.json` - Planner decision statistics
- `operator_history.json` - Operator improvement history
- Population information and logs for each generation


## Dependencies

Core dependencies:

```
openai          # LLM API calls
numpy           # Numerical computation
scikit-learn    # Machine learning tools
joblib          # Parallel processing
pyyaml          # YAML configuration parsing
```