Guided Evolution and Automated Refinement for LLM-based Heuristic Design

LLM-based Automated Heuristic Design (AHD) has shown great promise for combinatorial optimization (CO), discovering competitive heuristics for well-studied problems such as the Traveling Salesman Problem (TSP). However, the quality of LLM-generated heuristics degrades in less-studied CO domains such as airline crew pairing, where LLMs lack domain-specific priors. We hypothesize that the general heuristic-design knowledge of LLMs can still be effective in such domains, and that the bottleneck lies in how the surrounding search loop selects candidates and feeds back information. We study this in a joint multi-component setting, where constructive and refinement heuristics are evolved together; the enlarged space makes scalar-fitness-based selection and feedback particularly uninformative. We propose Guided heuristic Evolution and Automated Refinement (GEAR), which uses complementary-gain population management to retain candidates that excel on different instances, and an executable Analyst that writes feature functions over evaluated solutions to produce structured, distributional feedback. Across four less-studied and four classic CO domains, with all baselines adapted to the same joint space, \ours achieves the highest mean test fitness in all eight domains and consistent gains on scale-up generalization in the classic domains.