潜在启发式搜索：自动化算法设计的连续优化

# 潜在启发式搜索：面向自动化算法设计的连续优化 来源：https://arxiv.org/html/2605.17137 11institutetext:华为技术加拿大公司，本拿比，加拿大###### 摘要 将大型语言模型（LLMs）整合到进化框架中，为自动启发式发现建立了一种新范式。尽管前景广阔，但这些方法通常以程序语法的离散空间进行搜索，依赖随机采样来应对高度非凸的优化景观。本文提出了一种连续启发式发现框架，将优化转移到学习到的潜在流形上。我们使用编码器将离散程序映射为连续嵌入，并训练一个可微的代理模型来预测性能，从而实现基于梯度的搜索。为了规范优化轨迹，一个可逆的归一化流将这些嵌入映射到一个结构化的高斯先验上，在那里我们执行梯度上升。产生的优化后的潜在向量通过一个学习到的映射器投影为软提示，这些提示条件化一个冻结的LLM，使其能够合成新的可执行启发式算法。我们在旅行商问题（TSP）、带容量约束的车辆路径问题（CVRP）、背包问题（KSP）和在线装箱问题（OBP）上评估了所提出的方法。实验结果表明，连续潜在空间优化在性能上可以与最先进的离散进化基线相媲美，同时为自动化算法设计提供了一种互补的方法论选择。实现代码见 https://github.com/cheikh025/LHS。 ## 1 引言 启发式算法是组合优化的核心，能够在实际时间约束下为旅行商问题（TSP）\[10 (https://arxiv.org/html/2605.17137#bib.bib24)\]、带容量约束的车辆路径问题（CVRP）\[21 (https://arxiv.org/html/2605.17137#bib.bib25)\] 和在线装箱问题（OBP）\[7 (https://arxiv.org/html/2605.17137#bib.bib26)\] 等问题提供高质量解。尽管十分重要，但设计强大的启发式算法在很大程度上仍然依赖专家驱动，需要迭代优化、深厚的领域知识和大量的经验测试。 近期研究表明，当嵌入一个严格的“搜索-评估”循环时，大型语言模型（LLMs）能够支持算法发现。FunSearch 将基于LLM的代码生成与进化采样和基于执行评估相结合，在数学构造任务和经典启发式场景（如在线装箱）上展示了改进\[19 (https://arxiv.org/html/2605.17137#bib.bib1)\]。基于这一思想，启发式进化（EoH）引入了一个框架，共同进化描述启发式策略的高层自然语言“思想”与可执行代码，旨在提高搜索效率和多样性\[12 (https://arxiv.org/html/2605.17137#bib.bib2)\]。ReEvo 进一步将LLM视为超启发式算法，并使用反思反馈来引导进化搜索，提供了一种明确的机制来将生成过程导向更有效的启发式行为\[22 (https://arxiv.org/html/2605.17137#bib.bib3)\]。其他相关工作探索了替代搜索算子和探索策略，包括基于MCTS的探索\[23 (https://arxiv.org/html/2605.17137#bib.bib10)\]、带有和谐搜索的多样性驱动进化搜索\[2 (https://arxiv.org/html/2605.17137#bib.bib15)\]，以及更通用的用于科学和算法发现的进化编码智能体\[16 (https://arxiv.org/html/2605.17137#bib.bib16)\]。总的来说，这些工作突出了一个关键教训：当与系统性的探索和客观评估相结合时，LLM在启发式设计方面变得显著更加可靠，而不是一次性生成。 然而，许多基于LLM的自动启发式设计方法仍然主要在“程序的离散空间”中操作，依赖于变异、重组以及对代码令牌的重复LLM采样。这通常会产生一个具有挑战性的优化景观，并且可能需要大量昂贵的评估才能发现一致的改进。与此同时，关于“潜在程序表示”的研究表明，通过学习代码的连续嵌入并直接在所学空间中进行优化，可以使程序搜索更加结构化。诸如 LEAPS 之类的方法学习嵌入和解码器，从而能够在潜在变量上进行搜索，而不是进行显式的语法编辑\[20 (https://arxiv.org/html/2605.17137#bib.bib4)\]，后续工作则探索了将潜在程序空间搜索作为泛化和适应的一种机制\[14 (https://arxiv.org/html/2605.17137#bib.bib5)\]。密切相关的是，“程序合成”已被明确地表述为在给定输入/输出示例或基于测试的误差信号下的连续优化：NPO\[11 (https://arxiv.org/html/2605.17137#bib.bib21)\] 训练一个神经程序自编码器，将程序嵌入到一个连续空间，然后在潜在变量上应用无导数优化（例如 CMA-ES），将候选解解码回程序以进行基于执行的评分。相比之下，GENESYS\[15 (https://arxiv.org/html/2605.17137#bib.bib22)\] 避免使用学习到的自编码器，而是直接使用连续变量参数化令牌选择，并同样使用由重启策略增强的 CMA-ES 来优化这些参数。这些结果支持了如下假设：自动启发式设计可能受益于将主要搜索过程从代码令牌空间转移到一个连续表示空间，该空间捕捉启发式算法之间的语义变化；然而，我们的设置与 I/O 一致性合成不同之处在于，我们是在基于执行的基准测试下搜索“高性能的启发式程序”，而不是满足给定 I/O 示例集的程序。 在这项工作中，我们提出了一种通过学习到的“启发式程序潜在空间”中进行优化来发现改进的启发式算法的框架。我们的方法将候选程序表示为连续嵌入，并学习一个代理排名模型，该模型从这些表示预测启发式性能。为了规范优化过程并保持可解码性，我们拟合一个可逆的归一化流，将程序嵌入映射到一个结构化的先验空间，从而在一个条件良好的空间中进行基于梯度的搜索，同时保持在合理启发式流形附近。为了将优化后的潜在代码转换为可执行算法，我们引入了一条解码路径，其中候选嵌入被映射为软提示，这些软提示条件化一个基于LLM的代码生成器。生成的代码经过语法正确性验证，并在基准测试协议下执行以获得其性能得分。与令牌级进化搜索不同，我们的方法利用启发式设计上的“连续、可学习的搜索几何”，同时保留严格的基于执行的评估。 ## 2 问题形式化 令P\\mathcal\{P\}表示用固定编程语言编写、针对目标组合优化问题（例如 TSP、OBP）实现启发式算法的语法有效程序的集合。对于任何p∈Pp\\in\\mathcal\{P\}，我们通过在基准实例集Dbench=\{xj\}j=1MD\_\{\\mathrm\{bench\}\}=\\\{x\_\{j\}\\\}\_\{j=1\}^\{M\}上执行pp，并使用标准化协议（例如，固定的时间限制、可行性检查和评分规则）来评估性能，从而得到实例级目标值Cost\(p;xj\)∈R\\mathrm\{Cost\}\(p;x\_\{j\}\)\\in\\mathbb\{R\}。为了统一最小化和最大化任务的符号，我们定义 y\(p\):=1M∑j=1MCost\(p;xj\),s\(p\):=αy\(p\),α∈\{\+1,−1\},y\(p\)\\;:=\\;\\frac\{1\}\{M\}\\sum\_\{j=1\}^\{M\}\\mathrm\{Cost\}\(p;x\_\{j\}\),\\qquad s\(p\)\\;:=\\;\\alpha\\,y\(p\),\\quad\\alpha\\in\\\{\+1,\-1\\\},\(1\)其中α=\+1\\alpha=\+1用于最大化任务，α=−1\\alpha=\-1用于最小化任务。映射p↦s\(p\)p\\mapsto s\(p\)被视为一个黑盒，且相对于程序令牌是不可微的。利用这个评估器，我们维护一个评分程序的数据集D=\{\(pi,si\)\}i=1N\\mathcal\{D\}=\\\{\(p\_\{i\},s\_\{i\}\)\\\}\_\{i=1\}^\{N\}，其中si:=s\(pi\)s\_\{i\}:=s\(p\_\{i\}\)。目标是通过在学习到的连续表示空间中搜索（而非在程序空间中进行离散的令牌级编辑）来发现一个改进的启发式程序，即求解 p⋆∈arg⁡maxp∈P⁡s\(p\),p^\{\\star\}\\in\\arg\\max\_\{p\\in\\mathcal\{P\}\}\\;s\(p\),\(2\) ## 3 方法 我们提出了一种通过学习到的潜在程序空间中连续优化来进行启发式发现的框架。图3 (https://arxiv.org/html/2605.17137#S3) 提供了所提管线的概述。具体来说，我们 (i) 将程序编码为连续表示，(ii) 训练一个可微的代理模型，从这些表示预测程序性能，以及 (iii) 执行基于梯度的优化以识别改进的潜在候选解，随后由大型语言模型 (LLM) 解码为可执行程序，并在基准测试协议下进行评估。 ![[无标题图片]](https://arxiv.org/html/2605.17137v1/LHS_v1.png) ### 3.1 潜在启发式搜索 为了发现高性能的启发式算法，我们将搜索过程从离散、不可微的代码空间转移到连续的潜在流形上。这种转换使得能够在学习到的表示空间中使用连续优化技术，例如基于梯度的更新。完整的发现过程总结在算法1 (https://arxiv.org/html/2605.17137#alg1) 中。 每个启发式程序p∈Pp\\in\\mathcal\{P\}都使用一个代码编码器映射到一个潜在向量： z=E\(p\),z∈Rd\.z\\;=\\;E\(p\),\\qquad z\\in\\mathbb\{R\}^\{d\}\.\(3\) 我们的目标是找到在基准测试中性能得分s\(p\)s\(p\)最大化的程序（第2节 (https://arxiv.org/html/2605.17137#S2)）。由于s\(p\)s\(p\)是通过在基准测试协议下执行pp获得的，因此它被视为一个黑盒函数，并且不提供相对于zz的梯度。为了获得一个可微的搜索目标，我们学习一个代理预测器fθ:Rd→Rf\_\{\\theta\}:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}。使用已评估程序的数据集D=\{\(pi,si\)\}i=1N\\mathcal\{D\}=\\\{\(p\_\{i\},s\_\{i\}\)\\\}\_\{i=1\}^\{N\}，我们将每个程序编码为zi=E\(pi\)z\_\{i\}=E\(p\_\{i\}\)，并训练fθf\_\{\\theta\}使得： fθ\(zi\)≈si\.f\_\{\\theta\}\(z\_\{i\}\)\\approx s\_\{i\}\.\(4\) 给定一个种子潜在向量z\(0\)z^\{\(0\)\}（例如，一个参考程序的编码），我们通过代理模型上的梯度上升来生成改进的潜在候选解： z\(t\+1\)=z\(t\)\+η∇zfθ\(z\(t\)\),t=0,...,T−1\.z^\{\(t\+1\)\}\\;=\\;z^\{\(t\)\}\+\\eta\\,\\nabla\_\{z\}f\_\{\\theta\}\\\!\\left\(z^\{\(t\)\}\\right\),\\quad t=0,\\ldots,T\-1\.\(5\) 优化后，最终的潜在向量z\(T\)z^\{\(T\)\}必须转换回可执行代码。我们通过一个可学习的投影函数φω\\phi\_\{\\omega\}将z\(T\)z^\{\(T\)\}投影到代码生成LLM的嵌入空间中： h=φω\(z\(T\)\)∈RK×e,h\\;=\\;\\phi\_\{\\omega\}\(z^\{\(T\)\}\)\\in\\mathbb\{R\}^\{K\\times e\},\(6\)它产生KK个连续的调节嵌入。序列hh被用作软提示，以调节一个冻结的仅解码器LLMG\\mathcal\{G\}，用于基于前缀/提示调优的代码生成。给定一个上下文提示II（问题描述、规范、约束），我们生成一个候选程序： p^∼G\(I⊕h\)\.\\hat\{p\}\\sim\\mathcal\{G\}\\\!\\left\(I\\oplus h\\right\)\.\(7\)其中⊕\\oplus表示任务提示II和软提示hh的拼接。然后我们验证并执行p^\\hat\{p\}以获取其基准测试得分s\(p^\)s\(\\hat\{p\}\)。 ### 3.2 训练潜在到提示的映射器 映射器网络φω\\phi\_\{\\omega\}充当紧凑潜在空间与解码器高维输入空间之间的语义桥梁。它将程序的潜在向量zz投影为一个由KK个连续嵌入向量组成的序列，本质上是一个软前缀，用于条件化冻结的大型语言模型（LLM）。这种方法采用了前缀调优策略\[9 (https://arxiv.org/html/2605.17137#bib.bib6)\]，允许我们引导生成过程，而无需修改LLM的参数。 对于数据集中的每个程序pip\_\{i\}，我们首先使用编码器计算其潜在表示zi=E\(pi\)z\_\{i\}=E\(p\_\{i\}\)。然后，映射器将此向量转换为一个软令牌序列： hi=φω\(zi\)∈RK×e,h\_\{i\}\\;=\\;\\phi\_\{\\omega\}\(z\_\{i\}\)\\in\\mathbb\{R\}^\{K\\times e\},\(8\)其中e e表示解码器G\\mathcal\{G\}的嵌入维度。为了确保hih\_\{i\}保留重建原始程序所需的语义信息，我们使用监督重建目标训练ψ\\psi。将程序pip\_\{i\}标记化为一个序列\(ti,1,...,ti,Ti\)\(t\_\{i,1\},\\dots,t\_\{i,T\_\{i\}\)\)，并令IiI\_\{i\}表示固定的文本任务提示（指定问题定义、接口和约束）。解码器G\\mathcal\{G\}定义了一个自回归概率分布： PG\(ti,1:Ti∣Ii,hi\)=∏k=1TiPG\(ti,k\|ti,sj\}\)。 这可以产生多达O\(N2\)O\(N^\{2\}\)个训练比较，而它们仅来源于N N个评估，从而显著增加了拟合fθf\_\{\\theta\}可用的监督约束数量。我们强调这些成对示例并非独立；因此，我们使用程序级别的划分来评估泛化能力。 我们训练fθf\_\{\\theta\}以最小化 RankNet 损失\[1 (https://arxiv.org/html/2605.17137#bib.bib8)\]。参数ω\\omega被优化以最大化正确预测更优候选解的可能性： Lrank\(ω\)=−E\(ui,uj\)∼Dr\[log⁡σ\(fθ\(ui\)−fθ\(uj\)\)\],\\mathcal\{L\}\_\{\\mathrm\{rank\}\}\(\\omega\)=\-\\mathbb\{E\}\_\{\(u\_\{i\},u\_\{j\}\)\\sim\\mathcal\{D\}\_\{r\}\}\\Big\[\\log\\sigma\\Big\(f\_\{\\theta\}\(u\_\{i\}\)\-f\_\{\\theta\}\(u\_\{j\}\)\\Big\)\\Big\],\(14\)其中σ\\sigma是 Sigmoid 函数。 算法 1 潜在启发式搜索 (LHS) 1:预训练编码器 EE，流 FφF\_\{\\varphi\}，代理 fθf\_\{\\theta\}，映射器 φω\\phi\_\{\\omega\}，以及冻结的代码LLM G\\mathcal\{G\} 2:初始种子语料库 P0\\mathcal\{P\}\_\{0\}；任务提示 II；基准测试评估器 s\(⋅\)s\(\\cdot\) 3:预算：外部迭代次数 RR，每轮候选解数量 BB，梯度上升步数 TT，步长 η\\eta 4: D←∅\\mathcal\{D\}\\leftarrow\\emptyset 5:for all p∈P0p\\in\\mathcal\{P\}\_\{0\}do 6:执行 pp以获取得分 s\(p\)s\(p\) 7: D←D∪\{\(p,s\(p\)\)\}\\mathcal\{D\}\\leftarrow\\mathcal\{D\}\\cup\\\{\(p,s\(p\)\)\\\} 8:endfor 9:for r=1r=1to RRdo 10:从 D\\mathcal\{D\}中选择种子程序 \{p\(b\)\}b=1B\\\{p^\{\(b\)\}\\\}\_\{b=1\}^\{B\}（例如，前 kk 个） 11:for b=1b=1to BBdo 12: z\(0\)←E\(p\(b\)\)z^\{\(0\)\}\\leftarrow E\(p^\{\(b\)\}\)； u\(0\)←Fφ\(z\(0\)\)u^\{\(0\)\}\\leftarrow F\_\{\\varphi\}\(z^\{\(0\)\}\) 13:for t=0t=0to T−1T\-1do 14: u\(t\+1\)←u\(t\)\+η∇ufθ\(u\(t\)\)u^\{\(t\+1\)\}\\leftarrow u^\{\(t\)\}\+\\eta\\,\\nabla\_\{u\}f\_\{\\theta\}\\big\(u^\{\(t\)\}\\big\) 15:endfor 16: z∗←Fφ−1\(u\(T\)\)z^\{\*\}\\leftarrow F\_\{\\varphi\}^\{\-1\}\(u^\{\(T\)\}\)； h←φω\(z∗\)h\\leftarrow\\phi\_\{\\omega\}\(z^\{\*\}\) 17:采样候选代码 p^∼G\(Concat\(I,h\)\)\\hat\{p\}\\sim\\mathcal\{G\}\(\\mathrm\{Concat\}\(I,h\)\) 18:if p^\\hat\{p\}有效 then 19:执行 p^\\hat\{p\}以获取 s\(p^\)s\(\\hat\{p\}\) 20: D←D∪\{\(p^,s\(p^\)\)\}\\mathcal\{D\}\\leftarrow\\mathcal\{D\}\\cup\\\{\(\\hat\{p\},s\(\\hat\{p\}\)\)\\\} 21:endif 22:endfor 23:endfor 24:return最佳程序 p∗=arg⁡max\(p,s\)∈D⁡sp^\{\*\}=\\arg\\max\_\{\(p,s\)\\in\\mathcal\{D\}\}s ## 4 实验 我们通过实验验证了所提出的潜在