通过潜在感知实例生成与LLM进化并行算法组合

# 通过基于LLMs的潜力感知实例生成演化并行算法组合

**来源：** https://arxiv.org/html/2608.06808

Shaofeng Zhang, Shengcai Liu, Zhiyuan Wang, and Ke Tang

Shaofeng Zhang is with the Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China, and also with the Zhongguancun Academy, Beijing 100094, China \(e-mail: [email protected]\). Shengcai Liu, Zhiyuan Wang, and Ke Tang are with the Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China \(e-mail: [email protected]; [email protected]; [email protected]\).

###### 摘要

基于大语言模型的自动组合构建（LLM-ACP）在解决复杂组合优化问题时，在实际少样本场景中泛化能力较差。实例与算法协同演化框架通过将当前算法组合表现不佳的生成困难实例扩充到训练数据集中来解决这一问题，从而增强泛化能力。然而，这一范式面临两个关键局限：评估实例难度依赖高质量参考解，且单一模式的生成方式限制了实例多样性。为克服这些局限，我们提出了潜力感知的实例与算法协同演化（PIAC）框架。我们的核心贡献有两方面。首先，我们提出了*潜力增益*，一种无需参考解的新型度量。该度量通过对生成的算法进行扰动，并评估它们在生成的实例上的改进潜力，来估计泛化增益。其次，PIAC利用LLMs合成多样化的实例变异器，探索问题实例空间中更广泛的区域，从而增强算法组合的泛化能力。鉴于不同算法的扰动空间各不相同，我们在贪心构造、蚁群优化和引导局部搜索算法骨干上实例化我们的框架。在旅行商问题（TSP）和带容量约束车辆路径问题（CVRP）上的六个不同数据分布的综合评估表明，PIAC始终优于最先进的LLM-ACP基线，特别是在TSP贪心构造组合上实现了19.76%的相对改进。

## I 引言

并行算法组合（PAPs）已成为解决复杂工程优化问题的强大范式[11](https://arxiv.org/html/2608.06808#bib.bib3), 8(https://arxiv.org/html/2608.06808#bib.bib5)。受没有免费午餐定理[34](https://arxiv.org/html/2608.06808#bib.bib1)的启发，该定理认为不同算法在不同问题特征上的表现各不相同，PAPs旨在构建一组互补的成员算法，以提升整个问题空间上的整体性能。在推理过程中，PAP通常并行运行多个成员算法，并将找到的最佳解作为最终输出返回。通过这种方式，PAPs可以有效利用成员之间的互补性，同时充分利用现代并行计算资源（如多核CPU）来实现优异的整体性能。由于手动构建高质量的PAP并非易事，自动组合构建（ACP）已被广泛研究[38](https://arxiv.org/html/2608.06808#bib.bib8), 15(https://arxiv.org/html/2608.06808#bib.bib9)。为了减少人工投入，主流ACP框架采用数据驱动范式。给定算法搜索空间（通常是基础求解器的参数配置空间）和一组训练实例，标准框架迭代地探索该空间以演化候选算法。在训练实例上性能的引导下，最终返回一组互补的成员算法组合，使整体性能最大化。

近年来，大语言模型（LLMs）编程能力的进步催生了基于LLMs的自动组合构建（LLM-ACP），成为ACP的一个强大新子领域[18](https://arxiv.org/html/2608.06808#bib.bib14), 43(https://arxiv.org/html/2608.06808#bib.bib15), 16(https://arxiv.org/html/2608.06808#bib.bib23)。LLM-ACP与ACP的根本区别在于算法搜索空间。LLM-ACP将范式从调整固定参数配置转向探索开放式编程空间，例如启发式代码片段。尽管取得了这些进展，ACP（包括LLM-ACP）经常面临*少样本*泛化挑战。在实践中，可用的训练实例数量有限，且往往无法捕获真实世界数据中复杂的实例分布[26](https://arxiv.org/html/2608.06808#bib.bib30), 29(https://arxiv.org/html/2608.06808#bib.bib31)。因此，在如此有限的训练集上构建的组合极易过拟合，且常常无法泛化到未见过的实例。

为克服这一局限，先前的研究（如CEPS[28](https://arxiv.org/html/2608.06808#bib.bib6)和DACE[33](https://arxiv.org/html/2608.06808#bib.bib7)）利用实例-算法协同演化来动态扩充训练数据集。在本文中，我们将问题实例的质量定义为将其纳入训练数据集后PAP泛化性能的提升。为了获得此类高质量实例，现有方法主动生成当前组合难以解决的对抗性或“困难”实例。具体来说，这些困难实例暴露了当前算法表现不佳的问题空间区域。用这些实例扩充训练集，推动组合在这些特定区域提升性能，从而增强整体泛化能力。

然而，将传统的协同演化框架（如CEPS和DACE）应用于LLM-ACP范式，暴露出两个关键局限。首先，在对高质量解的依赖方面，现有方法通常依赖接近最优的参考解来评估新生成实例的质量[30](https://arxiv.org/html/2608.06808#bib.bib2), 32(https://arxiv.org/html/2608.06808#bib.bib13), 3(https://arxiv.org/html/2608.06808#bib.bib4)。具体来说，这些方法基于实例的难度来评估其质量，即难度度量，并通过计算当前PAP与参考解之间的性能差距来量化该度量。在许多实际或新设置的场景中，获取此类高质量解是一项具有挑战性的任务。其次，在单模式实例生成方式方面，先前的实例生成策略通常依赖固定、预定义的操作符，例如简单的几何变换或随机扰动[28](https://arxiv.org/html/2608.06808#bib.bib6), 33(https://arxiv.org/html/2608.06808#bib.bib7)。这种单模式生成范式缺乏多样性，产生高度同质的实例，从而限制了最终算法组合的泛化能力。

为克服这些局限，我们提出了潜力感知的实例与算法协同演化（PIAC）框架。在协同演化框架的基础上，PIAC通过两项针对LLM-ACP的核心创新推进了这一范式。首先，我们提出了*潜力增益*，一种新的潜力感知度量，避免了高质量参考解的需求。PIAC不依赖难度度量来确定实例质量，而是将评估重点转向算法组合的“改进潜力”。潜力增益度量通过对所设计的算法进行扰动，并量化扰动后的算法相对于原始算法在新生成实例上实现的性能改进来运作。通过直接度量这种经验增益，*潜力增益*为该组合在给定实例上的改进潜力提供了替代信号。其次，为增强生成实例的多样性，PIAC利用LLMs的代码生成能力来合成并演化一群程序化实例变异器。通过从静态、预定义的操作符转向多样化的变异器，PIAC有效扩展了可搜索的实例空间，并进一步增强了泛化能力。潜力感知评估与程序化实例合成共同用有价值的实例扩充训练集，引导组合演化朝向更强的互补性和更好的泛化能力。

为了评估算法组合的泛化能力，我们在少样本设置下构建PAPs，并在旅行商问题