BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design
Summary: arXiv:2604.12898v1 Announce Type: new
Introduction
In the rapidly evolving field of artificial intelligence, Large Language Model-based Hyper Heuristic (LHH) has emerged as a promising approach for the automated design of heuristics. However, traditional LHHs have limitations, primarily in their ability to optimize single functions within a predefined solver. This single-layer evolution restricts their effectiveness in crafting complete, competent solvers.
The Challenges of Existing LHHs
Many existing LHHs seek to enhance performance through methods such as hyperparameter tuning or iterative local modifications. Despite these efforts, they often fall short in high-level algorithmic modeling, which limits their exploration efficiency. This lack of sophistication in design underscores the need for a more robust framework that can address these challenges.
Introducing BEAM
To tackle these issues, researchers have reformulated heuristic design as a Bi-level Optimization problem and introduced BEAM (Bi-level Memory-adaptive Algorithmic Evolution). This innovative approach features two layers of evolution:
- Exterior Layer: This layer focuses on evolving high-level algorithmic structures that include function placeholders using a genetic algorithm (GA).
- Interior Layer: The interior layer operates by realizing these placeholders through Monte Carlo Tree Search (MCTS).
Adaptive Memory Module
One of the key advancements in BEAM is the incorporation of an Adaptive Memory module designed to facilitate the generation of complex code. This addition allows the algorithm to manage memory more effectively, enhancing its ability to generate and optimize sophisticated heuristic designs.
Knowledge Augmentation Pipeline
In addressing the limitations of starting LHHs from scratch or from static code templates, the researchers have introduced a Knowledge Augmentation (KA) Pipeline. This pipeline is crucial for improving the evaluation process in complex code generation, ensuring that the heuristic designs produced are not only innovative but also practical and implementable.
Experimental Results
Extensive experiments conducted on various optimization problems have demonstrated the superiority of BEAM over existing LHHs. Notably, BEAM has achieved a significant reduction in the optimality gap by 37.84% on aggregate in the design of hybrid algorithms for the Capacitated Vehicle Routing Problem (CVRP). Furthermore, BEAM has successfully designed a heuristic that surpasses the state-of-the-art (SOTA) Maximum Independent Set (MIS) solver, KaMIS.
Conclusion
BEAM represents a significant advancement in the field of heuristic design by leveraging bi-level optimization and adaptive memory strategies. Its ability to effectively generate complex code and outperform existing methodologies marks a pivotal moment in the evolution of automated heuristic design, paving the way for more sophisticated and efficient AI applications.