HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

2026-05-11 · Source: cs.AI updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences, Robotics & Autonomous Systems · Depth: Expert, extended

Summary

HMACE, a Heterogeneous Multi-Agent Collaborative Evolution framework, is introduced as a novel approach to automated heuristic design for NP-hard combinatorial optimization problems (COPs). This framework reconceptualizes heuristic search as an organizational design problem, decomposing each evolutionary generation into a 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 updates. HMACE integrates behavior-aware retrieval, lightweight candidate filtering, and fitness-grounded archive updates to guide the search towards diverse and promising heuristic behaviors while minimizing redundant evaluations. Extensive evaluations on COPs like TSP, Online BPP, MKP, and PFSP demonstrate that HMACE achieves a favorable quality-efficiency trade-off, outperforming state-of-the-art single-agent and multi-agent baselines. Notably, it achieves the lowest average gaps on TSP (0.464%) and Online BPP (0.223%) with significantly fewer tokens (0.13M and 0.42M, respectively) compared to other LLM-driven methods.

Key takeaway

For Machine Learning Engineers developing LLM-based solvers for NP-hard combinatorial optimization problems, HMACE offers a blueprint for improving both solution quality and token efficiency. You should consider adopting a heterogeneous multi-agent architecture with explicit role specialization and an archive-backed memory. This approach can help your systems escape local optima and achieve more robust, diversified exploration, significantly reducing API costs and search time compared to monolithic or homogeneous multi-agent designs.

Key insights

Heterogeneous multi-agent collaboration with specialized roles and memory-guided reflection enhances heuristic discovery for COPs.

Principles

• Decompose complex search into specialized agent roles.
• Ground search in measurable performance, not self-reported quality.
• Use behavior-aware memory for diverse exploration and exploitation.

Method

HMACE employs a four-agent evolutionary loop: Proposer drafts strategies, Generator synthesizes code, Evaluator assesses performance and behavior, and Reflector updates an archive for memory-guided retrieval and search redirection.

In practice

• Implement lightweight filtering to conserve evaluation budget.
• Track both fitness and behavioral metrics for heuristics.
• Utilize a CVT-MAP-Elites archive for diversity-aware memory.

Topics

• Heterogeneous Multi-Agent Systems
• Combinatorial Optimization
• LLM-based Heuristic Design
• Evolutionary Algorithms
• Archive-backed Memory

Best for: AI Scientist, Research Scientist, Machine Learning Engineer

Related on AIssential

• GrowthHacker: Automated Off-Policy Evaluation Optimization Using Code-Modifying LLM Agents — LLM-based agents can autonomously optimize Off-Policy Evaluation code, significantly improving performance and reliability in data-driven systems.
• LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization — CoEvo-AHD uses LLMs and co-evolution to design heuristics for coupled combinatorial optimization problems, improving solution quality.
• Towards Pareto-Optimal Tool-Integrated Agents with Pareto Ranking Policy Optimization — ParetoPO optimizes tool-integrated LLMs for superior accuracy-efficiency trade-offs using a two-stage multi-objective framework.
• Enhancing LLM-based Search Agents via Contribution Weighted Group Relative Policy Optimization — CW-GRPO improves LLM search agents by using an LLM judge for fine-grained, per-round credit assignment.
• COMAP: Co-Evolving World Models and Agent Policies for LLM Agents — COMAP co-evolves world models and agent policies through closed-loop interaction for adaptive LLM agents.
• Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search — LLM-driven evolution can automate and enhance complex metaheuristic algorithm design by decoupling and optimizing core components.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.