HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

📄 arXiv: 2605.07214v1 📥 PDF

作者: Yuping Yan, Jirui Han, Fei Ming, Yuanshuai Li, Yaochu Jin

分类: cs.AI

发布日期: 2026-05-08

💡 一句话要点

提出HMACE异构多智能体协作进化框架，以解决组合优化问题中的启发式算法自动设计难题。

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

关键词: 组合优化 多智能体系统 大语言模型 启发式算法 进化计算 自动化设计

📋 核心要点

  1. 现有LLM驱动的启发式设计多依赖刚性模板，导致探索受限且易陷入局部最优。
  2. 提出HMACE框架，通过四个专业化智能体协作，将启发式搜索转化为组织设计问题。
  3. 实验表明HMACE在TSP和在线BPP任务中达到最优性能，且Token消耗显著低于基线。

📝 摘要（中文）

大型语言模型（LLM）已成为自动设计NP难组合优化问题启发式算法的新范式。然而，现有基于LLM的方法通常依赖于受限于刚性模板的单体工作流，这限制了记忆引导的探索能力，并易导致过早收敛至局部最优。为实现自主且协作的架构，本文提出了HMACE（异构多智能体协作进化框架），将启发式搜索重构为组织设计问题。HMACE将每一进化代分解为包含四个协作智能体的自主角色化循环：负责策略探索的Proposer、负责可执行启发式合成的Generator、负责实证评估的Evaluator以及负责基于存档记忆更新的Reflector。通过耦合行为感知检索、轻量级候选过滤和基于适应度的存档更新，HMACE引导搜索过程向多样化且有前景的启发式行为演进，同时避免了冗余评估。在TSP、在线BPP、MKP和PFSP等典型组合优化问题上的广泛评估表明，HMACE在质量与效率之间取得了优异的平衡，在TSP和在线BPP上实现了最低的平均差距，且显著降低了Token消耗。

🔬 方法详解

问题定义：论文旨在解决NP难组合优化问题（COP）中启发式算法自动设计的效率与质量瓶颈。现有方法多采用单一LLM工作流，缺乏有效的记忆机制与多维度探索能力，导致搜索过程容易陷入局部最优且计算成本高昂。

核心思路：将启发式搜索过程建模为一种组织协作行为。通过引入异构多智能体系统，将复杂的进化过程解耦为分工明确的子任务，利用角色化协作增强搜索的多样性与深度，并引入存档机制实现知识的长期积累与复用。

技术框架：HMACE框架由四个核心智能体组成：Proposer负责基于历史经验提出新策略；Generator将策略转化为可执行代码；Evaluator进行实证评估；Reflector负责更新记忆存档。系统通过循环迭代，不断优化启发式规则。

关键创新：引入了“行为感知检索”与“适应度引导的存档更新”机制。与传统单体LLM方法不同，HMACE通过多智能体分工实现了搜索空间的有效解耦，并利用存档过滤冗余评估，显著提升了搜索效率。

关键设计：采用了轻量级候选过滤策略，在生成代码前进行初步筛选；利用基于适应度的存档管理机制，确保只有高质量且具有多样性的启发式策略被保留，从而引导搜索向更优解空间收敛。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在TSP和在线BPP任务中，HMACE实现了极低的平均差距（分别为0.464%和0.223%），优于现有的单智能体及多智能体基线。在效率方面，该方法在上述任务中仅消耗0.13M和0.42M Token，大幅降低了计算开销，证明了其在资源受限环境下进行高效启发式搜索的卓越性能。

🎯 应用场景

该研究广泛适用于各类NP难组合优化场景，如物流配送中的旅行商问题（TSP）、资源分配中的多维背包问题（MKP）、在线装箱问题（BPP）以及生产调度中的置换流水车间调度问题（PFSP）。其自动化设计能力可显著降低工业界在复杂调度与规划任务中开发启发式算法的人力成本，并提升求解质量。

📄 摘要（原文）

Large Language Models have recently emerged as a promising paradigm for automated heuristic design for NP-hard combinatorial optimization problems. Despite this progress, existing LLM-based methods typically rely on monolithic workflows constrained by rigid templates, thereby restricting memory-guided exploration and triggering premature convergence to local optima. To design an autonomous and collaborative architecture, we introduce HMACE, a Heterogeneous Multi-Agent Collaborative Evolution framework that reconceptualizes heuristic search as an organizational design problem. HMACE decomposes each evolutionary generation into an autonomous, role-specialized loop with four coordinated agents: a Proposer for strategy exploration, a Generator for executable heuristic synthesis, an Evaluator for empirical assessment, and a Reflector for archive-backed memory update. By coupling behavior-aware retrieval, lightweight candidate filtering, and fitness-grounded archive updates, HMACE guides the search toward diverse and promising heuristic behaviors while avoiding redundant evaluations. Extensive evaluations on representative COPs, including TSP, Online BPP, MKP, and PFSP, show that HMACE achieves a favorable quality-efficiency trade-off compared to state-of-the-art single-agent and multi-agent baselines. In the matched LLM-driven reference comparison, HMACE achieves the lowest average gaps on TSP and Online BPP (0.464\% and 0.223\%, respectively), while requiring only 0.13M and 0.42M tokens for the two tasks, substantially fewer than the compared baselines.