Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs

📄 arXiv: 2608.06808v1 📥 PDF

作者: Shaofeng Zhang, Shengcai Liu, Zhiyuan Wang, Ke Tang

分类: cs.AI

发布日期: 2026-08-07

💡 一句话要点

提出潜力感知实例与算法共演框架以提升组合优化问题求解能力

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

关键词: 组合优化 算法投资组合 潜力增益 实例变异器 大型语言模型

📋 核心要点

  1. 现有的LLM-ACP方法在解决复杂组合优化问题时，泛化能力较差，尤其是在少样本场景下表现不佳。
  2. 本文提出的PIAC框架通过引入潜力增益度量和多样化实例变异器，克服了实例难度评估和生成模式的限制。
  3. 在TSP和CVRP的实验中，PIAC相较于现有基线表现出显著的性能提升，特别是在TSP贪婪构造投资组合上达到了19.76%的提升。

📝 摘要（中文）

自动构建组合算法投资组合的方法（LLM-ACP）在实际的少样本场景中表现出较差的泛化能力，尤其是在解决复杂的组合优化问题时。现有的实例与算法共演框架通过生成当前投资组合表现不佳的困难实例来扩展训练数据集，从而增强泛化能力。然而，该范式面临两个关键限制：实例难度评估依赖高质量参考解，以及单一模式生成限制了实例多样性。为此，本文提出了潜力感知实例与算法共演（PIAC）框架。我们的核心贡献包括提出了一种新颖的潜力增益度量，消除了对参考解的需求，并利用大型语言模型（LLMs）合成多样化的实例变异器，从而提升投资组合的泛化能力。实验结果表明，PIAC在旅行商问题（TSP）和容量车辆路径问题（CVRP）上均优于现有的LLM-ACP基线，尤其在TSP贪婪构造投资组合上实现了19.76%的相对提升。

🔬 方法详解

问题定义：本文旨在解决现有LLM-ACP方法在组合优化问题中的泛化能力不足，尤其是在少样本情况下的表现不佳。现有方法依赖于高质量的参考解来评估实例难度，且生成模式单一，限制了实例的多样性。

核心思路：PIAC框架的核心思路是引入潜力增益度量，消除对参考解的依赖，通过评估算法在生成问题实例上的改进潜力来增强泛化能力。同时，利用LLMs合成多样化的实例变异器，探索更广泛的问题实例空间。

技术框架：PIAC框架包括两个主要模块：潜力增益度量模块和实例变异器生成模块。潜力增益度量模块通过扰动生成的算法来评估其在新实例上的表现潜力，而实例变异器生成模块则利用LLMs生成多样化的实例变异器，以增加实例的多样性。

关键创新：本文的关键创新在于提出了潜力增益这一新颖度量，消除了对高质量参考解的需求，并通过多样化的实例变异器生成方法，显著提升了算法投资组合的泛化能力。

关键设计：在设计中，潜力增益的计算方式通过对生成算法的扰动进行评估，确保了评估的准确性。实例变异器的生成则通过LLMs进行，确保了生成实例的多样性和复杂性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在实验中，PIAC框架在旅行商问题（TSP）和容量车辆路径问题（CVRP）上均表现优异，尤其是在TSP贪婪构造投资组合上实现了19.76%的相对提升，显著优于现有的LLM-ACP基线，展示了其强大的性能和实用性。

🎯 应用场景

该研究的潜在应用领域包括组合优化、调度问题和资源分配等多个领域。通过提升算法投资组合的泛化能力，PIAC框架能够在实际应用中更有效地解决复杂问题，具有重要的实际价值和未来影响。

📄 摘要（原文）

The Automatic Construction of Portfolios via Large Language Models (LLM-ACP) suffers from poor generalization in practical few-shot scenarios when solving complex combinatorial optimization problems. Instance and algorithm co-evolution frameworks address this by expanding the training dataset with generated hard instances on which the current algorithm portfolio underperforms, thereby enhancing generalization. However, this paradigm faces two critical limitations: evaluating instance hardness relies on high-quality reference solutions, and single-mode generation patterns limit instance diversity. To overcome these limitations, we introduce the Potential-aware Instance and Algorithm Co-evolution (PIAC) framework. Our core contribution is twofold. First, we propose potential gain, a novel metric that eliminates the need for reference solutions. This metric estimates generalization gain by perturbing the generated algorithms and assessing their improvement potential on generated problem instances. Second, PIAC leverages LLMs to synthesize diverse instance mutators, exploring a broader region of the problem-instance space and thereby enhancing the portfolio's generalization capabilities. Given that perturbation spaces vary across different algorithms, we instantiate our framework on Greedy Constructive, Ant Colony Optimization, and Guided Local Search algorithmic backbones. Comprehensive evaluations on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) across six distinct data distributions demonstrate that PIAC consistently outperforms state-of-the-art LLM-ACP baselines, notably achieving a 19.76% relative improvement for TSP Greedy Constructive portfolios.