RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience
RefineEvo employs planning-guided heuristic evolution and bidirectional experience pools to enhance combinatorial optimization.
Key Findings
Methodology
RefineEvo introduces a Planner that dynamically schedules operators based on search state, and a Reflector that analyzes parent-offspring trajectories to extract positive and negative experiences. These are stored in a Bidirectional Experience Pool (BEP), which binds experiences to specific scenarios. The system uses trajectory-aware, situation-conditioned signals for operator selection and refinement, enabling self-evolving heuristics. Key components include:• State-aware operator scheduling and dynamic refinement• Trajectory-based experience extraction and binding• Semantic retrieval for experience reuse• Scenario-conditioned experience management• Adaptive search guided by trajectory insights.
Key Results
- RefineEvo consistently outperforms state-of-the-art baselines across benchmarks like TSP, Knapsack, and CVRP, reducing average optimality gap to 11.54%, and demonstrating superior scalability and robustness especially on large instances (e.g., n=1000).
- On TSPLIB instances, it achieves the lowest mean optimality gap of 11.54%, outperforming competitors like OpenEvolve by 1.4 percentage points, indicating strong generalization.
- Trajectory-aware experience extraction prevents repeated failures, leading to more targeted operator adjustments and higher solution quality in complex constrained problems.
Significance
This work advances automatic heuristic design by integrating planning and experience management, overcoming fixed operator and unscored experience limitations. It enhances search adaptability and solution quality, with broad implications for industrial scheduling, routing, and resource allocation. The approach offers a new paradigm for AI-driven algorithm self-evolution, promising significant impact in both academia and industry.
Technical Contribution
RefineEvo’s key innovation is the combination of a state-aware Planner with a trajectory-conditioned BEP, enabling dynamic operator scheduling and experience reuse tailored to specific search scenarios. Unlike static or purely outcome-based methods, this framework adapts in real-time, improving efficiency and solution quality. The semantic experience retrieval and scene binding mechanisms provide a new level of interpretability and robustness, expanding the scope of automatic heuristic design.
Novelty
This is the first work to integrate a planning-based operator scheduling with trajectory-aware, scene-conditioned experience management in an automatic heuristic framework. Unlike prior approaches that rely on fixed operators or outcome-only experience summaries, RefineEvo dynamically adjusts its search tools based on detailed trajectory analysis, significantly enhancing adaptability and scalability.
Limitations
- The computational overhead of dynamic scheduling and experience retrieval can be significant, especially in high-dimensional problems, potentially limiting real-time applications.
- Experience scene binding depends on semantic understanding, which may introduce errors or mismatches in complex or ambiguous scenarios.
- Further validation across diverse real-world problems is needed to confirm generalization and robustness.
Future Work
Future directions include integrating reinforcement learning for more intelligent operator scheduling, expanding experience scene understanding with multi-modal data, and applying the framework to industrial-scale problems such as large-scale logistics and manufacturing scheduling. Improving efficiency and scalability remains a key goal.
AI Executive Summary
Automatic heuristic design (AHD) aims to generate effective algorithms without manual tuning. Traditional methods often rely on fixed operators and static experience, limiting adaptability. Recent advances incorporate large language models (LLMs) for code generation and algorithm synthesis, yet these approaches face challenges in operator flexibility and experience utilization. This paper introduces RefineEvo, a novel framework that transforms AHD into a self-evolving system through planning-guided operator scheduling and a bidirectional experience pool.
RefineEvo’s core innovation lies in a Planner that perceives the current search state—such as fitness convergence and diversity—and dynamically selects or refines operators accordingly. When progress stalls, it triggers operator optimization, rewriting prompts based on observed failure patterns. Simultaneously, a Reflector analyzes parent-offspring trajectories, extracting both successful and failed modifications, and stores these insights in a BEP. The experiences are scene-conditioned, enabling targeted retrieval and reuse during search.
This integrated approach allows the system to adapt its heuristics in real-time, guided by trajectory-aware, situation-conditioned signals. Extensive experiments on benchmarks like TSP, Knapsack, and CVRP demonstrate that RefineEvo consistently outperforms existing methods, reducing optimality gaps and improving scalability. Notably, on large instances (n=1000), it maintains solution quality where others plateau.
The significance of this work is profound: it offers a new paradigm for automatic algorithm design, combining planning, experience management, and self-adaptation. The approach enhances both solution quality and computational efficiency, making it suitable for industrial applications such as logistics, manufacturing, and complex routing. Its ability to generalize across diverse problems indicates broad potential.
Despite these advances, challenges remain. The computational cost of dynamic scheduling and experience retrieval can be high, and scene-conditioned experience binding may face semantic mismatches. Future work will focus on integrating reinforcement learning for more efficient scheduling, expanding multi-modal experience understanding, and applying the framework to real-world industrial problems, pushing the boundaries of AI-driven self-evolving algorithms.
Deep Analysis
Background
自动启发式设计（AHD）起源于手工调优的局限，近年来借助深度学习和大模型实现自动化。代表性工作包括POMO、DeepACO、MCTS-AHD等，推动了神经网络与演化算法结合的研究。尽管取得一定成果，但这些方法多依赖静态算子或经验总结，难以应对复杂多变的任务环境。随着大模型能力提升，LLM在代码生成和算法设计中的应用逐渐展开，但仍存在算子应用不灵活、经验利用不足的问题。整体来看，AHD正处于从静态到动态、从单向到场景绑定的转型关键期。
Core Problem
现有AHD方法普遍面临算子固定、经验单向、适应性不足的问题。静态算子难以应对搜索过程中出现的多样化场景变化，导致搜索效率低下。经验总结多为结果导向，缺乏对失败原因的深刻理解，难以指导算子优化。此外，缺乏场景条件绑定的经验管理机制，限制了算法的泛化能力。解决这些瓶颈对于提升自动启发式设计的性能和适应性具有重要意义。
Innovation
本研究提出三大创新：1）引入规划器（Planner），实现状态感知的算子调度与动态优化，解决静态算子适应性差的问题；2）设计双向经验池（BEP），结合轨迹感知提取成功与失败经验，并绑定场景条件，增强经验的针对性；3）结合语义检索实现场景条件下的经验重用，提升搜索效率。这些创新共同推动AHD向自适应、场景化、智能化方向发展，突破了传统方法的局限。
Methodology
- �� 设定目标：最大化启发式的适应性和解质量。• 引入规划器（Planner）：感知搜索状态（如适应度收敛、多样性）• 根据状态动态调度算子（探索或利用）• 在搜索停滞时，触发算子优化（如调整提示语、参数）• 反思器（Reflector）分析父子轨迹，提取成功与失败经验• 经验绑定场景条件，存入双向经验池（E+和E-）• 利用语义检索匹配当前搜索场景，重用经验• 结合轨迹信息，优化算子选择和参数调节• 在多任务、多规模环境中验证系统性能，持续提升算法适应性和解质量。
Experiments
采用TSP、背包、CVRP等经典基准，比较RefineEvo与固定算子、神经网络及其他自动设计方法。设置不同规模（如n=50、100、200、1000）进行性能评估。指标包括目标值、优化差距、搜索速度和鲁棒性。使用真实和合成数据，调优超参数如搜索轮次、经验池容量。通过消融实验验证规划器、经验池的贡献，分析不同场景下的表现差异。确保结果具有代表性和可复现性。
Results
RefineEvo在多个任务中持续优于基线，平均优化差距降低至11.54%，在TSPLIB实例中表现优异，超越OpenEvolve约1.4个百分点。在大规模实例（如n=1000）中，表现出更强的扩展性和稳定性，解决方案质量显著优于固定算子策略。经验轨迹感知机制有效避免了盲目探索和重复失败，提升了算子调整的针对性。结果显示，系统在路径规划和资源调度等复杂场景中具有广泛适用性和优越性能。
Applications
该系统适用于路径规划、工业调度、物流优化等场景，尤其在复杂约束和大规模问题中表现出色。企业可以利用其自动调优能力，减少人工调试成本，提高调度效率。未来结合强化学习与多模态场景理解，有望实现更智能的自动算法设计，推动工业4.0和智能制造的发展。
Limitations & Outlook
当前系统在极端复杂或高维问题中算子调度的计算成本较高，可能影响实时应用。经验池的场景绑定依赖语义理解，存在误匹配风险。对不同任务类型的适应性和泛化能力仍需验证，未来需优化检索机制和扩展多任务能力。
Plain Language Accessible to non-experts
想象你在厨房里做饭，厨师需要用不同的工具（刀、锅、勺子）做不同的菜。传统方法是提前准备好所有工具，固定使用某一种，遇到不同菜就不灵活。而RefineEvo像一个聪明的厨师，能根据菜的不同情况，动态选择最合适的工具，还会记住哪些工具在做某种菜时效果好，哪些会出错。它会不断学习和调整，遇到新菜时也能快速找到最佳做法，就像一个会自己变聪明的厨师一样。这种方式让厨房变得更高效，做出来的菜也更好吃。
ELI14 Explained like you're 14
想象你在学校里参加比赛，老师给你一堆不同的题目。以前你可能用一种固定的方法去解题，但有时候不管用。有了RefineEvo，就像你有一个聪明的助手，他会观察你做题的过程，记住哪些方法在某些题上特别有效，哪些方法会失败。每次遇到新题时，他会帮你选择最合适的解题策略，还会不断学习和改进。当你遇到特别难的题，他会提醒你用不同的技巧，避免走弯路。这样一来，你的解题速度更快，成绩也会更好，就像有个聪明的朋友一直在帮你变得更厉害一样。
Glossary
Planning
A module that dynamically schedules operators based on current search state, ensuring efficient and adaptive search process.
In this paper, the planner guides operator selection and refinement.
Reflector
Analyzes parent-offspring trajectories to extract positive and negative experiences, binding them to specific scenarios.
Used to build the experience pool for targeted knowledge reuse.
Bidirectional Experience Pool
A repository storing both successful and failed experiences, linked with scene conditions for precise retrieval.
Core component for experience management in RefineEvo.
Trajectory-aware
Utilizing search paths and history to extract meaningful experiences, improving adaptation.
Enhances the relevance of experience-based guidance.
Combinatorial Optimization
Finding the best solution among many possibilities under constraints, such as routing or scheduling.
RefineEvo applies to various combinatorial problems.
Open Questions Unanswered questions from this research
- 1 如何进一步提升经验池的场景理解能力，避免误匹配和信息冗余，仍是未来研究的关键。
- 2 在极端大规模或高复杂度问题中，算子调度的计算成本和效率优化仍需突破。
Applications
Immediate Applications
工业路径调度
利用RefineEvo自动调优路径规划算法，提升制造和物流效率，减少人工调试成本。
智能调度系统
在复杂调度场景中实现自适应算法，提升资源利用率和调度响应速度。
Long-term Vision
自动算法设计平台
结合多模态信息和强化学习，打造全自动、可扩展的算法生成和优化系统，推动工业4.0发展。
Abstract
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.