Abstract
Although Large Language Models have advanced Automated Heuristic Design, treating algorithm evolution as a monolithic text generation task overlooks the coupling between discrete algorithmic structures and continuous numerical parameters. Consequently, existing methods often discard promising algorithms due to uncalibrated constants and suffer from premature convergence resulting from simple similarity metrics. To address these limitations, we propose TIDE, a Tuning-Integrated Dynamic Evolution framework designed to decouple structural reasoning from parameter optimization. TIDE features a nested architecture where an outer parallel island model utilizes Tree Similarity Edit Distance to drive structural diversity, while an inner loop integrates LLM-based logic generation with a differential mutation operator for parameter tuning. Additionally, a UCB-based scheduler dynamically prioritizes high-yield prompt strategies to optimize resource allocation. Extensive experiments across nine combinatorial optimization problems demonstrate that TIDE discovers heuristics that significantly outperform state-of-the-art baselines in solution quality while achieving improved search efficiency and reduced computational costs.
The Challenges of LLM-Based Heuristic Design
Automated Heuristic Design (AHD) aims to replace the manual labor of human intuition with algorithms capable of designing other algorithms. While Large Language Models (LLMs) have shown promise as "intelligent designers," current approaches suffer from two critical flaws:
- Numerical Blindness: LLMs excel at symbolic reasoning but struggle with numerical precision. When an LLM generates a heuristic, it often suggests suboptimal constants. If these constants perform poorly, the entire logical strategy may be discarded during evolution, even if the underlying logic was superior.
- Surface-Level Diversity: Most frameworks rely on textual similarity (e.g., Jaccard distance or CodeBLEU) to maintain population diversity. These metrics are easily deceived by variable renaming or comment changes, causing the search to converge prematurely on a single, mediocre logic.
The TIDE Framework
TIDE introduces a nested, two-level evolutionary architecture designed to decouple structural logic from parameter tuning.
The Outer Loop: TSED-Guided Island Model
Instead of a monolithic population, TIDE utilizes an "island model" where subpopulations evolve independently. To ensure genuine diversity, TIDE employs Tree Similarity Edit Distance (TSED). By analyzing the Abstract Syntax Tree (AST) of the code, TIDE distinguishes between fundamental logical changes and mere syntactic noise.
Islands share information through a Dual-Mode Migration strategy:
- Code Transfer (Exploitation): If two islands are logically similar, they exchange code to refine existing strategies.
- Insight Transfer (Exploration): If islands are logically distinct, the LLM distills the "pivotal mechanisms" of one island into a natural language prompt for the other, allowing for high-level cross-pollination of ideas without forcing identical code structures.
The Inner Loop: Co-Evolution and Tuning
Within each island, TIDE optimizes the search process using two key mechanisms:
- UCB-based Scheduler: The selection of prompting strategies (e.g., crossover vs. mutation) is treated as a Multi-Armed Bandit problem. The Upper Confidence Bound (UCB) algorithm dynamically prioritizes strategies that yield the highest performance gains.
- Differential Mutation Operator: To solve "numerical blindness," TIDE integrates a gradient-free numerical optimizer. Once a promising logic is identified, this operator fine-tunes the constants without consuming additional LLM tokens, significantly improving efficiency.
Experimental Results
TIDE was evaluated across nine combinatorial optimization problems, including routing (TSP, CVRP), packing (BPP, Knapsack), and control tasks (Mountain Car).
- Superior Solution Quality: On TSP50, TIDE achieved a gap of only 4.76% from the optimal solution, whereas the baseline EoH trailed at 12.11%. In the Knapsack problem, TIDE reached a near-perfect 0.02% gap.
- Enhanced Efficiency: TIDE proved more token-efficient than its predecessors. In TSP-ACO tasks, it outperformed ReEvo while utilizing approximately 33% fewer input tokens.
- Robustness in Complex Tasks: In the Mountain Car reinforcement learning benchmark, TIDE discovered a policy requiring only 98.3 steps, outperforming MCTS-AHD (105.7 steps).
Conclusion
By treating algorithm design as a bi-level optimization problem—separating the "architectural" logic from "calibrated" parameters—TIDE overcomes the inherent numerical limitations of LLMs. The transition from textual similarity to AST-based diversity metrics ensures a more robust and systematic exploration of the heuristic space. Future work will explore multi-objective optimization and the potential for cross-domain transfer of structural insights.
Summary updated