2024 | Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, Qingfu Zhang
This paper introduces Evolution of Heuristics (EoH), a novel approach that combines large language models (LLMs) and evolutionary computation (EC) to automatically design heuristics. EoH represents heuristic ideas in natural language (called thoughts) and translates them into executable code using LLMs. The system evolves both thoughts and codes in an evolutionary framework, enabling the generation of high-performance heuristics. Experiments on three combinatorial optimization problems—online bin packing, traveling salesman, and flow shop scheduling—show that EoH outperforms existing hand-crafted heuristics and other automatic heuristic design methods, including FunSearch. Notably, EoH achieves better performance with fewer LLM queries, making it more efficient. The method uses prompt strategies to guide LLMs in generating diverse and effective heuristics, and it integrates both natural language descriptions and code implementations for each heuristic. EoH demonstrates strong performance across various problem instances and shows good generalization to out-of-distribution data. The study also highlights the importance of combining thoughts and code in heuristic evolution and shows that using more powerful LLMs can further improve performance. Future work includes exploring domain-specific LLMs, understanding heuristic search spaces, and improving interaction with human experts. EoH provides a principled approach to automatic algorithm design and is implemented in Python.This paper introduces Evolution of Heuristics (EoH), a novel approach that combines large language models (LLMs) and evolutionary computation (EC) to automatically design heuristics. EoH represents heuristic ideas in natural language (called thoughts) and translates them into executable code using LLMs. The system evolves both thoughts and codes in an evolutionary framework, enabling the generation of high-performance heuristics. Experiments on three combinatorial optimization problems—online bin packing, traveling salesman, and flow shop scheduling—show that EoH outperforms existing hand-crafted heuristics and other automatic heuristic design methods, including FunSearch. Notably, EoH achieves better performance with fewer LLM queries, making it more efficient. The method uses prompt strategies to guide LLMs in generating diverse and effective heuristics, and it integrates both natural language descriptions and code implementations for each heuristic. EoH demonstrates strong performance across various problem instances and shows good generalization to out-of-distribution data. The study also highlights the importance of combining thoughts and code in heuristic evolution and shows that using more powerful LLMs can further improve performance. Future work includes exploring domain-specific LLMs, understanding heuristic search spaces, and improving interaction with human experts. EoH provides a principled approach to automatic algorithm design and is implemented in Python.