💻 computer science

LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency

本文提出了一种由大语言模型（LLM）引导的进化搜索框架，该框架通过一种增强型特征多样性保留（Profile-Diverse Retention, PDR）策略来维持候选重构方案中的行为多样性，证明了这种多样化的上下文选择结合基于验证的模型选择，与仅依赖于近期性或性能的策略相比，能显著提高求解器在组合优化问题上的效率。

原作者： Kostis Michailidis, Dimos Tsouros, Nguyen Dang, Tias Guns

发布于 2026-07-31

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Kostis Michailidis, Dimos Tsouros, Nguyen Dang, Tias Guns

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在试图解开一个巨大的、令人脑力激荡的谜题。在计算机科学领域，这被称为“约束规划”（Constraint Programming）。它是航空航班调度、工厂装配线组织、破解秘密代码以及规划完美学校课表背后的魔力。困难之处不仅在于找到一个答案，而在于如何快速找到它。为此，人类编写“模型”——即一套严格的规则和指令，告诉计算机求解器究竟该如何寻找解。把模型想象成一张地图。一张好的地图能让你迅速到达目的地，但一张糟糕的地图可能会让你在原地兜圈子数小时，即便它在技术上最终能通向正确的地方。

长期以来，专家们一直知道，绘制这张地图的方式比求解器本身更重要。但绘制出最好的地图是一项艰巨的工作。最近，我们遇到了一位新的助手：大语言模型（LLMs）。这些是超级智能的 AI 聊天机器人，它们可以阅读问题描述并为你编写规则。它们非常擅长把规则写对，但并不总是擅长让规则运行得快。这就像有一个厨师，他能完美地遵循食谱，却不知道如何高效地切菜。这篇论文提出了一个重大问题：我们能否教会这些 AI 厨师不仅能烹饪出佳肴，还能重新设计厨房，从而以创纪录的速度完成烹饪？

这项研究背后的研究人员决定将模型创建视为一场进化生存游戏。他们没有要求 AI 一次性写出完美的模型，而是建立了一个循环，让 AI 尝试、失败、学习并再次尝试。他们称之为“进化搜索”。其运作方式如下：AI 提出一个新版本的谜题规则（一种“重构”）。然后，计算机测试这个新版本与旧版本之间的差异。如果新版本更快，它就能留在比赛中；如果变慢了或出错了，它就会被淘汰。随后，AI 会观察自己过去的尝试以及收到的反馈，从而编写下一个（也希望是更好的）版本。

团队测试了十种不同的策略，用于 AI way 如何记忆其过去的尝试。有些策略告诉 AI 只看它的最后一次尝试（就像一个只在考试前一晚复习的学生）。另一些则告诉它只记住它曾经做过的最快的尝试（就像一个只关注个人最好成绩的跑步者）。但研究人员怀疑这些方法过于片面。他们想知道，AI 是否需要一个更具多样性的“记忆库”——一个结合了快速尝试以及以完全不同方式解决问题的尝试的混合体。

为了测试这一点，他们发明了一种名为**剖面多样性保留（Profile-Diverse Retention, PDR）**的新策略。想象你是一名训练跑步队的教练。一个只记得最快跑步者的教练可能会忽略这样一个事实：有的选手擅长短跑，而另一些选手擅长长跑。PDR 就像一位保留着这样一群选手的教练：他们不仅跑得快，而且拥有独特的跑步风格。通过在 AI 的记忆中保留一组“既快又各具特色”的尝试，AI 可以通过混合和匹配这些想法，创造出真正新颖且高效的东西。

结果令人兴奋。在八种不同类型的复杂谜题（从“社交高尔夫”到“任务分配”）中，进化搜索始终能找到比原始人工编写模型更快的模型。事实上，对于某些问题，新模型的速度提高了数百倍。研究表明，保持多样化记忆（PDR）的策略比仅仅保留最近的或单一最快的尝试效果更好。它还证明了在另一组“测试”谜题上检查模型（验证）是至关重要的；如果没有这一步，AI 有时只会死记硬背训练谜题，而不是学习如何进行通用的求解。

有趣的是，研究人员还将他们的“全模型重构”方法与仅在原始模型中添加少量额外规则的方法（比如在地图上添加几个额外的箭头）进行了对比。他们的“全重构”方法每次都胜出了，这表明有时你需要重新绘制整张地图，而不仅仅是添加几个箭头。

最后，这篇论文表明，我们可以利用 AI 不仅去解决问题，还要去重新发明我们向计算机传达解决问题方式的过程。通过让 AI 进化它自己的策略，并保持一个多样化的最佳创意库，我们可以构建出效率极高的约束模型。这是迈向未来的一步，在那个未来，计算机不仅会遵循我们的指令，还会帮助我们为它们编写更好的指令。

技术摘要：基于 LLM 引导的进化搜索进行约束模型重构

问题陈述

组合优化问题在工业应用中无处不在，通常使用约束规划（Constraint Programming, CP）进行建模。虽然大语言模型（LLM）已展示出能够根据自然语言生成正确的声明式约束模型的能力，但仅有正确性并不保证效率。一个语义正确的模型可能由于次优的建模选择（例如：变量视角、约束公式或编码方式）而在计算上非常昂贵。手动重构这些模型以提高求解器性能是一个关键的瓶颈。现有的自动化方法通常依赖于基于规则的转换，或是在固定的模型结构上附加“流线化器”（streamliners，即额外的约束），而不是进行能够改变模型视角或变量编码的整体重构。

