💻 computer science

Latent Heuristic Search: Continuous Optimization for Automated Algorithm Design

本文介绍了潜在启发式搜索，这是一个在所学潜在流形内利用连续优化的框架——通过编码器、可微分代理和归一化流——通过条件化一个冻结的大型语言模型，为组合优化问题高效生成高性能启发式方法。

原作者： Cheikh Ahmed, Mahdi Mostajabdaveh, Zirui Zhou

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Cheikh Ahmed, Mahdi Mostajabdaveh, Zirui Zhou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试发明一种全新的、超高效的方法来解决复杂的谜题，比如为卡车车队规划配送路线，或者完美地打包行李箱。传统上，人类必须通过反复试错、不断调整规则来完成这项工作。

最近，科学家们开始利用大型语言模型（LLMs）——即那种能够编写代码的同类人工智能——来自动发明这些规则。他们将 AI 视为创意伙伴，要求其生成新的“配方”（算法），并通过测试来找出表现最佳的那一个。

然而，目前的做法有点像试图通过一次随机更改食谱中的一个词来寻找完美配方。你可能会把“盐”改成“糖”，再把“面粉”改成“沙子”，希望能偶然发现一道更好的菜肴。这种方法既缓慢又混乱，而且往往导致无法食用的结果，因为你是在一个由词语和符号构成的混乱、离散的“离散空间”中进行搜索。

本文提出了一种更聪明的方法：“潜在启发式搜索”（Latent Heuristic Search, LHS）。

以下是其工作原理的简明解析，辅以一些日常类比：

1. “魔法地图”（潜在空间）

研究人员不再逐字查看食谱，而是首先将每一种可能的食谱转化为平滑、连续的地图上的一个单点。

类比：想象每一种可能的配送路线都是巨大三维景观上的一个点。优质的路线位于高处的阳光山丘上，而劣质路线则深陷于幽暗的山谷中。
问题：在旧方法中，你必须随机地从一个点跳到另一个点。而在新方法中，AI 会学习这片景观的形状，从而能够“平滑地”滑向最佳山丘。

2. “翻译器”（编码器与代理模型）

为了让这张地图发挥作用，系统使用了两种特殊工具：

编码器：这就像一位翻译，将杂乱无章的书面食谱（代码）转化为地图上干净的坐标。
代理模型：这是一个“水晶球”，它只需查看食谱在地图上的坐标，就能预测该食谱的好坏。你无需真正烘焙蛋糕（运行代码）就能知道它是否美味；水晶球会进行猜测。这节省了海量时间。

3. “安全网”（归一化流）

这里是棘手之处：如果你只是在地图上随意滑动，可能会滑出边缘，进入不存在任何有效食谱的区域（比如一个指示“添加 500 磅糖”的坐标）。

解决方案：研究人员使用了归一化流（Normalizing Flow）。将其想象为一块神奇的可拉伸橡胶 sheet。它将食谱那杂乱无章、不规则的地图拉伸成一个完美、平滑的圆球（高斯形状）。
为何有效：当 AI 寻找最佳食谱时，它在这个完美的圆球内部滑动。由于球体形状如此规整，AI 滑入“胡言乱语”区域的可能性大大降低。它使搜索过程保持安全且有序。

4. “反向翻译器”（映射器与大型语言模型）

一旦 AI 在光滑的球体上找到了完美的坐标（最佳位置），它就需要将该坐标转换回真实、可执行的计算机程序。

过程：它使用“软提示”（一组特殊的隐形指令）向大型语言模型低语：“嘿，基于地图上的这个完美位置，为我编写一个新的配送路线算法。”
随后，大型语言模型生成实际代码，并经过测试以验证其是否真正有效。

他们发现了什么？

研究人员在四个经典谜题上测试了这种方法：

旅行商问题：寻找访问多个城市的最短路径。
车辆路径问题：在有限的卡车空间内向多个房屋配送包裹。
背包问题：在重量限制下将价值最高的物品装入包中。
装箱问题：将物品装入随到随发的箱子中。

结果：

性能：他们的新方法找到的解决方案与依赖随机词语交换的最佳现有方法一样好，有时甚至更好。
效率：它更快、更可靠地找到了这些解决方案。
稳定性：由于有了“安全网”（橡胶 sheet），该系统极少生成无法运行的损坏代码。

核心结论

本文提出了一种自动化发明问题解决算法的方法，它将搜索过程转化为一次平滑的数学滑行，而非一场混乱的“猜测下一个词”游戏。它利用 AI 理解优质解决方案的形状，使其能够径直滑向最佳创意，而不会迷失在噪音之中。

技术摘要：潜在启发式搜索（LHS）

问题陈述

