EALG: Evolutionary Adversarial Generation of Language Model–Guided Generators for Combinatorial Optimization
Ruibo Duan, Yuxin Liu, Xinyao Dong, Chenglin Fan · 2025
Read EALG: Evolutionary Adversarial Generation of Language Model–Guided Generators for Combinatorial Optimization by Ruibo Duan, Yuxin Liu, Xinyao Dong, Chenglin Fan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-02594.txt.
Introduction
Ruibo Duan and colleagues let language models evolve both solvers and test problems for routing tasks. Their twenty twenty-five paper presents a closed-loop framework called ACEvo. Language models can write heuristic programs for hard planning problems. Training them on fixed benchmarks can hide solver weaknesses, though.
In ACEvo, one program invents harder problem cases over time. Another program improves as a solver against those cases. The contest creates a rising curriculum for both sides. Tests covered travelling salesman and vehicle routing problems. Evolved cases exposed larger gaps than standard benchmarks did. Solvers trained this way also handled shifted problem patterns better. The framework doubles as a lab for studying automated algorithm design.
Catalog record
| CREATOR | Ruibo Duan, Yuxin Liu, Xinyao Dong, Chenglin Fan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-02594
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
EALG: Evolutionary Adversarial Generation of Language Model–Guided Generators for Combinatorial Optimization Ruibo Duan, Yuxin Liu, Xinyao Dong, Chenglin Fan Abstract Generating challenging instances is crucial for the evaluation and advancement of combinatorial optimization solvers. In this work, we introduce EALG (Evolutionary Adversarial Generation of Language Model–Guided Generators), a novel framework that automates the co-evolution of optimization problem instances and their corresponding heuristic solvers using large language models (LLMs). EALG leverages a mutation-based adversarial approach that dynamically evolves instance generation procedures to create increasingly difficult problems, while simultaneously synthesizing adaptive heuristic algorithms through interactions with LLMs guided by algorithmic structure. Unlike existing approaches that focus solely on static benchmark creation or manual solver design, EALG provides a seamless pipeline from instance generation to solver synthesis. Experimental results demonstrate that EALG generates significantly harder instances than current benchmarks, and its synthesized solvers generalize effectively across a broad spectrum of combinatorial tasks. This work explores a new paradigm for combinatorial optimization that integrates instance generation with solver design, resulting in state-of-the-art performance. 1 Introduction Combinatorial optimization (CO) problems are ubiquitous across scientific and industrial domains, including logistics, scheduling, network design, and circuit layout. However, the combinatorial explosion of the solution space, combined with the structural diversity of these problems, makes the design of effective solvers a persistent and formidable challenge [ 7 , 8 ] . Traditional approaches often rely on handcrafted heuristics, which are time-consuming to develop and typically lack generalizability across different problem types. Recently, large language models (LLMs) have demonstrated impressive capabilities in code generation and complex reasoning, opening a promising new direction for the automated design of heuristic algorithms tailored to CO problems [ 5 , 16 ] . Existing studies typically rely on fixed datasets or uniform instance generation protocols, resulting in limited diversity across problem settings. Moreover, most approaches focus on incremental enhancements to existing solvers rather than introducing fundamentally novel frameworks [ 39 , 3 , 28 , 23 ] . This static evaluation paradigm restricts our ability to assess solver generalization and robustness. As a result, two critical challenges remain underexplored: (1) how to generate increasingly challenging problem instances, and (2) how to design solvers that can co-evolve alongside rising problem complexity. Addressing these challenges requires a fully automated, mutually reinforcing framework that can simultaneously synthesize harder instances and adapt solver strategies in response. To address these challenges, we introduce EALG (Evolutionary Adversarial Generation of Language Model–Guided Generators), a novel framework that leverages large language models to co-evolve optimization problem instances and their corresponding heuristic solvers. EALG iteratively mutates instance-generation programs to produce increasingly complex and difficult problems, while concurrently synthesizing more adaptive solver code. This adversarial co-evolution loop enables the solver and problem to continuously challenge and improve each other. Experimental results show that EALG can generate problem instances that are significantly more challenging than existing benchmarks, while simultaneously synthesizing heuristic solvers with strong performance and generalization capabilities—all achieved without manual intervention. This framework paves a new path for LLM-driven benchmark generation and solver co-evolution in combinatorial optimization. We summarize our key contributions as follows: • We introduce EALG , a novel framework that enables fully automated co-evolution of optimization instances and solver algorithms via large language models. • We develop a mutation-based adversarial mechanism that adaptively modifies instance generation procedures to yield increasingly challenging optimization problems. • We propose a structured generation process that leverages large language model to automatically synthesize adaptive, high-quality heuristic algorithms without human intervention. • We empirically validate EALG across multiple combinatorial optimization tasks, demonstrating the generation of more challenging problem instances and the synthesis of solvers that achieve state-of-the-art performance. 2 Related Work 2.1 Classical and Heuristic Methods for Combinatorial Optimization Classical approaches to combinatorial optimization can be broadly categorized into exact algorithms and heuristic methods. Exact algorithms such as branch-and-bound [ 24 ] guarantee optimal solutions but suffer from poor scalability as problem size increases. To address this, heuristic approaches like greedy algorithms and local search are often employed to provide efficient, though suboptimal, solutions. Metaheuristics—such as simulated annealing [ 29 ] and ant colony optimization [ 6 ] —offer improved scalability and have demonstrated strong empirical performance on problems such as the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) [ 2 , 17 ] . 2.2 Benchmark Design and Instance Difficulty Beyond designing effective solvers, constructing benchmark datasets with high discriminatory power is critical for evaluating and comparing algorithm performance [ 30 ] . While the widely-used TSPLIB [ 25 ] has been a standard in the literature [ 31 , 21 , 15 ] , it does not support instance difficulty adjustment based on solver capabilities. Other datasets generated by fixed-range random sampling often yield uniform or easy instances that lack diversity and fail to challenge solvers across a range of difficulty levels [ 30 ] . On such datasets, solvers frequently converge to similar optima, making it difficult to assess their relative strengths [ 18 , 38 , 27 ] . In contrast, our proposed EALG framework actively generates challenging problem instances that significantly amplify performance differences across solvers. 2.3 Adversarial Training in Combinatorial Optimization Adversarial training, originally developed in the context of image generation via Generative Adversarial Networks (GANs) [ 9 ] , has shown promise in synthesizing high-quality, diverse data [ 44 , 14 ] . Inspired by this success, recent research has applied adversarial ideas to combinatorial optimization [ 36 , 34 , 11 , 10 ] , primarily to improve solution quality or enhance solver generalization. These approaches typically focus on optimizing solutions via adversarial learning objectives. In contrast, our work introduces a co-evolutionary adversarial framework that simultaneously evolves both instance generators and solvers. 2.4 Large Language Models for Optimization Recent advances have shown the potential of large language models (LLMs) in tackling a variety of optimization tasks by leveraging their strong generalization and program synthesis capabilities [ 41 , 13 , 35 , 43 , 12 ] . Common strategies include few-shot prompting [ 4 ] , code completion [ 5 ] , and feedback-guided iterative refinement [ 18 , 39 , 40 ] . Within combinatorial optimization, LLMs are primarily used as solvers [ 37 , 20 , 42 , 32 ] , generating and refining candidate solutions through code synthesis. They are often integrated with evolutionary techniques such as genetic algorithms to iteratively improve solution quality [ 19 , 18 , 39 ] , demonstrating growing potential as hybrid learning and search agents. 3 LLM-Based Hard Instance Generator Let \mathcal{G} denote the space of instance generators g:\mathcal{Z}\rightarrow\mathcal{I} , where \mathcal{Z} is a latent seed space and \mathcal{I} represents the space of TSP instances. Each g\in\mathcal{G} is an executable heuristic function by a language model \mathcal{L}_{\text{inst}} , conditioned on a natural language prompt \mathcal{P}_{\text{inst}} . Formally, g\sim\mathcal{L}_{\text{inst}}(\mathcal{P}_{\text{inst}}),\quad I=g(z),\;z\sim\mathcal{Z}. (1) The resulting generator g defines a programmatic distribution over instances via algorithmic logic, spatial sampling patterns, and geometric transformations. To quantify the difficulty of generated instances in a normalized and scale-invariant manner, we used the relative optimality gap as: \text{Gap}(I;h)=\frac{\mathbb{E}_{i=1}^{n}\left[f(h(I_{i}))\right]}{\mathbb{E}_{i=1}^{n}\left[f^{*}(I_{i})\right]}-1, (2) where \{I_{1},\dots,I_{n}\} are instances generated by the instance generator g , f(h(I_{i})) is the cost of the heuristic solution, and f^{*}(I_{i}) is the cost of the