方法论

作者提出了一种用于面向性能的约束模型重构的 LLM 引导进化搜索框架。受自动启发式设计（Automatic Heuristic Design, AHD）的启发，该系统通过迭代生成、评估和选择模型重构方案来运行。

核心工作流

初始化： 建立基准模型（ $B$ ），并在训练集（ $D_{tr}$ ）上测量其运行时性能。
迭代循环： 进行 $T$ $T$ 次迭代：
- 上下文选择： 搜索策略（ $\sigma$ ）选择先前尝试的一个子集（包括理由、模型和反馈）以构成提示词上下文（ $R_t$ ）。
- 生成： LLM 接收包含任务描述、基准模型、运行时历史和所选上下文的提示词。它输出一个理由（ $\rho_t$ ）和一个候选模型（ $m_t$ ）。
- 评估： 候选模型在 $D_{tr}$ 上执行。评估器检查解的有效性（确保候选模型的答案与基准模型在相同实例上的答案一致）并测量总运行时。
- 历史更新： 将该次尝试记录在历史记录 $H_t$ 中。
最终选择： 在搜索终止后，将所有解有效的入选模型在独立的验证集（ $D_{val}$ ）上进行评估。选择在 $D_{val}$ 上总运行时最低的模型作为最终输出。这一步对于防止对训练实例的过拟合至关重要。

搜索策略

论文比较了十种用于向 LLM 提供上下文 $R_t$ 的策略：

基准策略： 采样（Sampling，无上下文）、全量历史（Full-history，所有先前的尝试）、最近 K 个（Last-k，侧重近期性）以及 最优 K 个（Top-k，侧重质量/速度）。
混合策略： 结合了近期性和质量。
启发式进化（EoH）： 维护一个模型种群，并使用特定的算子（例如：“不同方法”、“兼容组合”）来引导生成，包括带有和不带有性能反馈的情况。
剖面多样性保留（PDR）： 本文引入的一种新颖策略。PDR 显式地寻求行为多样性。它将每个模型表示为跨训练实例的归一化运行时向量。它使用**最大边际相关性（MMR）**来选择一组既快速（高质）又在行为上具有显著差异（运行时剖面相似度低）的尝试。

实验设置

基准测试： 来自 CSPLib 的八个满足问题（例如：任务分配、汽车序列化、覆盖阵列）。
模型： DeepSeek V4 Flash（1M token 上下文）。
求解器： 通过 CPMpy 使用 OR-Tools CP-SAT。
指标： 在留出测试集（ $D_{test}$ ）上的加速比几何平均值（GM），使用 PAR2（惩罚平均运行时）处理超时情况。

核心贡献

进化框架： 一种专门针对声明式 CP 模型进行全模型重构的 AHD 改编版，允许 LLM 改变视角、变量和编码，而不仅仅是附加约束。
剖面多样性保留（PDR）： 一种应用 MMR 处理实例级运行时向量的上下文选择策略。它保留那些虽快但表现出不同求解行为的尝试，旨在使搜索空间超越简单的近期性或质量指标。
系统性评估： 对十种搜索策略在八个问题上的全面比较，证明了保持多样化上下文的策略优于仅依赖近期性或质量的策略。
基于验证的选择： 引入了基于验证的最终模型选择步骤（这在 AHD 流水线中经常缺失），结果表明该步骤能持续提高留出性能并减轻过拟合。

结果

性能提升： 进化搜索在留出测试实例上产生了显著的加速。表现最好的策略（PDR）在所有问题上的几何平均加速比达到了 2.26×，特定实例的增益高达 250.7×（在覆盖阵列问题上）。
多样性的重要性： 维持多样化上下文的策略（PDR、带反馈的 EoH）通常优于仅依赖近期性（Last-1）或质量（Top-1）的策略。PDR 的表现优于仅考虑质量的 Top-5 策略 1.30 倍。
全模型 vs. 流线化器： 所提出的全模型重构方法显著优于一种改编的基准方法，后者仅生成附加的流线化约束（StreamLLM-single），后者仅实现了 1.02× 的加速。
成本效率： 虽然采样生成了最多的 token，但由于 KV 缓存的存在，全量历史 仍然具有成本效益。PDR 以比采样更低的成本提供了最高的加速比。
可靠性： 所选模型在测试实例上均未返回无效答案或错误的不可满足结果。基于验证的选择成功过滤掉了对训练数据过拟合的候选模型。

意义与主张

论文声称，由 LLM 引导的迭代重构可以实现自动发现高性能约束模型，无需人工干预即可实现显著加速。研究强调，搜索上下文中的行为多样性是成功的关键因素，其重要性超过了传统的近期性或原始速度等指标。

作者谦虚地指出，尽管结果令人鼓舞，但本研究受限于单一 LLM、单一求解器配置以及八个特定的满足问题。他们建议未来的工作可以探索优化问题、不同的求解器，以及更显式地利用丰富的求解器反馈（例如：冲突计数、搜索树深度）来进一步精细化多样性度量。这项工作将自身定位为迈向自动化约束建模“圣杯”的一步，即从仅仅追求正确性转向追求面向性能的自动化。