Multi-directional search improves automatic heuristic design for optimization

Directing to Diversify: Multi-Directional Search for Automatic Heuristic Design

Artificial Intelligence

Summary

Finding good solutions to hard problems often uses step-by-step rules called heuristics. The authors introduce a new way to automatically create better heuristics by exploring changes in three clear directions: making rules bigger and richer, making them simpler, and fine-tuning them. Their method carefully explores many options without getting stuck early, finding diverse and effective rules for different tricky problems.

What this means in practice

  • For operations research teams: Automatically generate varied and effective heuristics for complex scheduling and routing problems in logistics and manufacturing.
  • For ai software engineers: Improve optimization modules by integrating multi-directional heuristic search to enhance solutions in automated decision-making systems.

Authors

Jianghan Zhu, Jianan Zhou, Fei Liu, Ni Zhang, Yaoxin Wu, Zhuoyi Lin, Zhiguang Cao

Abstract

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.