用对抗共进化让算法和测试题一起变难,提升算法适应力
ACEvo: Adversarial Co-Evolution of Problem Distributions and Solvers for Combinatorial Optimization
- LLM同时生成难题和解法,两者在循环中互相挑战优化
- 生成的难题使解法与基准相比差距更大,且在分布漂移下表现更优
- 适合研究大模型如何自适应生成算法与测试环境
大语言模型(LLMs)被用于生成启发式算法,但现有方法多在固定基准分布上优化求解器。这种静态设置会掩盖求解器弱点,并限制对模型算法在分布变化下的适应能力的理解。本文提出对抗共进化(ACEvo)框架,通过闭环机制让LLM迭代生成两类可执行程序:启发式求解器和问题生成器。生成器持续提出更具挑战性的实例,求解器则随之优化以应对不断演化的分布,形成自动化的对抗性训练课程。我们在路由问题(包括TSP、OP、CVRP)上实现该框架,结果表明生成的实例分布始终产生比标准基准更大的最优性差距,且所获求解器在分布漂移下优于静态训练基线。此外,ACEvo还为研究大模型算法设计在演化分布下的行为提供了实验平台,揭示了反思变异、对抗反馈和协同适应如何塑造生成器与求解器的演化路径。结果表明,闭环共进化是利用语言模型不仅生成算法,还构建自适应评估环境的有力范式。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。