合成特征提取器：一种用于算法选择的智能体方法

# 一种基于智能体的算法选择方法
来源：https://arxiv.org/html/2608.17170
## 特征提取器综合：一种基于智能体的算法选择方法
致谢：代码、数据及完整可复现性存档：https://doi.org/10.5281/zenodo.20161743\.

海霞（Hai Xia）卡洛斯·安索特吉（Carlos Ansótegui）  
所属机构：莱里达大学逻辑与优化组，西班牙莱里达 carlos\.ansotegui@udl\.cat  
斯特凡·塞德尔（Stefan Szeider）  
所属机构：维也纳工业大学算法与复杂性组，奥地利维也纳 \{hxia,sz\}@ac\.tuwien\.ac\.at

###### 摘要

约束满足问题的算法选择需要提取能捕捉问题结构的特征。手动设计特征提取器需要深厚的领域专业知识，并且当新问题类别出现时会迅速成为瓶颈。我们提出一种自动化方法，利用大语言模型（LLMs）在智能体式的“检查-修复-验证”循环中，综合生成可执行的Python脚本，作为可解释的、问题特定的特征提取器。给定一个高级MiniZinc模型和一个实例，LLM智能体生成代码，构建类型化的图表示并计算结构属性，如图密度、变量聚类和约束紧度。我们在三个组合问题（车辆路径规划、汽车排序、固定长度纠错码）上评估了我们的方法，并使用了包含五个先进求解器的组合。综合生成的提取器所产出的算法选择器，其表现始终优于专家设计的 *mzn2feat* 特征（在FLECC上测试集准确率提升高达8.3个百分点）以及最佳的基于Transformer的 *trans2feat* 变体。同时，综合生成的特征提取器仍保持可检查性。

## 1 引言

