Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search

This paper introduces a closed-loop, large-language-model-driven evolutionary framework that automatically reconstructs all seven key components of Adaptive Large Neighborhood Search (ALNS), achieving superior performance on TSPLIB benchmarks and revealing novel design patterns through a MAP-Elites guided process.

The Gist

Imagine you are trying to solve a massive, impossible-looking puzzle: the Traveling Salesman Problem. You need to find the shortest possible route for a delivery truck to visit 100 different cities and return home. Doing this by hand is like trying to find a needle in a haystack while wearing blindfolded gloves.

For decades, the best way to solve this has been using a method called ALNS (Adaptive Large Neighborhood Search). Think of ALNS as a highly skilled, but very traditional, master chef. This chef has a recipe book with specific rules:

1. Destroy: "Take out 20% of the ingredients randomly."
2. Repair: "Put them back in the cheapest spots."
3. Decide: "If the new dish tastes worse, throw it away unless it's really bad."

The problem? This chef has been cooking for 20 years using the same old recipe. If you ask the chef to cook a new type of cuisine (a new logistics problem), they struggle because they rely on human intuition and trial-and-error. They can't easily invent new ways to chop vegetables or season the soup.

The Big Idea: The AI "Evolutionary Kitchen"

This paper introduces a revolutionary new kitchen. Instead of a human chef, they built a robotic kitchen powered by a super-smart AI (a Large Language Model).

But here's the twist: They didn't just ask the AI to write a new recipe. They asked the AI to evolve the entire kitchen from scratch.

1. Breaking the Chef into Seven Parts

The researchers realized that the "chef" is actually made of seven distinct tools. They broke the ALNS algorithm down into seven "modules" and told the AI to reinvent every single one of them:

• The Destroyer: How to break the current route apart.
• The Repairer: How to fix the broken route.
• The Selector: Which tool to pick next.
• The Scorekeeper: How to update the "best so far" score.
• The Starter: How to make the first guess.
• The Judge: Whether to accept a worse solution (to avoid getting stuck).
• The Controller: How much to break the route at any given time.

2. The "Survival of the Fittest" Game

The AI doesn't just guess once. It plays a game of evolution, similar to how nature evolves animals over millions of years, but sped up to happen in hours.

• The Loop: The AI generates a new version of a tool (e.g., a new "Destroyer").
• The Test: It puts this new tool into a "sparring ring" with the other six tools (which are still the old, classic versions) and lets it try to solve the puzzle.
• The Score: If the new tool finds a better route, it gets a high score. If it fails, it's discarded.
• The Archive (The "Elite Pool"): The researchers use a special system called MAP-Elites. Imagine a museum where they don't just keep the best tool, but the most diverse tools. They keep a "Destroyer" that is great at small cities, another that is great at clustered cities, and another that is great at speed. This ensures the AI doesn't get stuck in one way of thinking.

3. The Results: The AI Chef Outsmarts the Human Master

After thousands of generations of this digital evolution, the AI produced a completely new algorithm. When they tested it against the classic human-designed chef:

• Better Solutions: The AI found routes that were significantly shorter. On large, difficult puzzles, the "gap" between the AI's solution and the perfect solution dropped from 3.18% down to 0.74%. That's like the AI finding a shortcut that saves the delivery company thousands of dollars.
• Faster: The AI didn't just find better answers; it found them faster. It was like the AI chef learned to chop vegetables with a laser while the human chef was still using a dull knife.
• Surprising Discoveries: The AI invented strategies that humans would never think of.
  • Example: The classic rule is "If you make a mistake, you get punished." The AI invented a rule that says, "If you make a small mistake, ignore it and keep going. Only punish big mistakes." This helped the AI escape "dead ends" in the puzzle that would trap a human.
  • Example: The AI learned to "forget" the tools it just used, forcing itself to try new things instead of getting stuck in a loop of doing the same thing over and over.

The Takeaway

This paper proves that we don't need to rely on human experts to design complex optimization algorithms anymore. By letting an AI evolve every single part of the system simultaneously, we can create "super-algorithms" that are smarter, faster, and more adaptable than anything a human could design alone.

It's like going from a hand-crafted wooden cart to a self-driving electric car. The human engineer built the cart, but the AI evolved the car, discovering physics and engineering principles that the human never even considered.

Technical Summary

Here is a detailed technical summary of the paper "Large Language Model–Driven Full-Component Evolution of Adaptive Large Neighborhood Search" by Yu, Chen, and Liu.

1. Problem Statement

Adaptive Large Neighborhood Search (ALNS) is a leading metaheuristic for combinatorial optimization (e.g., TSP, VRP). However, its development suffers from a "manual design bottleneck":

• Reliance on Expertise: Traditional ALNS relies on hand-crafted operators and heuristics tuned by domain experts through tedious trial-and-error.
• Static Limitations: While ALNS adapts operator selection probabilities, higher-level logic (weight update formulas, acceptance criteria, destruction rates) is often hard-coded and static.
• Unbalanced Evolution: Existing automated design efforts (e.g., ReEvo, LMO) typically evolve only local operators while keeping decision and control layers fixed, creating performance bottlenecks due to the "weakest link" in the algorithmic chain.

The paper addresses the need for a full-pipeline automated design framework that can systematically redesign all components of ALNS, from low-level operators to high-level control logic, to overcome human bias and discover non-intuitive, high-performance strategies.

