Evolutionary AI Agents for Automated Combinatorial Optimization

Recent advances in large language models (LLMs) and AI agents have opened up new opportunities for automated combinatorial optimization. However, existing LLM/agent-based automated algorithm/heuristic design methods heavily rely on users to manually configure problem-dependent tools, heuristics, and iterative pipelines. To go beyond such design-level automation, we introduce Automated Problem Solving (APS), which enables AI agents to autonomously discover and organize the entire problem-solving process for combinatorial optimization. We further propose EvoAge, a self-evolving agentic framework for APS that explores, composes, and evolves reusable skills via evolutionary optimization. Inspired by natural evolution, EvoAge treats problem-solving trajectories, rather than individual heuristics or algorithms, as evolvable units and employs evolutionary search to automatically discover novel problem-solving strategies. It further distills successful experience into reusable skills and continuously evolves its skill library, enabling capabilities to accumulate, adapt, and expand across diverse tasks in an open-ended environment. Experiments across four classes of combinatorial optimization problems show that EvoAge obtains skills that can autonomously solve them without any human design or intervention and consistently outperforms state-of-the-art LLM/agent-based methods, demonstrating the effectiveness and huge potential of APS as a new paradigm for combinatorial optimization.