Introduction
Automatic Heuristic Design (AHD) has emerged as a transformative approach for solving complex combinatorial optimization problems. While recent Large Language Model (LLM)-based methods have shown promise, they predominantly rely on fixed evolutionary operators and struggle to effectively accumulate and reuse historical search experience. To address this, researchers have introduced RefineEvo, a novel multi-agent evolutionary framework that transforms AHD from a static trial-and-error process into a planning-guided, experience-driven system. By dynamically managing search strategies and learning from both successes and failures, RefineEvo creates a self-improving system that is highly effective and token-efficient.
The Challenge of Automatic Heuristic Design
Combinatorial Optimization (CO) encompasses notoriously difficult tasks, such as finding the shortest delivery route or packing a warehouse efficiently. Traditionally, experts spend years hand-crafting heuristics—rules of thumb—to solve these problems.
Recently, LLMs have been leveraged to automate this design process. However, current LLM-based AHD methods suffer from two major limitations:
- Static Search: They utilize a fixed set of evolutionary operators (e.g., "mutate this code") regardless of whether the search is stagnating or making rapid progress.
- Short-Term Memory: Existing systems typically retain only the "winners" and discard the "losers." This approach ignores the valuable lessons hidden in failed attempts and fails to capture the contextual reasons behind why a specific change succeeded or failed.
The RefineEvo Framework
RefineEvo treats heuristic design as a closed-loop, experience-driven process managed by specialized agents:
- The Planner: Acting as the system's "brain," the Planner monitors the state of the search, evaluating metrics like algorithm diversity and score stagnation. Based on these observations, it decides whether to Explore (test novel ideas) or Exploit (refine current top performers). Crucially, if an operator loses effectiveness, the Planner triggers Operator Refinement, rewriting the operator's prompt to adapt to the increasing complexity of the search.
- The Reflector: After an algorithm is tested, the Reflector analyzes the evolutionary trajectory from parent to offspring. Instead of merely looking at the final score, it identifies the specific code changes that caused an improvement or a failure.
- The Bidirectional Experience Pool (BEP): Serving as the system's long-term memory, the BEP stores both Positive Insights (strategies to replicate) and Negative Pitfalls (mistakes to avoid). These experiences are "situation-conditioned," meaning they are tagged with the specific context in which they apply.
When the Evolver agent generates a new algorithm, it uses Retrieval-Augmented Generation (RAG) to pull relevant lessons from the BEP, ensuring the system continuously builds on past knowledge without repeating mistakes.
Experimental Setup
The framework was rigorously evaluated on several classic combinatorial optimization benchmarks:
- Routing Problems: Traveling Salesman Problem (TSP), Capacitated Vehicle Routing (CVRP), and Vehicle Routing with Time Windows (VRPTW).
- Packing Problems: Online Bin Packing (BPP).
- Selection Problems: 0-1 Knapsack Problem (KP) and Multiple Knapsack Problem (MKP).
- Real-World Data: Evolved TSP heuristics were tested on the TSPLIB benchmark to assess generalization to real-world graph structures.
Key Findings and Results
RefineEvo demonstrates significant advancements in automated algorithm design:
- State-of-the-Art Performance: RefineEvo consistently outperformed strong baselines, including FunSearch, EoH, and ReEvo, across all evaluated tasks.
- Superior Generalization: On the real-world TSPLIB benchmark, RefineEvo achieved a mean optimality gap of 11.54%, significantly outperforming the next best method, OpenEvolve (12.92%).
- Efficiency Gains: By selectively scheduling operators, the Planner provided a nearly twofold improvement in token efficiency. In ablation studies, RefineEvo consumed approximately 511k tokens, compared to ~965k for a baseline that applied all operators indiscriminately.
- Cross-Task Learning: The study revealed that experiences gained from solving one problem (e.g., TSP) could assist the system in solving entirely different problems (e.g., Bin Packing). This suggests the LLM successfully learns and transfers general algorithmic "motifs."
Limitations and Future Directions
While highly effective on benchmarks, the authors note that real-world industrial problems often feature complex, messy constraints that require further validation. Additionally, the system's performance is inherently bounded by the code-generation capabilities of the underlying LLM (such as DeepSeek-V3 or GPT-4o), and like many agentic frameworks, it currently lacks a formal theoretical proof for its convergence properties.
Future work will focus on extending RefineEvo to multi-objective optimization—such as balancing computational cost against execution speed—and adapting the framework for more complex, constrained optimization environments.
Summary updated