1 Jun 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 paradigm that combines Large Language Models (LLMs) and Evolutionary Computation (EC) to automatically design heuristics for complex search and optimization problems. EoH represents heuristic ideas in natural language, termed *thoughts*, which are then translated into executable *codes* by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it highly effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent Automatic Heuristic Design (AHD) methods, including FunSearch. Notably, EoH produces heuristics with better performance than those designed by FunSearch, using significantly fewer queries to LLMs. The paper also discusses the benefits of evolving both thoughts and codes, the impact of different LLMs, and the potential for integrating expert heuristics into the EoH framework. Future work includes developing pre-trained domain LLMs, understanding the search space of heuristics, and enhancing interaction with human experts.This paper introduces Evolution of Heuristics (EoH), a novel paradigm that combines Large Language Models (LLMs) and Evolutionary Computation (EC) to automatically design heuristics for complex search and optimization problems. EoH represents heuristic ideas in natural language, termed *thoughts*, which are then translated into executable *codes* by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it highly effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent Automatic Heuristic Design (AHD) methods, including FunSearch. Notably, EoH produces heuristics with better performance than those designed by FunSearch, using significantly fewer queries to LLMs. The paper also discusses the benefits of evolving both thoughts and codes, the impact of different LLMs, and the potential for integrating expert heuristics into the EoH framework. Future work includes developing pre-trained domain LLMs, understanding the search space of heuristics, and enhancing interaction with human experts.