Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design
作者: 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)
关键词: 自动算法设计 大型语言模型 启发式算法 协同进化 组合优化
📋 核心要点
- 传统组合优化算法依赖手工设计的启发式算法，需要大量领域知识和实现工作。
- EvoPH框架通过岛屿迁移模型和精英选择算法，模拟多样化的启发式算法种群，并协同进化提示和启发式算法。
- 在旅行商问题和装箱问题上的实验表明，EvoPH相对于最优解的相对误差最低，提升了自动算法设计性能。
📝 摘要（中文）
本文提出了一种用于自动算法设计的经验引导的提示与启发式算法协同进化框架（EvoPH）。该框架集成了岛屿迁移模型与精英选择算法，以模拟多样化的启发式算法种群。在EvoPH中，提示与启发式算法在性能反馈的指导下共同进化。我们在旅行商问题和装箱问题上评估了该框架。实验结果表明，EvoPH在两个数据集上均实现了相对于最优解的最低相对误差，推动了基于大型语言模型的自动算法设计领域的发展。
🔬 方法详解
问题定义：论文旨在解决组合优化问题中，手工设计启发式算法耗时耗力，且依赖专家知识的问题。现有基于LLM的自动启发式算法设计方法容易陷入局部最优，难以探索更广阔的解空间。
核心思路：论文的核心思路是利用经验引导的提示与启发式算法协同进化，通过模拟多个种群（岛屿）的并行搜索，并定期进行种群迁移，增加种群多样性，避免陷入局部最优。同时，提示（Prompt）也参与进化，从而更好地指导LLM生成更有效的启发式算法。
技术框架：EvoPH框架包含以下主要模块：1) 初始化：初始化多个启发式算法种群（岛屿）和对应的提示。2) 种群内进化：在每个岛屿内，使用LLM作为变异算子，根据提示生成新的启发式算法，并根据性能进行选择和淘汰。3) 岛屿迁移：定期将表现优秀的启发式算法从一个岛屿迁移到另一个岛屿，促进种群间的信息交流和多样性。4) 提示进化：根据启发式算法的性能反馈，使用LLM优化提示，使其更好地指导启发式算法的生成。
关键创新：EvoPH的关键创新在于：1) 提示与启发式算法的协同进化，使得提示能够更好地适应启发式算法的搜索过程。2) 岛屿迁移模型的使用，增加了种群多样性，避免陷入局部最优。3) 经验引导，利用历史性能数据指导提示和启发式算法的进化方向。
关键设计：论文中，LLM被用作变异算子，用于生成新的启发式算法和优化提示。具体的提示工程和LLM选择（例如，使用哪个LLM，如何设计提示模板）是关键的设计细节，但论文中可能没有详细描述。岛屿迁移的频率和迁移策略（例如，迁移多少个体，选择哪些个体进行迁移）也是重要的参数。
🖼️ 关键图片
📊 实验亮点
实验结果表明，EvoPH在旅行商问题和装箱问题上均取得了显著的性能提升，相对于最优解的相对误差最低。具体而言，EvoPH在两个数据集上都优于现有的基于LLM的自动算法设计方法，证明了其有效性和优越性。具体的性能提升幅度未知，需要查阅论文原文。
🎯 应用场景
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.