基于势感知实例生成与LLM的并行算法组合进化

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