Directing to Diversify: Multi-Directional Search for Automatic Heuristic Design
PRS tackles automatic heuristic design by making diversification an explicit generation-level operation rather than an emergent property of population management. The framework factorizes heuristic transformation into three semantic directions—expansion, compression, and steering—and rewrites perturbed ideas into executable code via LLMs within a breadth-first search with adaptive operator control. This matters because existing evolutionary frameworks mutate code without directly controlling the semantic trajectory of change, which often leads to premature convergence.
The paper presents a conceptually clean framework that shifts diversification from population selection to idea-generation semantics, achieving consistent empirical advantages over LLM-based AHD baselines across 11 problem settings. The ablations lend credible support to the three-operator design, yet the evaluation hinges on an unreleased model (GPT-5-nano) and relatively shallow BFS parameters ($\kappa=3, d=3$) whose sensitivity is under-explored in the main text. "PRS consistently discovers high-quality heuristics, demonstrating the effectiveness and generality of explicitly directional exploration design."
The factorization of idea perturbation from code rewrite is methodologically sound: by separating semantic intent from executable realization, PRS sidesteps brittle syntax-level mutation and instead steers exploration through natural-language algorithmic descriptions. The ablation evidence is strong—disabling any of the three operators degrades performance, and "Disabling UCB-based operator selection and replacing it with random selection consistently degrades performance, indicating that adaptively allocating search effort among the three operators is beneficial."
The strongest limitation is reproducibility: the experiments rely on GPT-5-nano, a model inaccessible to the community, with no stated plan for code or data release, making independent verification impossible. The BFS structure is shallow ($d=3$), and while the paper notes sensitivity analyses in appendices, the main text never justifies why such limited depth is sufficient or how beam width interacts with LLM query budgets.
Additionally, the idea-space diversity claim is asserted but not quantified in the main paper—readers must trust that expansion and compression produce structurally distinct heuristics rather than surface-level paraphrases. "The direction of heuristic change is largely uncontrolled by the search mechanism itself: different transformation patterns may emerge during evolution, but they are not explicitly harnessed as distinct search primitives."
PRS reports lower optimality gaps than FunSearch, EoH, ReEvo, HSEvo, and MCTS-AHD across CVRP, OP, KP, OBPP, and FSSP under standardized budgets, which supports its headline claim. The protocol is fair—shared seeds, datasets, and a 5,000-query cap—but omits wall-clock time and per-query cost. Prior work confirms the EC framing: "treats each algorithm as an individual and utilizes an evolutionary framework to evolve new algorithms." "These results suggest that PRS is particularly effective in discovering heuristics with stronger out-of-distribution generalization under the ACO framework."
Reproducibility is seriously impaired by the exclusive use of GPT-5-nano, a model unavailable through public APIs at the time of writing, and by the absence of any mention of code or prompt release. While Algorithm 1 and Appendix D provide exhaustive methodological detail, critical hyperparameters—including the stagnation threshold $\mathcal{C}$, UCB window size, and exact annealing endpoints $c_0$ and $c_T$—are deferred to appendices or omitted entirely from the main text. "All experiments were conducted on a machine equipped with a single Intel Core i9-12900KF CPU."
Large language models (LLMs) have demonstrated strong potential to automate heuristic design for NP-hard combinatorial optimization (CO) tasks without human intervention. Recent methods predominantly rely on evolutionary computation (EC) frameworks, where heuristic diversification is mainly induced through EC-like operators or downstream selection, while the direction of heuristic transformation remains largely unharnessed. In this paper, we propose a multi-directional Perturbation-Rewrite Search (PRS) framework for automatic heuristic design that factorizes heuristic transformation through directional search primitives at the generation level. Specifically, PRS operates on heuristic ideas through three complementary directions: expansion toward richer and more expressive designs, compression toward simpler and less specialized designs, and steering for fine-grained refinement, together enabling broader and more sustained exploration of diverse regions in the heuristic design space. PRS further organizes candidate exploration within a breadth-first search-based process with adaptive operator control, which ensures thorough candidate utilization and sustained exploration, and maintains strong search dynamics while preventing premature convergence. Extensive empirical results across diverse CO tasks show that PRS consistently discovers high-quality heuristics, demonstrating the effectiveness and generality of explicitly directional exploration design.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.