Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design

Created by
  • Haebom

Author

Fei Liu, Yilu Liu, Qingfu Zhang, Xialiang Tong, Mingxuan Yuan

Outline

This paper proposes Automatic Heuristic Set Design (AHSD), a novel method for automatically generating complementary heuristic sets applicable to diverse problem instances, to address the problem of poor generalization performance caused by the generation of a single heuristic, which is Limitations, in Automatic Heuristic Design (AHD) using Large Language Models (LLMs). AHSD aims to generate a small set of complementary heuristics so that at least one heuristic optimizes each problem instance. We show that the objective function of AHSD is monotonically increasing and hyper-modular, and we propose the Evolution of Heuristic Sets Algorithm (EoH-S) that effectively generates high-quality complementary heuristic sets by leveraging two novel mechanisms: complementary population management and complementary-aware genetic algorithm search. Experimental results on AHD tasks with three different sizes and distributions of problem instances demonstrate that EoH-S consistently outperforms existing state-of-the-art AHD methods, achieving up to a 60% performance improvement.

Takeaways, Limitations

•
Takeaways:
◦
We present a novel method (AHSD) that overcomes the limitations of a single heuristic in LLM-based AHD and improves generalization performance for diverse problem instances.
◦
By revealing the mathematical properties of the objective function of AHSD (monotonically increasing and hypermodular), we establish a theoretical basis for algorithm design.
◦
Development of the EoH-S algorithm to effectively generate a high-quality complementary heuristic set through complementary group management and complementary cognitive genetic algorithm search mechanisms.
◦
We present experimental results that significantly outperform existing best-performing AHD methods on a variety of problem instances (up to 60% performance improvement).
•
Limitations:
◦
The effectiveness of the proposed method may be limited to a specific problem domain, and its generalizability to other types of problems requires further research.
◦
Analysis on parameter tuning of the EoH-S algorithm is lacking, and further research on parameter optimization is needed.
◦
There may be a high dependency on the size and performance of the LLM, and there is a possibility of performance degradation due to the limitations of the LLM.
◦
The diversity of problem instances used in the experiments may be limited, and further experiments on a wider range of problem instances are needed.
👍
Made with Slashpage