用博弈论让代码与题目互相进化，提升大模型发现算法的泛化能力
Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery
- 将求解器与题目生成器建模为零和博弈，双向迭代优化
- 在多个组合优化任务中显著优于静态训练基线，对分布外数据更鲁棒
- 适合研究自动算法发现、强化学习与对抗训练的学者
大语言模型（LLMs）推动了自动启发式发现（AHD）的快速发展，但现有方法大多受限于对固定实例分布的静态评估，导致过拟合并缺乏分布外泛化能力。本文提出算法空间响应预言机（ASRO），一种基于博弈论的框架，将启发式发现重新定义为求解器与实例生成器之间的程序级协同演化。ASRO将二者互动建模为双人零和博弈，分别维护不断增长的策略池，并通过大模型驱动的最佳响应预言机，针对混合对手元策略进行迭代扩展，从而以自生成的动态课程替代静态评估。在多个组合优化领域中，ASRO持续优于基于相同程序搜索机制的静态训练基线，在多样化及分布外实例上展现出显著增强的泛化性与鲁棒性。
原文摘要 · Abstract (English)
Large language models (LLMs) have enabled rapid progress in automatic heuristic discovery (AHD), yet most existing methods are predominantly limited by static evaluation against fixed instance distributions, leading to potential overfitting and poor generalization under distributional shifts. We propose Algorithm Space Response Oracles (ASRO), a game-theoretic framework that reframes heuristic discovery as a program level co-evolution between solver and instance generator. ASRO models their interaction as a two-player zero-sum game, maintains growing strategy pools on both sides, and iteratively expands them via LLM-based best-response oracles against mixed opponent meta-strategies, thereby replacing static evaluation with an adaptive, self-generated curriculum. Across multiple combinatorial optimization domains, ASRO consistently outperforms static-training AHD baselines built on the same program search mechanisms, achieving substantially improved generalization and robustness on diverse and out-of-distribution instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。