Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

📄 arXiv: 2610.03316v1 📥 PDF

作者: Zhouliang Xie, Changliang Zhou, Genghui Li, Zhenkun Wang

分类: cs.AI

发布日期: 2026-10-02

💡 一句话要点

提出MECo框架以解决零-shot跨问题泛化挑战

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

关键词: 组合优化 启发式算法 零-shot学习 多任务学习 大型语言模型 进化算法 调度问题 自动化设计

📋 核心要点

  1. 现有的启发式算法设计方法依赖于问题反馈，难以在新问题上进行有效泛化。
  2. MECo框架通过维护任务条件的启发式种群，利用跨任务性能差距来指导启发式的转移与重组。
  3. 在32个问题变体上，MECo在相同预算下实现了最低的平均成本，且在领域外问题上超越了最强基线。

📝 摘要（中文）

设计有效的启发式算法以应对多样的组合优化问题通常需要大量专业知识和反复搜索。大型语言模型（LLMs）能够自动化启发式生成和优化，但启发式搜索通常依赖于优化问题的评估反馈。因此，仅依靠源任务反馈来推广到新问题定义仍然是一个核心挑战。本文提出了MECo，一个基于LLM的多任务进化框架，用于零-shot跨问题泛化。MECo维护任务条件的启发式种群，并利用跨任务种群性能的转移差距来指导它们的交互。这些交互使得启发式的转移和重组成为可能。通过奖励每个成员对源组合的额外覆盖，构建一个紧凑的启发式集合。实验结果表明，MECo在32个车辆路径（VRP）和灵活作业车间调度（FJSP）问题变体上，较八个自动化启发式设计基线实现了最低的平均成本。

🔬 方法详解

问题定义：本文旨在解决如何在没有目标任务反馈的情况下，实现启发式算法在新组合优化问题上的有效泛化。现有方法通常依赖于特定问题的反馈，导致在新问题上表现不佳。

核心思路：MECo框架的核心思路是通过维护任务条件的启发式种群，利用跨任务的性能差距来引导启发式的转移和重组，从而实现零-shot泛化。

技术框架：MECo的整体架构包括任务条件的启发式种群、基于转移差距的交互机制和补充选择标准。首先，维护多个任务的启发式种群，然后通过交互实现启发式的转移和重组，最后通过选择标准构建紧凑的启发式集合。

关键创新：MECo的主要创新在于引入了跨任务性能差距的概念，允许启发式在不同问题之间进行有效的转移和重组，这与传统方法依赖于单一任务反馈的方式有本质区别。

关键设计：在设计上，MECo采用了任务条件的种群管理策略，并通过奖励机制来激励启发式的多样性和覆盖范围，确保所选启发式集合在目标问题上具有良好的适应性。具体的参数设置和损失函数设计尚未详细披露，属于未知领域。

🖼️ 关键图片

fig_0
img_1
img_2

📊 实验亮点

在32个车辆路径和灵活作业车间调度问题变体的实验中，MECo在相同预算下实现了最低的平均成本，且在领域外问题上超越了每个家族中最强的基线。此外，将MECo与不同的自动化启发式设计方法结合，提升了它们在同一领域和领域外的表现。

🎯 应用场景

MECo框架具有广泛的应用潜力，特别是在组合优化领域，如车辆路径规划和作业调度等。其自动化启发式生成能力能够显著降低专家知识的需求，提升算法在新问题上的适应性和效率，未来可能推动智能调度系统和优化工具的发展。

📄 摘要（原文）

Designing effective heuristics for diverse combinatorial optimization problems requires substantial expertise and repeated search. Large language models (LLMs) automate heuristic generation and refinement, but heuristic search typically depends on evaluation feedback from the problem being optimized. Generalizing to new problem definitions using only source-task feedback therefore remains a central challenge. We introduce MECo, an LLM-driven multi-task evolutionary framework for zero-shot cross-problem generalization. MECo maintains task-conditioned heuristic populations and uses a transfer gap based on cross-task population performance to guide their interactions. These interactions enable the transfer and recombination of heuristics. A complementary selection criterion then constructs a compact heuristic set by rewarding each member's additional coverage of source combinations. The selected set is applied to target problems without further search or adaptation. Experiments on 32 problem variants across vehicle routing (VRP) and flexible job-shop scheduling (FJSP) show that MECo achieves the lowest mean costs compared with eight automated heuristic design (AHD) baselines under the same budgets. On out-of-domain problems, it outperforms the strongest baseline in each family. Moreover, integrating the framework of MECo with different AHD methods improves their ID and OOD performance in both families, supporting its effectiveness across different methods.