🤖 AI

HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

本文介绍了 HMACE，这是一个异构多智能体协同进化框架，它将启发式搜索重新概念化为组织设计问题，以克服基于单体大语言模型方法的局限性，并通过专业化智能体角色和记忆引导的探索，在解决 NP 难组合优化问题时实现更优的质量与效率权衡。

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

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

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

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图解决一个庞大且看似不可能的拼图难题，比如为 1,000 辆卡车规划配送路线，或将数千个箱子装入仓库。这就是计算机科学家所称的“组合优化问题”。其复杂程度之高，以至于即使是超级计算机也难以在合理时间内找到完美答案。

几十年来，人类一直编写特殊的规则（启发式算法）来帮助计算机解决这些难题。但手动编写这些规则既缓慢、昂贵，又难以适应新问题。

最近，我们开始使用大型语言模型（LLMs）——即驱动聊天机器人的同一种人工智能——来自动编写这些规则。然而，该论文指出，当前的 AI 方法就像“一个人试图独自完成复杂工作”：它们会陷入困境，会感到疲惫，并且往往满足于一个“足够好”但并非最佳的答案。

作者介绍了一种名为 HMACE（异构多智能体协同进化）的新系统。以下是其工作原理，辅以简单的类比：

问题：“独奏艺术家”与“交响乐团”

当前的 AI 方法试图通过让一个 AI 模型一次性完成所有任务来解决这些难题：提出想法、编写代码、测试代码，并判断其好坏。

类比：想象一位独奏音乐家试图同时创作交响乐、演奏每一件乐器、指挥乐团并评论演出表现。他们会感到不堪重负，想法变得重复，并错失全局。他们容易陷入“局部最优”——一座看起来像顶峰的小山丘，但实际上并非如此。

解决方案：HMACE“专业团队”

HMACE 通过将问题视为“组织设计挑战”来改变游戏规则。它不再让一个 AI 包揽一切，而是创建一个由四个专业“智能体”（AI 工作者）组成的团队，它们在一个循环中协同工作。可以将它们想象成一个高科技初创团队：

提议者（创意生成器）：该智能体审视过去成功的想法，并提出：“如果我们尝试一种略有不同的方法会怎样？”它专注于探索——寻找新的、多样化的方向。
生成器（构建者）：该智能体将提议者模糊的想法转化为实际可运行的计算机代码。它专注于执行。
评估者（测试员）：该智能体在真实难题上运行新代码，以观察其表现如何。它根据性能打分，而不仅仅是看代码“看起来”如何。
反思者（图书管理员与教练）：这是最独特的部分。它维护着一个巨大的“记忆库”（档案），记录所有已尝试过的想法。关键在于，它不仅仅记住最好的分数；它还记住想法如何表现。如果团队陷入僵局，反思者会说：“嘿，我们有一段时间没尝试这种特定类型的表现了。让我们回到档案，从那个‘邻域’中找一个例子来启发提议者。”

它们如何协同工作：“进化循环”

团队按以下循环运作：

反思者从记忆库中提取几个多样化的示例展示给提议者。
提议者基于这些示例起草新策略。
生成器将这些策略转化为代码。
在昂贵的测试阶段之前，一个快速过滤器会剔除损坏或重复的代码（节省金钱和时间）。
评估者测试剩余的代码。
反思者根据新结果更新记忆库，按它们如何表现而非仅仅按得分高低进行组织。

为何重要：“质量 - 效率”权衡

该论文在四个经典的困难问题上测试了 HMACE：

TSP（旅行商问题）：规划旅行商的最短路线。
在线 BPP（装箱问题）：随着物品到达将其装入箱子（如同繁忙的仓库）。
MKP（多维背包问题）：将物品装入有重量限制的背包。
PFSP（流水车间调度问题）：在工厂机器上安排作业。

结果：

更优的解决方案：HMACE 找到的解决方案（更接近完美答案）优于之前的单 AI 方法和其他多 AI 方法。
更便宜、更快速：这是一个巨大的惊喜。HMACE 使用了显著更少的"token"（AI 计算的货币）来达成这些结果。
- 类比：想象两位厨师试图制作完美的蛋糕。一位厨师（旧方法）购买了 100 种原料，尝试了 50 种食谱，在得到一块像样的蛋糕之前就把厨房烧毁了。HMACE 则像一位使用智能食谱书的厨师，提前品尝面糊以避免浪费，并且只购买他们确切需要的东西。他们用十分之一的原料做出了更好的蛋糕。

核心要点

该论文声称，AI 解决这些问题的瓶颈不仅仅在于 AI 有多“聪明”，而在于AI 的组织方式。通过将工作分解为专业角色，并赋予团队一个智能的、感知行为的记忆系统，HMACE 避免了陷入循环，并以比竞争对手更快、更便宜的方式找到更好的解决方案。

这并非关于让 AI 变得更聪明，而是关于赋予它更优秀的团队结构。

技术摘要：HMACE——用于组合优化的异构多智能体协同进化

1. 问题陈述

