[2605.07214] HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

Computer Science > Artificial Intelligence arXiv:2605.07214 (cs) [Submitted on 8 May 2026] Title:HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization Authors:Yuping Yan, Jirui Han, Fei Ming, Yuanshuai Li, Yaochu Jin View a PDF of the paper titled HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization, by Yuping Yan and 4 other authors View PDF HTML (experimental) Abstract: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 behavio...