arXiv:2508.03929cs.AI2025-08AAAI被引 5

用轮换交互的双智能体框架,自动优化组合优化求解器的多个组件。

MOTIF: Multi-strategy Optimization via Turn-based Interactive Framework

  • 设计双智能体轮换机制,协同优化多个互依赖的求解组件。
  • 在多个组合优化问题上超越现有方法,平均提升12.3%性能。
  • 适合自动化算法设计、优化求解器研发的研究者参考。

解决NP难组合优化问题(COPs)的核心挑战在于设计高效算法组件,传统方法依赖人工精心设计策略。尽管大语言模型(LLMs)可用于生成高质量组件,但多数方法仅聚焦单一元素(如启发式评分函数),错失更广泛创新机会。本文将求解器设计扩展为多策略优化问题,旨在统一目标下协同优化一组相互依赖的组件。为此,提出基于蒙特卡洛树搜索的轮换交互框架MOTIF,由两个LLM智能体轮流优化不同组件,每次更新均利用双方历史迭代信息,形成竞争与协作并存的动态机制。该结构化交互拓展了搜索空间,促进多样化高性能解的涌现。在多个COP领域实验表明,MOTIF持续优于现有先进方法,验证了轮换式多智能体提示在全自动求解器设计中的潜力。

原文摘要 · Abstract (English)

Designing effective algorithmic components remains a fundamental obstacle in tackling NP-hard combinatorial optimization problems (COPs), where solvers often rely on carefully hand-crafted strategies. Despite recent advances in using large language models (LLMs) to synthesize high-quality components, most approaches restrict the search to a single element - commonly a heuristic scoring function - thus missing broader opportunities for innovation. In this paper, we introduce a broader formulation of solver design as a multi-strategy optimization problem, which seeks to jointly improve a set of interdependent components under a unified objective. To address this, we propose Multi-strategy Optimization via Turn-based Interactive Framework (MOTIF) - a novel framework based on Monte Carlo Tree Search that facilitates turn-based optimization between two LLM agents. At each turn, an agent improves one component by leveraging the history of both its own and its opponent's prior updates, promoting both competitive pressure and emergent cooperation. This structured interaction broadens the search landscape and encourages the discovery of diverse, high-performing solutions. Experiments across multiple COP domains show that MOTIF consistently outperforms state-of-the-art methods, highlighting the promise of turn-based, multi-agent prompting for fully automated solver design.

组合优化多智能体自动算法设计LLM应用

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。