用大模型生成难题实例,提升算法组合的泛化能力。
Evolving Parallel Algorithm Portfolios via Potential-Aware Instance Generation with LLMs

- 引入潜在增益指标,无需参考解即可评估实例难度。
- 通过多样化实例扰动,使算法组合在6种数据分布上表现更优。
- 适合研究自动算法设计与组合优化的开发者使用。
大型语言模型构建算法组合(LLM-ACP)在解决复杂组合优化问题时,面对少样本场景泛化能力差。现有协同进化框架通过生成当前算法表现不佳的难例来扩充训练集,但存在两大局限:实例难度评估依赖高质量参考解,且生成模式单一导致实例多样性不足。为此,本文提出潜在感知的实例与算法协同进化框架(PIAC)。核心贡献有二:首先提出“潜在增益”新指标,通过扰动生成算法并评估其在生成实例上的改进潜力,无需参考解即可衡量泛化增益;其次利用大模型生成多样化的实例扰动器,拓展问题实例空间,增强算法组合泛化能力。基于贪心构造、蚁群优化和引导局部搜索三种算法骨架,在旅行商问题(TSP)与带容量约束车辆路径问题(CVRP)上,跨六种数据分布的实验表明,PIAC持续优于现有最先进方法,尤其在TSP贪心构造组合上实现19.76%的相对性能提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。