arXiv:2605.07214cs.AI2026-05被引 1

用多个角色协作的AI系统自动设计组合优化算法,效果更好且更省资源。

HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

论文配图:HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization
图 1 · 摘自论文原文
  • 四类智能体分工协作:提出策略、生成算法、评估效果、更新记忆。
  • 在旅行商等难题上平均误差仅0.464%,比现有方法少用90%以上推理次数。
  • 适合想自动生成优化算法的研究者和工业界应用者。

大型语言模型近年来在自动化求解NP难组合优化问题的启发式算法设计方面展现出巨大潜力。然而,现有基于LLM的方法通常依赖僵化的单一流程,限制了记忆引导的探索,易陷入局部最优。为此,我们提出HMACE——一种异构多智能体协同进化框架,将启发式搜索重构为组织设计问题。该框架将每一代进化分解为由四个协同智能体组成的自主循环:提案者负责策略探索,生成者合成可执行启发式,评估者进行实证测试,反思者基于档案更新记忆。通过行为感知检索、轻量级候选过滤与基于适应度的档案更新机制,HMACE有效引导搜索向多样化且有前景的启发式行为演化,同时避免重复评估。在典型组合优化问题(包括TSP、在线装箱问题BPP、多维背包问题MKP和流水车间调度问题PFSP)上的大量实验表明,相比当前最先进单智能体与多智能体基线,HMACE实现了更优的质量-效率权衡。在相同LLM驱动的对比中,其在TSP和在线BPP任务上的平均差距分别低至0.464%和0.223%,且仅需0.13M和0.42M token,显著低于对比方法。

原文摘要 · Abstract (English)

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.

组合优化多智能体提示工程自动化设计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。