HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs

Pham Vu Tuan Dat, Long Doan, Huynh Thi Thanh BinhAAAI 2025 · DOI

TL;DR

This paper introduces HSEvo, a novel framework that uses Large Language Models (LLMs) and evolutionary computation to automatically design effective heuristics for complex optimization problems. By introducing new diversity metrics and incorporating a Harmony Search algorithm, HSEvo achieves a better balance between exploring new solutions and exploiting existing ones, leading to superior performance compared to previous LLM-based approaches.

What Problem Does This Paper Address?

Designing efficient heuristics for complex combinatorial optimization problems (COPs) is a challenging and time-consuming task, often requiring significant expert knowledge. While Automatic Heuristic Design (AHD) aims to automate this process, existing methods like Hyper-Heuristics and Neural Combinatorial Optimization have limitations. The recent emergence of Large Language Models (LLMs) has opened new avenues for AHD, leading to LLM-based Evolutionary Program Search (LLM-EPS) frameworks. However, a critical gap exists in understanding the search spaces of these LLM-generated heuristics and achieving a balance between exploration (finding diverse solutions) and exploitation (refining promising solutions), which is crucial for effective optimization. Previous LLM-EPS approaches like FunSearch, EoH, and ReEvo have shown promise but struggle with this balance, leading to either unstable performance or insufficient diversity.

Methods

The paper proposes HSEvo, an adaptive LLM-EPS framework designed to address the exploration-exploitation trade-off. Key components include:

  • Diversity Measurement Metrics: Two novel metrics, the Shannon-Wiener Diversity Index (SWDI) and the Cumulative Diversity Index (CDI), are introduced to quantify population diversity. These metrics are inspired by ecological diversity measures and adapted for the unique representation of heuristics as code snippets.
  • Population Encoding: A method to encode LLM-EPS populations is proposed, involving removing comments, standardizing code, and using a code embedding model to convert code snippets into vector representations.
  • Harmony Search (HS) Integration: To balance diversity and convergence, HSEvo incorporates a Harmony Search algorithm. This algorithm optimizes the parameters (e.g., thresholds, weights) of the best-performing heuristics in the population, effectively fine-tuning them without sacrificing diversity.
  • Flash Reflection: A more cost-efficient reflection mechanism is used, which analyzes and provides feedback on heuristic pairs to guide the generation process.
  • Genetic Algorithm Components: Standard genetic algorithm operations like initialization, crossover, and mutation are enhanced to leverage LLMs and the diversity metrics. Initialization uses diverse role-playing prompts for LLMs, crossover combines parent heuristics based on feedback, and elitist mutation refines the best heuristic using LLM analysis.

Datasets

The paper evaluates HSEvo on three standard AHD problems:

  • Bin Packing Online (BPO): A benchmark for online packing problems where items arrive sequentially.
  • Traveling Salesman Problem (TSP): A classic problem requiring the shortest route visiting all cities. HSEvo's heuristics are used to enhance a Guided Local Search solver.
  • Orienteering Problem (OP): A problem focused on maximizing collected scores within a tour length constraint. HSEvo's heuristics are used with an Ant Colony Optimization (ACO) solver.

The datasets for these problems were generated following established methodologies from previous related studies.

Key Insights and Ideas

  • Diversity is Crucial for Escaping Local Optima: The analysis reveals that while focusing on exploitation can lead to quick gains, a lack of population diversity (low CDI) can trap the system in local optima, hindering further improvement. Conversely, maintaining diversity, especially with a high SWDI, can lead to significant objective score improvements.
  • LLM-EPS Faces an Inherent Trade-off: Experiments on previous LLM-EPS frameworks (FunSearch, EoH, ReEvo) highlight a clear trade-off between diversity (CDI) and objective performance. Some methods achieve high diversity but poor scores (EoH), while others achieve good scores but lower diversity (ReEvo, FunSearch).
  • Harmony Search Balances Exploration and Exploitation: Integrating Harmony Search into the LLM-EPS process helps optimize heuristic parameters, leading to better objective scores without necessarily sacrificing diversity, as demonstrated by HSEvo's performance.
  • Flash Reflection is More Efficient: The proposed flash reflection mechanism is shown to be more cost-effective than original reflection methods, achieving comparable or better results with fewer tokens.

Key Results

  • HSEvo consistently achieved the best objective scores across all three AHD problems (BPO, TSP, and OP), outperforming previous LLM-EPS frameworks like FunSearch and ReEvo.
  • While HSEvo did not always achieve the highest CDI compared to EoH, it demonstrated a stronger balance between diversity and objective performance.
  • Ablation studies showed that Harmony Search significantly improved ReEvo's performance on the OP problem, suggesting its effectiveness in enhancing optimization when combined with a diversity-promoting mechanism.
  • The experiments indicated that diversity-promoting mechanisms are essential for flash reflection to effectively improve optimization processes.

Limitations and Future Work

  • Computational Cost: While HSEvo aims for efficiency, LLM-based approaches inherently involve significant computational resources for prompt generation and evaluation.
  • Generalizability: The paper focuses on specific AHD problems. Further research could explore HSEvo's applicability to a wider range of complex optimization tasks.
  • Future Work: The authors suggest that their work can benefit future research in LLM-EPS by providing foundational theories on heuristic search spaces and a framework that effectively balances diversity and optimization performance. They also highlight the importance of further exploring the interplay between diversity metrics and LLM-driven heuristic design.

Summary updated

BibTeX
@inproceedings{dat2025hsevo,
  author = {Pham Vu Tuan Dat and Long Doan and Huynh Thi Thanh Binh},
  title = {{HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34898},
}
Figure