QDEvo：一种用于自动启发式设计的多目标质量-多样性框架

# QDEvo：用于自动启发式设计的多目标质量多样性框架
来源：https://arxiv.org/html/2607.11916

###### 摘要

大型语言模型（LLM）与进化计算的结合已成为组合优化中自动启发式设计的一种强大范式。然而，现有方法存在模式坍塌问题，收敛到同质化的种群，缺乏语义多样性，无法探索完整的算法空间。我们提出质量多样性进化（QDEvo），一个多目标框架，将质量多样性优化与LLM驱动的启发式搜索相结合，利用预训练的代码嵌入维护一个不受限的语义多样化算法存档，并引入分层自我反思来引导进化过程。在标准基准测试和实际工业应用上的大量实验表明，QDEvo在超体积和逆世代距离指标上显著优于现有最先进方法。我们的框架能够发现同时具有高性能、计算高效和语义多样性的启发式算法，为从业者解决复杂优化问题提供了丰富的解决方案组合。

大型语言模型、质量多样性优化、自动启发式设计、进化计算、多目标优化、反思学习

††CCS：计算方法论 启发式函数构建
††CCS：计算理论 离散优化

## 1. 引言

大型语言模型（LLM）在各类任务中展现出非凡能力（Zhao等人，2023 (https://arxiv.org/html/2607.11916#bib.bib1)），其代码生成能力尤其推动了自动启发式设计（AHD）的发展。通过将LLM与进化计算（EC）相结合，一种“思想到代码”的范式应运而生，其中自然语言推理直接指导生成人类可读、可执行的启发式算法来解决组合优化问题（COPs）。从FunSearch（Romera-Paredes等人，2024 (https://arxiv.org/html/2607.11916#bib.bib9)）开始，后续工作（Liu等人， (https://arxiv.org/html/2607.11916#bib.bib5)；Ye等人，2024 (https://arxiv.org/html/2607.11916#bib.bib2)；Dat等人，2025 (https://arxiv.org/html/2607.11916#bib.bib3)；Zheng等人，2025 (https://arxiv.org/html/2607.11916#bib.bib6)）进一步推动了这一方向，尽管这些方法最初专注于单目标设置，仅优化解的质量。

最近的努力开始将基于LLM的AHD扩展到多目标设置，同时优化解质量和计算效率（Yao等人，2025 (https://arxiv.org/html/2607.11916#bib.bib10)；Kiet等人，2026 (https://arxiv.org/html/2607.11916#bib.bib7)）或多目标解（Hieu等人，2026 (https://arxiv.org/html/2607.11916#bib.bib4)）。然而，探索-利用困境仍然是单目标和多目标方法面临的基本挑战。这些方法倾向于收敛到一组狭窄的高性能但同质化的解，因为其选择机制仅在目标空间中运作，没有考虑底层的算法结构。这种语义多样性的缺乏严重限制了搜索过程，阻止了新算法范式的发现，并导致过早收敛到局部最优。

为了解决这个问题，我们提出QDEvo（质量多样性进化），一个新颖的框架，将质量多样性优化原理（Pugh等人，2016 (https://arxiv.org/html/2607.11916#bib.bib8)）与LLM驱动的启发式搜索相结合。QDEvo维护一个不受限的算法存档，这些算法既高性能又语义独特，使用预训练的代码嵌入来度量算法相似性并主动强制多样性。这为从业者提供了多样化的算法策略，并能够发现“垫脚石”解，通过进一步进化得到更优的启发式算法。该框架还集成了分层反思记忆，从整个进化过程中的成功和失败中学习。我们的贡献如下：

- • **质量多样性进化框架**：我们提出第一个基于LLM的启发式生成框架，利用语义代码嵌入强制种群多样性，防止模式坍塌，并实现对算法空间的更广泛探索。
- • **多目标优化**：我们还证明了QDEvo可以同时优化单目标解质量和计算效率，或解决本质上的多目标问题。
- • **分层反思记忆**：一种结构化的记忆架构，使LLM能够从成功策略中学习，综合长期经验，并明确避免先前遇到过的错误。

参见图注1. QDEvo框架概览。进化循环始于从**种群存档**中进行**父本选择**。选中的父本，连同来自**分层反思**的洞察，输入到**提示构建**（虚线箭头表示反馈循环）。**LLM生成器**产生新的候选启发式算法，经过**评估**。最后，**语义生存选择**（包括代码嵌入、聚类和局部竞争）决定哪些个体返回存档以用于后续世代。

## 2. 方法

### 2.1. 进化过程

QDEvo框架作为一个迭代进化循环运行，如图1 (https://arxiv.org/html/2607.11916#S1.F1)所示。每个个体被表示为一个“思想到代码”对 \((T, C)\)，其中 \(T\) 表示算法思想（启发式策略的自然语言描述），\(C\) 表示实现该策略的可执行Python代码（Liu等人， (https://arxiv.org/html/2607.11916#bib.bib5)）。这种双重表示使LLM能够在概念和实现两个层面上推理算法设计。每个个体进一步附带一个用于基于多样性选择的嵌入向量，以及一个用于多目标适应度评估的得分向量 \([f_{\text{质量}}, f_{\text{运行时}}]\)。

进化过程始于**种群存档**，这是一个不受限的结构，存储搜索过程中发现的所有非支配个体。与之前工作中固定大小的种群不同，这个存档自然会增长以容纳多样化解，同时在生存选择期间修剪支配个体。遵循LLM进化方法的标准实践（Liu等人， (https://arxiv.org/html/2607.11916#bib.bib5)；Romera-Paredes等人，2024 (https://arxiv.org/html/2607.11916#bib.bib9)），存档通过零样本生成和自适应采样进行引导，仅从任务描述迭代生成启发式算法，直到最少数量的有效个体通过评估。初始化期间使用较高的温度（\(\tau=1.0\)）以最大化多样性。

从这个存档中，**父本选择**模块采样个体进行变异。对于突变，从有效个体中均匀随机选择一个父本，这促进了行为空间中的探索。对于交叉，随机采样两个父本并根据帕累托优势进行排序：

\[
(1) \quad (P_{\text{更好}}, P_{\text{更差}}) = 
\begin{cases}
(P_1, P_2) & \text{如果 } P_1 \succ P_2 \\
(P_2, P_1) & \text{否则}
\end{cases}
\]

这种排序使LLM能够从更好的父本中识别出优越的设计模式，同时可能从较差的父本中拯救出有益的组件。

选中的父本然后流入**提示构建**，其中组装任务上下文、父本信息和反思洞察。关键的是，来自**分层反思记忆**（详见第2.2节 (https://arxiv.org/html/2607.11916#S2.SS2)）的洞察通过反馈循环进入此阶段，使LLM能够利用先前世代积累的知识。

构建的提示被传递到**LLM生成器**，它充当变异算子。QDEvo采用一种交叉和三种突变策略：**交叉**结合两个父本的设计元素，由反思洞察引导；**随机突变**通过激进的结构变化鼓励新颖性；**反思引导突变**利用积累的经验来指导修改；**运行时突变**专注于通过向量化和缓存优化来提高计算效率。

每个生成的启发式算法随后经历**评估**，采用双目标评估：

\[
(2) \quad \mathbf{f}(C) = [f_{\text{质量}}(C), f_{\text{运行时}}(C)]
\]

其中 \(f_{\text{质量}}\) 衡量对目标优化问题的有效性，\(f_{\text{运行时}}\) 衡量计算效率（负执行时间）。无效个体（语法错误、运行时异常、超时）获得 \(\mathbf{f} = [-\infty, -\infty]\)，其错误信息会被捕获以用于错误反思机制。

最后，评估后的个体进入**语义生存选择**阶段（详见第2.3节 (https://arxiv.org/html/2607.11916#S2.SS3)）。该模块将每个启发式算法转换为语义嵌入，将相似解聚类在一起，并在每个聚类内应用局部帕累托竞争。存活的非支配个体返回种群存档，完成进化循环，并实现连续发现多样化、高质量的启发式算法。

### 2.2. 分层反思记忆

如（Ye等人，2024 (https://arxiv.org/html/2607.11916#bib.bib2)）所示，语言梯度在基于LLM的AHD中扮演重要角色。QDEvo通过整合一个三级分层反思机制来扩展这一概念，该机制能够从进化历史中进行渐进式学习。反思输出通过反馈循环输入到提示构建中，使LLM能够利用积累的知识进行改进的生成。

**快速反思**在每个世代提供即时反馈。分析覆盖从好到差性能范围的多样化个体样本，LLM比较更好与更差启发式算法的配对，识别区分高性能与低性能设计的模式。输出包括详细的比较洞察（例如，“比较最好的和最差的，我们观察到……”）和简洁的可操作建议。

**全面反思**聚合多个世代的经验，将其综合为结构化指导，包含四个部分：**关键词**（关键概念），**建议**（推荐策略），**避免**（应预防的陷阱），以及**解释**（指导背后的推理）。这种反思区分了导致帕累托前沿改进的经历与未导致改进的经历，实现了对成功设计原则的长期学习。

**错误反思**跟踪失败的个体及其错误信息（错误类型、消息、回溯）。一种修复机制尝试使用错误感知提示修复失败的启发式算法，将运行时失败提炼为明确的避免规则。这防止LLM重复常见错误，并系统性地引导未来世代走向有效解。

### 2.3. 语义生存选择

每个启发式算法被规范化（移除注释，通过AST解析规范化格式）并使用预训练的代码嵌入模型嵌入到密集向量 \(\mathbf{v}\) 中。个体基于余弦相似度被划分为语义簇：

\[
(3) \quad \text{sim}(P_i, P_j) = \frac{\mathbf{v}_i \cdot \mathbf{v}_j}{\|\mathbf{v}_i\| \|\mathbf{v}_j\|}
\]

只有当个体与**所有**成员的相似度超过阈值 \(\delta = 0.95\) 时，它才加入簇 \(C_k\)；否则创建一个新簇：

\[
(4) \quad P_{\text{新}} \in C_k \iff \forall P_j \in C_k,\ \text{sim}(P_{\text{新}}, P_j) \geq \delta
\]

在每个簇内，只有帕累托非支配个体存活，确保语义相似的解在局部竞争，同时跨算法生态位的多样性得以保留（Pugh等人，2016 (https://arxiv.org/html/2607.11916#bib.bib8)）。

## 3. 实验

我们将QDEvo与MEoH（Yao等人，2025 (https://arxiv.org/html/2607.11916#bib.bib10)）（最先进的基于LLM的方法）以及经典进化算法（NSGA-II、MOEA/D）在三个基准类别上进行比较：(1) **单目标COP** 重新表述为双目标（质量 vs. 运行时），包括TSP（构造型和GLS）、CVRP和在线装箱问题；(2) **多目标COP** 包括Bi-TSP和Bi-KP；(3) **实际任务** 包括航空公司机组配对和算子内并行性¹¹ASPLOS 2025编程竞赛：算子内并行性优化。https://sites.google.com/view/asplos25contest。访问于2025年。性能通过超体积（HV，越高越好）和逆世代距离（IGD，越低越好）衡量。所有方法均使用Codestral 2作为LLM，最大样本数为300，种群大小为30。

### 3.1. 结果

表1. QDEvo与基线方法在构造型、多目标和实际基准上的整体性能。超体积（HV↑）和IGD（↓）的最佳结果以粗体突出显示。

表1 (https://arxiv.org/html/2607.11916#S3.T1) 总结了QDEvo在代表性基准上的性能。QDEvo在三个类别的大多数实例上取得了最高的HV。对于构造型启发式，QDEvo在CVRP-C 200上比NSGA-II低73.2%的IGD（0.237 vs. 0.883）。在多目标基准上，QDEvo在Bi-TSP-200上比MEoH提升了1.4%的HV（1.178 vs. 1.162），并将IGD降低了15.4%。对于实际任务，QDEvo在机组配对问题上比MEoH低59.1%的IGD（0.110 vs. 0.269），表明对权衡结构有更优越的覆盖。

### 3.2. 消融研究

我们将QDEvo的语义嵌入（Embedding）与两种变体进行比较：**Cell**（结构代码指标作为MAP-Elites描述符）和**NSGAII**（仅拥挤距离，无QD存档）。

表2. 消融：语义嵌入与结构指标（Cell）和NSGA-II。粗体 = 最佳。

语义嵌入方法在所有实例上取得了最高的HV（表2 (https://arxiv.org/html/2607.11916#S3.T2)）。在TSP-GLS 100上差距最为显著，Embedding获得的HV为1.123 vs. 两种替代方案的1.089——提升了3.1%，反映了发现了根本不同的算法策略。结构代码指标（Cell）无法区分具有相似控制流的语义不同算法，而NSGAII沿前沿保持了分布，但无法扩展到未探索的区域。

## 4. 结论

在本文中，我们介绍了QDEvo，一个用于自动启发式设计的新颖多目标质量多样性框架。通过将大型语言模型与语义存档和分层反思记忆相结合，QDEvo有效解决了先前方法中存在的模式坍塌和单目标过度优化问题。我们在标准组合基准和复杂实际工业任务上的大量实验表明，QDEvo显著优于最先进的基线方法，产生的启发式算法不仅高性能，