自动化从自然语言生成QUBO公式

arXiv cs.AI 论文
qubo quantum-computing optimization multi-agent machine-learning benchmark open-source

摘要

一个多智能体框架能够自动化地从自然语言描述生成QUBO公式，并在新提出的QUBOBench基准测试中达到68%的准确率。

arXiv:2609.10629v1 公告类型：新 摘要：二次无约束二进制优化（QUBO）是组合优化的核心公式，由于其与量子、混合量子经典和量子启发式求解器的兼容性，日益受到关注。然而，将自然语言问题描述转化为正确的QUBO公式仍然困难，需要识别二进制变量、约束、目标函数、惩罚项和合适的惩罚权重。这一过程耗时且常常需要大量的领域专业知识。为了解决这一挑战，我们提出了一种端到端的多智能体框架，能够从自然语言问题描述自动生成QUBO公式，并支持结构化或非结构化测试用例。为了评估其性能，我们还引入了QUBOBench，这是一个包含12个应用领域中100个组合优化问题的基准测试，这些问题是来自同行评审文献、竞赛和经典NP困难问题中精心挑选的。实验结果表明，我们的框架在QUBOBench上实现了68%的准确率，比直接的单次调用基线高出22%。进一步的分析表明，迭代自我修复是提高性能的最重要组件。数据和代码已在 https://quitttcat.github.io/QuantumQUBOAgent 开源。
查看原文
查看缓存全文

缓存时间: 2026/09/12 08:19 

# QuantumQUBO智能体：从自然语言自动化生成二次无约束二值优化（QUBO）公式
来源：https://arxiv.org/html/2609.10629
Niloy Kumar Mondal  
机构：孟加拉国工程技术大学  
通讯作者：[[email protected]](mailto:[email protected])  
Md Rizwan Parvez  
机构：卡塔尔计算研究所，哈马德·本·哈利法大学，卡塔尔多哈  
通讯作者：[[email protected]](mailto:[email protected])

###### 摘要

二次无约束二值优化（QUBO）是组合优化的核心公式，因其与量子、混合量子-经典及类量子求解器的兼容性而日益受到关注。然而，将自然语言问题描述转化为正确的QUBO公式仍然困难，需要识别二进制变量、约束条件、目标函数、惩罚项及合适的惩罚权重。这一过程耗时且通常需要大量领域专业知识。为解决此挑战，我们提出一个端到端的多智能体框架，能从自然语言问题描述（结合结构化或非结构化测试用例）自动生成QUBO公式。为评估其性能，我们还引入了QUBOBench基准，该基准包含来自同行评审文献、竞赛和经典NP困难问题的100个组合优化问题，涵盖12个应用领域。实验结果显示，我们的框架在QUBOBench上达到68%的准确率，比直接单次调用基线高出22%。进一步分析表明，迭代自我修复是提升性能最关键的组件。数据和代码已开源于：https://quitttcat.github.io/QuantumQUBOAgent/

###### 关键词

机器学习，ICML

## 1引言

二次无约束二值优化（QUBO）问题是一类NP困难的组合优化问题，意味着目前没有已知的高效算法能在多项式时间内求得最优解。它在计算机科学、金融、物理学、工程学、医学、VLSI设计、量子计算、交通管理、机器调度等多个领域有广泛应用（Punnen, 2022）。随着量子计算的进步（Preskill, 2018），QUBO问题变得越来越重要，因为它们可以通过量子、混合量子-经典以及类量子方法来求解，例如量子退火（Rajak et al., 2023）和量子近似优化算法（QAOA）（Farhi and Harrow, 2016）。量子退火是求解优化问题的强大启发式方法（Somma et al., 2012）。

众多领域的研究人员正在探索量子优化算法，以期获得潜在的加速和精度提升。这些算法已应用于机器学习任务，如特征选择（Mücke et al., 2023; Samanta et al., 2025; Pathak et al., 2025）和贝叶斯网络结构学习（Shikuri, 2025）；计算机视觉问题，包括图像分割和去噪（Heidari et al., 2024; Kerger and Miyazaki, 2023; Venkatesh et al., 2024）；供应链（Moncayo-Martínez and He, 2025; Ciacco et al., 2026）；药物发现（Yang, 2025）；RNA折叠（Fox et al., 2022）；卫星观测（Ferrari et al., 2025）；调度问题（Zhou et al., 2025; Gebler et al., 2024）；网络安全（Marini and Arpe, 2025）；物联网（Zhang et al., 2025b）以及计算化学（Negre et al., 2022）。