2. Methodology

The authors propose a closed-loop, Large Language Model (LLM)-driven evolutionary framework that decouples ALNS into seven independent modules and evolves them simultaneously.

A. Framework Architecture

The system operates in a "Generate–Evaluate–Feedback" loop:

1. Decoupling: ALNS is decomposed into seven key modules:
   • Solution Operations: Destroy operators, Repair operators, Initial solution generator.
   • Adaptive Mechanism: Operator selector, Weight updater.
   • Global Control: Acceptance rule, Destruction-rate controller.
2. Evolution Engine: An LLM acts as an "intelligent mutation operator." It receives a prompt containing the current code, historical performance feedback, and hard constraints (e.g., Python/NumPy only, specific function signatures).
3. Quality-Diversity Search (MAP-Elites): To prevent premature convergence to a single local optimum, the framework uses the MAP-Elites mechanism. It maintains an elite archive mapping solutions to a multi-dimensional behavior space (e.g., Solution Quality vs. Stability vs. Diversity). This ensures the evolution explores diverse algorithmic structures while maximizing performance.
4. Isolated Evaluation: To accurately attribute performance gains, each component is evolved in an isolated environment where all other components are fixed to classic textbook implementations (e.g., evolving a "Destroy" operator while using a fixed "Greedy Repair").

B. Prompt Design & Evaluation

• Prompting: Uses a "fixed instruction + dynamic context" strategy. The LLM is role-played as an optimization expert and provided with historical metrics (gap, stability) to guide code generation.
• Scoring Function: A multi-objective quality model is used:
  $$Quality = \alpha \cdot S_{gap} + \beta \cdot S_{stability} - \gamma \cdot P_{penalty}$$
  Where $S_{gap}$ is the solution gap score, $S_{stability}$ is performance consistency, and $P_{penalty}$ accounts for runtime or diversity constraints.

3. Key Contributions

1. Full-Component Co-Evolution: Unlike prior work focusing only on operators, this framework evolves all seven core components of ALNS, enabling a systematic reshaping of the entire algorithm architecture.
2. Discovery of Non-Intuitive Logic: The LLM-generated algorithms uncovered counter-intuitive but effective design patterns, such as:
   • Momentum-based Bayesian Bandits: Aggressively rewarding operators with rapidly improving performance while down-weighting recently used ones to break "winner-takes-all" path dependence.
   • Adaptive Tolerance Buffers: A modified acceptance criterion that treats small degradations as "noise" (accepting them outright) rather than penalizing them immediately, facilitating escape from local optima.
   • Hybrid Regret Insertion: Combining regret scores with absolute insertion costs to balance structural necessity with cost efficiency.
3. Fine-Grained Attribution & Model Analysis: The study provides a rigorous ablation analysis of component contributions and compares the evolutionary capabilities of four frontier LLMs (GPT-5.2, Grok-Code, DeepSeek-v3.2, MiniMax-m2), revealing trade-offs between early-stage efficiency and long-run convergence.

4. Experimental Results

The framework was tested on TSPLIB benchmarks (24 evolution instances, 18 unseen test instances) under fixed-iteration (1k, 25k) and fixed-time (60s) budgets.

• Performance vs. Baseline: The evolved algorithm (Evolved-GPT) significantly outperformed a human-tuned Baseline-ALNS.
  • Fixed Iterations (1,000): Optimality gap reduced from 3.18% to 0.74% on large-scale test instances (a 76.6% improvement).
  • Fixed Time (60s): The evolved model showed superior computational efficiency, reducing gaps by ~60–80% across all instance sizes compared to the baseline.
  • Scalability: Gains were most pronounced on large-scale instances ($N > 300$), where the average gap dropped from 3.18% to 0.74% under a 25,000-iteration budget.
• Ablation Study:
  • Destroy/Repair Operators: The most critical components. Removing evolved destroy operators degraded performance by 136%, and removing repair operators by 76%.
  • Destruction Controller: Removing this caused a 66% drop, highlighting the importance of dynamic perturbation strength.
  • Other Components: Acceptance criteria, weight updaters, and selectors provided incremental but consistent gains (4–12% impact).
• LLM Comparison:
  • GPT-5.2 demonstrated the most consistent performance across fixed iterations and long budgets.
  • DeepSeek-v3.2 excelled in early-stage efficiency (short time budgets).
  • Grok-Code showed strong long-run convergence, comparable to GPT-5.2.
  • Statistical tests (Wilcoxon signed-rank) confirmed the improvements were significant ($p < 0.001$).

5. Significance

• Paradigm Shift: This work moves algorithm design from "expert-crafted" to "automatically evolved," demonstrating that LLMs can not only generate code but also discover novel algorithmic logic that surpasses human intuition.
• Practical Impact: The evolved algorithms offer a "plug-and-play" solution for complex logistics and production optimization problems, reducing development time and cost while delivering higher solution quality and faster convergence.
• Theoretical Insight: The discovery of specific mechanisms (e.g., tolerance buffers in acceptance, hybrid regret scoring) provides new theoretical building blocks for future metaheuristic design, suggesting that "non-intuitive" logic often yields superior computational results.
• Model Selection Guidance: The study offers empirical evidence for selecting specific LLMs based on the desired outcome (e.g., speed vs. ultimate optimality) in automated algorithm design tasks.