RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience

Automatic Heuristic Design (AHD) has emerged as a transformative approach for solving 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. This paper proposes RefineEvo, a novel evolutionary framework that transforms AHD from a static trial-and-error process into a planning-guided, experience-driven system. RefineEvo introduces a Planner to dynamically schedule evolutionary operators and trigger refinement based on the current search state, and a Reflector to distill valuable lessons into a Bidirectional Experience Pool containing both positive insights and negative pitfalls. This synergistic framework enables the system to adapt its search tools to the evolving complexity of the problem and leverage trajectory-aware, situation-conditioned insights to guide generation. Experiments on several classic combinatorial optimization benchmarks demonstrate that RefineEvo consistently outperforms strong baselines. In particular, RefineEvo delivers superior solution quality while improving token efficiency, enabling more efficient and autonomous heuristic design.

Many important planning problems, such as finding shorter delivery routes or packing items into fewer boxes, are hard to solve perfectly because there are too many possible choices to check. In practice, people often design shortcut rules that quickly find good solutions, but creating these rules usually requires expert knowledge and repeated manual trial and error. This paper presents RefineEvo, a system that uses Large Language Models to help design such rules automatically. Instead of trying many changes blindly, RefineEvo plans which type of change is most useful at each stage. It also learns from past attempts: successful changes are stored as useful lessons, while failed changes are stored as warnings to avoid similar mistakes later. These lessons are used only when they match the current situation, so the system does not blindly reuse advice from unrelated cases. We test RefineEvo on several classic planning and decision-making problems. The results show that it can discover better rules than strong existing methods, while also using fewer tokens. This suggests that combining planning with experience reuse can make automatic algorithm design more effective and efficient.