🤖 AI

HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

This paper introduces HMACE, a heterogeneous multi-agent collaborative evolution framework that reconceptualizes heuristic search as an organizational design problem to overcome the limitations of monolithic LLM-based methods, achieving superior quality-efficiency trade-offs in solving NP-hard combinatorial optimization problems through specialized agent roles and memory-guided exploration.

Original authors: Yuping Yan, Jirui Han, Fei Ming, Yuanshuai Li, Yaochu Jin

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuping Yan, Jirui Han, Fei Ming, Yuanshuai Li, Yaochu Jin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, impossible-looking puzzle, like organizing a delivery route for 1,000 trucks or packing a warehouse with thousands of boxes. This is what computer scientists call a "Combinatorial Optimization Problem." It's so complex that even supercomputers struggle to find the perfect answer in a reasonable time.

For decades, humans have written special rules (heuristics) to help computers solve these puzzles. But writing these rules by hand is slow, expensive, and hard to adapt to new problems.

Recently, we started using Large Language Models (LLMs)—the same kind of AI that powers chatbots—to write these rules automatically. However, the paper argues that current AI methods are like a single person trying to do a complex job alone: they get stuck, they get tired, and they often settle for a "good enough" answer that isn't actually the best one.

The authors introduce a new system called HMACE (Heterogeneous Multi-Agent Collaborative Evolution). Here is how it works, using simple analogies:

The Problem: The "Solo Artist" vs. The "Orchestra"

Current AI methods try to solve these puzzles by asking one AI model to do everything at once: come up with an idea, write the code, test it, and decide if it's good.

The Analogy: Imagine a solo musician trying to write a symphony, play every instrument, conduct the orchestra, and critique the performance all at the same time. They get overwhelmed, their ideas get repetitive, and they miss the big picture. They get stuck in a "local optimum"—a small hill that looks like the top, but isn't.

The Solution: The HMACE "Specialized Team"

HMACE changes the game by treating the problem like an organizational design challenge. Instead of one AI doing everything, it creates a team of four specialized "agents" (AI workers) that work together in a loop. Think of them as a high-tech startup team:

The Proposer (The Idea Generator): This agent looks at past successful ideas and says, "What if we tried a slightly different approach?" It focuses on exploration—finding new, diverse directions.
The Generator (The Builder): This agent takes the Proposer's vague idea and turns it into actual, working computer code. It focuses on execution.
The Evaluator (The Tester): This agent runs the new code on real puzzles to see how well it works. It gives a score based on performance, not just how the code looks.
The Reflector (The Librarian & Coach): This is the most unique part. It keeps a giant "memory bank" (an archive) of all the ideas tried so far. Crucially, it doesn't just remember the best scores; it remembers how the ideas behaved. If the team is stuck, the Reflector says, "Hey, we haven't tried this specific type of behavior in a while. Let's go back to the archive and find an example from that 'neighborhood' to inspire the Proposer."

How They Work Together: The "Evolutionary Loop"

The team works in a cycle:

The Reflector pulls a few diverse examples from the memory bank to show the Proposer.
The Proposer drafts new strategies based on those examples.
The Generator turns those strategies into code.
Before the expensive testing phase, a quick filter removes broken or duplicate code (saving money and time).
The Evaluator tests the remaining code.
The Reflector updates the memory bank with the new results, organizing them by how they behaved, not just how well they scored.

Why This Matters: The "Quality-Efficiency" Trade-off

The paper tested HMACE on four classic difficult problems:

TSP: Planning the shortest route for a traveling salesman.
Online BPP: Packing items into bins as they arrive (like a busy warehouse).
MKP: Fitting items into knapsacks with weight limits.
PFSP: Scheduling jobs on factory machines.

The Results:

Better Solutions: HMACE found better solutions (closer to the perfect answer) than previous single-AI methods and other multi-AI methods.
Cheaper & Faster: This is the big surprise. HMACE used significantly fewer "tokens" (the currency of AI computing) to get these results.
- Analogy: Imagine two chefs trying to make a perfect cake. One chef (the old method) buys 100 ingredients, tries 50 recipes, and burns the kitchen down before getting a decent cake. HMACE is like a chef who uses a smart recipe book, tastes the batter early to avoid waste, and only buys exactly what they need. They get a better cake using 1/10th of the ingredients.

The Key Takeaway

The paper claims that the bottleneck in AI solving these problems isn't just how "smart" the AI is, but how the AI is organized. By breaking the job into specialized roles and giving the team a smart, behavior-aware memory system, HMACE avoids getting stuck in loops and finds better solutions faster and cheaper than the competition.

It's not about making the AI smarter; it's about giving it a better team structure.

Technical Summary: HMACE – Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

1. Problem Statement

Combinatorial Optimization Problems (COPs), such as the Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), and Bin Packing Problem (BPP), are fundamental yet NP-hard, rendering optimal solutions computationally prohibitive for large scales. While traditional heuristics rely on costly, hand-crafted rules, recent Large Language Model (LLM) approaches have attempted to automate heuristic design. However, existing LLM-based methods face two structural bottlenecks:

