MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

Imagine you are trying to solve a massive, messy puzzle, like organizing a delivery truck route for hundreds of stops or packing a suitcase with the most valuable items possible. These are "combinatorial optimization problems," and they are notoriously difficult because the number of possible ways to arrange the pieces is so huge that even the fastest supercomputers can't check them all. For decades, humans have tried to write special "rules of thumb" (called heuristics) to solve these puzzles quickly. But here's the catch: a rule that works perfectly for a city with a grid-like street layout might fail miserably in a city with winding, circular roads. This is the "No Free Lunch" reality: there is no single magic rule that works for every situation.

Recently, scientists started using "Large Language Models" (LLMs)—the same kind of AI that writes stories and answers questions—to automatically invent these rules. However, most of these AI experiments were like training a student only on a single, small textbook. The AI would get really good at solving the problems in that specific book, but if you gave it a slightly different puzzle, it would get confused. It was like teaching a chef to make a perfect omelet, but only using eggs from one specific farm; if you gave them eggs from a different farm, the omelet might fall apart. The old way of training these AIs also relied on very simple feedback, like a teacher just saying "Good job" or "Bad job" without explaining why or where the mistake happened.

Enter MOSAIC, a new framework developed by researchers at the Georgia Institute of Technology. Think of MOSAIC not as a single student trying to memorize a textbook, but as a massive, living library where different "specialist" rules are trained for different types of puzzles. Instead of just asking an AI to "make a better rule," MOSAIC sets up a high-stakes game of cat and mouse. It pits the AI's current rules against a team of "adversarial" puzzle-makers. These puzzle-makers are also AI, and their only job is to create the hardest, most confusing puzzles specifically designed to break the current rules. When a rule fails, the system doesn't just say "you lost." It uses a smart decision tree to figure out exactly what kind of puzzle broke the rule, and then stores that puzzle and the lesson learned in a specific "cell" of a giant grid. Over time, this grid fills up with a diverse collection of specialists: one rule for grid-like cities, another for clustered neighborhoods, another for long, winding routes. The system then uses these stored lessons to evolve even better rules, creating a team of experts where each one is a master of their own specific territory.

The researchers tested this idea on three classic problems: the Traveling Salesman Problem (finding the shortest route), the Knapsack Problem (packing the most value), and the Capacitated Vehicle Routing Problem (delivering goods with limited truck space). They found that MOSAIC consistently outperformed other state-of-the-art AI methods. While other methods struggled when the puzzles changed slightly, MOSAIC's "team of specialists" handled the changes with ease, often finding solutions that were significantly closer to the perfect answer. For instance, on the Traveling Salesman Problem, MOSAIC's best team of rules was up to 22% more accurate than the next-best method.

Perhaps even more exciting, the "adversarial" puzzles MOSAIC created were far more diverse and challenging than those made by traditional methods. The system managed to cover 33% more of the "feature space" (the different types of puzzle structures) than previous methods, meaning it learned to handle a much wider variety of real-world scenarios. The study suggests that by treating the problem as a co-evolutionary battle—where the puzzles get harder to expose weaknesses, and the rules get smarter to fix them—we can build AI that doesn't just memorize a few examples, but truly understands the landscape of the problem. It's a shift from training a single genius who knows everything about one thing, to building a diverse community of experts who know a little bit about everything, and a lot about their specific corner of the world.