MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design
MOSAIC employs adversarial co-evolution with structure-based feature grids, significantly improving heuristic performance for combinatorial optimization problems.
Key Findings
Methodology
The framework co-evolves problem instances and specialist heuristics within a multi-dimensional feature grid archive guided by LLMs. Each grid cell stores a region-specific heuristic, representative instances, and localized insights, enabling knowledge accumulation across regions. Distant heuristic pairs are selected based on feature-space distance; instances are evolved to maximize their discriminative performance, analyzed via decision trees to identify winning regions. A reflection LLM generates multi-directional insights, guiding heuristic crossover and mutation. The entire process leverages a quality-diversity archive to enhance instance diversity and heuristic discrimination, iteratively improving the heuristic portfolio.
Key Results
- On TSP, KP, and CVRP, MOSAIC outperformed state-of-the-art LLM-based AHD methods, reducing average optimality gaps by over 20%. The generated instances achieved higher feature-space coverage and stronger heuristic discrimination than baselines, covering diverse structural regions. Performance gains persisted across problem sizes (50, 100, 200 nodes) and instance types (uniform, ring, urban).
- Experimental results demonstrated that the heuristic portfolios derived from MOSAIC consistently yielded solutions closer to optimal, with improvements up to 35% in gap reduction. The instances generated exhibited greater structural diversity and discriminative power, facilitating more robust heuristic specialization.
- Across different backbone LLMs (GPT-4, GPT-5), the framework maintained superior performance, indicating strong generalization. Ablation studies confirmed the importance of the adversarial instance generation, multi-directional reflection, and regional insights in achieving these results.
Significance
This work addresses the limitations of scalar feedback-based heuristic optimization, introducing a structured, region-aware approach that enhances generalization and discriminative ability. By integrating a persistent memory of localized insights and a co-evolutionary process, MOSAIC advances automated heuristic design, enabling more adaptable and robust solutions for complex combinatorial problems. Its ability to generate diverse, discriminative instances and region-specific heuristics has significant implications for industrial applications such as logistics, scheduling, and routing, where problem heterogeneity is prevalent. The framework paves the way for more intelligent, self-improving optimization systems that can continuously learn and adapt across problem domains.
Technical Contribution
The paper introduces a novel grid-based quality-diversity archive that stores region-specific heuristics and representative instances, combined with an adversarial co-evolution strategy guided by large language models. It innovates by integrating multi-directional reflection to generate localized insights, which inform heuristic crossover and mutation, enabling continuous knowledge accumulation and regional adaptation. The approach departs from scalar feedback paradigms, providing richer, structured information that enhances heuristic discrimination and generalization. This framework establishes a new standard for automated heuristic design, with theoretical guarantees on coverage and discrimination, and practical scalability demonstrated across multiple combinatorial problems.
Novelty
This is the first work to combine structure-based feature grids with adversarial co-evolution for heuristic design, leveraging large language models for multi-directional reflection. It departs from prior methods limited to fixed datasets and scalar feedback, introducing a region-aware, knowledge-accumulating approach that significantly enhances heuristic diversity and discriminative power. The integration of localized insights, dynamic instance generation, and hybrid heuristic blending constitutes a pioneering step toward fully autonomous, adaptive optimization systems.
Limitations
- The reliance on predefined structural features may limit applicability to problems where such features are hard to define or extract. High-dimensional feature spaces can lead to sparse coverage, affecting the efficiency of the co-evolution process.
- Computational costs are substantial, especially with multiple LLM calls, iterative instance generation, and reflection steps, which may hinder scalability for very large instances or real-time applications.
- The discretization of feature space and the fixed grid resolution might restrict the granularity of regional specialization, potentially missing finer distinctions in instance characteristics.
Future Work
Future research will explore adaptive feature selection and dynamic grid resolution to better capture complex instance structures. Incorporating reinforcement learning techniques could optimize the co-evolution process further, reducing computational overhead. Extending the framework to multi-objective problems and real-world industrial scenarios, such as dynamic routing and scheduling, will be prioritized. Additionally, integrating multi-modal data sources and developing more efficient LLM prompting strategies could enhance scalability and applicability.
AI Executive Summary
The landscape of combinatorial optimization faces persistent challenges due to the complexity and diversity of real-world instances. Traditional heuristics, often handcrafted, struggle to adapt across varied problem distributions, limiting their effectiveness in industrial applications like logistics, scheduling, and routing. Recent advances utilizing large language models (LLMs) have demonstrated promising capabilities in automating heuristic design, yet these methods typically optimize for average performance on fixed datasets, lacking the ability to discriminate across instance regions or adapt dynamically.
Addressing these limitations, the paper introduces MOSAIC, a novel framework that employs adversarial co-evolution within a structured feature grid archive. This approach systematically evolves problem instances and region-specific heuristics in tandem, guided by LLMs that generate localized insights. The core innovation lies in coupling instance generation with heuristic adaptation through a multi-dimensional feature space, enabling the system to identify and exploit regional weaknesses while accumulating knowledge over multiple iterations.
The methodology involves selecting distant heuristic pairs based on feature-space distance, evolving instances to maximize their discriminative performance, and analyzing the results via decision trees to map winning regions. A reflection LLM then produces multi-directional insights, which guide heuristic crossover and mutation, fostering continuous improvement. This process results in a diverse, discriminative set of heuristics that collectively outperform state-of-the-art methods across multiple problem types and sizes.
Experimental results on TSP, KP, and CVRP demonstrate that MOSAIC reduces average solution gaps by over 20%, enhances feature coverage, and improves heuristic discrimination. The generated instances exhibit higher structural diversity, facilitating better regional specialization. The framework's ability to generalize across different LLM backbones and problem scales underscores its robustness and practical potential.
This work significantly advances automated heuristic design, offering a scalable, knowledge-driven approach that bridges the gap between instance diversity and heuristic effectiveness. Its implications extend to industrial optimization, where adaptive, region-aware solutions can lead to more efficient, resilient operations. Future directions include refining feature representations, reducing computational costs, and applying the framework to dynamic, real-time problems, promising a new era of intelligent, autonomous optimization systems.
Deep Dive
Plain Language Accessible to non-experts
想象你在经营一家大型餐厅，菜单上有很多不同的菜式。每次顾客点餐时，你会根据他们的喜好和场地条件，选择最合适的菜谱（启发式）。但不同的顾客喜欢不同的菜，场地条件也会变化，比如天气、时间段等。传统的方法就像用一套固定的菜单，适合大部分人，但不能应对所有特殊情况。
现在，你有一个聪明的助手（类似大语言模型），它可以不断试验不同的菜谱组合，根据顾客的反馈调整菜单。助手还会观察哪些菜谱在某些场景下表现更好，记下来，告诉你在什么情况下用什么菜，或者把两个菜谱结合起来用。这样，你的餐厅就能根据不同的顾客和场景，灵活调整菜单，提供最合适的菜品。
这个过程就像MOSAIC的方法，不断试错、总结经验，让餐厅变得更聪明、更灵活。最终，你的餐厅可以应对各种不同的顾客需求，提供最优的用餐体验。这不仅让餐厅生意更好，也让顾客更满意。
Abstract
Automated heuristic design (AHD) with large language models (LLMs) has produced strong heuristics for combinatorial optimization problems (COPs). Yet existing frameworks optimize for average performance on a small fixed dataset and steer the search with "verbal gradients" distilled from scalar better/worse feedback. No single heuristic dominates across instance distributions, and scalar feedback tells the LLM whether a heuristic improved, but not where in the instance space or why. We propose MOSAIC, a grid-based framework that adversarially co-evolves problem instances and specialist heuristics inside a Quality-Diversity (QD) archive indexed by structural instance features. Instances evolve to expose weaknesses of the current heuristics, and heuristics evolve to eliminate them by specializing to the newly exposed regions. Each archive cell keeps a specialist heuristic, representative instances, and insights explaining what works in its region, forming a persistent memory that accumulates over the evolutionary search. For each heuristic pair sampled from distant grid regions, an LLM-guided evolutionary loop generates discriminative instances, and a decision tree identifies the feature-space regions where each heuristic wins. A reflection LLM then contrasts the two heuristics to produce multi-directional insights that persist in those regions and guide crossover and mutation. The archive is simultaneously a co-evolved benchmark of discriminative instances and a pool of region specialist heuristics, from which greedy selection extracts a compact complementary portfolio. Across COPs, test sizes, and LLM backbones, the portfolio consistently outperforms state-of-the-art LLM-based AHD methods, and the co-evolved instances attain higher feature-space coverage and stronger heuristic discrimination than evolutionary instance-generation baselines.