针对组合优化问题（如旅行商问题、车辆路径问题、背包问题）设计高质量启发式算法的传统过程是专家驱动的，需要迭代优化和深厚的领域知识。最近的进展已将大语言模型（LLM）集成到进化框架中（例如 FunSearch、EoH、ReEvo），以自动化这一发现过程。然而，这些现有方法主要在程序语法的离散空间中运行。它们依赖随机采样、令牌级变异和重组来导航高度非凸的优化景观。这种方法通常需要大量昂贵的基于执行的评估才能发现一致的改进，并且在离散搜索空间的脆弱性方面存在困难。

方法论

本文提出了潜在启发式搜索（LHS），这是一个将优化过程从离散令牌空间转移到学习到的连续潜在流形的框架。该方法由四个相互关联的组件组成：

潜在编码：一个预训练的代码编码器（ $E$ ）将离散的启发式程序映射到连续向量嵌入（ $z \in \mathbb{R}^d$ ）。
代理建模：训练一个可微的代理模型（ $f_\theta$ ），根据潜在嵌入预测启发式的性能得分。为了确保对噪声评估和尺度变化的鲁棒性，该模型使用**成对排序损失（RankNet）**而非点对点回归进行训练，重点关注候选项的相对排序。
基于归一化流的正则化优化：为了解决原始编码器嵌入中常见的各向异性和低密度区域问题，该框架采用可逆归一化流（ $F_\phi$ ）。该流将复杂的程序嵌入空间映射到结构化的凸高斯先验空间（ $u \in \mathbb{R}^d$ ）。优化在该先验空间内通过梯度上升执行，确保搜索轨迹保持在合理、有效的启发式流形附近。
通过软提示解码：优化后的潜在向量通过一个学习到的潜在到提示映射器（ $\phi_\omega$ ）投影回仅解码器冻结 LLM 的输入空间。该映射器生成连续的“软提示”（条件嵌入），引导 LLM 合成新的、可执行的启发式代码。生成的代码经过语法验证并在基准实例上进行评估，以更新数据集。

整体过程是迭代的：种子程序被编码，在潜在先验空间中优化，解码为新的代码，进行评估，并添加到训练池中，以细化代理模型和流模型。

主要贡献

连续启发式发现：本文引入了从离散令牌级进化搜索到基于学习到的程序表示的连续优化的范式转变，使得能够使用基于梯度的方法进行启发式设计。
流正则化搜索：它证明了使用归一化流将程序嵌入映射到结构化先验的必要性。这种正则化防止搜索漂移到潜在空间中的无效区域，与在原始嵌入空间直接优化相比，显著提高了生成代码的成功率。
基于排序的代理：使用成对排序代理模型为梯度上升提供了稳定的学习信号，避免了在噪声评估环境中与绝对分数回归相关的脆弱性。
软提示条件：该框架利用一个可学习的映射器将潜在向量转换为软提示，从而能够在不修改其内部参数的情况下引导冻结的 LLM。

实验结果

LHS 框架在四个组合优化任务上进行了评估：TSP、带容量限制的车辆路径问题（CVRP）、背包问题（KSP）和在线装箱问题（OBP）。

性能：在路径规划任务（TSP 和 CVRP）上，LHS 实现了最先进的性能，始终优于离散进化基线（FunSearch、EoH、ReEvo）和基于 MCTS 的方法。例如，在 TSP-200 上，LHS 实现了 12.49 的目标值，优于 ReEvo（12.58）和 EoH（13.15）。
效率：LHS 表现出具有竞争力或更优越的运行时效率。在 TSP 实验中，与 ReEvo（29.61 秒）相比，LHS 所需时间显著更少（例如 TSP-200 为 4.86 秒），同时取得了更好的结果。
消融研究：
- 无流（No-Flow）：移除归一化流并直接在原始嵌入空间中优化，导致生成代码的成功率显著下降（61% 对比 74%），证实了流在稳定搜索中的作用。
- 无梯度（No-Grad）：用简单的插值替代梯度上升，虽然产生了高有效性（86%），但优化能力较差（目标分数更差），凸显了梯度信号对于发现高质量启发式的必要性。
泛化性：该方法表现出强大的跨尺寸泛化能力，在搜索阶段使用的实例尺寸（如 TSP-100、TSP-200）更大的情况下表现良好。

意义与主张

作者声称，LHS 为现有的离散进化方法提供了一种互补的方法论替代方案。通过将程序视为连续潜在向量，该框架能够在保持基于执行评估严谨性的同时，利用梯度信息系统地导航启发式设计空间。

论文强调，连续优化是离散搜索的有力补充，能够在固定的评估预算内实现更优的目标。然而，作者对局限性保持谦逊，指出 LHS 的有效性从根本上取决于代理模型的质量和初始训练语料库。他们承认，过于激进的优化步骤可能会将候选项推离可执行代码的流形，建议未来的工作应探索将 LHS 与离散进化算子混合，以平衡全局探索与局部细化。该框架被呈现为迈向自动化算法设计更可微流水线的一步，特别是在涉及跨相关任务重复搜索的场景中，初始数据生成的成本可以被摊销。