ACEvo: Adversarial Co-Evolution of Problem Distributions and Solvers for Combinatorial Optimization

arXiv:2506.02594v2 Announce Type: replace Abstract: Large language models (LLMs) are increasingly used to synthesize heuristic programs, yet most existing pipelines optimize solvers against fixed benchmark distributions. This static setup can obscure solver weaknesses and limit understanding of how LLM-designed algorithms adapt under distribution shift. We present Adversarial Co-Evolution (ACEvo), a closed-loop framework in which LLMs iteratively co-evolve two types of executable programs: heuristic solvers and problem generators. The generator proposes increasingly challenging instances, while the solver is refined to improve performance on the evolving distribution, forming an automated adversarial curriculum for program design and evaluation. We instantiate ACEvo on routing problems, including TSP, OP, and CVRP. Across these domains, the framework produces instance distributions that consistently induce larger optimality gaps than standard benchmarks and yields solver programs that outperform those obtained from static-training baselines under distribution shift. Beyond final performance, ACEvo provides a testbed for studying LLM-based algorithm design under evolving distributions, including how reflective mutation, adversarial feedback, and co-adaptation shape the evolution of both generators and solvers. These results suggest that closed-loop co-evolution is a promising paradigm for using language models not only to generate algorithms, but also to construct adaptive evaluation environments.

Source: arXiv cs.AI | 2026-08-11