1 Introduction↩︎

Large Language Models (LLMs) have demonstrated remarkable capabilities across diverse tasks [1], with their code generation proficiency particularly advancing Automated Heuristic Design (AHD). By combining LLMs with Evolutionary Computation (EC), a “Thought-to-Code” paradigm has emerged where natural language reasoning directly guides the generation of human-readable, executable heuristics to solve combinatorial optimization problems (COPs). Starting with FunSearch [2], subsequent works [3]–[6] have advanced this direction, though these methods initially focused on single-objective settings, optimizing only solution quality.

Recent efforts have begun extending LLM-based AHD to multi-objective settings, simultaneously optimizing solution quality and computational efficiency [7], [8] or multi-objective solutions [9]. However, the exploration-exploitation dilemma remains a fundamental challenge across both single- and multi-objective approaches. These methods tend to converge to a narrow set of high-performing but homogeneous solutions, as their selection mechanisms operate solely in the objective space without considering the underlying algorithmic structure. This lack of semantic diversity severely constrains the search process, preventing the discovery of novel algorithmic paradigms and causing premature convergence to local optima.

To address this, we propose Quality-Diversity Evolution (QDEvo), a novel framework that integrates Quality-Diversity optimization principles [10] with LLM-driven heuristic search. QDEvo maintains an unbounded archive of algorithms that are both high-performing and semantically distinct, using pre-trained code embeddings to measure algorithmic similarity and actively enforce diversity. This provides practitioners with diverse algorithmic strategies and enables the discovery of “stepping stone” solutions that lead to superior heuristics through further evolution. The framework further incorporates Hierarchical Reflective Memory to learn from both successes and failures across the evolutionary process. Our contributions are as follows:

• Quality-Diversity Evolution Framework: We propose the first LLM-based heuristic generation framework that leverages semantic code embeddings to enforce population diversity, preventing mode collapse and enabling broader exploration of the algorithmic space.

• Multi-Objective Optimization: We also demonstrate that QDEvo can simultaneously optimize for both single-objective solution quality and computational efficiency, or for inherently multi-objective problems.

• Hierarchical Reflective Memory: A structured memory architecture that enables the LLM to learn from successful strategies, synthesize long-term experiences, and explicitly avoid previously encountered errors.

2 Methodology↩︎

2.1 Evolutionary Process↩︎

The QDEvo framework operates as an iterative evolutionary loop, as illustrated in Figure 1. Each individual is represented as a Thought-to-Code pair \((T, C)\), where \(T\) denotes the algorithmic thought a natural language description of the heuristic strategy and \(C\) represents the executable Python code implementing that strategy [3]. This dual representation enables the LLM to reason about algorithm design at both conceptual and implementation levels. Each individual is further augmented with an embedding vector for diversity-based selection and a score vector \([f_{\text{quality}}, f_{\text{runtime}}]\) for multi-objective fitness evaluation.

The evolutionary process begins with the Population Archive, an unbounded structure that stores all non-dominated individuals discovered throughout the search. Unlike fixed-size populations in previous works, this archive naturally grows to accommodate diverse solutions while pruning dominated individuals during survival selection. Following standard practice in LLM-based evolutionary methods [2], [3], the archive is bootstrapped via zero-shot generation with adaptive sampling, iteratively generating heuristics from only the task description until a minimum number of valid individuals pass evaluation. A higher temperature (\(\tau = 1.0\)) is used during initialization to maximize diversity.

From this archive, the Parent Selection module samples individuals for variation. For mutation, a single parent is selected uniformly at random from valid individuals, promoting exploration across the behavioral space. For crossover, two parents are randomly sampled and ordered based on Pareto dominance: \[(P_{\text{better}}, P_{\text{worse}}) = \begin{cases} (P_1, P_2) & \text{if } P_1 \succ P_2 \\ (P_2, P_1) & \text{otherwise} \end{cases}\] This ordering enables the LLM to identify superior design patterns from the better parent while potentially rescuing beneficial components from the worse parent.

The selected parents then flow into Prompt Construction, where task context, parent information, and reflection insights are assembled. Critically, insights from the Hierarchical Reflective Memory (detailed in Section 2.2) feed into this stage via a feedback loop, enabling the LLM to leverage accumulated knowledge from prior generations.

The constructed prompts are passed to the LLM Generator, which serves as the variation operator. QDEvo employs one crossover and three mutation strategies: Crossover combines design elements from both parents guided by reflection insights; Random Mutation encourages novelty through radical structural changes; Reflection-Guided Mutation leverages accumulated experience to guide modifications; and Runtime Mutation focuses exclusively on computational efficiency through vectorization and caching optimizations.

Each generated heuristic then undergoes Evaluation with bi-objective assessment: \[\mathbf{f}(C) = [f_{\text{quality}}(C), f_{\text{runtime}}(C)]\] where \(f_{\text{quality}}\) measures effectiveness on the target optimization problem and \(f_{\text{runtime}}\) measures computational efficiency as the negative of execution time. Invalid individuals (syntax errors, runtime exceptions, timeouts) receive \(f = [-\infty, -\infty]\), with their error information captured for the error reflection mechanism.

Finally, evaluated individuals enter the Semantic Survival Selection stage (detailed in Section 2.3). This module transforms each heuristic into a semantic embedding, clusters similar solutions together, and applies local Pareto competition within each cluster. Surviving non-dominated individuals return to the Population Archive, completing the evolutionary cycle and enabling continuous discovery of diverse, high-quality heuristics.

