Evolutionary-Potential-Aware Iterative Preference Learning for LLM-Based Automatic Heuristic Design

Automatic Heuristic Design (AHD) uses large language models (LLMs) to construct heuristics for complex optimization problems. Existing LLM adaptation methods largely learn from the immediate performance of generated heuristics, overlooking the longer-term evolutionary potential revealed by their descendants. Search trees naturally preserve parent–descendant relationships and the outcomes of subsequent exploration, providing structural information that can serve as preference supervision. We propose an evolutionary-potential-aware iterative preference learning framework for LLM-based AHD that converts this information into search-feedback signals. After each MCTS expansion, newly observed descendants reassess the relative evolutionary potential of their ancestors; changes in local rankings then yield search-feedback preference pairs. These pairs complement on-policy performance preferences from newly generated candidates to fine-tune a local LLM through direct preference optimization. The updated LLM subsequently guides MCTS exploration, closing the iterative search–learning loop. Experiments across NP-hard combinatorial optimization tasks show that our method achieves the best overall result in six of nine ACO task–scale settings and the best LLM-based AHD result in eight. Despite using a locally deployed quantized 7B model, it outperforms GPT-4o-mini-based AHD baselines across all nine ACO settings.