TL;DR
Existing LLM-based automatic algorithm design frameworks evolve code heuristics using static prompts, frequently causing searches to stall in local optima or propagate execution bugs across generations. EvoPH (Experience-Guided Reflective Co-Evolution of Prompts and Heuristics) solves this by co-evolving both the heuristic code and the prompting instructions that steer the LLM, backed by an island-based elite selection mechanism. Across Traveling Salesman and Bin Packing benchmarks, EvoPH significantly outperforms prior methods like FunSearch, EoH, and ReEvo in both solution quality and code executability.
What Problem Does This Paper Address?
Designing efficient heuristics for NP-hard Combinatorial Optimization Problems (COPs) typically requires deep human domain expertise. While recent methods leverage Large Language Models (LLMs) as semantic mutation operators to automatically discover heuristics, they face key failure modes:
- Premature Convergence: Fixed prompts and conventional evolutionary algorithms lack search diversity and often get trapped in local optima.
- Error Cascades: Code execution errors (syntax or logic bugs) often persist or multiply across descendant generations, wasting computational budget.
- Static Steering: Prompts remain constant throughout evolution, failing to adapt mutation styles to the current state of search or the specific failures encountered.
Methods
EvoPH establishes a closed-loop system that co-adapts heuristic algorithms and the prompts guiding them across two interactive cycles:
- Heuristics Evolution & Island-Based Elites Selection: The candidate population is split into independent sub-populations ("islands"). Each island maintains a multi-dimensional behavioral archive storing the best heuristics across diverse behavioral descriptors (e.g., solution quality vs. potential). Periodic migration between islands exchanges top-performing elites to balance global exploration with local exploitation.
- Experience Distillation: Candidate programs are evaluated against problem instances. Whether code runs cleanly or fails, performance metrics and execution stack traces are distilled into structured "experience."
- Prompt Evolution (Meta-Prompting): Prompts are treated as evolvable artifacts. An LLM meta-prompt consumes accumulated execution experience and historical prompts to generate updated, specialized instructions. It adopts a hierarchical posture: if candidate code fails, instructions adapt to enforce debugging and boundary-case handling; once execution stabilizes, prompts prioritize algorithmic exploration.
- Experience-Driven Strategy Sampling: EvoPH adaptively selects mutation operators from a modular strategy pool based on past success:
- Parameter modification (fine-tuning thresholds/constants)
- Redundancy removal (code simplification/efficiency)
- Structural modification (loop restructuring, data structures)
- Heuristic rewrite (replacing a core sub-routine)
- Complete rewrite (re-implementing from scratch to break severe stagnation)
[ Island-Based Elite Population ] ──(Select Parent)──► [ LLM Heuristic Mutation ]
▲ │
│ ▼
(Archive / Migrate) [ Code Execution & Eval ]
│ │
└──────────── [ Experience & Feedback ] ◄────────────────┘
│
▼
[ Prompt Evolution ]
(Evolves Prompts &
Selects Strategies)
Datasets
To overcome limitations of synthetic, fixed-size toy benchmarks that encourage overfitting, the authors constructed two standardized benchmarks solved with exact methods:
- TSP-Gurobi-Bench (TGB): Derived from TSPLIB, transformed into full distance matrices. Contains 58 instances solved to exact optimality within a 600-second limit using the Gurobi solver.
- BPP-Ortools-Bench (BOB): Derived from BPPlib. Contains 92 diverse bin packing instances with ground-truth optimal bin counts calculated using Google OR-Tools.
Key Insights and Ideas
- Prompts Should Be Evolvable First-Class Citizens: Just as genetic programming evolves operators, meta-heuristic LLM frameworks should evolve the meta-instructions. Stagnation often stems from static prompt bias; adapting instructions to the state of the search acts as an escape mechanism.
- Dynamic Focus Shift (Fix First, Optimize Later): The meta-prompt naturally evolves a two-stage strategy: when errors occur, instructions explicitly forbid optimization and demand root-cause isolation. Once code passes verification, prompts instruct the LLM to explore neighborhood structures and candidate lists.
- Dual-Level Diversity Preservation: Macro-level diversity is preserved through isolated island subpopulations, while micro-level mutation diversity is maintained by dynamically sampling conservative vs. radical rewrite operators based on execution history.
Key Results
Evaluated using Gemini-2.5-Pro across 20 iterations against baselines including FunSearch, EoH, mEoH, and ReEvo:
- Traveling Salesman Problem (TGB):
- EvoPH achieved the lowest relative error across all 6 classical initialization heuristics.
- For weak initial heuristics like Christofides, EvoPH lowered relative error from 20.64% to 5.17% (vs. EoH: 9.64%, ReEvo: 20.60%).
- When starting from a strong baseline like 2-opt, it further reduced error from 6.62% down to 4.20%.
- Bin Packing Problem (BOB):
- Dramatically improved Best-Fit heuristics, slashing relative error from 28.13% to 1.65% (competing frameworks achieved 17.20%–26.77%).
- Reduced First-Fit error from 4.90% to 0.43%.
- Code Executability & Ablations:
- Incorporating prompt evolution increased the executable code rate from 20%–40% to 45%–75%.
- Removing Island-based Elites Selection caused the steepest drops in solution quality (e.g., nearest-insertion error jumped from 4.41% to 9.70%), proving its role as the framework's backbone.
Limitations and Future Work
- Scope of Problems: Evaluated strictly on two classic, offline combinatorial optimization problems (TSP and offline BPP); performance on online settings or broader problem classes remains to be explored.
- LLM Dependency & Cost: Relies on powerful proprietary models (Gemini-2.5-Pro) for dual evolution loops (code generation + prompt generation), which may introduce notable API latency and cost.
- Future Work: The authors plan to extend EvoPH to a wider variety of combinatorial optimization tasks and deploy it to practical, real-world algorithmic design scenarios.
Summary updated