2.2 Hierarchical Reflective Memory↩︎

As demonstrated in [4], verbal gradients play an important role in LLM-based AHD. QDEvo extends this concept by incorporating a three-level hierarchical reflection mechanism that enables progressive learning from evolutionary history. The reflection outputs feed into prompt construction via a feedback loop, enabling the LLM to leverage accumulated knowledge for improved generation.

Flash Reflection provides immediate feedback at each generation. A diverse sample of individuals spanning the performance spectrum is analyzed, where the LLM compares pairs of better versus worse heuristics, identifying patterns that distinguish high-performing from low-performing designs. The output consists of detailed comparison insights (e.g., “Comparing best vs worst, we observe...”) and concise actionable advice.

Comprehensive Reflection aggregates experiences from multiple generations, synthesizing them into structured guidance with four components: Keywords (key concepts), Advice (recommended strategies), Avoid (pitfalls to prevent), and Explanation (reasoning behind the guidance). This reflection distinguishes between experiences that led to Pareto front improvements versus those that did not, enabling long-term learning of successful design principles.

Error Reflection tracks failed individuals with their error information (error type, message, traceback). A repair mechanism attempts to fix failed heuristics using error-aware prompts, distilling runtime failures into explicit avoidance rules. This prevents the LLM from repeating common mistakes and systematically guides future generations toward valid solutions.

2.3 Semantic Survival Selection↩︎

Each heuristic is canonicalized (removing comments, normalizing formatting via AST parsing) and embedded into a dense vector \(\mathbf{v}\) using a pre-trained code embedding model. Individuals are partitioned into semantic clusters based on cosine similarity: \[\text{sim}(P_i, P_j) = \frac{\mathbf{v}_i \cdot \mathbf{v}_j}{\|\mathbf{v}_i\| \|\mathbf{v}_j\|}\] An individual joins cluster \(C_k\) only if its similarity to all members exceeds threshold \(\delta{=}0.95\); otherwise a new cluster is created: \[P_{new} \in C_k \iff \forall P_j \in C_k, \;\text{sim}(P_{new}, P_j) \ge \delta\] Within each cluster, only Pareto non-dominated individuals survive, ensuring that semantically similar solutions compete locally while diversity is preserved across algorithmic niches [10].

3 Experiments↩︎

We compare QDEvo against MEoH [7] (state-of-the-art LLM-based method) and classic evolutionary algorithms (NSGA-II, MOEA/D) across three benchmark categories: (1) single-objective COPs reformulated as bi-objective (quality vs.runtime), including TSP (constructive and GLS), CVRP, and Online Bin Packing; (2) multi-objective COPs including Bi-TSP and Bi-KP; and (3) real-world tasks including Airline Crew Pairing and Intra-operator Parallelism¹. Performance is measured by Hypervolume (HV, higher is better) and Inverted Generational Distance (IGD, lower is better). All methods use Codestral 2 as the LLM, with 300 max samples and population size 30.

3.1 Results↩︎

Table 1 summarizes QDEvo’s performance across representative benchmarks. QDEvo achieves the highest HV on the majority of instances across all three categories. For constructive heuristics, QDEvo attains 73.2% lower IGD than NSGA-II on CVRP-C 200 (\(0.237\) vs.\(0.883\)). On multi-objective benchmarks, QDEvo improves HV by 1.4% over MEoH on Bi-TSP-200 (\(1.178\) vs.\(1.162\)) and reduces IGD by 15.4%. For real-world tasks, QDEvo achieves 59.1% lower IGD than MEoH on Crew Pairing (\(0.110\) vs.\(0.269\)), indicating superior coverage of the trade-off structure.

3.2 Ablation Study↩︎

We compare QDEvo’s semantic embedding (Embedding) against two variants: Cell (structural code metrics as MAP-Elites descriptors) and NSGAII (crowding distance only, no QD archive).

The semantic embedding approach achieves the highest HV across all instances (Table 2). The gap is most pronounced on TSP-GLS 100, where Embedding attains HV of \(1.123\) vs.\(1.089\) for both alternatives—a 3.1% improvement reflecting the discovery of fundamentally different algorithmic strategies. Structural code metrics (Cell) fail to distinguish semantically distinct algorithms with similar control flow, while NSGAII maintains spread along the front but cannot expand into unexplored regions.

4 Conclusion↩︎

In this paper, we introduced QDEvo, a novel multi-objective Quality-Diversity framework for automated heuristic design. By integrating Large Language Models with a semantic archive and hierarchical reflective memory, QDEvo effectively addresses the challenges of mode collapse and single-objective over-optimization found in previous approaches. Our extensive experiments across standard combinatorial benchmarks and complex real-world industrial tasks demonstrate that QDEvo significantly outperforms state-of-the-art baselines, producing heuristics that are not only high-performing but also computationally efficient and semantically diverse. The ablation study further confirms the critical role of semantic embeddings in maintaining a rich population of algorithmic strategies. Future work will explore the application of QDEvo to even broader classes of problems and the integration of more advanced reasoning capabilities into the evolutionary process. The source code for QDEvo is publicly available at https://github.com/datphamvn/QDEvo.

References↩︎