HMACE：面向组合优化的异构多智能体协同进化

# HMACE：用于组合优化的异构多智能体协同演化

来源：https://arxiv.org/html/2605.07214
Yuping Yan, Jirui Han, Fei Ming, Yuanshuai Li, and Yaochu Jin
西lake大学工程学院
yanyuping\(hanjirui,mingfei,liyuanshuai,jinyaochu\)@westlake\.edu\.cn

###### 摘要

大型语言模型（LLM）最近成为自动化启发式设计的有前景范式，用于解决NP难组合优化问题。尽管取得了进展，但现有的基于LLM的方法通常依赖于受限于刚性模板的单体工作流程，从而限制了记忆引导的探索并导致过早收敛到局部最优。为了设计一个自主且协同的架构，我们引入了HMACE，这是一个异构多智能体协同演化框架，它将启发式搜索重新概念化为一个组织设计问题。HMACE将每一代演化分解为具有四个协调智能体的自主、角色专业化循环：负责策略探索的提议者（Proposer）、负责可执行启发式合成的生成器（Generator）、负责实证评估的评估器（Evaluator），以及负责基于档案的记忆更新的反思者（Reflector）。通过结合行为感知检索、轻量级候选过滤和基于适应度的档案更新，HMACE引导搜索走向多样且有希望的启发式行为，同时避免冗余评估。在包括旅行商问题（TSP）、在线装箱问题（Online BPP）、多维背包问题（MKP）和比例流水车间调度问题（PFSP）在内的代表性组合优化问题上的广泛评估表明，与最先进的单智能体和多智能体基线相比，HMACE实现了良好的质量-效率权衡。在匹配的LLM驱动参考对比中，HMACE在TSP和Online BPP上实现了最低的平均差距（分别为0.464%和0.223%），而这两个任务仅需要0.13M和0.42M个token，远低于对比基线。

## 1 引言

