Overview
This research introduces a closed-loop, large language model (LLM)-driven evolutionary framework designed to automatically reconstruct and evolve all components of Adaptive Large Neighborhood Search (ALNS). ALNS is a metaheuristic widely applied in production and logistics optimization. The framework aims to address the reliance on hand-crafted components in traditional ALNS, which can slow development and make adaptation to new problems costly.
Research Context
Adaptive Large Neighborhood Search (ALNS) has been a prominent technique for optimization problems in areas like production and logistics. Historically, its success has depended on components—such as destroy and repair operators—that were manually designed based on expert experience. This expert-driven development process often results in slow development cycles and challenges in adapting ALNS to novel or evolving problem types.
The proposed framework seeks to move beyond this reliance on manual design by automating the creation and evolution of ALNS components using large language models. The evolution targets both solution quality and strategic diversity through mechanisms like multi-dimensional elite archiving.
Approach
The framework systematically decomposes ALNS into seven distinct modules: destroy, repair, operator selection, weight update, initial solution construction, acceptance rule, and destroy-rate control. Each of these modules is subjected to dedicated evolutionary tasks within the framework.
A key mechanism integrated into the framework is the Multi-dimensional Archive of Phenotypic Elites (MAP-Elites). This mechanism is employed to maintain a multi-dimensional elite archive, simultaneously guiding the evolution towards improved solution quality and enhanced strategic diversity among the evolved algorithms.
The research also explores various evolutionary paradigms, including parallel and sequential multi-module evolution, as well as single-expert-driven and multi-expert-driven evolution. These paradigms were evaluated to understand their impact on the performance of the generated algorithms.
The proposed system utilizes large language models to drive this evolutionary process, decoupling the components and rebuilding them automatically. Comparisons across multiple language models were also conducted to assess their differing capabilities in supporting evolutionary algorithm design.
Findings
- Evolved algorithms consistently outperformed optimized classic ALNS baselines. This superior performance was observed under both fixed-iteration and fixed-time limits during evaluations.
- The evaluations were conducted on established benchmarks for the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP).
- The framework demonstrated a degree of generalizability, indicating its applicability beyond the specific problems directly optimized.
- Cross-problem transferability was also observed, suggesting that design patterns or components evolved for one problem might be applicable, to some extent, to other related problems.
- Code analysis of the evolved algorithms revealed several design patterns. These patterns were described as counterintuitive yet meaningful, emerging naturally during the evolutionary process.
- Comparisons among different large language models highlighted clear differences in their effectiveness and ability to support the evolutionary algorithm design process.
Why This Matters
The findings offer practical and theoretical insights for the future design of ALNS, particularly through the identification of counterintuitive yet meaningful design patterns that emerged naturally from the evolutionary process. The observed differences in large language models' capabilities for evolutionary algorithm design can guide model selection for real-world engineering applications.