组合问题如车辆路径规划（VRP）、汽车排序（CS）和固定长度纠错码（FLECC）是计算困难的：最先进的求解器可能运行数小时仍无法找到已证明的最优解，并且对于一个实例，最佳求解器与一个选择不当的求解器之间的性能差距可能跨越数个数量级（Kotthoff, 2016 (https://arxiv.org/html/2608.17170#bib.bib12); Kerschke et al., 2019 (https://arxiv.org/html/2608.17170#bib.bib10)）。实例的难度很大程度上取决于其结构（客户密度、时间窗紧度、约束耦合），而该结构决定了哪个求解器表现最佳（Smith-Miles and Lopes, 2012 (https://arxiv.org/html/2608.17170#bib.bib23)）。算法选择（AS）正是利用了这一事实，将实例映射到由互补求解器组成的组合中，选出最有效的那个（Rice, 1976 (https://arxiv.org/html/2608.17170#bib.bib20); Kerschke et al., 2019 (https://arxiv.org/html/2608.17170#bib.bib10)）。

标准的AS流程依赖于一个 *特征提取器*，它从问题实例计算信息特征向量。然而，设计这样的提取器通常需要大量的领域专业知识和洞察力，以确定哪些结构属性与求解器性能相关。此外，在实例上验证提取器的效率和有效性需要很长时间。因此，AS主要应用于具有成熟形式化体系的领域，主要是SAT（Hoos et al., 2021 (https://arxiv.org/html/2608.17170#bib.bib9); Shavit and Hoos, 2024 (https://arxiv.org/html/2608.17170#bib.bib22)）和通过 *mzn2feat* 进行的约束编程（Amadini et al., 2013 (https://arxiv.org/html/2608.17170#bib.bib1); Amadini et al., 2014 (https://arxiv.org/html/2608.17170#bib.bib2)）。当涉及传统形式化体系之外的问题类别时，研究人员要么从头构建新的提取器，要么将问题转换成其中一种形式化体系，这可能导致结构信息的丢失。

一般来说，有几个方面阻碍了AS流程的广泛应用。在设计端，它需要专家设计的提取器，如 *mzn2feat*。但对于这些提取器，仍然可能遗漏我们实验所揭示的与求解器相关的结构属性（第4节 (https://arxiv.org/html/2608.17170#S4)）。需要专业知识的设计也使得特征提取器无法完全自主生成。然而，LLM（大语言模型）在多样化的领域知识上进行了训练，使其适合用于策划特征提取器。在LLM端，一个简单的单次提示在实践中效果不佳：较弱的开源后端在10次尝试中无法生成一个工作的提取器，而对于强大的模型，移除我们下面循环中的任何步骤也会使成功率降至零（第3节 (https://arxiv.org/html/2608.17170#S3) 和第4.9节 (https://arxiv.org/html/2608.17170#S4.SS9)）。技术问题在于如何包装LLM，使其输出可靠可执行、与AS相关且可检查。

#### 我们的方法：通过LLM自动化特征提取

我们引入一个基于LLM的框架，自动生成可执行的Python脚本作为特征提取器。设计是一个 *两级过程*：一个LLM智能体，包裹在“检查-修复-验证”纠错循环中，综合生成程序，而输出程序随后就是提取器。该智能体首先读取高级MiniZinc问题描述（Stuckey et al., 2014 (https://arxiv.org/html/2608.17170#bib.bib25); Marriott et al., 2008 (https://arxiv.org/html/2608.17170#bib.bib15)）并生成一个Python脚本。然后，提取器（即Python脚本）从实例构建图表示，并输出一个可解释的特征向量。由于MiniZinc是一种具有丰富信息的声明式形式化体系，比如能给LLM提供问题结构模式的紧凑视图，我们使用MiniZinc作为我们的问题建模环境。

该框架生成显式的特征提取器（Python程序），其输出特征是可解释的，而非不透明的神经嵌入。虽然最近的工作探索了深度学习来生成潜在问题表示（Pellegrino et al., 2025 (https://arxiv.org/html/2608.17170#bib.bib18); Zhang et al., 2024 (https://arxiv.org/html/2608.17170#bib.bib30); Loreggia et al., 2016 (https://arxiv.org/html/2608.17170#bib.bib14)），但这些方法为了自动化而牺牲了透明度。我们生成的提取器产出的是图形特征，如图密度、变量聚类、约束紧度、数据统计摘要等，领域专家可以阅读、验证和改进。这种“灰盒”设计使自动化既易于人类理解，也便于改进。

#### 实证验证

我们在三个组合问题（VRP、CS、FLECC）的AS上验证了该方法，使用了五个先进求解器（Gurobi、CPLEX、SCIP、Gecode、OR-Tools）的组合。综合生成的提取器优于 *mzn2feat*（用于MiniZinc问题的既定专家设计提取器）（Amadini et al., 2013 (https://arxiv.org/html/2608.17170#bib.bib1); Amadini et al., 2014 (https://arxiv.org/html/2608.17170#bib.bib2)）和基于Transformer的 *trans2feat*（Pellegrino et al., 2025 (https://arxiv.org/html/2608.17170#bib.bib18)）。这种优势源于捕捉了扁平化表示和不透明嵌入所遗漏的高级结构属性。

#### 贡献

1. 1\. 我们证明了LLM智能体能够推理组合问题结构，并从MiniZinc问题描述中综合生成功能性、可解释的特征提取器，从而降低了为可在MiniZinc中表达的问题构建AS流程的人工工程成本。
2. 2\. 我们提出了一种基于智能体的“检查-修复-验证”流程，其中的中间产物是一个显式的Python程序。与不透明的神经嵌入不同，生成的提取器暴露了可检查的特征。
3. 3\. 在VRP、CS和FLECC上，基于我们综合特征构建的选择器优于基于专家设计的 *mzn2feat* 和基于Transformer的 *trans2feat* 构建的选择器。这表明LLM揭示了专家设计的提取器和基于Transformer的流程所遗漏的、感知求解器的结构模式。

## 2 相关工作

*算法选择问题*（AS）（Rice, 1976 (https://arxiv.org/html/2608.17170#bib.bib20); Kerschke et al., 2019 (https://arxiv.org/html/2608.17170#bib.bib10)）考虑一个算法组合 \mathcal{P}、一个实例集合 I、一个性能度量 PM(A,i) 以及一个资源预算 B。由于算法 A ∈ \mathcal{P} 的性能在不同实例上有所变化，AS策略必须在求解 *之前* 预测给定实例上运行哪个 A。为了使此过程可行，每个实例 i ∈ I 由一个 *特征向量* \phi(i) ∈ \mathbb{R}^{d} 描述，该向量由特征提取器 \Phi: i \mapsto \phi(i) 获得。AS任务是学习一个选择器 S: \mathbb{R}^{d} \rightarrow \mathcal{P}，最大化 \sum_{i \in I} PM(S(\phi(i)), i)，并受预算 B 约束。两个参考点校准了AS性能：

###### 定义 2.1（单一最佳求解器）。

*单一最佳求解器*（SB）是算法 A^{\text{SB}}=\arg\max_{A \in \mathcal{P}} PM(A,I)，在整个实例集 I 上实现最佳整体性能。SB策略将 A^{\text{SB}} 应用于每个实例。

###### 定义 2.2（虚拟最佳求解器）。

*虚拟最佳求解器*（VBS）是（假设性的）逐实例选择器，对于每个 i ∈ I，选择在该实例上实现最佳性能的算法 A ∈ \mathcal{P}：PM(\text{VBS},I)=\sum_{i \in I} \max_{A \in \mathcal{P}} PM(A,\{i\})。VBS 为任何 AS策略的性能设定了上限。

MiniZinc（Nethercote et al., 2007 (https://arxiv.org/html/2608.17170#bib.bib17)）是一种用于约束满足和优化的高级声明式建模语言。模型文件（.mzn）定义变量、约束以及（可选的）目标。数据文件（.dzn）包含实例参数。

#### 专家设计的特征

经典的AS建立在手工设计的特征集上，如SATzilla的（Shavit and Hoos, 2024 (https://arxiv.org/html/2608.17170#bib.bib22)）和 *mzn2feat* 的（Amadini et al., 2013 (https://arxiv.org/html/2608.17170#bib.bib1); Amadini et al., 2014 (https://arxiv.org/html/2608.17170#bib.bib2)）；手工特征同样驱动求解器内部的逐实例策略选择，例如在基于SAT的树分解中（Xia and Szeider, 2024 (https://arxiv.org/html/2608.17170#bib.bib28)）。

#### 不使用LLM的基于图的特征

将组合实例编码为图用于特征提取本身并不需要LLM。Stone等人，2024 (https://arxiv.org/html/2608.17170#bib.bib24) 将来自三个问题域的实例转换为领域无关的图和图像编码，提取通用图度量，并将所得表示用于算法选择和其他下游任务。他们的流程在所有领域应用一种固定的、手工指定的编码和特征集；而我们的智能体则 *为每个问题族编写一个新的提取器程序*，根据高级MiniZinc模型决定构建哪种类型化的图，以及将哪些问题适应的、感知求解器的量具体化为命名的、可编辑的特征（例如，对于VRP的需求集中度和配送中心偏心率，第4.8节 (https://arxiv.org/html/2608.17170#S4.SS8)）。这些方法是互补的：通用编码以零综合成本转移，综合生成的提取器则捕捉固定编码丢弃的语义信息。

#### 基于LLM的特征工程与程序综合

CAAFE（Hollmann et al., 2023 (https://arxiv.org/html/2608.17170#bib.bib8)）使用LLM为表格ML数据集生成Python特征转换，而FeatLLM（Han et al., 2024 (https://arxiv.org/html/2608.17170#bib.bib7)）提示LLM为少样本表格学习推导基于规则的特征。两者都作用于现有的表格输入。更广泛地说，基于LLM的程序搜索可以产生在组合设置中具有竞争力的可执行产物（Romera-Paredes et al., 2024 (https://arxiv.org/html/2608.17170#bib.bib21)）。我们的工作则从声明式的.mzn/.dzn规范开始，综合生成一个完整的、可复用的提取器程序，该程序计算问题规范本身的结构和语义属性。

#### 用于算法选择的神经嵌入

Wu等人，2024 (https://arxiv.org/html/2608.17170#bib.bib27) 使用LLM嵌入算法源代码和文档用于AS。Zhang等人，2024 (https://arxiv.org/html/2608.17170#bib.bib30) 将图神经网络与专家知识结合用于选择SAT求解器，学习CNF公式的结构嵌入。Pellegrino等人，2025 (https://arxiv.org/html/2608.17170#bib.bib18) 直接将Transformer编码器应用于约束优化实例的高级文本表示以学习特征。这些神经方法产生的高维嵌入，其各个维度缺乏清晰的语义意义，且不易检查或编辑。在FLECC和CS实例集上，Pellegrino等人，2025 (https://arxiv.org/html/2608.17170#bib.bib18) 发布了 *trans2feat* 特征，我们的 *LLM2feat* 选择器在测试准确率上比最佳 *trans2feat* 变体高出7.4和5.4个百分点（第4.7节 (https://arxiv.org/html/2608.17170#S4.SS7)）。

## 3 问题特定的基于LLM的智能体

我们建立在连接LLM与约束满足求解的智能体框架之上（Szeider, 2025 (https://arxiv.org/html/2608.17170#bib.bib26)）。

###### 定义 3.1（LLM智能体）。

一个 *大语言模型智能体*（Yao et al., 2023 (https://arxiv.org/html/2608.17170#bib.bib29)）是一个元组 \mathcal{A}=(L,T,M,\pi,E)，其中 L 是语言模型，T 是一组外部工具，M 是内存模块，\pi 是将观察和历史映射到模型输入的提示策略，E 是环境。智能体在一个循环 o_{t} \xrightarrow{\pi} p_{t} \xrightarrow{L} a_{t} \xrightarrow{T,E} o_{t+1} 中运作，其中 o_{t} 是时间 t 的观察，p_{t} 是构建的提示，a_{t} 是动作（例如工具调用），o_{t+1} 是下一个观察。

我们的智能体接收一个MiniZinc问题描述（.mzn和.dzn文件）和数据模式作为输入，并输出一个Python脚本，用于从该问题的任何实例中提取特征向量。图1 (https://arxiv.org/html/2608.17170#S3.F1) 中的循环由两个提示控制：*script\_system\_prompt*（一个通用的Python脚本生成提示，定义了严格的工作流程、技术要求和可用工具）和 *mzn-tuning*（一个领域特定的提示，指导智能体从适合AS的约束编程问题中提取50个标准化结构特征）。

图 1：生成问题特定特征提取器的工作流程。智能体循环执行 Clear、Insert、Check/Fix 和 Execute 步骤，直到获得一个可生成已验证特征向量的可执行 Python 脚本。

#### 通用脚本提示

通用Python脚本提示（script-system-prompt.md）强制执行四步工作流程：(i) Clear 清除所有先前内容；(ii) Insert 插入完整脚本；(iii) Check/Fix 检查并修复语法和结构要求，如有需要处理验证错误；(iv) Execute 执行脚本并验证其输出。预期的脚本结构如代码清单1 (https://arxiv.org/html/2608.17170#LST1) 所示。

1

2 import necessary_modules

3

4 CONSTANTS= values

5

6 def helper_functions():

7     pass

8

9 if __name__=="__main__":

10

11     result_dict={"key":"value","results":data}

12

13     output_results(result_dict)

代码清单 1：由 script-system-prompt.md 引导的通用 Python 脚本模板。

#### MiniZinc 调优提示

专门的 *mzn-tuning* 提示（mzn-tuning-prompt）