Abstract

Automatic Heuristic Design (AHD) is an active research area due to itsutility in solving complex search and NP-hard combinatorial optimizationproblems in the real world. The recent advancements in Large Language Models(LLMs) introduce new possibilities by coupling LLMs with evolutionarycomputation to automatically generate heuristics, known as LLM-basedEvolutionary Program Search (LLM-EPS). While previous LLM-EPS studies obtainedgreat performance on various tasks, there is still a gap in understanding theproperties of heuristic search spaces and achieving a balance betweenexploration and exploitation, which is a critical factor in large heuristicsearch spaces. In this study, we address this gap by proposing two diversitymeasurement metrics and perform an analysis on previous LLM-EPS approaches,including FunSearch, EoH, and ReEvo. Results on black-box AHD problems revealthat while EoH demonstrates higher diversity than FunSearch and ReEvo, itsobjective score is unstable. Conversely, ReEvo's reflection mechanism yieldsgood objective scores but fails to optimize diversity effectively. With thisfinding in mind, we introduce HSEvo, an adaptive LLM-EPS framework thatmaintains a balance between diversity and convergence with a harmony searchalgorithm. Through experimentation, we find that HSEvo achieved high diversityindices and good objective scores while remaining cost-effective. These resultsunderscore the importance of balancing exploration and exploitation andunderstanding heuristic search spaces in designing frameworks in LLM-EPS.