ACEvo: 조합 최적화를 위한 문제 분포 및 솔버의 적대적 공진화

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

최근 대규모 언어 모델(LLM)은 휴리스틱 프로그램을 생성하는 데 점점 더 많이 사용되고 있지만, 대부분의 기존 파이프라인은 고정된 벤치마크 분포에 대한 솔버를 최적화합니다. 이러한 정적인 설정은 솔버의 약점을 가리고 LLM 설계 알고리즘이 분포 변화에 어떻게 적응하는지에 대한 이해를 제한할 수 있습니다. 본 논문에서는 LLM이 휴리스틱 솔버와 문제 생성기를 반복적으로 공진화시키는 폐루프 프레임워크인 Adversarial Co-Evolution (ACEvo)을 제시합니다. 생성기는 점차 더 어려운 인스턴스를 제안하고, 솔버는 진화하는 분포에 대한 성능을 개선하도록 개선되어 프로그램 설계 및 평가를 위한 자동화된 적대적 커리큘럼을 형성합니다. ACEvo를 라우팅 문제(TSP, OP, CVRP 포함)에 적용한 결과, 이 프레임워크는 표준 벤치마크보다 일관되게 더 큰 최적성 간극을 유발하는 인스턴스 분포를 생성하며, 분포 변화 하에서 정적 학습 기준보다 우수한 성능의 솔버 프로그램을 제공합니다. 최종 성능 외에도 ACEvo는 LLM 기반 알고리즘 설계가 진화하는 분포 환경에서 어떻게 작동하는지 연구하기 위한 테스트베드를 제공합니다. 여기에는 반사적 돌연변이, 적대적 피드백 및 공진화가 생성기와 솔버의 진화를 어떻게 형성하는지가 포함됩니다. 이러한 결과는 폐루프 공진화가 언어 모델을 사용하여 알고리즘을 생성할 뿐만 아니라 적응형 평가 환경을 구축하는 데 유망한 패러다임임을 시사합니다.

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.