为了将量子算法应用于各领域，优化问题必须首先被重述为QUBO形式，通常也需要转化为伊辛模型（Lucas, 2014）。一般来说，给定一个组合优化问题的自然语言描述，任务是找到二进制决策变量 \(x \in \{0,1\}^n\) 的取值，以最小化形如以下的成本函数：

\[\min_{x \in \{0,1\}^n} \; E(x) \;=\; x^{\top}Q\,x \;+\; c,\]
(1)

其中 \(Q\) 是系数矩阵，\(c\) 是常数偏移量（Glover et al., 2019）。解空间包含 \(2^n\) 个候选比特串，而通常情况下找到最优解是NP困难的。

因此，认知任务涉及识别二进制决策变量、提取隐式和显式约束、设计成本函数和针对约束违规的惩罚项、选择合适的惩罚权重，并最终使用经典启发式方法或最前沿的量子求解器来求解生成的QUBO。这些步骤极具挑战性且非常耗时，因为如此复杂的任务通常需要领域专业知识、数学严谨性和实验反馈。

为解决这一认知瓶颈，我们提出了一个端到端的多智能体框架，能从自然语言问题描述（结合结构化或非结构化测试用例）生成QUBO公式。为评估我们的框架，我们引入了QUBOBench，这是一个包含100个组合优化问题（涵盖12个应用领域）的基准，问题选自同行评审的会议、竞赛和经典的NP困难问题。我们的框架在QUBOBench上达到了68%的准确率，比直接单次调用基线（46%）高出22个百分点，其中迭代自我修复被确定为驱动性能提升最关键的部分。

## 2相关工作

近期研究探讨了大型语言模型如何将自然语言问题描述转化为形式化的优化模型。NL4Opt竞赛通过要求系统根据自然语言描述来制定优化问题，确立了这一方向（Ramamonjison et al., 2023）。后续系统通过更结构化的推理和智能体工作流扩展了这一思路。Chain-of-Experts在多个专家型LLM智能体之间分解复杂的运筹学问题（Xiao et al., 2024），而Optimus则利用LLMs为下游求解器生成可扩展的混合整数和线性规划模型（AhmadiTeshnizi et al., 2024）。OptimAI和LLMOPT进一步探索了由LLM驱动的智能体，这些智能体可以从自然语言中定义、建模和求解一般优化问题（Thind et al., 2025; Shu et al., 2025）。

先前基于LLM的优化建模方法主要关注线性规划（LP）、混合整数线性规划（MILP）或通用的求解器就绪公式，而QUBO设置尽管在量子和类量子优化中扮演核心角色，却相对而言研究较少。然而，AutoQUBO虽然实现了从形式化程序输入自动生成QUBO，但仍假设用户能提供问题的精确计算描述，并未解决从自然语言研究描述生成公式的问题（Moraglio et al., 2022）。

LLM-QUBO是与此最相关的工作，研究了将自然语言优化描述自动转换为QUBO公式的可能性。然而，其实验主要关注MILP到QUBO的转换，并通过结构检查（如输入格式遵循、二值化、松弛变量引入和惩罚项有效性）来验证正确性（Zhang et al., 2025a）。因此，它对生成的公式作为可执行研究成果的端到端验证支持有限。此外，它没有系统地验证自然语言规范、结构化公式、生成的实现以及小实例最优解之间是否相互一致，也没有在发生错误时提供反馈驱动的重构过程。另外，其实证评估仅限于少量经典教科书问题，并未评估在多样化、特定领域的优化任务上的性能。

## 3方法论

图1：QuantumQUBO智能体的工作流程和架构

从自然语言问题陈述生成QUBO公式涉及几个不同的步骤：理解问题、选择二进制编码变量和约束、定义惩罚项、推导成本函数、生成可运行代码以及验证正确性。我们不依赖单个LLM来处理所有步骤，而是将任务分解到专门的智能体中，每个智能体负责一个步骤。整体架构如图1所示。每个智能体的角色和端到端工作流在以下小节中描述。

### 3.1多智能体架构

我们的框架由六个LLM智能体组成：规划智能体、公式化智能体、编码智能体、调试智能体、写入智能体和一个评判智能体。

#### 3.1.1规划智能体

