Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search
Authors: Shaohua Yu, Tianyu Chen, Linyan Liu, Jakob Puchinger
Organizations: School of Intelligent Science and Technology, Nanjing University of Science and Technology, Nanjing 210094, China · School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China · Université Paris-Saclay, CentraleSupélec, Laboratoire Génie Industriel, 91190, Gif-sur-Yvette, France · EM Normandie Business School, Métis Lab, 92110, Clichy, France
Adaptive Large Neighborhood Search (ALNS) is a prominent metaheuristic and a widely adopted approach for production and logistics optimization. However, it has long relied on hand-crafted components built on expert experience, which makes development slow and costly to adapt to new problems. This paper proposes a closed-loop, large-language-model-driven evolutionary framework that decouples ALNS and automatically rebuilds all of its components. We break ALNS into seven key modules: destroy, repair, operator selection, weight update, initial solution construction, acceptance rule, and destroy-rate control, and evolve each module through a dedicated task. By incorporating the Multi-dimensional Archive of Phenotypic Elites mechanism, the framework maintains a multi-dimensional elite archive to simultaneously drive the evolution of solution quality and strategic diversity. In addition, we design multiple mechanisms, including parallel and sequential multi-module evolution as well as single-expert-driven and multi-expert-driven evolution, to systematically evaluate the impact of different evolutionary paradigms on algorithm generation performance. Evaluations on Traveling Salesman Problem and Capacitated Vehicle Routing Problem benchmarks demonstrate that evolved algorithms consistently outperform optimized classic ALNS baselines under both fixed-iteration and fixed-time limits. The framework also shows a degree of generalizability and cross-problem transferability. Code analysis also uncovers several counterintuitive yet meaningful design patterns that emerged naturally during evolution, offering practical and theoretical insights for future ALNS design. Finally, comparisons across multiple language models highlight clear differences in their ability to support evolutionary algorithm design, helping guide model selection for real-world engineering use.
Figures & tables
Figure 1: Closed-loop evolution process based on an LLM
Component
Primary Input Context
Output Requirements
Layer 1: Solution Operators
Destroy Operator
Solution state, removal size k , instance data
Partial solution and a list of removed elements.
Repair Operator
Partial solution, removed elements, instance data
A reconstructed feasible solution.
Initial Solution Generator
Problem instance data (matrices, constraints)
A valid initial solution.
Layer 2: Adaptive Mechanisms
Operator Selector
Operator weights and historical performance
Selected destroy and repair operator pair.
Table 1: Specifications for the Seven Evolved ALNS Components.
Figure 2: The two methodological axes that define the four evolution paradigms studied in this paper.
Component
Strategy and description
Destroy operators
∙ Random Destroy : randomly remove k nodes.
∙ Worst Destroy : remove nodes yielding largest cost decrease.
∙ Shaw Destroy : remove similar nodes based on relatedness.
Repair operators
∙ Greedy Repair : reinsert at position with smallest cost increase.
∙ Regret-2 Repair : insert based on the two largest regret values.
∙ Regret-3 Repair : insert based on the three largest regret values.
Table 2: Component configuration of Baseline-ALNS.
1,000 Iterations
10,000 Iterations
60 Seconds
Problem
Evolution Mode
Small-Evo
Med-Evo
MS-Test
Lg-Test
Small-Evo
Med-Evo
MS-Test
Lg-Test
Small-Evo
Med-Evo
MS-Test
Lg-Test
TSP
Baseline-ALNS
1.714 38.86s
2.007 285.79s
2.749 705.16s
4.177 4,721.02s
0.300 266.78s
1.071 2,842.05s
1.326 6,965.08s
3.251 45,765.72s
1.662 1,176.1
3.723 206.2
6.135 147.1
10.378 14.4
Parallel + SE (default)
0.239 3.89s
0.485 24.72s
1.230 45.99s
1.844 216.69s
0.047 37.98s
0.161 377.91s
0.493 681.03s
1.026 3423.82s
0.098 2,992
0.449 2,275
1.138 998
2.680 299
Parallel + ME
0.319 13.71s
0.558 73.39s
1.329 140.98s
1.987 640.92s
0.086 91.22s
0.204 631.22s
0.559 1263.85s
1.214 5545.81s
0.215 3,744
0.608 870
1.582 679
3.729 53
Serial + SE
0.117 33.6s
0.291 340.49s
0.757 775.35s
1.624 4364.59s
0.038 255.34s
0.144 4026.98s
0.492 9009.49s
1.108 59599.22s
0.218 498
0.760 188
1.652 131
3.900 24
Serial + ME
0.203 27.7s
0.459 306.34s
1.107 789.11s
2.209 4465.37s
0.035 177.49s
0.116 2868.91s
0.323 6758.24s
0.941 44873.98s
0.171 941
0.791 291
2.466 211
4.461 52
Table 3: Average optimality gap (%) of evolution paradigms on TSP and CVRP benchmarks under three computational budgets.
Figure 4: Macro-level comparison of evolution paradigms across problems and computational budgets.
Problem
Mode
Base GAP
Destroy
Repair
Initial
Selector
Weight
Acceptance
D. Ctrl.
TSP
Parallel + SE
1.848 2.607
0.487 (73.6) 0.997 (61.8)
1.672 (9.5) 0.792 (69.6)
1.112 (39.8) 1.475 (43.4)
1.384 (25.1) 2.706 (-3.8)
1.508 (18.4) 2.653 (-1.8)
1.280 (30.7) 2.243 (14.0)
0.806 (56.4) 1.925 (26.2)
TSP
Parallel + ME
1.848 2.607
0.464 (74.9) 0.640 (75.5)
1.632 (11.7) 0.726 (72.2)
0.898 (51.4) 0.974 (62.6)
1.366 (26.1) 1.993 (23.6)
1.450 (21.5) 2.095 (19.6)
1.340 (27.5) 1.739 (33.3)
0.631 (65.9) 1.084 (58.4)
TSP
Serial + SE
1.848 2.607
0.487 (73.6) 0.876 (66.4)
0.517 (72.0) 0.909 (65.1)
1.160 (37.2) 1.363 (47.7)
1.885 (-2.0) 2.627 (-0.8)
1.888 (-2.2) 2.554 (2.0)
1.663 (10.0) 2.441 (6.4)
1.147 (37.9) 2.103 (19.3)
TSP
Serial + ME
1.848 2.607
0.484 (73.8) 0.825 (68.4)
1.842 (0.3) 2.220 (14.8)
1.258 (31.9) 1.422 (45.5)
1.848 (0.0) 2.411 (7.5)
1.848 (0.0) 2.414 (7.4)
1.848 (0.0) 2.407 (7.7)
1.351 (26.9) 1.756 (32.6)
CVRP
Parallel + SE
4.602 3.219
4.558 (1.0) 2.722 (15.4)
1.525 (66.9) 0.865 (73.1)
2.642 (42.6) 1.773 (44.9)
4.104 (10.8) 2.589 (19.6)
4.023 (12.6) 2.435 (24.4)
2.018 (56.2) 1.890 (41.3)
4.556 (1.0) 2.788 (13.4)
CVRP
Parallel + ME
4.602 3.219
4.470 (2.9) 2.633 (18.2)
1.439 (68.7) 0.839 (73.9)
2.930 (36.3) 1.896 (41.1)
3.983 (13.5) 2.551 (20.8)
3.970 (13.7) 2.472 (23.2)
2.029 (55.9) 0.992 (69.2)
4.456 (3.2) 2.578 (19.9)
Table 4: Additive ablation results across evolution paradigms
Problem
Mode
Full GAP
Destroy
Repair
Initial
Selector
Weight
Acceptance
D. Ctrl.
TSP
Parallel + SE
0.352 0.259
0.384 (9.1) 0.253 (-2.3)
0.357 (1.4) 0.761 (193.8)
0.361 (2.6) 0.277 (7.0)
0.388 (10.2) 0.351 (35.5)
0.357 (1.4) 0.291 (12.4)
0.366 (4.0) 0.265 (2.3)
0.913 (159.4) 0.448 (73.0)
TSP
Parallel + ME
0.428 0.395
0.407 (-4.9) 0.391 (-1.0)
0.456 (6.5) 0.682 (72.7)
0.480 (12.2) 0.431 (9.1)
0.530 (23.8) 0.421 (6.6)
0.463 (8.2) 0.400 (1.3)
0.426 (-0.5) 0.399 (1.0)
0.625 (46.0) 0.194 (-50.9)
TSP
Serial + SE
0.197 0.466
0.353 (79.7) 0.638 (36.9)
0.306 (55.3) 0.569 (22.1)
0.235 (19.7) 0.486 (4.3)
0.214 (8.9) 0.441 (-5.4)
0.206 (4.8) 0.483 (3.7)
0.335 (70.4) 0.525 (12.7)
0.881 (347.8) 0.752 (61.4)
TSP
Serial + ME
0.320 0.455
1.014 (216.4) 1.005 (120.9)
0.423 (32.2) 0.591 (29.9)
0.385 (20.2) 0.568 (24.8)
0.320 (0.0) 0.469 (3.1)
0.320 (0.0) 0.456 (0.2)
0.320 (0.0) 0.463 (1.8)
1.080 (237.1) 0.711 (56.3)
CVRP
Parallel + SE
0.712 0.541
0.815 (14.5) 0.605 (11.8)
1.551 (118.0) 1.433 (164.9)
0.899 (26.4) 0.484 (-10.5)
0.727 (2.2) 0.515 (-4.8)
0.715 (0.5) 0.478 (-11.7)
1.060 (49.0) 0.576 (6.5)
0.673 (-5.4) 0.468 (-13.5)
CVRP
Parallel + ME
0.834 0.391
0.864 (3.6) 0.366 (-6.4)
1.475 (77.0) 0.797 (103.8)
1.019 (22.2) 0.388 (-0.8)
0.868 (4.1) 0.352 (-10.0)
0.892 (7.0) 0.341 (-12.8)
0.970 (16.3) 0.486 (24.3)
0.785 (-5.9) 0.342 (-12.5)
Table 5: Subtractive ablation results across evolution paradigms
Setting
Dataset split
Baseline
DeepSeek-V3.2
Grok-4.1-Fast
Gemini-3-Flash
1,000 iterations
Small-Evo
1.714%
0.365%
0.402%
0.239%
Med-Evo
2.007%
0.688%
0.803%
0.485%
MS-Test
2.749%
1.170%
1.425%
1.230%
Lg-Test
4.177%
2.089%
2.255%
1.844%
Runtime 60s
Small-Evo
1.662%
0.413%
0.058%
0.098%
Med-Evo
3.723%
1.404%
0.474%
0.449%
Table 6: Performance comparison of evolved algorithms driven by different LLMs (average GAP).
Direction
Evolution mode
Baseline
Native
Transfer
Transfer vs. Native Δ GAP / Δ Effort
Transfer vs. Baseline GAP improvement / Δ Effort
Panel A: Fixed iterations = 1,000; entries are mean GAP / Time(s)
CVRP → TSP
Parallel + SE
2.438 / 962.78
0.816 / 51.76
0.952 / 29.22
+16.7 / -43.6
+61.0 / -97.0
CVRP → TSP
Parallel + ME
2.438 / 962.78
0.908 / 154.98
0.794 / 36.29
-12.6 / -76.6
+67.4 / -96.2
CVRP → TSP
Serial + SE
2.438 / 962.78
0.561 / 944.62
0.861 / 590.81
+53.6 / -37.5
+64.7 / -38.6
CVRP → TSP
Serial + ME
2.438 / 962.78
0.815 / 952.17
1.366 / 539.00
+67.6 / -43.4
+44.0 / -44.0
TSP → CVRP
Parallel + SE
6.328 / 59.69
1.046 / 55.96
2.315 / 109.47
+121.2 / +95.6
+63.4 / +83.4
Table 7: Cross-problem transfer performance under four evolution modes, averaged over all benchmark instances.
Problem
Method
Mean
Standard deviation
Minimum
Median
Maximum
Best #
TSP ( n=40 )
Parallel + SE
0.95
0.88
0.00
0.73
2.80
25
Serial + ME
1.00
0.95
0.00
0.74
3.24
13
G-LNS
2.37
1.46
0.00
2.50
6.80
2
EoH-S
8.46
3.39
3.40
8.50
16.90
0
CVRP ( n=47 )
Parallel + SE
1.34
0.95
0.00
1.31
3.54
36
Serial + SE
1.77
1.29
0.00
1.61
5.08
11
Table 8: Comparison of Evolved-ALNS with G-LNS and EoH-S. Values are optimality gaps (%); lower is better. “Best #” counts instances where the method attains the strictly lowest gap among the four solvers.
The integration of Large Language Models (LLMs) into evolutionary frameworks has established a new paradigm for automated heuristic discovery. Despite their promise, these methods typically search in the discrete space of program syntax, relying on stochastic sampling to navigate a highly non-convex optimization landscape. This work proposes a continuous heuristic discovery framework that shifts optimization to a learned latent manifold. We employ an encoder to map discrete programs into continuous embeddings and train a differentiable surrogate model to predict performance, enabling gradient-based search. To regularize the optimization trajectory, an invertible normalizing flow maps these embeddings to a structured Gaussian prior, where we perform gradient ascent. The resulting optimized latent vectors are projected through a learned mapper into soft prompts, which condition a frozen LLM to synthesize novel executable heuristics. We evaluate the proposed method on the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), the Knapsack Problem (KSP), and Online Bin Packing (OBP). Empirical results demonstrate that continuous latent-space optimization achieves performance competitive with state-of-the-art discrete evolutionary baselines while offering a complementary methodological alternative for automated algorithm design. The implementation code is available at https://github.com/cheikh025/LHS.
The paradigm of automated program generation is shifting from one-shot generation to inference-time search, where Large Language Models (LLMs) function as semantic mutation operators within evolutionary loops. While effective, these systems are currently governed by static schedules that fail to account for the non-stationary dynamics of the search process. This rigidity results in substantial computational waste, as resources are indiscriminately allocated to stagnating populations while promising frontiers remain under-exploited. We introduce AdaEvolve, a framework that reformulates LLM-driven evolution as a hierarchical adaptive optimization problem. AdaEvolve uses an "accumulated improvement signal" to unify decisions across three levels: Local Adaptation, which dynamically modulates the exploration intensity within a population of solution candidates; Global Adaptation, which routes the global resource budget via bandit-based scheduling across different solution candidate populations; and Meta-Guidance which generates novel solution tactics based on the previously generated solutions and their corresponding improvements when the progress stalls. We demonstrate that AdaEvolve consistently outperforms the open-sourced baselines across 185 different open-ended optimization problems including combinatorial, systems optimization and algorithm design problems.
In this paper, we introduce ES-AHD, a novel framework that fundamentally integrates Evolution Strategy (ES) into Large Language Model (LLM)-driven Automatic Heuristic Design (AHD). Existing evolutionary approaches predominantly rely on random, individual-level mutation, leading to blind search and an imbalance between exploration and exploitation. To address these issues, ES-AHD introduces two core mechanisms. First, Semantic Recombination via LLMs discards traditional point-to-point reproduction. By leveraging the LLM's contextual reasoning to explicitly extract core insights from top-performing individuals, the algorithm establishes a promising semantic search direction. This transforms random code mutation into targeted, center-guided sampling inspired by ES. Second, Stochastic Covariance Adaptation via Temperature Sampling dynamically addresses the exploration-exploitation dilemma. By mapping the covariance matrix in ES to the LLM's sampling temperature, the framework employs a stochastic random walk mechanism with momentum. This approach primarily shrinks the search radius for micro-level code refinement, while retaining the critical ability to occasionally sample higher temperatures to escape semantic local optima. Ultimately, ES-AHD provides a highly directional, robust, and efficient search paradigm, significantly accelerating the generation of high-quality heuristic algorithms. The source code is available at: https://github.com/Mriya0306/ES-AHD.
Yutao Lai, Kezhao Lai, Hai-Lin Liu +2
School of Mathematics and Statistics Guangdong University of Technology Guangzhou, China · School of Computer Science and Technology Xidian University Xi’an, China · School of Systems Science Beijing Normal University Beijing, China