Dream-COP: Guiding Algorithm Discovery for Combinatorial Optimization Problems in an Experience World

📄 arXiv: 2610.36618v1 📥 PDF

作者: Kuan Xu, Jianming Wang, Ni Zhang, Yaoxin Wu, Yong Wang, Zhiguang Cao

分类: cs.LG, cs.AI

发布日期: 2026-10-27

💡 一句话要点

提出Dream-COP以优化组合优化问题的算法发现

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

关键词: 组合优化 算法发现 策略学习 经验世界 程序生成 性能优化 机器学习

📋 核心要点

  1. 核心问题：现有方法在有限预算内组织搜索以发现更优算法面临挑战，导致算法性能不佳。
  2. 方法要点：Dream-COP通过策略代理在经验世界中进行学习，指导发现代理生成和优化组合优化程序。
  3. 实验或效果：在五个COP的实验中，Dream-COP显著提升了算法性能，减少了搜索请求数量。

📝 摘要（中文）

大型语言模型（LLMs）通过迭代程序生成和评估，促进组合优化问题（COPs）的算法发现。核心挑战在于如何在有限预算内组织搜索，以发现更好的算法。我们提出Dream-COP，其中一个策略代理在经验世界中进行“梦境”学习，以指导发现代理生成和优化COP程序。具体而言，策略重放提供了对程序质量和搜索步骤的反馈，从而更有效地指导策略选择。在五个COP的实验中，Dream-COP在启发式组件设计和完整求解器生成方面发现了比固定探索更好的算法，尤其在KP问题上达到了最优值，并将OBPP的差距从2.112%减少到1.199%，同时减少了42.5%的搜索请求。此外，学习到的探索策略在不同COP之间有效迁移，得益于经验世界的支持。

🔬 方法详解

问题定义：本论文旨在解决组合优化问题（COPs）中的算法发现挑战。现有方法在有限的搜索预算下，难以有效组织搜索，导致算法性能未能达到最优。

核心思路：论文提出的Dream-COP通过构建一个经验世界，利用过去的搜索轨迹和结果，帮助策略代理学习更优的执行策略，从而指导发现代理生成和优化COP程序。这样的设计使得算法发现过程更加高效和智能。

技术框架：Dream-COP的整体架构包括两个主要模块：策略代理和发现代理。策略代理通过在经验世界中“梦境”学习，生成可执行的策略，而发现代理则利用这些策略生成和优化COP程序。整个流程通过策略重放机制进行反馈和优化。

关键创新：最重要的技术创新在于引入了经验世界的概念，通过策略重放提供反馈，显著提升了算法发现的效率和质量。这与现有方法的本质区别在于，Dream-COP能够动态调整策略选择，而不是依赖固定的探索策略。

关键设计：在设计中，关键参数包括策略学习的损失函数和网络结构，确保策略代理能够有效学习到高质量的执行策略。此外，重放机制的设计也至关重要，以便在生成和优化过程中提供实时反馈。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，Dream-COP在五个组合优化问题上表现优异，特别是在KP问题上达到了最优值，并在OBPP问题上将性能差距从2.112%减少至1.199%。同时，使用Dream-COP的搜索请求数量减少了42.5%，显示出其高效性。

🎯 应用场景

该研究的潜在应用领域包括运筹学、物流调度、网络优化等多个组合优化问题的实际场景。通过提升算法发现的效率和质量，Dream-COP能够为实际应用提供更优的解决方案，推动相关领域的技术进步与创新。

📄 摘要（原文）

Large language models (LLMs) enable algorithm discovery for combinatorial optimization problems (COPs) through iterative program generation and evaluation. A central challenge is how to organize search to discover better algorithms within a limited budget. Our key insight is that past search trajectories and their recorded outcomes form an experience world, which can be used to facilitate the COP solving through replay. We introduce Dream-COP, in which a \emph{policy agent} learns executable policies through \emph{dreaming} in this experience world to guide a \emph{discovery agent} in generating and refining COP programs. Specifically, policy replay provides feedback on the quality of the programs revealed and the search steps used, to guide policy selection more effectively. Across five COPs, \textsc{Dream} discovers better algorithms than fixed exploration in both heuristic component design and complete solver generation. Particularly, it matches the optimal values on KP and reduces the gap on OBPP from 2.112\% to 1.199\% while using 42.5\% fewer search requests. Moreover, the learned exploration policies transfer effectively across different COPs with the assitance of the experience world.