MO-EoH: Multi-Objectivization Evolution of Heuristics with Large Language Models

In recent years, Automated Heuristic Design (AHD) based on Large Language Models (LLMs) has achieved significant success. However, existing single-objective optimization methods use only the optimal performance on the target problem as the sole guidance signal during evolution, making it difficult to accurately assess heuristic performance and causing the search to become trapped in local optima. To address this issue, we introduce helper objectives into the original heuristic design objective, transforming the Single-Objective Optimization Problem (SOP) into a Multi-Objective Optimization Problem (MOP), while maintaining the ultimate goal of discovering better solutions to the original SOP. We refer to this process as multi-objectivization. Building on this idea, we propose Multi-Objectivization Evolution of Heuristics (MO-EoH), the first framework to introduce multi-objectivization into LLM-based AHD. Furthermore, we design a Lexicographic-Pareto mechanism that prioritizes the original heuristic design objective, thereby improving search efficiency. Experiments across eight classical planning benchmark domains demonstrate that MO-EoH consistently outperforms existing state-of-the-art LLM-based methods, achieving an average improvement of 24.5% on the original objective.