Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design

📄 arXiv: 2509.24509v2 📥 PDF

作者: Yihong Liu, Junyi Li, Wayne Xin Zhao, Hongyu Lu, Ji-Rong Wen

分类: cs.AI, cs.CL

发布日期: 2025-09-29 (更新: 2025-09-30)

💡 一句话要点

提出EvoPH框架，通过经验引导的提示与启发式算法协同进化，实现自动算法设计

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 自动算法设计 大型语言模型 启发式算法 协同进化 组合优化

📋 核心要点

  1. 现有自动启发式算法设计方法易陷入局部最优，缺乏对多样性的有效维护。
  2. EvoPH框架通过经验引导提示与启发式算法协同进化，并结合岛屿迁移模型和精英选择算法，维持种群多样性。
  3. 在旅行商问题和装箱问题上的实验表明，EvoPH显著降低了相对于最优解的相对误差。

📝 摘要（中文）

本文提出了一种用于自动算法设计的经验引导的提示与启发式算法协同进化框架（EvoPH）。传统上，组合优化问题依赖于手工设计的启发式算法，这需要大量的领域专业知识和实现工作。最近的研究表明，由大型语言模型（LLMs）驱动的自动启发式算法设计具有潜力，能够自动生成和改进启发式算法。这些方法通常维护一个启发式算法种群，并使用LLM作为变异算子来跨代进化它们。然而，这些方法常常面临陷入局部最优的风险。为了解决这个问题，EvoPH集成了岛屿迁移模型和精英选择算法，以模拟多样化的启发式算法种群。在EvoPH中，提示与启发式算法协同进化，并由性能反馈引导。我们在旅行商问题和装箱问题上评估了我们的框架。实验结果表明，EvoPH在两个数据集上都实现了相对于最优解的最低相对误差，从而推动了LLM自动算法设计领域的发展。

🔬 方法详解

问题定义：论文旨在解决组合优化问题中，手工设计启发式算法需要大量领域知识和人工成本的问题。现有基于LLM的自动启发式算法设计方法容易陷入局部最优，难以探索更广阔的解空间，缺乏对启发式算法种群多样性的有效维护。

核心思路：论文的核心思路是利用经验引导的提示与启发式算法协同进化，并结合岛屿迁移模型和精英选择算法，来维持种群的多样性，从而避免陷入局部最优。通过性能反馈来指导提示和启发式算法的进化方向，使其能够更好地适应问题特性。

技术框架：EvoPH框架主要包含以下几个模块：1) 初始化：初始化多个启发式算法种群（岛屿）和对应的提示；2) 岛内进化：在每个岛屿内，使用LLM作为变异算子，根据提示生成新的启发式算法，并根据性能进行选择；3) 岛屿迁移：定期将不同岛屿中的精英启发式算法进行迁移，促进种群之间的交流和多样性；4) 提示进化：根据启发式算法的性能反馈，使用LLM进化提示，使其能够更好地指导启发式算法的生成。

关键创新：EvoPH的关键创新在于：1) 经验引导的提示与启发式算法协同进化，使得提示能够根据启发式算法的性能进行自适应调整；2) 岛屿迁移模型和精英选择算法的结合，有效地维持了种群的多样性，避免了陷入局部最优；3) 将LLM作为变异算子，自动生成和改进启发式算法，降低了对领域知识的依赖。

关键设计：论文中关键的设计包括：1) 使用特定的提示模板来指导LLM生成启发式算法；2) 使用性能反馈来指导提示的进化，例如，可以根据启发式算法的平均性能、方差等指标来调整提示；3) 岛屿迁移的频率和迁移数量需要根据具体问题进行调整，以平衡种群的多样性和收敛速度；4) 精英选择算法的选择也会影响种群的进化效果，例如，可以使用轮盘赌选择、锦标赛选择等。

📊 实验亮点

实验结果表明，在旅行商问题和装箱问题上，EvoPH框架均取得了显著的性能提升，相对于最优解的相对误差是所有对比方法中最低的。具体来说，EvoPH在旅行商问题上将相对误差降低了X%，在装箱问题上将相对误差降低了Y%（具体数值未知）。这些结果表明，EvoPH框架能够有效地解决组合优化问题，并具有很强的竞争力。

🎯 应用场景

EvoPH框架具有广泛的应用前景，可以应用于各种组合优化问题，例如：物流配送、资源调度、生产计划等。该框架可以降低算法设计的门槛，使得非专业人员也能够快速开发出高性能的启发式算法。此外，EvoPH还可以用于探索新的算法设计思路，促进算法领域的创新。

📄 摘要（原文）

Combinatorial optimization problems are traditionally tackled with handcrafted heuristic algorithms, which demand extensive domain expertise and significant implementation effort. Recent progress has highlighted the potential of automatic heuristics design powered by large language models (LLMs), enabling the automatic generation and refinement of heuristics. These approaches typically maintain a population of heuristics and employ LLMs as mutation operators to evolve them across generations. While effective, such methods often risk stagnating in local optima. To address this issue, we propose the Experience-Guided Reflective Co-Evolution of Prompt and Heuristics (EvoPH) for automatic algorithm design, a novel framework that integrates the island migration model with the elites selection algorithm to simulate diverse heuristics populations. In EvoPH, prompts are co-evolved with heuristic algorithms, guided by performance feedback. We evaluate our framework on two problems, i.e., Traveling Salesman Problem and Bin Packing Problem. Experimental results demonstrate that EvoPH achieves the lowest relative error against optimal solutions across both datasets, advancing the field of automatic algorithm design with LLMs.