我们的第一个智能体是规划智能体。它是一个LLM智能体，阅读用户提供的自然语言问题描述，并提取决策变量、优化方向以及每个隐式或显式约束（连同其类型（等式、≤或≥）和硬度）。然后返回问题的结构化JSON表示，该表示被传递给评判智能体，以检查其与原始描述的一致性。如果评判智能体识别出任何不一致，它会将一份问题清单返回给规划智能体，形成一个反馈循环。规划智能体随后根据问题清单，从原始描述进行另一轮解析和规划。

#### 3.1.2公式化智能体

我们的第二个智能体是公式化智能体。它是一个LLM智能体，接收规划智能体的结构化JSON表示，并根据决策变量、约束条件和优化类型推导出相应的QUBO成本函数，并简化该函数。返回的公式（以结构化JSON形式，包含变量映射、目标项和惩罚项、惩罚权重理由以及常数偏移量）随后传递给评判智能体；如果被拒绝，公式化智能体将根据报告的问题重新生成公式。公式化智能体同时接收来自评判智能体和管道末端失败测试用例的反馈，并尝试改进公式。

#### 3.1.3评判智能体

我们的下一个智能体是评判智能体。它是一个LLM智能体，在两个检查点被调用：它首先检查规划智能体的结构化规范是否与原始描述一致，稍后检查公式化智能体的QUBO成本是否与规范一致（判断约束编码、惩罚形式和目标符号的正确性）。在两种角色下，它都返回通过/不通过的裁决以及一份具体问题清单，这些问题清单被反馈回相应的智能体以进行针对性的重试。

#### 3.1.4调试智能体

我们的下一个智能体是调试智能体。它是一个LLM智能体，本质上是一个解析器。它将用户提供的测试用例和真实结果从自然语言转换为适合自动验证的结构化JSON记录。它使用从结构化JSON公式传来的变量映射，将真实的最优选择编码为比特串。调试智能体从不查看编码智能体的输出或生成的成本编码矩阵，这确保了从生成公式得到的最优解永远不会被存储为真实结果。此外，编码智能体也看不到真实结果。

#### 3.1.5编码智能体

编码智能体是一个LLM智能体，负责将QUBO公式翻译成可执行的Python代码。它接收结构化规范、公式和单个样本实例的参数，但不接收真实比特串（这防止了信息泄露）。生成的函数随后交给测试运行器进行经验验证，任何失败信息都会作为反馈返回给编码智能体，以便进行下一次尝试。

#### 3.1.6测试运行器

测试运行器是一个确定性组件（非LLM智能体），用于在每个测试用例上验证编码智能体的输出与真实结果。它将任何失败分类为*编码错误*（异常或格式错误的函数）或*公式错误*（有效输出但其最优值与真实结果不符）。编码错误被路由回编码智能体，而公式错误则被路由回公式化智能体，以便根据报告的问题进行新的推导。

#### 3.1.7写入智能体

我们的最后一个智能体是写入智能体，负责生成输出的可视化表示和摘要。

## 4 QUBOBench

为评估我们的框架在特定领域问题上的表现，我们引入了QUBOBench，这是一个基准，包含100个组合优化问题和200个小实例测试用例，涵盖12个应用领域。问题实例从三个互补来源中精心挑选：76个来自同行评审的会议，5个来自竞赛和黑客马拉松，19个经典的NP困难问题主要改编自Lucas（Lucas, 2014）。数据样本由人工精心挑选的问题描述和示例小实例测试用例组成，两者均为自然语言形式。更多细节请参阅附录B。

## 5实验设置

### 5.1评估协议

我们在QUBOBench数据集上评估QuantumQUBO智能体。性能通过两个指标衡量：**准确率**，定义为智能体管道生成QUBO公式并匹配所有真实最优解的基准比例；以及**总令牌消耗**。

### 5.2基线指标

作为下界基线，我们进行了直接评估，即将自然语言问题描述直接提供给LLM并使用单个提示。为确保公平和完全自动化的评估，我们向模型提供了由调试智能体预先生成的结构化实例字典，并将输出限制为固定函数签名。这消除了自动评分中因格式问题导致的假阴性的可能性。真实最优解在任何阶段都未暴露给模型。

### 5.3模型选择

所有推理智能体（规划、评判、公式化、调试）使用qwen/qwen3-235b-a22b，而编码智能体使用qwen/qwen3-coder-next。我们相信我们的管道是与LLM无关的。对于直接评估，我们使用了qwen/qwen3-coder-next。

### 5.4消融研究

我们进行了两项消融研究：一次移除迭代反馈，一次移除评判智能体。

相似文章