组合优化问题（COPs），如旅行商问题（TSP）、车辆路径问题（VRP）和装箱问题（BPP），在运营和工程领域具有基础性地位\[4 (https://arxiv.org/html/2605.07214#bib.bib2),7 (https://arxiv.org/html/2605.07214#bib.bib1)\]。然而，由于其NP难的性质\[35 (https://arxiv.org/html/2605.07214#bib.bib3)\]，可行搜索空间通常随问题规模呈指数级增长，使得获得最优解在计算上变得不可行。因此，启发式和元启发式算法已成为在可接受的时间内寻找高质量近似解的主要方法\[39 (https://arxiv.org/html/2605.07214#bib.bib6)\]。尽管有效，传统启发式方法严重依赖由领域专家手工定制的规则，这使得它们开发成本高且难以跨任务推广\[43 (https://arxiv.org/html/2605.07214#bib.bib7)\]。

最近，大型语言模型（LLM）的出现革新了这一范式。利用其预训练知识，LLM可以直接生成有希望的解，或者在没有显式算法指令的情况下自动设计新的启发式策略\[28 (https://arxiv.org/html/2605.07214#bib.bib57),48 (https://arxiv.org/html/2605.07214#bib.bib4),49 (https://arxiv.org/html/2605.07214#bib.bib5)\]。尽管潜力巨大，但当前的基于LLM的启发式设计方法面临两个基本结构瓶颈。首先，缺乏结构化探索机制（如系统回溯或多样化），它们极易过早收敛和陷入局部最优\[30 (https://arxiv.org/html/2605.07214#bib.bib11),42 (https://arxiv.org/html/2605.07214#bib.bib10)\]。其次，解决复杂的COPs本质上需要异构的认知操作（例如，规划、生成、评估和细化）。强迫单体智能体统一这些不同角色不可避免地会引发严重的角色干扰\[27 (https://arxiv.org/html/2605.07214#bib.bib12)\]。综上所述，这些局限性表明，当前基于LLM的求解器的瓶颈不仅在于模型能力，更根本在于缺乏适当的组织结构来协调推理和搜索。

受此观察的启发，我们将目光转向多智能体系统作为自然解决方案。与其将问题解决视为单体生成过程，多智能体框架将其重新表述为组织设计问题，其中多个具有专门角色的自主智能体协同探索和细化解空间。然而，先前的研究表明，简单地增加智能体数量并不能保证性能提升；设计不佳的多智能体系统由于通信开销和协调噪声，甚至可能表现弱于强大的单智能体基线\[29 (https://arxiv.org/html/2605.07214#bib.bib8),26 (https://arxiv.org/html/2605.07214#bib.bib9)\]。

如图1 (https://arxiv.org/html/2605.07214#S1.F1)所示，解决复杂的COPs需要超越单体结构和简单的并行化。因此，关键挑战不仅仅是引入多个智能体，而是设计一个自主的、角色专业化的、感知记忆的多智能体架构，以实现组合优化的有效协作。

> Refer to caption
> **图1：用于COPs的基于LLM的求解器的架构演进。** (1) 固定演化搜索：LLM仅作为刚性、人工定制的全局循环中的生成模块。(2) 自主单智能体演化：单体智能体顺序执行所有认知操作，这不可避免地导致认知纠缠。(3) 同质多智能体演化：同质智能体在共享记忆下并行探索，但仍缺乏专门的认知焦点。(4) 异构多智能体演化：通过将问题解决解耦为专门、互动的角色，它稳健地消除了角色干扰并实现了系统化、多样化的探索。

作为迈向这一新范式的关键一步，我们引入了HMACE，一种新颖的**异构多智能体协同演化**框架，利用明确的角色分工来自动化COPs的启发式搜索。在本文中，我们将复杂的启发式生成过程重新概念化为组织设计问题，而非顺序编码任务。技术上，HMACE实现了一个协同演化循环，以鼓励多样化探索和可靠的状态管理。在每次迭代中，专业化智能体相互作用以提出、生成、评估和归档候选启发式方法。当搜索停滞或产生低效用候选者时，反思者更新档案，检索行为多样的范例，并将后续提议引导至更有希望或未被充分探索的区域。通过这样做，HMACE不断细化启发式程序，同时减轻过早收敛。消融研究证实，角色专门化和基于档案的反思都有助于观察到的性能提升。

我们的贡献有三点。首先，我们提出了HMACE，这是一个用于组合优化的异构多智能体演化框架，并将其制定为一种启发式设计组织方法，超越了先前由LLM驱动的单体工作流程。其次，我们引入了一种结合角色专门化协作的新型反思机制，使智能体能够通过行为感知检索和基于适应度的档案更新利用历史轨迹，从而提高搜索的鲁棒性和多样性，同时减轻过早收敛。第三，在经典COPs上的广泛实验表明，与强大的单智能体、搜索控制器和多智能体基线相比，HMACE实现了良好的质量-效率权衡。值得注意的是，在匹配的LLM驱动参考对比中，HMACE在TSP和Online BPP上实现了最低的平均差距，同时所需的token数量远少于对比基线。

## 2 相关工作

### 2.1 基于LLM的自动启发式设计

自动启发式设计旨在减少COPs对人工定制规则和领域知识的依赖。早期的自动化算法设计和超启发式方法在预定义的算法组件、配置或低级启发式选择上进行搜索，而最近的基于LLM的方法将这一空间扩展到自然语言想法和可执行程序。FunSearch通过LLM提议者和外部评估者演化程序，展示了程序搜索在数学发现和在线装箱方面的潜力\[41 (https://arxiv.org/html/2605.07214#bib.bib13)\]。EoH将启发式想法表示为与可执行代码配对的自然人语言“思维”，并在LLM-EC循环中对其进行演化\[28 (https://arxiv.org/html/2605.07214#bib.bib57)\]。ReEvo进一步引入了反思性演化，使用LLM生成的反思作为口头反馈，以指导多种COP设置下的启发式改进\[50 (https://arxiv.org/html/2605.07214#bib.bib14)\]。最近的工作通过改进搜索控制器本身，超越了固定的LLM-EC循环。HSEvo和MCTS-AHD探索分层或树状启发式搜索，而MoH明确研究了启发式优化器的元优化，而不是假设固定的演化控制器\[14 (https://arxiv.org/html/2605.07214#bib.bib15),51 (https://arxiv.org/html/2605.07214#bib.bib16),42 (https://arxiv.org/html/2605.07214#bib.bib10)\]。这些方法表明，搜索过程的组织在基于LLM的启发式发现中起着重要作用。然而，它们主要改进优化器或搜索策略，而不是明确地将过程组织为角色专门化的多智能体系统。HMACE共享自动启发式演化的目标，但强调协作搜索过程中的专门化智能体角色、感知记忆的复用和成本感知的过滤。

### 2.2 用于组合优化的LLMs

除了自动启发式设计外，LLM已被用作组合优化的建模助手、求解器接口和直接推理引擎。主要的一类工作使用LLM将自然语言问题描述翻译成数学公式或求解器就绪代码。OptiMUS将基于LLM的建模、调试、测试和执行与线性规划和混合整数线性规划求解器相结合\[2 (https://arxiv.org/html/2605.07214#bib.bib17)\]，而LM4OPT和LLMOPT研究语言模型如何桥接非正式规范与正式优化模型\[3 (https://arxiv.org/html/2605.07214#bib.bib18),20 (https://arxiv.org/html/2605.07214#bib.bib19)\]。另一类工作调查直接或辅助COP求解，涵盖调度、路由、路径查找和端到端LLM求解器\[1 (https://arxiv.org/html/2605.07214#bib.bib20),19 (https://arxiv.org/html/2605.07214#bib.bib21),5 (https://arxiv.org/html/2605.07214#bib.bib22),21 (https://arxiv.org/html/2605.07214#bib.bib23),13 (https://arxiv.org/html/2605.07214#bib.bib24)\]。这些工作拓宽了LLM在优化中的作用，但它们主要针对公式化、实例级推理或求解器编排。相比之下，HMACE不要求LLM直接解决每个实例；它使用LLM智能体在实证评估和预算约束下发现可重用的可执行启发式方法。

### 2.3 基于LLM的多智能体系统

基于LLM的多智能体系统将复杂任务分解为相互作用的角色和工作流。代表性的框架如CAMEL、AutoGen、MetaGPT和AgentVerse表明，角色扮演、工具增强对话、标准操作程序和动态协作可以改善复杂推理和生成任务\[25 (https://arxiv.org/html/2605.07214#bib.bib25),47 (https://arxiv.org/html/2605.07214#bib.bib26),18 (https://arxiv.org/html/2605.07214#bib.bib27),10 (https://arxiv.org/html/2605.07214#bib.bib28)\]。与优化更密切相关的，DRAGON引入了用于大规模COPs的分解和重构智能体，而CORAL研究了用于开放式发现的自主多智能体演化\[9 (https://arxiv.org/html/2605.07214#bib.bib33),38 (https://arxiv.org/html/2605.07214#bib.bib34)\]。然而，现有的多智能体优化框架并未直接解决可重用启发式发现的问题：DRAGON\[9 (https://arxiv.org/html/2605.07214#bib.bib33)\]专注于分解和重构单个问题实例，而CORAL\[38 (https://arxiv.org/html/2605.07214#bib.bib34)\]针对更广泛的开放式发现，而非COP特定的启发式演化。相反，HMACE将自动启发式设计视为一个角色专门化的协作搜索过程，其中提议、代码生成、实证评估和基于档案的反思在有限的LLM预算下协调进行。

## 3 方法论

图2 (https://arxiv.org/html/2605.07214#S3.F2)展示了HMACE的概述，这是一个用于COPs自动启发式搜索的异构多智能体演化框架。HMACE的核心原理是将一次搜索代际分解为四个协调的角色：提议者（Proposer）、生成器（Generator）、评估器（Evaluator）和反思者（Reflector），它们都通过基于档案的记忆进行通信。在每一代中，提议者根据当前种群和检索到的档案范例起草策略候选者，生成器将这些策略转化为可执行启发式方法，评估器衡量它们在训练实例上的实证性能，反思者更新档案以引导后续搜索。这种分阶段设计保留了行为不同的小生境间的多样性，同时将优化循环建立在测量的适应度而非口头自我评估之上。提示和档案记录的示例性例子见附录B.3 (https://arxiv.org/html/2605.07214#A2.SS3)，特别是表7 (https://arxiv.org/html/2605.07214#A2.T7)以及在该小节中收集的提示和记忆模板。

> Refer to caption
> **图2：HMACE框架概述。** 提议者以父代启发式和从档案中检索到的多样范例为条件，起草策略候选者；生成器将每个候选者翻译为可执行代码；评估器在训练集上对候选启发式方法进行评分；反思者维护基于档案的记忆，从不同的行为单元中检索多样范例，并用表现最好的候选者更新每个单元。

在以下小节中，我们介绍所提出的HMACE框架的技术细节。

### 3.1 问题形式化

设 $\mathcal{T}$ 表示组合优化问题的一组训练实例。一个*启发式* $h \in \mathbb{H}$ 是一个可执行的Python程序，给定一个实例状态，返回一个构造或修复决策。启发式设计目标是识别一个最优启发式 $h^\star \in \mathbb{H}$，它最小化在 $\mathcal{T}$ 上的预期损失：

$$
h^\star = \arg\min_{h \in \mathbb{H}} f(h, \mathcal{T}), \quad f(h, \mathcal{T}) = \frac{1}{|\mathcal{T}|} \sum_{T \in \mathcal{T}} \ell(h, T), \tag{1}
$$

其中 $\ell(h, T)$ 是每个实例的损失（超出下限或最优性差距，取决于问题）。假设类 $\mathbb{H}$ 是隐式的，定义为LLM驱动搜索过程的支持，该过程根据问题上下文发出源代码。我们通过演化范式来解决方程1 (https://arxiv.org/html/2605.07214#S3.E1)。从种群 $P_0 \subset \mathbb{H}$ 开始，p