用AI自动生成可解释的求解器选择特征提取器。
Synthesizing Feature Extractors: An Agentic Approach for Algorithm Selection
- 用大模型迭代生成可执行的特征提取代码。
- 在3类问题上准确率比人工特征高8.3个百分点。
- 适合需要快速适配新问题的算法研发者。
约束满足问题的算法选择依赖于捕捉问题结构的特征提取。手动设计特征提取器需深厚领域知识，新问题出现时迅速成为瓶颈。本文提出一种自动化方法，利用大语言模型在‘检查-修正-验证’循环中生成可执行的Python脚本，作为可解释、问题特定的特征提取器。给定高阶MiniZinc模型和实例，LLM代理生成代码，构建类型化图表示并计算图密度、变量聚类、约束紧致度等结构属性。我们在三类组合优化问题（车辆路径、汽车排序、固定长度纠错码）上评估，使用五种前沿求解器组合。合成的特征提取器使算法选择器在测试集上准确率持续超越专家设计的mzn2feat特征（在FLECC上最高提升8.3个百分点），也优于最佳的transformer-based trans2feat变体。同时，合成的特征提取器保持可读性。
原文摘要 · Abstract (English)
Algorithm selection for constraint satisfaction problems requires extracting features that capture problem structure. Manually designing feature extractors demands deep domain expertise and quickly becomes a bottleneck when new problem classes appear. We present an automated approach that uses Large Language Models (LLMs) in an agentic check--fix--verify loop to synthesize executable Python scripts that act as interpretable, problem-specific feature extractors. Given a high-level MiniZinc model and an instance, the LLM agent generates code that constructs a typed graph representation and computes structural properties such as graph density, variable clustering, and constraint tightness. We evaluate our approach on three combinatorial problems (vehicle routing, car sequencing, fixed-length error-correcting codes) with a portfolio of five state-of-the-art solvers. The synthesized extractors yield algorithm selectors that consistently outperform both expert-curated mzn2feat features (up to $8.3$ percentage points (pp) test-set accuracy on FLECC) and the best transformer-based trans2feat variants. In the meanwhile, the synthesized feature extractors remain inspectable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。