Premature Convergence: Monolithic workflows often lack structured exploration mechanisms (e.g., systematic backtracking), leading to entrapment in local optima.
Role Interference: Forcing a single agent to perform heterogeneous cognitive operations (planning, generation, evaluation, refinement) creates cognitive entanglement and degrades performance.

Current multi-agent attempts often suffer from communication overhead or lack specialized cognitive focus, failing to outperform strong single-agent baselines. The core challenge is designing an autonomous, role-specialized, and memory-aware architecture that coordinates reasoning and search effectively.

2. Methodology: HMACE Framework

The authors propose HMACE (Heterogeneous Multi-Agent Collaborative Evolution), which reconceptualizes heuristic search as an organizational design problem. Instead of a monolithic generation process, HMACE decomposes each evolutionary generation into a collaborative loop involving four specialized agents communicating via an archive-backed memory:

Proposer: Drafts strategy candidates in natural language. It conditions on the current population and retrieves diverse exemplars from the archive to ensure proposals combine or contrast distinct search patterns rather than refining a single dominant family.
Generator: Translates the proposed natural-language strategies into executable Python code (heuristics) that strictly adhere to the problem's I/O contract.
Evaluator: Executes candidate heuristics on training instances to compute two signals:
- Fitness ( $f_h$ ): A scalar score measuring solution quality (e.g., optimality gap).
- Behavior Vector ( $\phi_h$ ): A high-dimensional descriptor characterizing how the heuristic behaves during execution (e.g., runtime statistics, structural features).
Reflector: Manages the shared memory (archive) and guides the search. It performs:
- Behavior-Aware Retrieval: Selects diverse exemplars from distinct behavioral niches to condition the Proposer.
- Archive Update: Uses a CVT-MAP-Elites structure to store the best incumbent for each behavioral cell, ensuring coverage of the search space.
- Filtering: Before expensive evaluation, a lightweight deterministic filter removes malformed or near-duplicate programs to conserve the LLM budget.

Workflow: The system iterates through generations. The Reflector retrieves diverse exemplars; the Proposer drafts strategies; the Generator codes them; the Evaluator scores them; and the Reflector updates the population and archive. The process terminates when the generation budget is exhausted or no improvement is observed for a set number of generations.

3. Key Contributions

Organizational Approach to Heuristic Design: HMACE introduces a heterogeneous multi-agent evolutionary framework that decomposes the search process into specialized roles (Proposer, Generator, Evaluator, Reflector), moving beyond monolithic LLM-driven workflows.
Dual-Signal Reflection Mechanism: The framework integrates a novel reflection mechanism that leverages historical trajectories through behavior-aware retrieval and fitness-grounded archive updates. This allows agents to escape local optima by exploring diverse behavioral niches while maintaining high-quality incumbents.
Quality-Efficiency Trade-off: Extensive experiments demonstrate that HMACE achieves superior solution quality with significantly reduced computational costs (tokens and time) compared to state-of-the-art single-agent and multi-agent baselines.

4. Experimental Results

The framework was evaluated on four representative COPs: TSP, Online Bin Packing Problem (Online BPP), Multiple Knapsack Problem (MKP), and Permutation Flow-Shop Scheduling (PFSP).

Performance: HMACE achieved the lowest average optimality gaps among GPT-5.4 evaluated methods.
- TSP: Average gap of 0.387% (vs. 0.431% for CORAL and 0.467% for EoH).
- Online BPP: Average gap of 0.441% (outperforming MoH in 12/15 settings).
- PFSP & MKP: HMACE showed favorable quality-efficiency trade-offs, often reducing runtime and token usage significantly while maintaining competitive objective values.
Efficiency: HMACE demonstrated exceptional token efficiency.
- For TSP, it required only 0.13M tokens (vs. 0.94M for CORAL).
- For Online BPP, it required 0.42M tokens (vs. 5.48M for CORAL).
Ablation Studies: Removing behavior-aware retrieval (replacing it with random sampling) degraded solution quality, confirming the value of targeted behavioral priors. Removing the lightweight screening stage increased token costs without proportional quality gains.

5. Significance and Claims

The paper claims that the primary bottleneck of current LLM-based solvers is not merely model capability, but the lack of an appropriate organizational structure for coordinating reasoning and search.

Beyond Monolithic Agents: HMACE demonstrates that decoupling problem-solving into specialized, interactive roles robustly eliminates role interference and enables systematic, diversified exploration.
Memory as a Search Mechanism: The authors argue that reflection in HMACE is not merely verbal critique but an operational memory mechanism. By coupling fitness-driven exploitation with behavior-space exploration, the framework mitigates premature convergence.
Cost-Effective Discovery: The results suggest that a collaborative evolutionary workflow can discover reusable, high-quality heuristics more efficiently than single-agent approaches, achieving a favorable balance between solution quality and API token costs.

The authors acknowledge limitations, noting that the framework relies on a predefined, staged pipeline and that scaling long-term memory requires dynamic curation to prevent information overload. They position HMACE as a step toward addressing complex real-world challenges beyond classical COPs, such as continuous optimization.