组合优化问题（COPs），如旅行商问题（TSP）、车辆路径问题（VRP）和装箱问题（BPP），是基础性的，但属于 NP 难问题，使得在大规模情况下求得最优解在计算上不可行。虽然传统启发式方法依赖于昂贵的手工规则，但近期的大语言模型（LLM）方法试图自动化启发式设计。然而，现有的基于 LLM 的方法面临两个结构性瓶颈：

过早收敛：单体工作流通常缺乏结构化的探索机制（例如系统性的回溯），导致陷入局部最优。
角色干扰：迫使单个智能体执行异构的认知操作（规划、生成、评估、优化）会造成认知纠缠并降低性能。

当前的多智能体尝试往往受限于通信开销或缺乏专门的认知焦点，未能超越强大的单智能体基线。核心挑战在于设计一种自主的、角色专业化的、具备记忆感知能力的架构，以有效协调推理与搜索。

2. 方法论：HMACE 框架

作者提出了HMACE（异构多智能体协同进化），将启发式搜索重新概念化为一个组织设计问题。HMACE 不再采用单体生成过程，而是将每个进化代分解为一个协作循环，涉及四个通过基于存档的记忆进行通信的专业化智能体：

提议者（Proposer）：用自然语言起草策略候选。它基于当前种群进行条件设定，并从存档中检索多样化的示例，以确保提议能够结合或对比不同的搜索模式，而不是仅仅优化单一的主导族系。
生成器（Generator）：将提议的自然语言策略转换为可执行的 Python 代码（启发式算法），严格遵循问题的输入/输出契约。
评估器（Evaluator）：在训练实例上执行候选启发式算法，计算两个信号：
- 适应度（ $f_h$ ）：衡量解质量的标量分数（例如，最优性间隙）。
- 行为向量（ $\phi_h$ ）：一个高维描述符，刻画启发式算法在执行过程中的行为方式（例如，运行时统计、结构特征）。
反射器（Reflector）：管理共享记忆（存档）并引导搜索。它执行以下操作：
- 行为感知检索：从不同的行为生态位中选择多样化的示例，以作为提议者的条件输入。
- 存档更新：使用 CVT-MAP-Elites 结构存储每个行为单元的最佳当前解，确保搜索空间的覆盖。
- 过滤：在昂贵的评估之前，一个轻量级的确定性过滤器会移除格式错误或近似的程序，以节省 LLM 预算。

工作流程：系统迭代进行多代。反射器检索多样化示例；提议者起草策略；生成器编写代码；评估器评分；反射器更新种群和存档。当生成预算耗尽或连续若干代未观察到改进时，过程终止。

3. 主要贡献

启发式设计的组织化方法：HMACE 引入了一种异构多智能体进化框架，将搜索过程分解为专业化角色（提议者、生成器、评估器、反射器），超越了单体 LLM 驱动的工作流。
双信号反射机制：该框架整合了一种新颖的反射机制，通过行为感知检索和基于适应度的存档更新利用历史轨迹。这使得智能体能够通过探索多样化的行为生态位来逃离局部最优，同时保持高质量的当前解。
质量与效率的权衡：大量实验表明，与最先进的单智能体和多智能体基线相比，HMACE 以显著降低的计算成本（令牌和时间）实现了更优越的解质量。

4. 实验结果

该框架在四个具有代表性的 COP 上进行了评估：TSP、在线装箱问题（Online BPP）、多背包问题（MKP）和置换流水车间调度（PFSP）。

性能：HMACE 在评估的 GPT-5.4 方法中实现了最低的平均最优性间隙。
- TSP：平均间隙为0.387%（CORAL 为 0.431%，EoH 为 0.467%）。
- 在线 BPP：平均间隙为0.441%（在 15 种设置中有 12 种优于 MoH）。
- PFSP 与 MKP：HMACE 展现了有利的质量 - 效率权衡，通常在保持竞争性目标值的同时显著减少运行时间和令牌使用量。
效率：HMACE 表现出卓越的令牌效率。
- 对于 TSP，仅需0.13M 个令牌（CORAL 为 0.94M）。
- 对于在线 BPP，仅需0.42M 个令牌（CORAL 为 5.48M）。
消融研究：移除行为感知检索（替换为随机采样）会降低解质量，证实了针对性行为先验的价值。移除轻量级筛选阶段会增加令牌成本，但不会带来成比例的质量提升。

5. 意义与主张

该论文主张，当前基于 LLM 的求解器的主要瓶颈不仅仅是模型能力，而是缺乏协调推理与搜索的适当组织结构。

超越单体智能体：HMACE 证明，将问题解决解耦为专业化的交互角色，能够稳健地消除角色干扰，并实现系统化、多样化的探索。
记忆作为搜索机制：作者认为，HMACE 中的反射不仅仅是言语批评，而是一种操作性记忆机制。通过将适应度驱动的利用与行为空间探索相结合，该框架缓解了过早收敛。
成本效益发现：结果表明，协作进化工作流比单智能体方法更高效地发现可重用的高质量启发式算法，在解质量和 API 令牌成本之间实现了有利的平衡。

作者承认了局限性，指出该框架依赖于预定义的、分阶段的流程，且扩展长期记忆需要动态策展以防止信息过载。他们将 HMACE 定位为迈向解决超越经典 COP 的复杂现实世界挑战（如连续优化）的一步。